FIT2014 Theory of Computation Lecture 3 Predicate Logic
FIT2014 Theory of Computation
Lecture 3
Predicate Logic
slides by
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 20
Lecture overview
I Statements with variables
I Predicates
I Definitions and terminology
I Existential quantifier
I Universal quantifier
I Doing logic with quantifiers
2 / 20
Statements with variables
Consider these statements:
I W is negative.
I X passed this subject.
I Y = Z .
These do not yet have truth values.
The variables are free, in that no value is (yet) given to them.
You can, if you wish, assign values to them.
Each set of values you give to the variables creates a different specific proposition.
3 / 20
Statements with variables
For example, in the statement W is negative, the variable W is free.
If we assign values to it, we can create specific propositions:
…
…
−2 is negative True
−1 is negative True
0 is negative False
1 is negative False
2 is negative False
…
…
4 / 20
Predicates
Definitions
A predicate is a statement with variables such that, for any values of the variables, it
is either True or False.
I i.e., it becomes a proposition
We treat each variable as ranging over some domain.
I For the predicate W is negative, we’ve just been using the domain Z.
The variables of a predicate are also called its arguments.
A predicate is called k-ary if it has k arguments. Special cases: unary, binary, ternary, . . .
Some alternative terminology:
# arguments terminology
1 property
≥ 2 relation
5 / 20
Predicates
Definitions
A predicate is a statement with variables such that, for any values of the variables, it
is either True or False.
I i.e., it becomes a proposition
We treat each variable as ranging over some domain.
I For the predicate W is negative, we’ve just been using the domain Z.
The variables of a predicate are also called its arguments.
A predicate is called k-ary if it has k arguments. Special cases: unary, binary, ternary, . . .
Some alternative terminology:
# arguments terminology
1 property
≥ 2 relation
5 / 20
Predicates
Definitions
A predicate is a statement with variables such that, for any values of the variables, it
is either True or False.
I i.e., it becomes a proposition
We treat each variable as ranging over some domain.
I For the predicate W is negative, we’ve just been using the domain Z.
The variables of a predicate are also called its arguments.
A predicate is called k-ary if it has k arguments. Special cases: unary, binary, ternary, . . .
Some alternative terminology:
# arguments terminology
1 property
≥ 2 relation
5 / 20
Predicates: examples
# args. example domain
1 isNegative(X ) N
1 isNegative(X ) Z
2 = [always available] objects
2 X < Y numbers
2 isMotherOf(X ,Y ), meaning “X is the mother of Y ” people
3 gives(X ,Y ,Z ), meaning “X gives Y to Z” X ,Z are people,
Y is a gift
...
...
...
Predicates may be thought of as truth-valued functions, i.e., functions whose value is
always in {True, False}.
6 / 20
Predicates: examples
# args. example domain
1 isNegative(X ) N
1 isNegative(X ) Z
2 = [always available] objects
2 X < Y numbers
2 isMotherOf(X ,Y ), meaning “X is the mother of Y ” people
3 gives(X ,Y ,Z ), meaning “X gives Y to Z” X ,Z are people,
Y is a gift
...
...
...
Predicates may be thought of as truth-valued functions, i.e., functions whose value is
always in {True, False}.
6 / 20
Functions
We’ll also use functions whose values aren’t necessarily just True or False.
# args. example domain codomain
1
√
X nonnegative numbers numbers
1 motherOf(X ) people people
2 X + Y numbers numbers
...
...
...
Functions with no arguments are called constants.
I Examples: 5, Annie, . . .
A function’s arguments can be: constants; variables; functions.
7 / 20
Functions
We’ll also use functions whose values aren’t necessarily just True or False.
# args. example domain codomain
1
√
X nonnegative numbers numbers
1 motherOf(X ) people people
2 X + Y numbers numbers
...
...
...
Functions with no arguments are called constants.
I Examples: 5, Annie, . . .
A function’s arguments can be: constants; variables; functions.
7 / 20
Existential quantifier
There’s a fly in my soup. ∃X : (X is a fly) ∧ (X is in my soup).
There exists W : W is negative. ∃W : W < 0
If domain of W is N: it’s False. ∃W ∈ N : W < 0
If domain of W is Z: it’s True. ∃W ∈ Z : W < 0
8 / 20
Existential quantifier
There’s a fly in my soup. ∃X : (X is a fly) ∧ (X is in my soup).
There exists W : W is negative. ∃W : W < 0
If domain of W is N: it’s False. ∃W ∈ N : W < 0
If domain of W is Z: it’s True. ∃W ∈ Z : W < 0
8 / 20
Existential quantifier
Someone did it. ∃X : X did it.
It’s sort-of like a disjunction . . .
· · · · · ·∨(Annie did it)∨(Edward did it)∨(Henrietta did it)∨(Radhanath did it)∨· · · · · ·
. . . but:
I often the domain of a variable is infinite;
I keep the variables, they’re useful.
The variables are now bound.
You can no longer give specific values to the variables to create specific propositions.
The quantifier has turned the statement into a single proposition about the entire
domains of the variables.
Quantifiers can only be used with variables.
Using them with constant objects makes no sense: ∃5, ∃Annie.
9 / 20
Existential quantifier
Someone did it. ∃X : X did it.
It’s sort-of like a disjunction . . .
· · · · · ·∨(Annie did it)∨(Edward did it)∨(Henrietta did it)∨(Radhanath did it)∨· · · · · ·
. . . but:
I often the domain of a variable is infinite;
I keep the variables, they’re useful.
The variables are now bound.
You can no longer give specific values to the variables to create specific propositions.
The quantifier has turned the statement into a single proposition about the entire
domains of the variables.
Quantifiers can only be used with variables.
Using them with constant objects makes no sense: ∃5, ∃Annie.
9 / 20
Existential quantifier
Some computer is human. i.e., There exists a human computer.
If the domain of X is { computers }
Predicate:
I human(X ): X is human.
∃X : human(X )
But what if the domain of X is { everything on Earth } ?
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
10 / 20
Existential quantifier
Some computer is human. i.e., There exists a human computer.
If the domain of X is { computers }
Predicate:
I human(X ): X is human.
∃X : human(X )
But what if the domain of X is { everything on Earth } ?
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
10 / 20
Existential quantifier
Some computer is human. i.e., There exists a human computer.
If the domain of X is { everything on Earth }
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
Correct: Incorrect:
∃X : computer(X ) ∧ human(X ) ∃X : computer(X )⇒ human(X )
I “There exists something that is both
computer and human.”
I “There exists a human computer.”
I “Some computer is human.”
I “There exists something which is not
a computer or is human.”
I “There exists something which is not
both a computer and non-human.”
I “Not everything is a nonhuman
computer.”
11 / 20
Existential quantifier
Some computer is human. i.e., There exists a human computer.
If the domain of X is { everything on Earth }
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
Correct: Incorrect:
∃X : computer(X ) ∧ human(X ) ∃X : computer(X )⇒ human(X )
I “There exists something that is both
computer and human.”
I “There exists a human computer.”
I “Some computer is human.”
I “There exists something which is not
a computer or is human.”
I “There exists something which is not
both a computer and non-human.”
I “Not everything is a nonhuman
computer.”
11 / 20
Existential quantifier
Some computer is human. i.e., There exists a human computer.
If the domain of X is { everything on Earth }
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
Correct: Incorrect:
∃X : computer(X ) ∧ human(X ) ∃X : computer(X )⇒ human(X )
I “There exists something that is both
computer and human.”
I “There exists a human computer.”
I “Some computer is human.”
I “There exists something which is not
a computer or is human.”
I “There exists something which is not
both a computer and non-human.”
I “Not everything is a nonhuman
computer.”
11 / 20
Universal quantifier
Everyone can pass this subject. For every X : X can pass this subject.
∀X : canPass(X ).
All numbers are interesting. ∀X : X is interesting. ∀X : isInteresting(X ).
I True — and we’ll prove it!
For all W : W is negative ∀W : W < 0. False.
Again, the variables are now bound.
12 / 20
Universal quantifier
Every computer is human.
If the domain of X is { computers }
Predicate:
I human(X ): X is human.
∀X : human(X )
But what if the domain of X is { everything on Earth } ?
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
13 / 20
Universal quantifier
Every computer is human.
If the domain of X is { computers }
Predicate:
I human(X ): X is human.
∀X : human(X )
But what if the domain of X is { everything on Earth } ?
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
13 / 20
Universal quantifier
Every computer is human.
If the domain of X is { everything on Earth }
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
Incorrect: Correct:
∀X : computer(X ) ∧ human(X ) ∀X : computer(X )⇒ human(X )
I “Everything is both computer and
human.”
I “Everything is a human computer.”
I “For everything, if it’s a computer,
then it’s human.”
I “Everything that’s a computer is also
human.”
I “Every computer is human.”
14 / 20
Universal quantifier
Every computer is human.
If the domain of X is { everything on Earth }
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
Incorrect: Correct:
∀X : computer(X ) ∧ human(X ) ∀X : computer(X )⇒ human(X )
I “Everything is both computer and
human.”
I “Everything is a human computer.”
I “For everything, if it’s a computer,
then it’s human.”
I “Everything that’s a computer is also
human.”
I “Every computer is human.”
14 / 20
Universal quantifier
Every computer is human.
If the domain of X is { everything on Earth }
Predicates:
I human(X ): X is human.
I computer(X ): X is a computer.
Incorrect: Correct:
∀X : computer(X ) ∧ human(X ) ∀X : computer(X )⇒ human(X )
I “Everything is both computer and
human.”
I “Everything is a human computer.”
I “For everything, if it’s a computer,
then it’s human.”
I “Everything that’s a computer is also
human.”
I “Every computer is human.”
14 / 20
Multiple quantifiers
Thinking of graphs . . .
Suppose we have a predicate adj(X ,Y ) meaning that vertices X and Y are adjacent.
Some two vertices are not adjacent. ∃X ∃Y :
¬(X = Y ) ∧
¬adj(X ,Y ).
∃(X ,Y ) : ¬(X = Y ) ∧ ¬adj(X ,Y ).
Every pair of vertices is adjacent. ∀X ∀Y :
¬(X = Y ) ⇒
adj(X ,Y ).
∀(X ,Y ) : ¬(X = Y ) ⇒ adj(X ,Y ).
Some vertex is adjacent to all other vertices. ∃X ∀Y :
¬(X = Y ) ⇒
adj(X ,Y ).
Every vertex has a neighbour. ∀X ∃Y : adj(X ,Y ).
15 / 20
Multiple quantifiers
Thinking of graphs . . .
Suppose we have a predicate adj(X ,Y ) meaning that vertices X and Y are adjacent.
Some two vertices are not adjacent. ∃X ∃Y : ¬(X = Y ) ∧ ¬adj(X ,Y ).
∃(X ,Y ) : ¬(X = Y ) ∧ ¬adj(X ,Y ).
Every pair of vertices is adjacent. ∀X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ).
∀(X ,Y ) : ¬(X = Y ) ⇒ adj(X ,Y ).
Some vertex is adjacent to all other vertices. ∃X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ).
Every vertex has a neighbour. ∀X ∃Y : adj(X ,Y ).
15 / 20
Multiple quantifiers
Thinking of graphs . . .
Suppose we have a predicate adj(X ,Y ) meaning that vertices X and Y are adjacent.
Some two vertices are not adjacent. ∃X ∃Y : ¬(X = Y ) ∧ ¬adj(X ,Y ).
∃(X ,Y ) : ¬(X = Y ) ∧ ¬adj(X ,Y ).
Every pair of vertices is adjacent. ∀X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ).
∀(X ,Y ) : ¬(X = Y ) ⇒ adj(X ,Y ).
Some vertex is adjacent to all other vertices. ∃X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ).
Every vertex has a neighbour. ∀X ∃Y : adj(X ,Y ).
15 / 20
Multiple quantifiers
Six degrees of separation
Suppose we have a predicate knows(X ,Y ) meaning that person X knows person Y .
It has been claimed that, in the human social network,
the maximum distance between any two people is at most 6.
Exercise: write this claim in predicate logic, using just the predicate knows.
16 / 20
Doing logic with quantifiers
If we know that
∀X blah(X )
and obj is any specific object (in the domain of X ),
then we can deduce that
blah(obj)
We have:
(∀X blah(X )) ⇒ blah(obj)
Also:
blah(obj) ⇒ (∃X blah(X ))
17 / 20
Doing logic with quantifiers
If we know that
∀X blah(X )
and obj is any specific object (in the domain of X ),
then we can deduce that
blah(obj)
We have:
(∀X blah(X )) ⇒ blah(obj)
Also:
blah(obj) ⇒ (∃X blah(X ))
17 / 20
Doing logic with quantifiers
∀X (p(X ) ∧ q(X )) is logically equivalent to (∀X p(X )) ∧ (∀X q(X ))
∃X (p(X ) ∨ q(X )) is logically equivalent to (∃X p(X )) ∨ (∃X q(X ))
What about the logical relationship between . . .
∀X (p(X ) ∨ q(X )) and (∀X p(X )) ∨ (∀X q(X )) . . . ?
. . . etc
18 / 20
Doing logic with quantifiers
∀X (p(X ) ∧ q(X )) is logically equivalent to (∀X p(X )) ∧ (∀X q(X ))
∃X (p(X ) ∨ q(X )) is logically equivalent to (∃X p(X )) ∨ (∃X q(X ))
What about the logical relationship between . . .
∀X (p(X ) ∨ q(X )) and (∀X p(X )) ∨ (∀X q(X )) . . . ?
. . . etc
18 / 20
Relationship between quantifiers
¬ ∀Y means the same as ∃Y ¬
“Not all dogs are happy.” is the same as . . . “There exists an unhappy dog.”
¬∀X (dog(X ) ⇒ happy(X )) Not all dogs are happy
= ∃X ¬(dog(X ) ⇒ happy(X ))
= ∃X ¬(¬dog(X ) ∨ happy(X )) (see last lecture)
= ∃X (¬¬dog(X ) ∧ ¬happy(X )) (by De Morgan)
= ∃X (dog(X ) ∧ ¬happy(X )) There exists an unhappy dog
19 / 20
Relationship between quantifiers
Similarly,
¬ ∃Y means the same as ∀Y ¬
¬ ∀Y ¬ means the same as
¬ ∃Y ¬ means the same as
20 / 20