KS091201

MATEMATIKA DISKRIT
(DISCRETE
MATHEMATICS )

PREDICATE
&
QUANTIFIER
Discrete Math Team
 2 -- KS091201 MD W-03

Outline
 Propositional function
 Function with multiple variables
 Quantifier
 Universal quantifier
 Existensial quantifier
 Binding variable
 Negating quantifier
 Translating from English
 Multiple quantifiers
 Order of quantifiers
 Negating multiple quantifiers
 3 -- KS091201 MD W-03

Propositional Functions
 Consider P(x), as a symbolic notation of x > 5
 P(x): propositional function P at x (fungsi
proposisi P untuk x)
 x is subject
 > 5 is predicate
 P(x) has no truth value when x is unknown
 P(x) become a proposition when we assigned
certain value to x
 The value given to x is taken from certain
universe of discourse or domain (himpunan
semesta)
 4 -- KS091201 MD W-03

Propositional Functions (cont.)

 Example:

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

 Let P(x) = x + 3 > x

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

 5 -- KS091201 MD W-03

Function 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 -- KS091201 MD W-03

Quantifier
 A quantifier is “an operator that limits the variables
of a proposition”

 In some cases, it’s a more accurate way to

describe things than Boolean propositions

 Process of bounding the variable x with a

quantifier is called quantification

 Two types of quantifier will be discussed:

 Universal quantifier

 Existential quantifier
 7 -- KS091201 MD W-03

Universal Quantifier
 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”
 8 -- KS091201 MD W-03

Universal Quantifier (cont.)

 But is that always true?
 x P(x)
 Let x = the character ‘a’
 Is ‘a’+1 > ‘a’?
 Let x = the state of East Java
 Is East Java+1 > East Java?

 Don’t forget to specify your universe!

 What values x can represent
 Called the “domain” or “universe of discourse”
 9 -- KS091201 MD W-03

Universal Quantifier (cont.)

 Let the universe be the real numbers.

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

 Not true for the negative numbers! (Called as
counterexample)
 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, it must be shown to be false for only
ONE case
 10 -- KS091201 MD W-03

Universal Quantifier (cont.)

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

 11 -- KS091201 MD W-03

Existensial Quantifier
 Represented by an backwards E: 
 It means “there exists”
 Let P(x) = x2 > 10

 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,
x2 > 10 is true”
 Note that you still have to specify your
universe
 12 -- KS091201 MD W-03

Existensial Quantifier (cont.)

 Let P(x) = x+1= x
 There is no numerical value x for which x+1= x
 Thus, x P(x) is false
 Let P(x) = x+1 = 0
 There is a numerical value for which x+1= 0
 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
 13 -- KS091201 MD W-03

Existensial Quantifier (cont.)

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

 14 -- KS091201 MD W-03

Conclusion
Statement When True When False
x P(x) P(x) is TRUE for every x There is an x for which
P(x) is FALSE
 x P(x) There is an x for which P(x) is FALSE for every x
P(x) is TRUE
 15 -- KS091201 MD W-03

Notes
 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:
 Assign a certain value
 For example, P(-1) is false, P(1) is true
 Provide a quantification
 For example, x P(x) is false and x P(x) is true
 Let the universe of discourse be the real numbers
 16 -- KS091201 MD W-03

Binding Variable
 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

 17 -- KS091201 MD W-03

Binding Variable (cont.)

 (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
 18 -- KS091201 MD W-03

Negating Quantifiers
 Consider the statement:
 All students in this class have Acer Laptop

 What is required to show the statement is false?

 There exists a student in this class that does NOT has
Acer Laptop

 To negate a universal quantification:

 You negate the propositional function
 AND you change to an existential quantification
 ¬x P(x) = x ¬P(x)
 19 -- KS091201 MD W-03

Negating Quantifiers (cont.)

 Consider the statement:
 There is a student in this class with Acer Laptop.
 What is required to show the statement is
false?
 All students in this class do not have Acer
Laptop.
 Thus, to negate an existential quantification:
 negate the propositional function
 AND change to a universal quantification
 ¬x P(x) = x ¬P(x)
 20 -- KS091201 MD W-03

Conclusion

Proposition Negation TRUE FALSE

x P(x) x P(x) For all x, P(x) is There is a value

false of x for which
P(x) is true

x P(x) x P(x) There is a value For all x, P(x) is

of x for which true
P(x) is false
 21 -- KS091201 MD W-03

Translating from English

 Whatabout if the universe of discourse is all
people?
 S(x) be “x is a student in this class”
 C(x) be “x has studied Calculus”

 Every student in this class has studied Calculus.

 x (S(x)C(x))
 Thisis wrong! Why?
 It means that “All people are students in this class
and have studied Calculus”
 x (S(x)→C(x))
 Itmeans that “For every person x, if x is student in
this class, then x has studied Calculus”
 22 -- KS091201 MD W-03

Translating from English

 Consider:
 “Every student in this class has visited Manado
or Cianjur”

 Let:
 S(x) be “x is a student in this class”
 M(x) be “x has visited Manado”
 C(x) be “x has visited Cianjur”
 23 -- KS091201 MD W-03

Translating from English

 Consider: “Some students have visited Manado”
 Rephrasing: “There exists a student who has visited
Manado”

 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?
 The statement is true although there is someone not in the
class
 x (S(x)  M(x))
 There is a person x who is a student in this class and who has
visited Manado
 24 -- KS091201 MD W-03

Translating from English

 Consider: “Every student in this class has
visited Cianjur or Manado”

 x (M(x)C(x))
 When the universe of discourse is all students in
this class

 x (S(x)→(M(x)C(x))
 When the universe of discourse is all people
 25 -- KS091201 MD W-03

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)
 26 -- KS091201 MD W-03

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
 27 -- KS091201 MD W-03

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z P(x,y,z)) = xyz ¬P(x,y,z)
 28 -- KS091201 MD W-03

Negating multiple quantifiers (cont.)

 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”
 29 -- KS091201 MD W-03

Translating Quantifiers
 Let N(x) be the statement "x has visited North Dakota",
where he domain consist of the students in your school.
Express each of these quantifications in English.
a) x N(x)
Some students in the school have visited North Dakota.
There exists a student in the school who has visited N.D.
b) x N(x)
Every student in the school has visited North Dakota.
All students in the school have visited North Dakota.
c) ¬ x N(x) : negation of part a)
No student in the school has visited North Dakota.
There does not exist a student in the school who has visited
N.D.
 30 -- KS091201 MD W-03

Translating Quantifiers
 Let N(x) be the statement "x has visited North Dakota", where he
domain consist of the students in your school. Express each of
these quantifications in English.
d) x ¬ N(x)
Some students in the school have not visited North Dakota.
There exists a student in the school who has not visited N.D.
e) ¬ x N(x) : negation of part b)
It is not true that every student in the school has visited N.D.
Not all students in the school have visited N.D.
f) x ¬ N(x)
All students in the school have not visited North Dakota.
(common English sentence takes this sentence, incorrectly, the
answer of part e)

Note: c) and f) are equivalent; d) and e) are also equivalent.

But both pairs are not equivalent to each other.
 31 -- KS091201 MD W-03

Translating Quantifiers
Note: The domain is all integers
 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|)
 32 -- KS091201 MD W-03

Translating Quantifiers
Note:The domain is all real numbers
 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