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
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

3
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?

4
ANATOMY OF A PROPOSITIONAL
FUNCTION

P(x) = x + 5 > x

variable predicate

5
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) = …

6
SO, WHY DO WE CARE ABOUT
QUANTIFIERS?
 Many things (in this course and beyond) are
specified using quantifiers
 In some cases, it’s a more accurate way to describe
things than Boolean propositions

7
QUANTIFIERS
 A quantifier is “an operator that limits the
variables of a proposition”

 Two types:
 Universal
 Existential

8
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”

9
UNIVERSAL QUANTIFIERS 2
 But is that always true?
 x P(x)
 Let x = the character ‘a’
 Is ‘a’+1 > ‘a’?
 Let x = the state of Virginia
 Is Virginia+1 > Virginia?
 You need to specify your universe!
 What values x can represent
 Called the “domain” or “universe of discourse” by the
textbook

10
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 11
quantification is false, it must be shown to be
false for only ONE case
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)

12
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 13
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”

14
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

15
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
16
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)

17
A NOTE ON QUANTIFIERS
 Recall that P(x) is a propositional function
 Let P(x) be “x == 0”
 Recallthat 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
18
BINDING VARIABLES
 Let P(x,y) be x > y
 Consider: x P(x,y)
 This is not a proposition!
 What is y?
 If it’s 5, then x P(x,y) is false
 If it’s x-1, then x P(x,y) is true

 Note that y is not “bound” by a quantifier

19
BINDING VARIABLES 2
 (x P(x))  Q(x)
 The x in Q(x) is not bound; thus not a
proposition
 (x P(x))  (x Q(x))
 Both x values are bound; thus it is a
proposition
 (x P(x)  Q(x))  (y R(y))
 All variables are bound; thus it is a proposition
 (x P(x)  Q(y))  (y R(y))
 The y in Q(y) is not bound; this not a
proposition 20
NEGATING QUANTIFICATIONS
 Consider the statement:
 All students in this class have red hair
 What is required to show the statement is
false?
 There exists a student in this class that does
NOT have red hair
 To negate a universal quantification:
 You negate the propositional function
 AND you change to an existential
quantification
 ¬x P(x) = x ¬P(x) 21
NEGATING QUANTIFICATIONS 2
 Consider the statement:
 There is a student in this class with red hair
 What is required to show the statement is false?
 All students in this class do not have red hair
 Thus, to negate an existential quantification:
 Tou negate the propositional function
 AND you change to a universal quantification
 ¬x P(x) = x ¬P(x)

22
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

23
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))

24
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”

25
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?
26
 x (S(x)  M(x))
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?

27
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))

28
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 29
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))
30
 “Hummingbirds are small”
 x (P(x) → ¬Q(x))
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) 31
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

32
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) 33
= xyz ¬P(x,y,z)
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” 34
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))
 Thedifference 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 35
 xy (|x+y| ≤ |x| + |y|)
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 if36
and only if both factors are non-zero
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))
37
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) 38
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”

39
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”

40
EXAMPLE OF PROOF

 Given the hypotheses:

 “Linda, a student in this class, owns
a red convertible.” C(Linda)
R(Linda)
 “Everybody who owns a red
convertible has gotten at least one
speeding ticket” x (R(x)→T(x))
 Can you conclude: “Somebody in x (C(x)T(x))
this class has gotten a speeding
ticket”?
41
EXAMPLE OF PROOF
1. x (R(x)→T(x)) 3rd hypothesis
2. R(Linda) → T(Linda) Universal instantiation using step
1
3. R(Linda) 2nd hypothesis
4. T(Linda) Modes ponens using steps 2
&3
5. C(Linda) 1st hypothesis
6. C(Linda)  T(Linda) Conjunction using steps 4 & 5
7. x (C(x)T(x)) Existential generalization using
Thus, we have shown that “Somebody in
step 6
this class has gotten a speeding ticket” 42
EXAMPLE OF PROOF

 Given the hypotheses:

 “There is someone in this class who has
been to France” x (C(x)F(x))
 “Everyone who goes to France visits the
Louvre”
 Can you conclude: “Someone in this x (F(x)→L(x))
class has visited the Louvre”?

x (C(x)L(x))
43
 EXAMPLE OF PROOF
1. x (C(x)F(x)) 1st hypothesis
2. C(y)  F(y) Existential instantiation using step 1
3. F(y) Simplification using step 2
4. C(y) Simplification using step 2
5. x (F(x)→L(x)) 2nd hypothesis
6. F(y) → L(y) Universal instantiation using step 5
7. L(y) Modus ponens using steps 3 & 6
8. C(y)  L(y) Conjunction using steps 4 & 7
9. x (C(x)L(x)) Existential generalization using
step 8
44
Thus, we have shown that “Someone
in this class has visited the Louvre”