First-order logic

classical example of a logic argument:

all men are mortal
Socrates is a man

therefore, socrates is mortal

arguments may be complicated (Boole, 1854):

wealth consists of things transferable, limited in supply, and either productive of pleasure or preventive of pain

therefore, wealth that is not productive of pleasure is transferable, limited in supply, and preventive of pain

another example (Venn, 1880):

All X is either both Y and Z or not-Y
All XY that is Z is also W
No WX is YZ

therefore, No XY exists

people asked: how to check them?
answer: formal proof, like in mathematics

formal proof of a logical argument

requires writing the logic argument in a formal way

man(Socrates)
∀ x . man(x) → mortal(x)

conclusion: mortal(Socrates)

same line of reasoning
different object and properties:

all birds have wings
Tweety is a bird
therefore, tweety has wings

bird(Tweety)
∀ x . bird(x) → winged(x)
conclusion: winged(Tweety)

still a valid argument

another valid argument:

all robots are machines
C3PO is a robot
therefore, C3PO is a machine

formally:

robot(3CPO)
∀ x . robot(x) → machine(x)
conclusions: machine(3CPO)

argument valid regardless of object (Socrates, Tweety, C3PO)
and properties (man, mortal, bird, winged, robot, machine)

objects and properties

in the example	in general
Socrates	an object
man()	something that could be true or false of an object
mortal()	something else that could be true or false of an object

other objects and properties:

objects:: Tweety, 3CPO
properties:: bird(), winged(), robot(), machine()

argument, in general

property1(object)
∀ x . property1(x) → property2(x)
conclusion: property2(object)

same as above: object, property, property
valid for every object every two of its properties
short names: object c, properties P() and Q()

P(c)
∀ x . P(x) → Q(x)
conclusion: Q(c)

valid argument, formally

P(c)
∀ x . P(x) → Q(x)
conclusion: Q(c)

same line of reasoning
c in place of Socrates, Tweety, 3CPO
P() in place of man(), bird(), robot()
Q() in place of mortal(), winged(), machine()

unspecificity of validity

P(c)
∀ x . P(x) → Q(x)
conclusion: Q(c)

valid line of reasoning
not specific to Socrates and man/mortal
nor two Tweety, bird/winged, etc.
valid in general, regardless of what c is and what P and Q are:
valid with c=Socrates, P=man, Q=mortal
also valid with c=Tweety, P=bird, Q=winged

rule of replacement in logic

if a line of reasoning holds for an object and two of its properties (Socrates, man, mortal), then it holds for every object and two of its properties (Tweety, bird, winged; also 3CPO, robot, machine, etc.)

more generally, also for any number of objects and properties:

if an argument of reasoning is valid,
it remains valid when changing names
(ex. Tweety in place of Socrates, bird() in place of man(), etc.)

consequence of unspecificity

unspecificity of validity:

validity of a logical argument is not specific to an object (Socrates) and properties (man, mortal)

consequence:

formal way of proving validity does not depend on the specific objects and properties

practical consequence of unspecificity

arguments may be expressed with abstract names, like c, P() and Q()

if they are valid, they are valid regardless of what they mean

limits of formal logic

apparent failure of logic

all days of October are rainy
today is a day of October
therefore, today is a rainy day

octoberday(Today)
∀ x . octoberday(x) → rainy(x)
conclusion: rainy(Today)

same structure as above
object Today, properties octoberday() and rainy()
not a valid argument?

validity in logic

octoberday(Today)
∀ x . octoberday(x) → rainy(x)
conclusion: rainy(Today)

could not possibly be true
today is not raining
conclusion is wrong why?

vadity of argument and truth of premises

octoberday(Today)
∀ x . octoberday(x) → rainy(x)
conclusion: rainy(Today)

not all days of October are rainy

the second premise, "all days of October are rainy", is false
it's not the line of reasoning that is wrong

truth of premises

octoberday(Today)
∀ x . octoberday(x) → rainy(x)
conclusion: rainy(Today)

meaning: if the premises *are* true, the conclusion *is* true

but actually: if the premises *were* true, the conclusion *would be* true

logic "believes" the premises
takes them at face value

logic and reality

logic does not know about reality
does not care

logic is not concerned about the meaning of symbols
(Socrates, man, Tweety, Today, winged, rainy, etc.)

only concerned about the line of reasoning
if a line of reasoning is valid, remains valid for other symbols

from the point of view of logic:
"c", "Socrates", "Tweety", "3CPO" and "Today" are just different names for an object
"P()", "man()", "bird()" and "octoberday()" are just different names for a property of an object
same for "Q()", "mortal()", "winged()" and "rainy()"

logic does not know what they mean
does not know if they meet the premises
takes the premises for granted

validity in logic

octoberday(Tweety)
∀ x . octoberday(x) → machine(x)
conclusion: machine(Tweety)

formal logic only checks validity of argument

same structure as previous arguments
again, valid argument
premises nonsensical
if they *were* true, the conclusion *would be* true

humans: know the meaning of symbols and the validity of argument about them
logic: do not know the meaning of symbols, only the validity of arguments

human: argument wrong or nonsensical
logic: assumes the premises make sense and are correct; conclusion valid

validity and computers

computers take data as correct, just elaborate it

example:

accounting program
someones enters 100000E as monthly salary, 100E as montly expenses
asks how many months to by a Ferrari
program calculates result from its data: 100000E and 100E
not reality (e.g., 1200E and 1100E)

logic takes premises as correct
does not question them

validity and mathematics

two apples plus four apples minus one apple gives five apples
even if I buy three apples, then two and I eat two

result of math is five
reality is: left with four apples, not five

mathematics is right: 2+4-1=5
data is incorrect, does not corresond to reality
(2, 4, 1, reality was 3, 2, 2)

mathematics does not care about reality
works on the given data, assumes it correct

Mathematics does not cause confusion because it is written with abstract terms, like 2, 4, 1, +, -, etc. Logical formulae can instead be written with concrete, specific names like "Socrates", "man" and "mortal", giving the false impression to be grounded in reality.

what is invalid in logic, then?

Socrates is a man
all men are mortal
therefore, Socrates is not mortal

man(Socrates)
∀ x . man(x) → mortal(x)
conclusion: not mortal(x) *** INVALID ARGUMENT

even assuming the premises correct, the conclusion does not follow

another invalid argument in logic

Socrates is a man
all men are mortal
therefore, Socrates is Greek

man(Socrates)
∀ x . man(x) → mortal(x)
conclusion: greek(x) *** INVALID ARGUMENT

conclusion is true, but does not follow from premises
argument is invalid according to logics

formal logic, wrap up

c, P(), Q(), Socrates, man(), mortal(), Tweety, etc.
are just names of things and their properties in logic
logics unaffected by names (c in place of Socrates, etc.)
logics does not know or care about what they mean
the involved objects may be arbitrary
same for properties
only concerned about what follows from a given set of premises

partial validity, same object vs. different objects

"partial" validity?

George is mad
therefore, my cousin is mad

mad(George)
conclusion: mad(cousin)

valid if my cousin is George invalid otherwise

valid in logic?

rule of replacement

mad(George)
conclusion: mad(cousin)

if valid, remains so for other names

bird(Tweety)
conclusion: bird(Pluto)

premise holds, conclusion does not
invalid argument

validity and generality

mad(George)
conclusion: mad(cousin)

rule of replacement says: not valid

but is valid in some cases (George is my cousin)

yet, is invalid in others (George is not my cousin)

valid in logic = valid in all cases
this argument is invalid in logic

specific objects

mad(George)
conclusion: mad(cousin)

valid if the only considered person is my cousin George
invalid for two people, my friend George and my cousin Jeff

valid in one case only: not valid

abstract names

P(c)
consequence: P(d)

valid whenever only one possible object exists
c and d must be different names of that object
like George and cousin

invalid if two objects exists
like a bird and a dog
c and d may be both that object
they may not be

not valid in all cases = not valid

same object vs. different objects

two names for the same object
two names for two different objects

validity = validity in all cases
regardless of 1. and 2.

functions

logics unaffected by names
use symbols (c, P(), ...) in place of concrete names (Socrates, man(), ...)

three kinds of symbols, so far:

specific objects: c		examples: Socrates, Tweety, today
properties of objects: P(), Q()		examples: being a man, being mortal
unspecified object: x		example: for all objects x (generic, unspecific)

missing: relation between objects

Socrates is a man
the father of a man is a man
conclusion: Socrates' father is a man

man(Socrates)
∀ x . man(x) → man(???)
conclusion: ...

relation between objects, attempt 1

man(Socrates)
∀ x . man(x) → man(???)
conclusion: ...

??? = x
conclusion: man(Socrates), already known

does not work

relation between objects, attempt 2

man(Socrates)
∀ x . man(x) → man(???)
conclusion: ...

??? = y
conclusion: man(Tweety), since y is arbitrary

does not work

relation between objects

the father of a man is a man

how to identify the father of someone?
father(Socrates) is the father of a Socrates

man(Socrates)
∀ x . man(x) → man(father(x))
conclusion: man(father(Socrates))

validity

valid = valid in general
regardless of names and meanings
different functions in place of father()

bird(Tweety)
∀ x . bird(x) → bird(brother(x))
conclusion: bird(brother(Tweety))

robot(3CPO)
∀ x . robot(x) → man(creator(x))
conclusion: man(creator(3CPO))

rainy(today)
∀ x . rainy(x) → rainy(dayafter(x))
conclusion: rainy(dayafter(today))

last argument is still valid
second premise is false, not the line of reasoning

valid argument, false premise

another example:

octoberday(today)
∀ x . octoberday(x) → octoberday(dayafter(x))
conclusion: octoberday(dayafter(today))

second premise false for October, 31
conclusions may still be true, but is not guaranteed to be true

properties and relations

WARNING:

man(...) = true or false, NOT AN OBJECT
father(...) = an object, NOT TRUE OR FALSE

same kind of notation, very different things
true/false vs. an object

parenthesis = depend on something

man(something): is an object a man: true or false, depending on the objectS
father(someone): the father of someone: a man, which one depends on the man

syntax of first-order logic

costant:: specific object
(Socrates, tweety, today)
variable:: generic object
(when saying "all of these objects are also…")
function:: an object related to another object
(the father of someone)
predicate:: something that may be true or false about an object
(is something mortal)

think about the examples:

f(x) is?...		father of someone, an object
P(x) is?...		whether someone is mortal, a property

nestings

the grandfather of Socrates: father(father(Socrates))

the father of the creator of 3CPO: father(creator(3CPO))

multiple arguments

functions:: the day Sally and Jack married
dayofmarriage(Sally, Jack)
(an object)
predicates:: whether Bob and Clark are friends
friend(Bob, Clark)
(true or false)

between parenthesis: objects, always
one or more, but always objects
both for functions and predicates
functions produce objects, predicates produce true/false

multiple nested arguments

the day Doroty and the father of Jack married:: dayofmarriage(Doroty, father(Jack))
(a date, which is an object)
whether Luke and the father of Jack are friends:: friend(Luke, father(Jack))
(true or false)

terms and literals

dayofmarriage(Doroty, father(Jack)): term, a construction that denotes an object
friend(Luke, father(Jack)): literal, a construction that denotes a property of the given objects

with symbols in place of concrete names
functions f and g, predicate P()

f(g(c), d)	term
P(x, c, f(c))	literal

arguments valid = valid regardless of meaning of symbols
regardless of possible coincidence of objects

semantics of first-order logic

the aim of all of this

why formalizing an argument in logic?
tell whether it is valid or not
using simple steps, like calculations in math

validity

arguments may be valid or not
how to tell?
example: is this argument valid?

man(Socrates)
∀ x . man(x) → mortal(x)
conclusion: mortal(Socrates)

check by calculation, not by intuition

semantics of first order logic

two arguments:

man(Socrates)
∀ x . man(x) → mortal(x)
conclusion: mortal(Socrates)

mortal(Maria)
∀ x . man(x) → mortal(x)
conclusion: man(Maria)

first argument valid, second invalid
check by calculation, not by intuition

validity and names

P(c)
∀ x . P(x) → Q(x)
conclusion: Q(c)

same as first previous argument
f(), P(), Q() in place of Socrates, man(), mortal()

previous argument valid
this argument valid
validity unaffected by names of objects and properties
valid even with non-concrete names

a scenario

objects:: D
meaning of constants:: which object c is
evaluation of functions:: later
evaluation of predicates:: whether P(object) is true or false,
for every object
same for Q(object)

argument may hold in a scenario or not

a possible scenario

objects:: {1, 2, 3}
constants:: c is 2
predicates:: P(1) is true, P(2) is false, P(3) is true
Q(1) is false, Q(2) is false, Q(3) is true

another possible scenario

objects:: {"abcd", "efgh"}
constants:: c is "abcd"
predicates:: P("abcd") is true, P("efgh") is false
Q("abcd") is false, Q("efgh") is false

validity and objects

objects are numbers in the first scenario and strings in the second
three in the first, two in the second
c differ, P differ, Q differ

validity unaffected

evaluation of argument in the first scenario

objects:: {1, 2, 3}
constants:: c is 2
predicates:: P(1) is true, P(2) is false, P(3) is true
Q(1) is false, Q(2) is false, Q(3) is true

is P(c) the case?
is ∀ x . P(x) → Q(x) the case?
is Q(c) the case?

evaluation of argument in the first scenario

objects:: {1, 2, 3}
constants:: c is 2
predicates:: P(1) is true, P(2) is false, P(3) is true
Q(1) is false, Q(2) is false, Q(3) is true

c is 2
P(c) is P(2), false
is ∀ x . P(x) → Q(x) the case?

first premise false: P(c)
this scenario does not tell anything about validity

note: not an incorrect scenario!
just one that does not meet the premises
irrelevant for checking whether the premises entail the consequence

all scenarios are "correct"

evaluation of argument in the second scenario

objects:: {"abcd", "efgh"}
constants:: c is "abcd"
predicates:: P("abcd") is true, P("efgh") is false
Q("abcd") is false, Q("efgh") is false

c is "abcd"
P(c) is P("abcd"), true
is ∀ x . P(x) → Q(x) the case?

check P(x) → Q(x) for all possible values of x:

x="abcd":: P("abcd")=true, Q("abcd")=false
x="efgh":: P("efgh")=false, Q("efgh")=false

conclusion, P(x) → Q(x) is false for x="abcd"
P(x) → Q(x) is not true for all x
∀ x . P(x) → Q(x) is false

was the second premise
this scenario does not exclude validity

another scenario

objects:: {3.14, 2.5, 2.1, 7.77}
constants:: c is 3.14
predicates:: P(3.14) is true, P(2.5) is false, P(2.1) is false, P(7.77) is false
Q(3.14) is true, Q(2.5) is false, Q(2.1) is true, P(7.77) is false

P(c) is P(3.14), true

check P(x) → Q(x) for all possible values of x:

x=3.14:: P(3.14)=true, Q(3.14)=true
x=2.5:: P(2.5)=false, Q(2.5)=false
x=2.4:: P(2.4)=false, Q(2.4)=true
x=7.77:: P(7.77)=false, Q(7.77)=false

P(x) only true for x=3.14
Q(x) is true for x=3.14; true in the only case where P(x) is true
P(x) → Q(x) is true for all x

Q(c) is Q(3.14), true

premises true, conclusion true
argument may be valid

validity and scenarios

argument invalid in a scenario ⇒ argument invalid

try all scenarios
argument valid in any ⇒ valid

example invalid argument

Q(c)
∀ x . P(x) → Q(x)
conclusion: P(c)

invalid = one scenario invalidates it
(at least one)

counterexample to an argument

Q(c)
∀ x . P(x) → Q(x)
conclusion: P(c)

scenario:

objects:: {1,2}
constant:: c is 1
predicates:: P(1) is false, P(2) is true
Q(1) is true, Q(2) is true

Q(c) is Q(1), true

check P(x) → Q(x) for all possible values of x:
x=1: P(1) is false, Q(1) is true
x=2: P(2) is true, Q(2) is true

P(x) only true for x=2
Q(x) is true for x=2, the only case where P(x) is true
P(x) → Q(x) true for all values of x

P(c) is P(1), false

premises true, conclusion false
argument invalid

one counterexample is enough

semantics: summary

argument to be checked
possible interpretations
check the premises and conclusion of the argument
premises true and conclusion false ⇒ argument invalid, counterexample

invalid in one possible interpretation ⇒ invalid
otherwise, it is valid

why the domain?

semantics is complicated:

give a set D of elements
tell which one c is
tell which ones have the property P()
tell which ones have the property Q()

why not just:

tell whether P(c) is true or false and Q(c) is true or false

why not just?

for each constant c, tell whether P(c) is true, Q(c) is true, ...

does it work? (no)

possibilities

P(c)=true, Q(c)=true
P(c)=true, Q(c)=false
P(c)=false, Q(c)=true
P(c)=false, Q(c)=false

four possibilities
evaluate the argument in each

example: the second (P is true for c, Q is not)

evaluation of the argument in the four possibilities

argument:

P(c)
∀ x . P(x) → Q(x)
conclusion: Q(c)

possibilities:

P(c)=true, Q(c)=true
P(c)=true, Q(c)=false
P(c)=false, Q(c)=true
P(c)=false, Q(c)=false

first premise true in the first two possibilities
second premise true in the first, not in the second
premises both true only if P(c)=true, Q(c)=true
conclusion Q(c) true in it

argument is valid according to this semantics

another argument

man(Socrates)
mortal(Socrates)
consequence: ∀ x . man(x)

only valid if the only considered object is Socrates
not valid in general = not valid

does the simplified semantics recognize it?

alternative semantics fails

argument:

man(Socrates)
mortal(Socrates)
consequence: ∀ x . man(x)

possibilities:

man(Socrates)=true, mortal(Socrates)=true
man(Socrates)=true, mortal(Socrates)=false
man(Socrates)=false, mortal(Socrates)=true
man(Socrates)=false, mortal(Socrates)=false

first two premises hold only in the first case
conclusion true in the first case

argument invalid
semantics does not recognize it as invalid
semantics is wrong

objects that are not constants

same argument, semantics with the set of object

argument:

man(Socrates)
mortal(Socrates)
consequence: ∀ x . man(x)

counterexample:

D={1, 2}
man(1)=true, man(2)=false
mortal(1)=true, mortal(2)=false

premises true
consequence false (falsified by x=2)
argument invalid according to this semantics

problems with the simplified semantics

implicitely assumes: no object other than the constants
implicitely assumes: objects are all different

shown: 1

now showing: 2

different names, same thing

two constants may refer to the same object

example: 22-Oct-2022 and today

logic does not know about reality
does not care
only cares about validity of argument, not meaning of names

arguments should work in both cases:

if 22-Oct-2022 and today are the same day
if 22-Oct-2022 and today are different days

arguments should work regardless of the names:

with constants 22-Oct-2022 and today
with constants Socrates and Plato

why the domain?

without a domain:

possibility = whether predicates are true or not for all constants

implicitely assumes:

no objects outside constants
constants always refer to different objects

simplified semantics only works in this case
not in general

the semantics of functions

semantics of functions

man(Socrates)
∀ x . man(x) → man(father(x))
conclusion: man(father(Socrates))

father(Socrates) is an object

it may be the same as another constant
it may not
depends on the formulae

semantics is the same as with constants:
tell the father of each object

model

a model is a way to express one possibility

the set of objects
an object for each constant
the object related to the each other
the truth of the properties for each object

third: value of function(object) for every object of the domain

example model

domain: three people, 3 is "unknown"
Socrates is the first
the father of the first person is the second, etc.
man(x) is true for all three people

argument valid?

what is least intuitive about fol:
the syntax may contain concrete names (Socrates, father)
the semantics may not (1,2,3)

validity of argument in the model

argument:

man(Socrates)
∀ x. man(x) → man(father())
conclusion: man(father(Socrates))

model:

D={1,2,3}
Socrates is 1
man(1)=man(2)=man(3)=true

man(Socrates) is man(1), true

man(x) → man(father(x)) is true for all x
(since father(x) is one of the three people,
and man() is true for all people)

man(father(Socrates)) = man(father(1)) = man(2) = true

argument is valid

another model

domain: two people and two animals
Socrates is the first person
man() is true for the two people, false for the two animals

evaluation

argument:

man(Socrates)
∀ x. man(x) → man(father())
conclusion: man(father(Socrates))

model:

domain: {1,2,3,4}
Socrates is 1
father(1)=2, etc.
man(1)=man(2)=true, man(3)=man(4)=false

evaluation

argument:

man(Socrates)
∀ x. man(x) → man(father())
conclusion: man(father(Socrates))

model:

domain: {1,2,3,4}
Socrates is 1
father(1)=2, etc.
man(1)=man(2)=true, man(3)=man(4)=false

man(Socrates) is man(1), true
man(x) only true for x=1 and x=2, check man(father(x))
man(father(1))=man(2)=true
man(father(2))=man(2)=true
man(x) → man(father()) true for all x

man(father(Socrates)) is man(father(1)), which is man(2), true

argument valid

evaluation

argument valid in both models

valid in ALL models ⇒ argument valid

finiteness

father(father(father(...)))

infinite number of terms

each may correspond to a different object
or not

the domain may be infinite
or not

validity: valid in all models
both finite and infinite
both with coinciding and differing value of the terms