Predicates and Quantifiers

1
 Terminology review
• Proposition: a statement that is either true
or false
– Must always be one or the other!
– Example: “The sky is red”
– Not a proposition: x + 3 > 4

• Boolean variable: A variable (usually p, q,

r, etc.) that represents a proposition
2
3
 Predicates
• “x is greater than 3” has two parts.
– The first part,
• the variable x, is the subject of the statement.
– The second part—the predicate,
• “is greater than 3”—refers to a property that the
subject of the statement can have.
• denote the statement “x is greater than 3” by P(x),
– where P denotes the predicate “is greater than 3” and x
is the variable.

4
 Predicates
• P(x) -- the value of the propositional function P at x.

• Once a value assigned to the variable x,

– the statement P(x) becomes a proposition and has a truth value

5
 Propositional functions
• Consider P(x) = x < 5
– P(x) has no truth values (x is not given a
value)
– P(1) is true
• The proposition 1<5 is true
– P(10) is false
• The proposition 10<5 is false
• Thus, P(x) will create a proposition when
given a value
6
 Propositional functions 2
• Let P(x) = “x is a multiple of 5”
– For what values of x is P(x) true?

• Let P(x) = x+1 > x

– For what values of x is P(x) true?

• Let P(x) = x + 3
– For what values of x is P(x) true?
7
Anatomy of a propositional function

P(x) = x + 5 > x

variable predicate

8
 Propositional functions 3
• Functions with multiple variables:

– P(x,y) = x + y == 0
• P(1,2) is false, P(1,-1) is true

– P(x,y,z) = x + y == z
• P(3,4,5) is false, P(1,2,3) is true

– P(x1,x2,x3 … xn) = …
• value of the propositional function P at the
n-tuple (x1, x2, . . . , xn)
9
• P is also called an n-place predicate or a n-ary predicate.
10
11
12
13
14
15
16
 Predicate Logic
• 1. Ram is tall
– Tall(Ram)
• 2. Ram loves Sita
– Love(Ram, Sita)
3. Ram teaches either math or cs
– Teach(Ram, math) V Teach(Ram,cs)
– 4. Ram teaches math if and only if Ram
does not teach cs
– Teach(Ram, math) ↔ ~Teach(Ram,cs)
17
18
19
20
21
22
23
24
 Quantifiers
• A quantifier is “an operator that limits the
variables of a proposition”

• Two types:
– Universal
– Existential

25
 Universal quantifiers 1
• Represented by an upside-down A: 
– It means “for all”
– Let P(x) = x+1 > x

• We can state the following:

 x P(x)
• English translation: “for all values of x, P(x) is true”
• English translation: “for all values of x, x+1>x is
true”

26
Universal quantifiers

27
 Universal quantifiers 3
• Let the universe be the real numbers.
– Then, x P(x) is true

• Let P(x) = x/2 < x

– Not true for the negative numbers!
– Thus, x P(x) is false
• When the domain is all the real numbers

• In order to prove that a universal quantification is

true,
– it must be shown for ALL cases
• In order to prove that a universal quantification is
false, 28
 Universal quantification 4
• Given some propositional function P(x)

• And values in the universe x1 .. xn

• The universal quantification x P(x)

implies:

P(x1)  P(x2)  …  P(xn)

29
 Universal quantification 5
• Think of  as a for loop:

 x P(x), where 1 ≤ x ≤ 10

• … can be translated as …

for ( x = 1; x <= 10; x++ )

is P(x) true?

• If P(x) is true for all parts of the for loop, then x P(x)
– Consequently, if P(x) is false for any one value of the for loop,
then x P(x) is false
30
 Existential quantification 1
• Represented by an bacwards E: 
– It means “there exists”
– Let P(x) = x+1 > x

• We can state the following:

 x P(x)
– English translation: “there exists (a value of) x
such that P(x) is true”
– English translation: “for at least one value of x,
x+1>x is true”
31
 Existential quantification 2
• Note that you still have to specify your
universe
– If the universe we are talking about is all the
states in the US, then x P(x) is not true

• Let P(x) = x+1 < x

– There is no numerical value x for which x+1<x
– Thus, x P(x) is false

32
 Existential quantification 3
• Let P(x) = x+1 > x
– There is a numerical value for which x+1>x
• In fact, it’s true for all of the values of x!
– Thus, x P(x) is true

• In order to show an existential

quantification is true,
– you only have to find ONE value
• In order to show an existential
quantification is false,
– you have to show it’s false for ALL values

33
 Existential quantification 4
• Given some propositional function P(x)

• And values in the universe x1 .. xn

• The existential quantification x P(x)

implies:

P(x1)  P(x2)  …  P(xn)

34
 A note on quantifiers
• Recall that P(x) is a propositional function
– Let P(x) be “x == 0”
• Recall that a proposition is a statement that is
either true or false
– P(x) is not a proposition
• There are two ways to make a propositional
function into a proposition:
– Supply it with a value
• For example, P(5) is false, P(0) is true
– Provide a quantifiaction
• For example, x P(x) is false and x P(x) is true
– Let the universe of discourse be the real numbers
35
 x

Note: ∀x…………..→
∃x…………. ^ 36
Universe of Discourse (domain)
• The domain of a predicate variable is the
– collection of all possible values that the
variable may take.

37
Universe of Discourse (domain)
• The domain of a predicate variable is the
– collection of all possible values that the
variable may take.

38
Universal conditional statement:
• This statement has the form:
– ∀x, if P(x) then Q(x).

39
 Example
• All students like football
 x (student(x) → like(x, football))
• Some students like football
– ∃x (student(x) ^ like(x, football))
• All students are happy
 x (student(x) → happy(x))
• Some students are happy
– ∃x (student(x) ^ happy(x))
• S(x): x is a student
• H(x): x is happy
40
41
42
 Question 10
• Let C(x) be the statement “x has a cat,” let D(x) be the statement “x
has a dog,” and let F (x) be the statement “x has a ferret.” Express
each of these statements in terms of C(x), D(x), F (x), quantifiers,
and logical connectives. Let the domain consist of all students in
your class.
a) A student in your class has a cat, a dog, and a ferret.
∃x(C(x) ∧ D(x) ∧ F (x)).
b) All students in your class have a cat, a dog, or a ferret.
∀x(C(x) ∨ D(x) ∨ F (x))
c) Some student in your class has a cat and a ferret, but not a dog. d) No
student in your class has a cat, a dog, and a ferret.
∃x(C(x) ∧ F (x) ∧ ¬D(x))
d) No student in your class has a cat, a dog, and a ferret.
¬∃x(C(x) ∧ D(x) ∧ F (x))
e) For each of the three animals, cats, dogs, and ferrets, there is a student
in your class who has this animal as a pet.
(∃x C(x))∧(∃x D(x))∧(∃x F (x)) 43
 Question 11
• Let P (x) be the statement “x = x2.” If the
domain consists of the integers, what are
these truth values?
• a) P (0)
• b) P (1)
• c) P (2)
• d) P (−1)
• e) ∃xP (x)
• f ) ∀xP (x)
44
 Question 11
• Let P (x) be the statement “x = x2.” If the domain consists of the
integers, what are these truth values?

45
 Question 12
• Let Q(x) be the statement “x + 1 > 2x.” If the
domain consists of all integers, what are these
truth values?
– a) Q(0)
– b) Q(−1)
– c) Q(1)
– d) ∃xQ(x)
– e) ∀xQ(x)
– f ) ∃x¬Q(x)
– g) ∀x¬Q(x)

46
 Question 12
Let Q(x) be the statement “x + 1 > 2x.” If the domain consists
of all integers, what are these truth values?
– a) Q(0) • C) Q(1)

– b) Q(−1)
• d) ∃xQ(x)

47
 Question 12
Let Q(x) be the statement “x + 1 > 2x.” If the domain consists
of all integers, what are these truth values?
– e) ∀xQ(x) – g) ∀x¬Q(x)

– f ) ∃x¬Q(x)

48
 Question 5
Let P (x) be the statement “x spends more than five
hours every weekday in class,” where the domain for x
consists of all students. Express each of these
quantifications in English.
– a) ∃xP(x)
There exists a student who spends more than five hours every weekday in class.
– b) ∀xP (x)
Every student spends more than five hours every weekday in class.
– c) ∃x ¬P (x)
There exists a student who does not spend more than five hours every weekday in
class.
– d) ∀x ¬P (x)
Every student does not spend more than five hours every weekday in class.

49
Translation into Logical Expression

50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 Negating quantifications
• Consider the statement:
– All students in this class have red hair
 x P(x)
• What is required to show the statement is false?
– There exists a student in this class that does NOT have red
hair
• (x ¬P(x) )
• To negate a universal quantification:
– You negate the propositional function
– AND you change to an existential quantification
 ¬(x P(x)) = x ¬P(x)

68
69
 Negating quantifications 2
• Consider the statement:
– There is a student in this class with red hair
 x P(x)
• What is required to show the statement is false?
– All students in this class do not have red hair
 x ¬P(x)
• Thus, to negate an existential quantification:
– To negate the propositional function
– AND you change to a universal quantification
 ¬(x P(x)) = x ¬P(x)

70
71
72
73
74
75
Negating quantifications

76
77
78
 Translating from English
• Consider “For every student in this class,
that student has studied calculus”
• Rephrased: “For every student x in this
class, x has studied calculus”
– Let C(x) be “x has studied calculus”
– Let S(x) be “x is a student”
 x C(x)
– True if the universe of discourse is all
students in this class
79
 Translating from English 2
• What about if the unvierse of discourse is
all students (or all people?)
 x (S(x)C(x))
• This is wrong! Why?
 x (S(x)→C(x))
• Another option:
– Let Q(x,y) be “x has stuided y”
 x (S(x)→Q(x, calculus))

80
 Translating from English 3
• Consider:
– “Some students have visited Mexico”
– “Every student in this class has visited
Canada or Mexico”
• Let:
– S(x) be “x is a student in this class”
– M(x) be “x has visited Mexico”
– C(x) be “x has visited Canada”

81
 Translating from English 4
• Consider: “Some students have visited Mexico”
– Rephrasing: “There exists a student who has visited
Mexico”
 x M(x)
– True if the universe of discourse is all students
• What about if the universe of discourse is all
people?
 x (S(x) → M(x))
• This is wrong! Why?
 x (S(x)  M(x))
82
 Translating from English 5
• Consider: “Every student in this class has
visited Canada or Mexico”
 x (M(x)C(x)
– When the universe of discourse is all students
 x (S(x)→(M(x)C(x))
– When the universe of discourse is all people
• Why isn’t x (S(x)(M(x)C(x))) correct?

83
 Translating from English 6
• Note that it would be easier to define
V(x, y) as “x has visited y”
 x (S(x)  V(x,Mexico))
 x (S(x)→(V(x,Mexico)  V(x,Canada))

84
 Translating from English 7
• Translate the statements:
– “All hummingbirds are richly colored”
– “No large birds live on honey”
– “Birds that do not live on honey are dull in color”
– “Hummingbirds are small”
• Assign our propositional functions
– Let P(x) be “x is a hummingbird”
– Let Q(x) be “x is large”
– Let R(x) be “x lives on honey”
– Let S(x) be “x is richly colored”
• Let our universe of discourse be all birds
85
 Translating from English 8
• Our propositional functions
– Let P(x) be “x is a hummingbird”
– Let Q(x) be “x is large”
– Let R(x) be “x lives on honey”
– Let S(x) be “x is richly colored”
• Translate the statements:
– “All hummingbirds are richly colored”
 x (P(x)→S(x))
– “No large birds live on honey”
• ¬x (Q(x)  R(x))
• Alternatively: x (¬Q(x)  ¬R(x))
– “Birds that do not live on honey are dull in color”
 x (¬R(x) → ¬S(x))
– “Hummingbirds are small”
 x (P(x) → ¬Q(x)) 86
 Multiple quantifiers
• You can have multiple quantifiers on a statement

 xy P(x, y)
– “For all x, there exists a y such that P(x,y)”
– Example: xy (x+y == 0)

 xy P(x,y)
– There exists an x such that for all y P(x,y) is true”
– Example: xy (x*y == 0)

87
 Order of quantifiers
 xy and xy are not equivalent!

 xy P(x,y)
– P(x,y) = (x+y == 0) is false

 xy P(x,y)
– P(x,y) = (x+y == 0) is true

88
 Negating multiple quantifiers
• Recall negation rules for single quantifiers:
– ¬x P(x) = x ¬P(x)
– ¬x P(x) = x ¬P(x)
– Essentially, you change the quantifier(s), and negate
what it’s quantifying

• Examples:
– ¬(xy P(x,y))
= x ¬y P(x,y)
= xy ¬P(x,y)
– ¬(xyz P(x,y,z))
= x¬yz P(x,y,z)
= xy¬z P(x,y,z)
= xyz ¬P(x,y,z) 89
 Negating multiple quantifiers 2
• Consider ¬(xy P(x,y)) = xy ¬P(x,y)
– The left side is saying “for all x, there exists a y such
that P is true”
– To disprove it (negate it), you need to show that
“there exists an x such that for all y, P is false”

• Consider ¬(xy P(x,y)) = xy ¬P(x,y)

– The left side is saying “there exists an x such that for
all y, P is true”
– To disprove it (negate it), you need to show that “for
all x, there exists a y such that P is false”
91
 Translating between English and
quantifiers
• The product of two negative integers is positive
 xy ((x<0)  (y<0) → (xy > 0))
– Why conditional instead of and?
• The average of two positive integers is positive
 xy ((x>0)  (y>0) → ((x+y)/2 > 0))
• The difference of two negative integers is not
necessarily negative
 xy ((x<0)  (y<0)  (x-y≥0))
– Why and instead of conditional?
• The absolute value of the sum of two integers
does not exceed the sum of the absolute values
of these integers
 xy (|x+y| ≤ |x| + |y|) 92
 Translating between English and
quantifiers
 xy (x+y = y)
– There exists an additive identity for all real numbers
 xy (((x≥0)  (y<0)) → (x-y > 0))
– A non-negative number minus a negative number is
greater than zero
 xy (((x≤0)  (y≤0))  (x-y > 0))
– The difference between two non-positive numbers is
not necessarily non-positive (i.e. can be positive)
 xy (((x≠0)  (y≠0)) ↔ (xy ≠ 0))
– The product of two non-zero numbers is non-zero if
and only if both factors are non-zero 93
 Negation examples
• Rewrite these statements so that the negations
only appear within the predicates
a) yx P(x,y)
yx P(x,y)
yx P(x,y)
b) xy P(x,y)
xy P(x,y)
xy P(x,y)
c) y (Q(y)  x R(x,y))
y (Q(y)  x R(x,y))
y (Q(y)  (x R(x,y)))
y (Q(y)  x R(x,y))
94
 Negation examples
• Express the negations of each of these statements so
that all negation symbols immediately precede
predicates.
a) xyz T(x,y,z)
(xyz T(x,y,z))
xyz T(x,y,z)
xyz T(x,y,z)
xyz T(x,y,z)
xyz T(x,y,z)
b) xy P(x,y)  xy Q(x,y)
(xy P(x,y)  xy Q(x,y))
xy P(x,y)  xy Q(x,y)
xy P(x,y)  xy Q(x,y)
xy P(x,y)  xy Q(x,y)
95
 Rules of inference for the
universal quantifier
• Assume that we know that x P(x) is true
– Then we can conclude that P(c) is true
• Here c stands for some specific constant
– This is called “universal instantiation”

• Assume that we know that P(c) is true for

any value of c
– Then we can conclude that x P(x) is true
– This is called “universal generalization”
96
 Rules of inference for the
existential quantifier
• Assume that we know that x P(x) is true
– Then we can conclude that P(c) is true for
some value of c
– This is called “existential instantiation”

• Assume that we know that P(c) is true for

some value of c
– Then we can conclude that x P(x) is true
– This is called “existential generalization”
97