Introduction to 1st Order Predicate Logic in Logical Thinking

 
1
1
st
st
 order predicate logic
 order predicate logic
 
Introduction to Logical Thinking, Lesson 5
Introduction to Logical Thinking, Lesson 5
Course Guarantor
: Marek Menšík
Author of the slides:
 Marie Duží
 
1
 
Language of the 1
Language of the 1
st
st
 order predicate logic (PL1)
 order predicate logic (PL1)
 
We have seen that the language of propositional logic (PL) has a lot of
shortcomings; which is not to say that PL is not valuable. Just opposite, it is
the basic logical system contained in other more expressive systems.
Yet, the language of PL logic is rather poor in its expressive power. It makes
it possible to compose propositions into molecular ones,
 
but we cannot
analyse the 
structure
 of atomic propositions.
When evaluating or proving logical validity of an argument or a proposition,
atomic propositions contribute only by its truth value.
Hence, in PL we can prove only those arguments the validity of which does
not depend on the structure of atomic propositions
.
Propositional logic
Propositional logic
 = algebra 
 = algebra 
of truth values
of truth values
.
 
2
 
Language of the 1
Language of the 1
st
st
 order predicate logic (PL1)
 order predicate logic (PL1)
 
Example
Example
 
of an obviously valid argument that cannot be proved in PL
:
All monkeys like bananas
All monkeys like bananas
.
.
Judy 
Judy 
is a monkey
is a monkey
.
.
–––––––––––––––––––––––––
–––––––––––––––––––––––––
Judy 
Judy 
likes bananas
likes bananas
.
.
From the point of view of PL, premises and conclusion are 
atomic
atomic
propositions
propositions
, 
p
, 
q
, 
r
. 
But the PL argument
 
p
p
, 
, 
q 
q 
|– 
|– 
r
r
 
 
is not valid
is not valid
;
 
at the
valuation
 
p=
1, 
q=
1 a 
r=
0 
the premises are true and conclusion false
.
Yet the argument is valid  because assuming that Judy does not like bananas
contradicts the premises
. 
If
 Judy 
is a monkey and doesn’t like bananas
, 
then
the first premise that all the monkeys like bananas cannot be true
.
 
3
 
Language of the 1
Language of the 1
st
st
 order predicate logic (PL1)
 order predicate logic (PL1)
 
The argument has a valid schema:
All 
P
 are 
Q
.
a
 is a 
P
.
a
 is a 
Q
.
If we substitute for the symbol 
P
P
 
the property of 
being a monkey
being a monkey
, for the symbol 
Q
Q
 
the
property of 
liking bananas
liking bananas
, and for the symbol 
a
a
 
the individual 
Judy
Judy
, we obtain the above
valid argument.
Similarly we can apply another valid schema:
All 
P
 are 
Q
.
b
 is not a 
Q
.
b
 is not a 
P
.
Leaving interpretation of the symbols 
P 
and 
Q
 as above, and substituting for 
b 
individual
Barty, we obtain another valid argument that is not provable in PL:
All monkeys like bananas
All monkeys like bananas
.
.
Barty does not like bananas.
Barty does not like bananas.
–––––––––––––––––––––––––
–––––––––––––––––––––––––
Barty is not a monkey.
Barty is not a monkey.
 
4
 
Language of the 1
Language of the 1
st
st
 order predicate logic (PL1)
 order predicate logic (PL1)
 
The structure of propositions can be more complex. Not only 
properties
properties
 can
be ascribed to individuals, but also 
relations
relations
 
between them
. 
Consider, for
instance, these
 assumptions:
Everybody who likes George
Everybody who likes George
, 
, 
cooperates with
cooperates with
 Milan.
 Milan.
Milan 
Milan 
is not in good friends with anybody who is a friend of Luke
is not in good friends with anybody who is a friend of Luke
.
.
Petr 
Petr 
cooperates only with the friends of Charles
cooperates only with the friends of Charles
.
.
What follows from these assumption
?
For instance
, 
that
 
if
 Petr 
likes
 
George
, 
then
 Milan 
is a friend of
 
Charles
, 
and
if
 
Charles is a friend of Luke
, 
then
 Petr 
does not like George
.
Yet, inferring these conclusions from our premises is not so trivial as above
.
Hence, we need to introduce a formal language, prove valid argument
schemata and learn some more sophisticated methods of inferring
consequences and proving the validity
.
 This we are going to do in the rest of
this course.
 
5
 
Language of the 1
Language of the 1
st
st
 order predicate logic (PL1)
 order predicate logic (PL1)
 
We need to talk about 
properties
properties
 of the objects of interest (individuals) and
about 
relations
relations
 
 
between them. To this end, we introduce 
predicate symbols
predicate symbols
.
In addition, we need to refer to the 
individuals
individuals
 about whom we want to talk
and assign them properties or relations. To this end, we introduce 
terms
terms
.
Some claims are true for 
all
all
 
or only 
some
some
 individuals. To this end we
introduce 
quantifiers
quantifiers
, 
namely 
 (general) and 
 (existential).
Example
:
x
 [
M(x) 
 
B(x)
]
M(j)
–––––––––––––––––––––––––
B(j)
Gloss
. The formula 
x
 [
M(x) 
 
B(x)
] is read like this: for 
all (
all (
)
)
 
individuals 
individuals 
x
x
 
it
holds that 
if 
if 
x 
x 
has the property 
has the property 
M
M
 
(i.e. 
M(x)
), then it has also the 
property 
property 
B
B
(i.e. 
B(x)
). The formulas 
M(j)
M(j)
 and 
B(j)
B(j)
 
mean that the 
individual 
individual 
j 
j 
has the
has the
property 
property 
M
M
 
 
and
 
 
B, 
B, 
re
s
pectively
.
 
6
 
Language of the 1
Language of the 1
st
st
 order predicate logic (PL1)
 order predicate logic (PL1)
 
Some monkeys like bananas
 
 
x 
x 
[
[
M(x) 
M(x) 
 
 
B(x)
B(x)
]
]
The symbol 
x 
an 
individual
individual
 variable
. It refers to 
any 
element (individual) of
the domain of interest (
universe of discourse
universe of discourse
), namely depending on
valuation v
valuation v
. In one valuation it can refer to the individual Judy and in
another to Barty. Variables are atomic 
terms
terms
 that refer to individuals.
Mind
! In 
propositional logic 
we deal with 
truth-value variables
 
p
, 
q
, 
r
, … that
stand for 
propositions
, and refer to their truth values. However, in the 1
st
order
 
predicate logic
predicate logic
, we deal with  
individual variables
individual variables
 that refer to the
elements of the domain of interest; hence by their evaluation we obtain
individuals
individuals
.
The symbols 
, 
 are 
quantifiers
quantifiers
, namely 
general
general
 
(
) and 
existential
existential
 
(
).
Roughly, their meaning is this. In order a formula 
x
 (
F
) or 
x
 (
F
) be true,
the formula 
F
 must be true for 
some
some
 
or 
all
all
 (respectively) individuals referred
to by the variable 
x.
 
7
 
Language of the 1
Language of the 1
st
st
 order predicate logic
 order predicate logic
 
The symbols 
O 
and 
B 
are 
predicates
predicates
. In these formulas they represent 
properties
properties
 of
individuals.
 Predicate symbols can also represent 
relations
relations
 between individuals.
Example.
x 
x 
[
[
L(x,g) 
L(x,g) 
 
 
C(x,m)
C(x,m)
]
]
y 
y 
[
[
F(y,l)
F(y,l)
 
 
 
 
F(m,y)
F(m,y)
]
]
z
z
 [
 [
C(p,z) 
C(p,z) 
 
 
F(z,c)
F(z,c)
]
]
The symbols 
x
, 
y
, 
are variables, the symbols 
L
, 
C
, 
F
 are predicate symbols. In the
intended interpretation of the above example, the represent the relations 
Like
,
Cooperate
, 
Friend
, respectively.
In addition, we have got here another kind of terms referring to individuals, namely
constants
constants
: 
g
g
, 
, 
m
m
, 
, 
l
l
, 
, 
p
p
 a 
c
c
. 
Constants rigorously refer to just one individual,
independently of a valuation.  In our intended interpretation, they refer to 
George
,
Milan, Luke, Petr and Charles.
However, in another interpretation they can refer, e.g., to the numbers 1, 2, 3, 4, 5.
 
8
 
Definition of the PL1 language
Definition of the PL1 language
 
I)
 Alphabet
 consists of these symbols:
a)
Logical symbols
Individual variables 
x, y, z
,... (can be with subscripts)
Symbols for connectives: 
, 
, 
, 
, 
Quantifiers 
, 
b)
Special symbols
Predicate symbols: 
P
, 
Q
, 
R
, ... (can be with superscripts denoting 
arity
)
Functional symbols: 
f
, 
g
, 
h
, ... (can be with superscripts denoting 
arity
)
c)
Auxiliary symbols:  (,), [,],{,}
Arity is the number of arguments; By applying 
functional symbols
functional symbols
 to arguments, i.e. terms, we
create molecular terms, e.g. 
f(a,b).
For instance, if we interpret 
f 
as the adding function and constants 
a, b 
as the numbers 2, 3, we
obtain application of the function + to the numbers 2, 3, i.e., +(2,3), or 2+3 in the infix
mathematical notation. Then the term denotes the number 5.
 
9
 
Definition of the PL1 language
Definition of the PL1 language
 
II) 
Grammar 
that generates
a)
terms
Each variable symbol is an 
atomic term
atomic term
If 
t
1
, …, t
n 
(
n 
 0) are terms and 
f
 
is n-
ary functional symbol, then 
f
f
(
(
t
t
1
1
,
,
,
,
t
t
n
n
)
)
 is a term;
for 
n
 = 0 we have a ulary functional symbol, i.e. a 
constant
constant
, denoted 
a
a
, 
, 
b
b
, 
, 
c
c
, …;
for 
n 
> 0 we have a 
molecular
molecular
 
term
term
.
Only expressions due to i) and ii) are terms
b)
formulas
If 
P
 
is an n
-ary predicate symbol and 
t
1
, …, t
n 
are terms, then 
P
P
(
(
t
t
1
1
,
,
,
,
t
t
n
n
)
)
 is an 
atomic
atomic
formula
formula
If 
A
 is a formula, then 
A
A
 is a 
molecular formula
molecular formula
If 
A
 and 
B
 are formulas, then 
(
(
A
A
 
 
 
 
B
B
), (
), (
A
A
 
 
 
 
B
B
), (
), (
A
A
 
 
 
 
B
B
), (
), (
A
A
 
 
 
 
B
B
)
)
 are 
molecular formulas
molecular formulas
If 
x is a 
variable and 
A
 a formula, then 
x A
x A
 and 
x A
x A
 are 
molecular formulas
molecular formulas
Only expressions due to i) – vi) are 
formulas
 
10
 
PL1 language; comments
PL1 language; comments
 
1)
In PL
1 language, the only type of variables are 
individu
al variables that
can be bound by quantifiers.
 (
In the language of PL2 there are also
predicate variables
.)
2)
Notational conventions
 for omitting parentheses
:
The outermost parentheses can be omitted
.
Parentheses can be omitted due to the following priority of symbols
:
(
, 
), 
, 
, 
, 
, 
.
In case the priority does not decide, we evaluate the formula from left to
right
.
Since conjunction and disjunction are associative and commutative,
parentheses are not necessary here
.
Anyway, similarly as in PL, 
we do not recommend to overuse priority
conventions; It is better to insert parentheses whenever the structure of a
formula might not be clear.
 
11
 
PL1 language; examples
PL1 language; examples
 
The following sequences of symbols are well-formed formulas:
P(a)
, 
P(f(x)
,
y)
 atomic formulas
P(a) 
 
Q(x
,
y) 
 
R(a
,
x)
conjunction of atomic formulas, parentheses omitted
x
y 
[
P(a) 
 
Q(x
,
y) 
 
R(a
,
x)
]
parentheses here mark the 
scope of quantifiers
scope of quantifiers
Variable that occurs in the scope of a quantifier is 
bound
bound
. 
Bound
variables ‘behace’ in another way than free variables.
Hence, we define:
 
12
 
Free and bound variables; definition
Free and bound variables; definition
 
Definice 
(
free and bound variables
)
The 
occurrence
occurrence
 of a variable
 
x
 
in a formula
 
A
 
is
 
bound
bound
, 
if it occurs in a sub-
formula of 
A 
that is of the form
 
x B
x
 
or
 
x B
x
.
Variable
 
x
 
is
 
bound
bound
 
in a formula
 
A
, 
if 
x 
has in
 
A
 
a bound occurrence
.
The 
occurrence
occurrence
 of a variable
 
x
 
in a formula
 
A
 
that is not bound is 
free
free
.
Variable
 
x
 
is
 
free
free
 
in a formula
 
A
, 
if 
x 
has in
 
A
 
a free occurrence
.
A formula is
 
closed
closed
, 
if it does not contain any free variable
.
A formula that does contain at least one free variable is 
open
open
.
Note
. Variable 
x
 can have both free and bound occurrences in a formula 
A.
Anyway, we prefer to work with formulas with 
clear variables. 
clear variables. 
They are the
formulas in which all the occurrences of one and the same variable are
either free or bound.
 
13
 
Free and bound variables; examples
Free and bound variables; examples
 
x
x
 
 
[
[
P(
P(
x) 
x) 
 
 
Q(a,y)
Q(a,y)
]
]
The variable
 
x 
is bound in this formula, whereas the variable 
y 
is free.
The 
f
f
ormul
ormul
a is open
a is open
.
x
x
 
 
P(x) 
P(x) 
 
 
Q(a,x)
Q(a,x)
The first occurrence of
 
x 
is bound
, 
the second is free
. 
The 
formula is open
formula is open
,
,
and it is
 not a formula with clear variables
 not a formula with clear variables
.
The second occurrence of 
x 
is actually another variable. Thus it would be
more plausible to write this formula in a clear way, for instance as
 
x
 
P(x) 
 
Q(a,
y
)
x
x
 
 
y 
y 
[
[
P(x) 
P(x) 
 
 
Q(a,y)
Q(a,y)
]
]
The variable
 
x 
is bound by general quantifier
, 
the variable
 
y 
is bound by
existential quantifier
. 
The 
formula is closed
formula is closed
 
 
and it is the formula
 with clear
 with clear
variables
variables
.
 
14
 
Substitu
Substitu
tion
tion
 
We know that free variables denote 
any 
element of the universe,
while terms without free variables a certain definite element of the
universe. Hence, we can 
substitu
substitu
te
te
 
only
 
term
term
s
s
 
 
for free variables
for free variables
.
Since free variables differ from bound ones, the substitution must not
turn any variable occurring in the term as free to a bound one. Hence,
we must protect substitution from the 
collision of variables
collision of variables
.
Let 
A
A
t
t
/
/
x
x
 
be formula that is obtained from 
A
 
by the 
substitution of
term t
 
for the variable 
x
. 
In order the substitution be 
correct
correct
,
 
the 
term
term
t 
t 
must be
must be
 
 
substitu
substitu
table for
table for
 
 
the variable 
the variable 
x 
x 
in the formula 
in the formula 
A
A
.
There are two rules for a correct substitution.
 
15
 
Correct substitution;
Correct substitution;
 
 
two rules
two rules
 
1.
Term 
t 
can be substituted 
only for all the free occurrences
only for all the free occurrences
 
of the
variable
 
x
 
in the formula
 
A
;
 
hence, we replace 
all the free
occurrences 
of
 
the variable
 
x
 
by the term 
t 
in
 
A
.
2.
No
No
 
free
free
 
variable occurring in the term 
t
 
can become bound by the
substitution
 
t
/
x
.
Example
.
 
Let
 
A
(
x
) 
be
 
P
P
(
(
x
x
) 
) 
 
 
y
y
 
 
Q
Q
(
(
x, y
x, y
)
)
 
and
 
let 
term 
t
 
be
 
f
f
(
(
y
y
)
)
.
The substitution 
A
A
(
(
f
f
(
(
y
y
)/
)/
x
x
)
)
 
yields the formula
 
P
P
(
(
f
f
(
(
y
y
)) 
)) 
 
 
y
y
 
 
Q
Q
(
(
f
f
(
(
y
y
)
)
, y
).
We can see that the second occurrence of the variable 
y
 
is bound.Such
a substitution is 
incorrect
incorrect
. Hence, the
 
term 
term 
f
f
(
(
y
y
) 
) 
is not
is not
 
 
substitutable for 
substitutable for 
x
x
in the formula
in the formula
 
 
A
A
.
 
16
 
Formalization in the PL1 language
Formalization in the PL1 language
 
Expressions of a natural language that denote 
properties
properties
 of
individuals or 
relations
relations
 between them are replaced by 
predicate
predicate
symbols
symbols
 
 
P
P
, 
, 
Q
Q
, 
, 
R
R
, etc.
Expressions that denote 
functional mappings
functional mappings
 are replaced by
functional symbols
functional symbols
 
 
f
f
, 
, 
g
g
, 
, 
h
h
, etc.
Expressions like ‘
all
all
’, ‘
everybody
everybody
’, ‘
nobody’
nobody’
, ‘
none
none
’ are translated by
the qeneral quantifier 
Expressions like ‘
somebody’
somebody’
, ‘
some
some
’, ‘
something
something
’, ‘
there are
there are
’, ‘
exists
exists
are translated by the existential quantifier 
.
The other rules that we stated for the formalization in propositional logic
are valid as well, as the PL1 language is an extension of the PL language.
 
17
 
Formalization in the PL1 language
Formalization in the PL1 language
 
A natural language sentence that we want to formalize in PL1 should often be
reformulated in an equivalent way
reformulated in an equivalent way
, 
i.e., in such a way that the truth conditions
of sentences remain the same
.
It is also useful to find more such equivalent formulations, and then check that
the resulting formulas are, indeed, equivalent (have the same models). Now we
will make it only intuitively
. 
Later we will also learn some useful equivalent
transformations of formulas.
Example.
 
Only employees use the lift
 (is equivalent)
 
      
 
If somebody is not an employee, then they do not use the lift
 
 
      
 
There is nobody who would use the lift and were not an employee
x 
x 
[
[
L(x)
L(x)
 
 
 
 
E(x)
E(x)
] 
] 
 
 
x 
x 
[
[
E(x)
E(x)
 
 
 
 
L(x)
L(x)
] 
] 
 
 


x
x
 [
 [
L(x) 
L(x) 
 
 
E(x)
E(x)
]
]
The first equivalence is due to transposition of implication;
the second is application of de Morgan law.
 
18
 
Formalization in the PL1 language
Formalization in the PL1 language
 
Example
.
Some prime numbers are even
There is an
 
x
 
such that 
P
rime
(
x
) 
and
 
Even
(
x
)“
x 
x 
[
[
P(x) 
P(x) 
 
 
E
E
(
(
x
x
)]
)]
Another equivalent formulation
:
It is not true that no prime is even


x
x
 
 
[
[
P(x) 
P(x) 
 
 
E
E
(x)
(x)
]
]
 
 (
checking
)
x
 
[
P(x) 
 
S(x)
] 
 
x
 
[
P(x) 
 
S(x)
] 
 
x 
x 
[
[
P(x) 
P(x) 
 
 
S(x)
S(x)
]
]
We can see that our formalization is correct, as all the formulas we
obtained are equivalent; In the last line we again applied de Morgan law
.
 
19
 
De Morgan 
De Morgan 
laws
laws
 (
for negating quantified formulas
)
 
If it is not true that 
all
 
x 
satisfy the condition specified by the formula
 
A
,
i.e. 

x 
(
A
), 
then some
 
x 
do not satisfy this condition
, 
i.e.
 
x 
(
A
), 
and
vice versa
:


x 
x 
(
(
A
A
) 
) 
 
 
x 
x 
(
(
A
A
)
)
If it is not true that 
some
 
x 
satisfy the condition specified by the formula
A
, 
i.e. 

x 
(
A
), 
then no
 
x 
satisfies this condition
, 
i.e.
 
x 
(
A
), 
and vice
versa
:


x 
x 
(
(
A
A
) 
) 
 
 
x 
x 
(
(
A
A
)
)
Mind
! 
The last formula 
x 
(
A
)
 is read as “
No
 
x 
is 
A
”. If we read it as “All 
x 
are not
A
”, it would have different meaning. It would mean “Not all 
x 
are 
A
”, hence “Some
x 
are not 
A
”.
 
20
 
De Morgan 
De Morgan 
laws
laws
 
Recall de Morgan laws in propositional logic for negation of
conjunction and disjunction.
If it is not true that
 
A 
and
 
B
, 
i.e.
 
(
A 
 
B
), 
then
 
non
-
A 
or
 
non
-
B
, 
i.e.
(
A 
 
B
), 
and vice versa
.
(
(
A 
A 
 
 
B
B
) 
) 
 
 
(
(
A 
A 
 
 
B
B
)
)
If it is not true that
 
A 
and
 
B
, 
i.e.
 
(
A 
 
B
), 
then
 
neither
-
A, 
nor
-
B
, 
i.e.
(
A 
 
B
), 
and vice versa
.
(
(
A 
A 
 
 
B
B
) 
) 
 
 
(
(
A 
A 
 
 
B
B
)
)
 
21
 
Formalization in the PL1 language
Formalization in the PL1 language
 
Example
.
No prime number greater than
No prime number greater than
 2 
 2 
is even
is even
 
 
For all
For all
 
 
x
x
 
 
it holds that
it holds that
 
 
if
if
 (
 (
Pr
Pr
ime
ime
(
(
x
x
) 
) 
and
and
Greater
Greater
 x 
 x 
than
than
 
 
2), 
2), 
then 
then 
not
not
 
 
Even
Even
(
(
x
x
)“
)“
x 
x 
[(
[(
P(x) 
P(x) 
 
 
G
G
(x
(x
,2
,2
)
)
) 
) 
 
 
E
E
(
(
x
x
)]
)]
Equivalently
:
It is not true that
It is not true that
 
 
some prime numbers greater than 2 are even
some prime numbers greater than 2 are even


x
x
 
 
[(
[(
P(x) 
P(x) 
 
 
G
G
(x
(x
,2
,2
)
)
)
)
 
 
 
 
E
E
(x)
(x)
]
]
 
 (
check
)
x
x
 
 
[(
[(
P(x) 
P(x) 
 
 
G
G
(x
(x
,2
,2
)
)
)
)
 
 
 
 
E
E
(x)
(x)
] 
] 
x 
x 
[
[
(
(
P(x) 
P(x) 
 
 
G
G
(x
(x
,2
,2
)
)
)
)
 
 
 
 
E
E
(x)
(x)
] 
] 
x 
x 
[(
[(
P(x) 
P(x) 
 
 
G
G
(x
(x
,2
,2
)
)
) 
) 
 
 
E
E
(
(
x
x
)]
)]
In the last line, we have applied an important law of propositional logic that 
should be
remembered
:
(
(
A
A
 
 
 
 
B
B
)
)
 
 
 (
 (
A 
A 
 
 
B
B
)
)
Check this law by a truth table
.
 
22
 
The sense of quantifiers
The sense of quantifiers
 
Imagine that we work with a 
finite
finite
 
universe of discourse, i.e. the set {
a
1
, 
a
2
, …, 
a
n
}.
Then the statement that the condition 
F
 
is valid for 
all
 the elements of discourse,
i.e.
 
x F(x)
x F(x)
, 
is equivalent to the statement that the condition is valid for 
a
1 
and
 a
2
and
, …, 
a
n
. Hence, that the formula 
F(a
F(a
1
1
) 
) 
 
 
F(a
F(a
2
2
) 
) 
 
 
F(a
F(a
n
n
)
)
 is true.
Similarly, the statement that the condition 
F
 
is valid for 
some
 elements of
discourse, i.e.
 
x F(x)
x F(x)
, 
is equivalent to the statement that this condition is valid for
a
1 
or
 a
2
 
or
, …, 
a
n
, i.e. that the formula
 
F(a
F(a
1
1
) 
) 
 
 
F(a
F(a
2
2
) 
) 
 
 
F(a
F(a
n
n
)
)
 is true.
But if the universe is 
infinite
 (
for instance the set of natural numbers
 {0,1,2, …, }),
then it is impossible to write an infinite conjunction or disjunction. Hence, to this
end we use quantifiers.
General quantifier can be viewed as the generalization of conjunction and
existential quantifier as a generalization of disjunction for an infinite number of
elements. Schematically
:
x F
x F
(x)
(x)
 
 
 
 
F(a
F(a
1
1
) 
) 
 
 
F(a
F(a
2
2
) 
) 
 
 
F(a
F(a
n
n
) 
) 
x F
x F
(x)
(x)
 
 
 
 
F(a
F(a
1
1
) 
) 
 
 
F(a
F(a
2
2
) 
) 
 
 
F(a
F(a
n
n
) 
) 
 
23
 
The sense of quantifiers
The sense of quantifiers
 
Now the sense of de Morgan laws should also be clear. Again
schematically
, as an infinite conjunction or disjunction are not well-
formed formulas:


x F(x)
x F(x)
 
 
 
 
(
(
F(a
F(a
1
1
) 
) 
 
 
F(a
F(a
2
2
) 
) 
 
 
F(a
F(a
n
n
) 
) 
 …) 
 …) 
(
(
F(a
F(a
1
1
) 
) 
 
 
F(a
F(a
2
2
) 
) 
 
 
F(a
F(a
n
n
) 
) 
 …) 
 …) 
 
 
x 
x 
F(x)
F(x)


x F(x)
x F(x)
 
 
 
 
(
(
F(a
F(a
1
1
) 
) 
 
 
F(a
F(a
2
2
) 
) 
 
 
F(a
F(a
n
n
) 
) 
 …) 
 …) 
(
(
F(a
F(a
1
1
) 
) 
 
 
F(a
F(a
2
2
) 
) 
 
 
F(a
F(a
n
n
) 
) 
 …) 
 …) 
 
 
x 
x 
F(x)
F(x)
 
24
 
Important tenets of formalization
Important tenets of formalization
 
Sentences of the type
 
Some
Some
 
 
P 
P 
are
are
 
 
Q
Q
analyse as
 
x 
x 
[
[
P(x) 
P(x) 
 
 
Q(x)
Q(x)
]
]
Sentences of the type
All
All
 
 
P 
P 
j
j
are
are
 Q
 Q
analyse as
 
x 
x 
[
[
P(x) 
P(x) 
 
 
Q(x)
Q(x)
]
]
.
S
chema: 
x - 
x - 
, 
, 
x - 
x - 
 
25
 
Checking the correctness of analysis; negation
Checking the correctness of analysis; negation
 
Some students (
S
) 
have a job
 (
H
) 
 
There is an
 
x 
such that
 
x 
is a
 student 
and
x 
has a job
x 
[
S(x) 
 
H
(x)
]
It is not true that
 
some students have a job
 
 
No
 student 
has a job
 
It holds for all
 
x 
that if
 x 
is a 
student
 then 
x 
doesn’t have a job

x 
[
S(x) 
 
H(x)
] 
 
x 
[
S(x) 
 
H(x)
] 
x 
[
S(x) 
 
H(x)
] 
 
x 
[
S(x) 
 
H(x)
]
All students
 (
S
) 
have a job
 (
H
) 
 
It holds for all
 
x 
that if
 
x 
is a 
student
 then 
x
has a job
x
 
[
S(x) 
 
H(x)
]
It is not true that all students have a job
 
 
Some students don’t have a job

x
 [
S(x) 
 
H
(x)
] 
 
x 
[
S(x) 
 
H(x)
] 
x 
[
S(x) 
 
H(x)
] 
 
x 
[
S(x) 
 
H
(x)
]
 
 
26
Slide Note
Embed
Share

Explore the limitations of propositional logic and the enhanced expressive power of 1st order predicate logic (PL1). Understand how PL1 allows for analyzing the structure of atomic propositions and proving arguments that depend on these structures. Through examples and valid argument schemata, delve into the complexities of relations between individuals and properties. Prepare to learn formal language, valid argument schemata, and advanced inference methods in the upcoming lessons.


Uploaded on May 14, 2024 | 1 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. 1storder predicate logic Introduction to Logical Thinking, Lesson 5 Course Guarantor: Marek Men k Author of the slides: Marie Du 1

  2. Language of the 1storder predicate logic (PL1) We have seen that the language of propositional logic (PL) has a lot of shortcomings; which is not to say that PL is not valuable. Just opposite, it is the basic logical system contained in other more expressive systems. Yet, the language of PL logic is rather poor in its expressive power. It makes it possible to compose propositions into molecular ones, but we cannot analyse the structure of atomic propositions. When evaluating or proving logical validity of an argument or a proposition, atomic propositions contribute only by its truth value. Hence, in PL we can prove only those arguments the validity of which does not depend on the structure of atomic propositions. Propositional logic = algebra of truth values. 2

  3. Language of the 1storder predicate logic (PL1) Example of an obviously valid argument that cannot be proved in PL: All monkeys like bananas. Judy is a monkey. Judy likes bananas. From the point of view of PL, premises and conclusion are atomic propositions, p, q, r. But the PL argument p, q | r is not valid; at the valuation p=1, q=1 a r=0 the premises are true and conclusion false. Yet the argument is valid because assuming that Judy does not like bananas contradicts the premises. If Judy is a monkey and doesn t like bananas, then the first premise that all the monkeys like bananas cannot be true. 3

  4. Language of the 1storder predicate logic (PL1) The argument has a valid schema: All P are Q. a is a P. a is a Q. If we substitute for the symbol P the property of being a monkey, for the symbol Q the property of liking bananas, and for the symbol a the individual Judy, we obtain the above valid argument. Similarly we can apply another valid schema: All P are Q. b is not a Q. b is not a P. Leaving interpretation of the symbols P and Q as above, and substituting for b individual Barty, we obtain another valid argument that is not provable in PL: All monkeys like bananas. Barty does not like bananas. Barty is not a monkey. 4

  5. Language of the 1storder predicate logic (PL1) The structure of propositions can be more complex. Not only properties can be ascribed to individuals, but also relations between them. Consider, for instance, these assumptions: Everybody who likes George, cooperates with Milan. Milan is not in good friends with anybody who is a friend of Luke. Petr cooperates only with the friends of Charles. What follows from these assumption? For instance, that if Petr likes George, then Milan is a friend of Charles, and if Charles is a friend of Luke, then Petr does not like George. Yet, inferring these conclusions from our premises is not so trivial as above. Hence, we need to introduce a formal language, prove valid argument schemata and learn some more sophisticated methods of inferring consequences and proving the validity. This we are going to do in the rest of this course. 5

  6. Language of the 1storder predicate logic (PL1) We need to talk about properties of the objects of interest (individuals) and about relations between them. To this end, we introduce predicate symbols. In addition, we need to refer to the individuals about whom we want to talk and assign them properties or relations. To this end, we introduce terms. Some claims are true for all or only some individuals. To this end we introduce quantifiers, namely (general) and (existential). Example: x [M(x) B(x)] M(j) B(j) Gloss. The formula x [M(x) B(x)] is read like this: for all ( ) individuals x it holds that if x has the property M (i.e. M(x)), then it has also the property B (i.e. B(x)). The formulas M(j) and B(j) mean that the individual j has the property M and B, respectively. 6

  7. Language of the 1storder predicate logic (PL1) Some monkeys like bananas x [M(x) B(x)] The symbol x an individual variable. It refers to any element (individual) of the domain of interest (universe of discourse), namely depending on valuation v. In one valuation it can refer to the individual Judy and in another to Barty. Variables are atomic terms that refer to individuals. Mind! In propositional logic we deal with truth-value variables p, q, r, that stand for propositions, and refer to their truth values. However, in the 1st order predicate logic, we deal with individual variables that refer to the elements of the domain of interest; hence by their evaluation we obtain individuals. The symbols , are quantifiers, namely general ( ) and existential ( ). Roughly, their meaning is this. In order a formula x (F) or x (F) be true, the formula F must be true for some or all (respectively) individuals referred to by the variable x. 7

  8. Language of the 1storder predicate logic The symbols O and B are predicates. In these formulas they represent properties of individuals. Predicate symbols can also represent relations between individuals. Example. x [L(x,g) C(x,m)] y [F(y,l) F(m,y)] z [C(p,z) F(z,c)] The symbols x, y, z are variables, the symbols L, C, F are predicate symbols. In the intended interpretation of the above example, the represent the relations Like, Cooperate, Friend, respectively. In addition, we have got here another kind of terms referring to individuals, namely constants: g, m, l, p a c. Constants rigorously refer to just one individual, independently of a valuation. In our intended interpretation, they refer to George, Milan, Luke, Petr and Charles. However, in another interpretation they can refer, e.g., to the numbers 1, 2, 3, 4, 5. 8

  9. Definition of the PL1 language I) Alphabet consists of these symbols: a) Logical symbols Individual variables x, y, z,... (can be with subscripts) Symbols for connectives: , , , , Quantifiers , b) Special symbols Predicate symbols: P, Q, R, ... (can be with superscripts denoting arity) Functional symbols: f, g, h, ... (can be with superscripts denoting arity) c) Auxiliary symbols: (,), [,],{,} Arity is the number of arguments; By applying functional symbols to arguments, i.e. terms, we create molecular terms, e.g. f(a,b). For instance, if we interpret f as the adding function and constants a, b as the numbers 2, 3, we obtain application of the function + to the numbers 2, 3, i.e., +(2,3), or 2+3 in the infix mathematical notation. Then the term denotes the number 5. 9

  10. Definition of the PL1 language II) Grammar that generates a) terms Each variable symbol is an atomic term If t1, , tn(n 0) are terms and f is n-ary functional symbol, then f(t1, ,tn) is a term; for n = 0 we have a ulary functional symbol, i.e. a constant, denoted a, b, c, ; for n > 0 we have a molecular term. Only expressions due to i) and ii) are terms b) formulas If P is an n-ary predicate symbol and t1, , tnare terms, then P(t1, ,tn) is an atomic formula If A is a formula, then A is a molecular formula If A and B are formulas, then (A B), (A B), (A B), (A B) are molecular formulas If x is a variable and A a formula, then x A and x A are molecular formulas Only expressions due to i) vi) are formulas 10

  11. PL1 language; comments 1) In PL1 language, the only type of variables are individual variables that can be bound by quantifiers. (In the language of PL2 there are also predicate variables.) 2) Notational conventions for omitting parentheses: The outermost parentheses can be omitted. Parentheses can be omitted due to the following priority of symbols: ( , ), , , , , . In case the priority does not decide, we evaluate the formula from left to right. Since conjunction and disjunction are associative and commutative, parentheses are not necessary here. Anyway, similarly as in PL, we do not recommend to overuse priority conventions; It is better to insert parentheses whenever the structure of a formula might not be clear. 11

  12. PL1 language; examples The following sequences of symbols are well-formed formulas: P(a), P(f(x),y) atomic formulas P(a) Q(x,y) R(a,x) conjunction of atomic formulas, parentheses omitted x y [P(a) Q(x,y) R(a,x)] parentheses here mark the scope of quantifiers Variable that occurs in the scope of a quantifier is bound. Bound variables behace in another way than free variables. Hence, we define: 12

  13. Free and bound variables; definition Definice (free and bound variables) The occurrence of a variable x in a formula A is bound, if it occurs in a sub- formula of A that is of the form x B(x) or x B(x). Variable x is bound in a formula A, if x has in A a bound occurrence. The occurrence of a variable x in a formula A that is not bound is free. Variable x is free in a formula A, if x has in A a free occurrence. A formula is closed, if it does not contain any free variable. A formula that does contain at least one free variable is open. Note. Variable x can have both free and bound occurrences in a formula A. Anyway, we prefer to work with formulas with clear variables. They are the formulas in which all the occurrences of one and the same variable are either free or bound. 13

  14. Free and bound variables; examples x [P(x) Q(a,y)] The variable x is bound in this formula, whereas the variable y is free. The formula is open. xP(x) Q(a,x) The first occurrence of x is bound, the second is free. The formula is open, and it is not a formula with clear variables. The second occurrence of x is actually another variable. Thus it would be more plausible to write this formula in a clear way, for instance as xP(x) Q(a,y) x y [P(x) Q(a,y)] The variable x is bound by general quantifier, the variable y is bound by existential quantifier. The formula is closed and it is the formula with clear variables. 14

  15. Substitution We know that free variables denote any element of the universe, while terms without free variables a certain definite element of the universe. Hence, we can substitute only terms for free variables. Since free variables differ from bound ones, the substitution must not turn any variable occurring in the term as free to a bound one. Hence, we must protect substitution from the collision of variables. Let A(t/x) be formula that is obtained from A by the substitution of term t for the variable x. In order the substitution be correct, the term t must be substitutable for the variable x in the formula A. There are two rules for a correct substitution. 15

  16. Correct substitution; two rules 1. Term t can be substituted only for all the free occurrences of the variable x in the formula A; hence, we replace all the free occurrences of the variable x by the term t in A. 2. Nofree variable occurring in the term t can become bound by the substitution t/x. Example. Let A(x) be P(x) yQ(x, y) and let term t be f(y). The substitution A(f(y)/x) yields the formula P(f(y)) yQ(f(y), y). We can see that the second occurrence of the variable y is bound.Such a substitution is incorrect. Hence, the term f(y) is not substitutable for x in the formula A. 16

  17. Formalization in the PL1 language Expressions of a natural language that denote properties of individuals or relations between them are replaced by predicate symbols P, Q, R, etc. Expressions that denote functional mappings are replaced by functional symbols f, g, h, etc. Expressions like all , everybody , nobody , none are translated by the qeneral quantifier Expressions like somebody , some , something , there are , exists are translated by the existential quantifier . The other rules that we stated for the formalization in propositional logic are valid as well, as the PL1 language is an extension of the PL language. 17

  18. Formalization in the PL1 language A natural language sentence that we want to formalize in PL1 should often be reformulated in an equivalent way, i.e., in such a way that the truth conditions of sentences remain the same. It is also useful to find more such equivalent formulations, and then check that the resulting formulas are, indeed, equivalent (have the same models). Now we will make it only intuitively. Later we will also learn some useful equivalent transformations of formulas. Example. Only employees use the lift (is equivalent) If somebody is not an employee, then they do not use the lift There is nobody who would use the lift and were not an employee x [L(x) E(x)] x [ E(x) L(x)] x [L(x) E(x)] The first equivalence is due to transposition of implication; the second is application of de Morgan law. 18

  19. Formalization in the PL1 language Example. Some prime numbers are even There is an x such that Prime(x) and Even(x) x [P(x) E(x)] Another equivalent formulation: It is not true that no prime is even x [P(x) E(x)] (checking) x [P(x) S(x)] x [ P(x) S(x)] x [P(x) S(x)] We can see that our formalization is correct, as all the formulas we obtained are equivalent; In the last line we again applied de Morgan law. 19

  20. De Morgan laws (for negating quantified formulas) If it is not true that all x satisfy the condition specified by the formula A, i.e. x (A), then some x do not satisfy this condition, i.e. x (A), and vice versa: x (A) x (A) If it is not true that some x satisfy the condition specified by the formula A, i.e. x (A), then no x satisfies this condition, i.e. x (A), and vice versa: x (A) x (A) Mind! The last formula x (A) is read as No x is A . If we read it as All x are not A , it would have different meaning. It would mean Not all x are A , hence Some x are not A . 20

  21. De Morgan laws Recall de Morgan laws in propositional logic for negation of conjunction and disjunction. If it is not true that A and B, i.e. (A B), then non-A or non-B, i.e. ( A B), and vice versa. (A B) ( A B) If it is not true that A and B, i.e. (A B), then neither-A, nor-B, i.e. ( A B), and vice versa. (A B) ( A B) 21

  22. Formalization in the PL1 language Example. No prime number greater than 2 is even For all x it holds that if (Prime(x) and Greater x than 2), then notEven(x) x [(P(x) G(x,2)) E(x)] Equivalently: It is not true that some prime numbers greater than 2 are even x [(P(x) G(x,2)) E(x)] (check) x [(P(x) G(x,2)) E(x)] x [ (P(x) G(x,2)) E(x)] x [(P(x) G(x,2)) E(x)] In the last line, we have applied an important law of propositional logic that should be remembered: ( A B) (A B) Check this law by a truth table. 22

  23. The sense of quantifiers Imagine that we work with a finite universe of discourse, i.e. the set {a1, a2, , an}. Then the statement that the condition F is valid for all the elements of discourse, i.e. x F(x), is equivalent to the statement that the condition is valid for a1 and a2 and, , an. Hence, that the formula F(a1) F(a2) F(an) is true. Similarly, the statement that the condition F is valid for some elements of discourse, i.e. x F(x), is equivalent to the statement that this condition is valid for a1 or a2or, , an, i.e. that the formula F(a1) F(a2) F(an) is true. But if the universe is infinite (for instance the set of natural numbers {0,1,2, , }), then it is impossible to write an infinite conjunction or disjunction. Hence, to this end we use quantifiers. General quantifier can be viewed as the generalization of conjunction and existential quantifier as a generalization of disjunction for an infinite number of elements. Schematically: x F(x) F(a1) F(a2) F(an) x F(x) F(a1) F(a2) F(an) 23

  24. The sense of quantifiers Now the sense of de Morgan laws should also be clear. Again schematically, as an infinite conjunction or disjunction are not well- formed formulas: x F(x) (F(a1) F(a2) F(an) ) ( F(a1) F(a2) F(an) ) x F(x) x F(x) (F(a1) F(a2) F(an) ) ( F(a1) F(a2) F(an) ) x F(x) 24

  25. Important tenets of formalization Sentences of the type Some P are Q analyse as x [P(x) Q(x)] Sentences of the type All P jare Q analyse as x [P(x) Q(x)]. Schema: x - , x - 25

  26. Checking the correctness of analysis; negation Some students (S) have a job (H) There is an x such that x is a student and x has a job x [S(x) H(x)] It is not true that some students have a job No student has a job It holds for all x that if x is a student then x doesn t have a job x [S(x) H(x)] x [S(x) H(x)] x [ S(x) H(x)] x [S(x) H(x)] All students (S) have a job (H) It holds for all x that if x is a student then x has a job x [S(x) H(x)] It is not true that all students have a job Some students don t have a job x [S(x) H(x)] x [S(x) H(x)] x [ S(x) H(x)] x [S(x) H(x)] 26

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#