From propositional to predicate logic
Let’s consider the statement
“x is an odd number”
Its truth value depends on the the value of the variable x.
Once we assign x a value, it becomes a proposition.
Predicate logic will allow us to reason about statements with
variables without having to assign values to them.
Predicates
Predicate: A logical statement whose truth value is a function
of one or more variables.
Examples:
x is an odd number
Computer x is under attack
The distance between cities x and y is less than z
When the variables are assigned a value, the predicate becomes
a proposition and can be assigned a truth value.
Predicates
The truth value of a predicate can be expressed as a function
of the variables, for example:
“x is an odd number”
can be expressed as P(x).
So, the statement P(5) is the same as "5 is an odd number”.
“The distance between cities x and y is less than z miles”
Represented by a predicate function D(x, y, z)
D(fort-collins, denver, 100) is true.
The domain of a predicate
The domain of a variable in a predicate is the set of all possible
values for the variable.
Examples:
The domain of the predicate "x is an odd number" is the set of
all integers.
In general, the domain of a predicate should be defined with
the predicate.
Predicates
Let R(x, y) denote: x beats y in rock-paper-scissors with
the standard rules.
What are the truth values of:
R(Rock, Paper)
R(Scissors, Paper)
image from http://en.wikipedia.org/wiki/Rock-paper-scissors
Uses of predicate logic
Verifying program correctness
Consider the following snippet of code:
if (x < 0)
x = -x;
What is true before? (called precondition)
– x has some value
What is true after? (called postcondition)
– greaterEqual(x, 0)
Quantifiers
Assigning values to variables is one way to provide them with a
truth value.
Alternative: Say that a predicate is satisfied for every value
(universal quantification), or that it holds for some value
(existential quantification)
Example:
Let P(x) be the statement x + 1 > x.
This holds regardless of the value of x
We express this as: x P(x)
Universal quantification
Universal quantification is the statement
“P(x) for all values of x in the domain of P”
Notation: x P(x)
is called the universal quantifier
If the domain of P contains a finite number of elements
a1, a2,..., ak:
x P(x) ≡ P(a1) P(a2) ,..., P(ak)
Universal quantification
Universal quantification is the statement
“P(x) for all values of x in the domain of P”
Notation: x P(x)
is called the universal quantifier
An element x for which P(x) is false is called a counterexample.
Example: Let P be the predicate “x2 > x” with the domain of real
numbers. Give a counterexample.
What does the existence of a counterexample tell us about the
truth value of x P(x) ?
Existential quantification
Existential quantification of P(x) is the statement
There exists an element x in the domain of P such that P(x)
Notation: x P(x)
is called the existential quantifier
Example:
M(x) - “x is a mammal” and
E(x) - “x lays eggs”
(both with the domain of “animals”).
What is the truth value of x (M(x) E(x))?
True (Platipus)
Existential quantification
Existential quantification of P(x) is the statement
There exists an element x in the domain of P such that P(x)
Notation: x P(x)
is called the existential quantifier
If the domain of P contains a finite number of elements
a1, a2,..., ak:
x P(x) ≡ P(a1) P(a2) ,..., P(ak)
Quantified statements
Consider the following predicates:
P(x): x is prime
O(x): x is odd
The proposition x (P(x) ¬O(x)) states that there exists a
positive number that is prime and not odd.
Is this true?
What about x (P(x) → O(x)) ?
Precedence of quantifiers
The quantifiers : and have higher precedence than the logical
operators from propositional logic.
Therefore:
x P(x) Q(x) means:
(x P(x)) Q(x) rather than:
x (P(x) Q(x))
Image from:
http://mrthinkyt.tumblr.com/
Binding variables
When a quantifier is used on a variable x, we say that this
occurrence of x is bound
All variables that occur in a predicate must be bound or assigned a
value to turn it into a proposition
Example: x D(x, Denver, 60)
Examples
In the statement x (x + y = 1) x is bound
In the statement x P(x) x R(x) all variables are bound
Can also be written as: x P(x) y R(y)
What about x P(x) Q(x) ?
Better to express this as x P(x) Q(y)
Negating quantified statements
Suppose we want to negate the statement:
“Every student in CS220 has taken Math160”
Translation into logic:
x P(x) where P is the predicate “x has taken Math160”, with the
domain of CS220 students.
The negation: “not every student in CS220 has taken Math160”, or
“there exists a student in CS220 who hasn’t taken Math160” i.e.:
x P(x)
Note
Alternative way of expressing the statement
“Every student in CS220 has taken Math160”
x (takes(x, CS220) hasTaken(x, math160))
or
x (takesCS220(x) hasTakenMath160(x))
De Morgan’s laws for quantifiers
We have illustrated the logical equivalence:
¬ x P(x) ≡ x ¬P(x)
A similar equivalence holds for the existential quantifier:
¬ x P(x) ≡ x ¬P(x).
Example: There does not exist someone who likes to go to
the dentist. Same as: everyone does not like to go to the
dentist
De Morgan’s laws for quantifiers
Example:
Each quantifier be expressed using the other
x Likes(x,IceCream) x Likes(x,IceCream)
x Likes(x,Broccoli) x Likes(x,Broccoli)
English to Logic
Express these statements in an alternative way:
No one in this class is wearing shorts and a ski parka.
Everyone in the class
either doesn’t wear a parka or doesn’t wear shorts
Some lions do not drink coffee
Not all lions drink coffee
Nested quantifiers
If a predicate has more than one variable, each variable must be
bound by a separate quantifier.
The logical expression is a proposition if all the variables are
bound.
Nested quantifiers of the same type
Example:
M(x, y): x sent an email to y, with the domain of people.
Consider the statement
x y M(x, y)
In English: Every person sent an email to everyone.
This is a statement on all pairs x,y:
For every pair of people, x,y it is true that x sent y a mail.
Nested quantifiers
Example:
M(x, y): x sent an email to y, with the domain of people.
Consider the statement
x y M(x, y)
In English: Every person sent an email to everyone – including
themselves.
But what if we would like to exclude the self emails?
x y ((x ≠ y) → M(x, y))
Nested quantifiers of the same type
Example:
M(x, y): x sent an email to y, with the domain of people.
Express the following in English:
x y M(x, y)
Order does not matter:
x y is the same as y x
x y is the same as y x
Alternating nested quantifiers
x y is not the same as y x:
x y Likes(x, y)
There is a person who likes everyone
y x Likes(x, y)
Everyone is liked by at least one person
Nested quantifiers as a two person game
Two players: the Universal player, and the Existential player.
Each selects values for their variables.
Example: x y (x + y = 0)
The Universal player selects a value.
Given the value chosen, the Existential player chooses its value,
making the statement true.
Expressing uniqueness
L(x): x was late
How do we express the statement that exactly one person was
late?
What’s wrong with x L(x) ?
Expressing uniqueness
L(x): x was late
How do we express the statement that exactly one person was
late?
What’s wrong with x L(x) ?
Instead:
x (L(x) y((x ≠ y) → ¬L(y) )
Moving quantifiers
L(x): x was late
How do we express the statement that exactly one person was
late?
x (L(x) y((x ≠ y) → ¬L(y))
Equivalent to:
x y (L(x) ((x ≠ y) → ¬L(y))
De Morgan’s laws with nested quantifiers
¬ x y P(x, y) ≡ x y ¬P(x, y)
¬ x y P(x, y) ≡ x y ¬P(x, y)
¬ x y P(x, y) ≡ x y ¬P(x, y)
¬ x y P(x, y) ≡ x y ¬P(x, y)
Example:
x y Likes(x, y ) : There is a person who likes everyone
Its negation:
¬ x y Likes(x, y ) : There is no person who likes everyone.
¬ x y Likes(x, y ) ≡ x y ¬Likes(x, y ) : Every person has
someone that they do not like.
