CSE181

Discrete Mathematics
Lecture: 4

Farhad Uz Zaman
 2

Lecture Outline

1.3 Predicates and Quantifiers

• Predicates
• Quantifiers
• Universal Quantifier, ∀
• Existential Quantifier, ∃
• Precedence of Quantifiers
• Negating Quantified Expressions
• Translating from English into Logical Expressions
 3

Objectives and Outcomes

• Objectives: To understand predicates , universal and

existential quantifiers, how to translate English
statements into logical expressions
• Outcomes: Students are expected to be able to explain
predicate logic, be able to find out the truth value of
universal and existential quantifications, be able to
translate English statements into logical expressions
using predicates, quantifiers and logical connectives.
 4

Predicates
• Predicate: Declarative sentence or statement with one or more
variables.
• Example: “ x > 3 ”
x: variable
>3: predicate
• We can 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.
• The statement P(x) is also said to be the value of the propositional
function P at x.
• P(x): x>3
• The value of the propositional function P at x
• Note: Once a value has been assigned to the variable x, the statement
P(x) becomes a proposition and has a truth value (either TRUE or FALSE)
 5

Predicates contd.
• A predicate is a sentence that contains a finite number of variables and
becomes a proposition when specific values are substituted for the
variables.
• A predicate, or propositional function, is a function that takes some
variable(s) as arguments and returns True or False.
• A PREDICATE is symbolized by a CAPITAL LETTER and the variable(s) by
small letter(s).
• The sentence “x is a bachelor” is symbolized as P(x),
where x is a variable. When concrete values are substituted in
place of x, a proposition results(with a truth value, either True or
False). P(x) is also called a propositional function , because each choice
of x produces a proposition P(x) that is either true or false.
 6

Example 1
• Let P(x) denote the statement “x>3”.
What are the truth values of P(4) and P(2)?

▪ Solution: Given ==> P(x) : “x>3”

• We obtain the statement P(4) by setting x = 4 in the
statement “x>3”. Hence P(4), which is the statement
“4>3”, is true.
• However, P(2) which is the statement “2>3”, is false.
 7

Example 2
• Let, A(x) : “Computer x is under attack by an intruder”. Suppose
that of the computers on campus, only C1 and C7 are currently
under attack by intruders. What are the truth values of A (C1),
A(C3), A(C7)?
▪ Solution:
• A(C1): “Computer C1 is under attack by an intruder” is true
• A(C7): “Computer C7 is under attack by an intruder” is true
• A(C3): “Computer C3 is under attack by an intruder” is false
Why ? Because C3 is not in the list of computers that are attacked by intruders.
 8

Example 3
• Let, P(x) : “ x is the capital of Bangladesh”.
What are the truth values of P(Dhaka) and P(Chennai) ?
▪ Solution:
• P(Dhaka): “Dhaka is the capital of Bangladesh” is true
• P(Dhaka): “Chennai is the capital of Bangladesh” is false
 9

Multivariable Predicates
• Multivariable Predicates ==> Predicates that have
more than one variable.
• For example, Q(x, y): “x = y + 3” ,
where x and y are variables and Q is the predicate.

▪ Note: When values are assigned to the variables x and

y, the statement Q(x, y) has a truth value.
 10

Example 3
Let Q(x, y) denote the statement “x = y + 3”.
What are the truth values of the propositions Q(1,2)
and Q(3,0)?
▪ Solution:
• To obtain Q(1,2), set x=1 and y=2 in the statement
Q(x,y).
Therefore, Q(1,2): “1 = 2 + 3” is false
Similarly, Q(3,0): “3 = 0 + 3” is true
 11

Quantifiers
• Quantification: Two Categories –
• Universal quantification: A predicate is true for every element in
the domain
• Existential quantification: There is one or more elements in the
domain for which a predicate is true

▪ Domain /domain of discourse/universe of discourse:

🡺The values a variable in a propositional function may take.
 Quantifiers

1. Universal Quantifier: ∀ is called the universal quantifier.

“∀” reads “for All”

2. Existential Quantifier: ∃ is called the existential

quantifier.
“∃” reads “there Exists”

12
The Universal Quantifier

Definition: The universal quantification of P(x) is the

statement “P(x) for all values of x in the domain”.
• The notation ∀x P(x) denotes the universal
quantification of P(x).
• We read ∀x P(x) as “for all x P(x)” or “for every x P(x)”
• An element for which P(x) is false is called a
counterexample of ∀x P(x)

13
The Universal Quantifier

• “∀x P (x)” is true when every instance of x makes P (x)

true when plugged in

• Like taking conjunction over the entire universe:

∀x P (x ) ≡ P (x1) ∧P (x2) ∧ P (x3) ∧ … ∧ P(xn)

14
Example 8
Let P(x) be the statement “x + 1 > x”
What is the truth value of the quantification ∀x P(x ),
where the domain consists of all real numbers?

Solution: Because P(x) is true for all real numbers x, the

truth value of the quantification ∀x P (x ) is true.

Note: If we add 1 to any real number x, that number is

always bigger than x

15
Example 9
• Let Q(x) be the statement “x < 2”. What is the truth
value of the quantification ∀x Q(x ), where the domain
consists of all real numbers?

• Solution: Q(x) is not true for every real number x,

because, for instance, Q(3) is false. That is, x = 3 is a
counterexample for the statement ∀x Q(x ).
Thus, the truth value of ∀x Q(x ) is false.

16
(Modified) Example 10
Let P(x) be the statement “x2 > 0”. What is the truth value
of the quantification ∀x P(x ), where the universe of
discourse consists of all integers?

Solution: P(x) is not true for all integers.

We can give a counter example. We see that x = 0 is a
counterexample, because x2 = 0 when x = 0, so that x2 is
not greater than 0 when x = 0.
Therefore, truth value of ∀x P(x ) is false.

17
Example 11
What is the truth value of ∀x P(x ), where P(x) is the
statement “x2 < 10” and the domain consists of the
positive integers not exceeding 4?

Solution: The statement ∀x P(x ) is the same as the

conjunction P(1) ∧ P(2) ∧ P(3) ∧ P(4), because the
domain consists of the integers 1, 2, 3, and 4.
Because P(4), which is the statement “42<10”, is false, it
follows that ∀x P(x ) is false.

18
Another Example
What is the truth value of ∀x P(x ), where P(x) is the statement “x2 < 10” and
the domain consists of the positive integers less than 4?

Solution: The statement ∀x P(x ) is the same as the conjunction P(1) ∧ P(2) ∧
P(3) , because the domain consists of the integers 1, 2, 3.
So, the truth value of ∀x P(x ) is true.

How?----------See Below-------------------------------------
P(1): “12<10”, is true
P(2): “22<10” is true
P(3): “32<10” is true
P(1) ∧ P(2) ∧ P(3) ≡ T ∧ T ∧ T ≡ T

19
 The Existential Quantifier
▪ Definition: The existential quantification of P(x) is the
proposition “There exists an element x in the domain such
that P(x)”.
▪ We denote the existential quantification of P(x) by ∃x P(x)
▪ Existential quantification ∃x P(x) is read as:
• “There is an x such that P(x)”, or
• “There is at least one x such that P(x)”, or
• “for some x P(x)”

20
The Existential Quantifier

• “∃x P(x)” is true when an instance can be found

which when plugged in for x, makes P(x) true.

• Like taking disjunction over the entire domain

∃x P (x ) ≡ P (x1) ∨ P (x2) ∨ P (x3) ∨ … P(xn)

21
Example 14

• Let P(x) denote the statement “x > 3”. What is the

truth value of the quantification ∃x P(x), where the
domain consists of all real numbers?

• Solution: Because “x > 3” is sometimes true –for

instance, when x = 4, the existential quantification
of P(x) , which is ∃x P (x), is true.

22
Example 15
▪ Let Q(x) denote the statement “x = x + 1”. What is the
truth value of the quantification ∃x Q(x), where the
domain consists of all real numbers?
• Solution: Because Q(x) is false for every real number x,
the existential quantification of Q(x), which is ∃x Q(x),
is false.
• Note: If we add 1 to any real number x, that number
will NEVER be equal to x, it will be always 1 bigger
than x.

23
Example 16
• What is the truth value of ∃x P(x), where P(x) is the statement
“x2 >10” and the universe of discourse consists of the positive
integers not exceeding 4?

• Solution: Because the domain is { 1, 2, 3, 4}, the proposition ∃x

P(x) is the same as the disjunction
P(1)∨ P(2) ∨ P(3)∨ P(4) .
Because P(4), which is the statement “42>10” , is true, it follows
that truth value of ∃x P(x) is true.

24
 Class Work
1. Let P(x) denote the statement “x>0”. What is the truth value of the quantification
∃x P (x)” , where the domain consists of integers?
2. Let P(x) denote the statement “x>0”. What is the truth value of the quantification
∀x P (x)” , where the domain consists of non-negative integers?
3. Let P(x) denote the statement “x>0”. What is the truth value of the quantification
∃x P (x)” , where the domain consists of negative integers?
4. Let P(x) denote the statement “x<2”. What is the truth value of the quantification
∃x P (x)” , where the domain consists of all prime numbers?
5. Let P(x) denote the statement “x ≤ 2”. What is the truth value of the
quantification ∃x P (x)” , where the domain consists of all prime numbers?

25
Answers

1. True
2. False
3. False
4. False
5. True

26
Universal & Existential Quantifiers:
When True? When False?

27
Precedence of Quantifiers
• The quantifiers ∀ and ∃ have higher precedence
than all logical operators from propositional
calculus.
• For example, ∀x P(x) ∨ Q(x) is the disjunction of
∀x P(x) and Q(x).
In other words, it means (∀x P(x)) ∨ Q(x) rather
than
∀x ( P(x)) ∨ Q(x) )

28
 Negating Quantified Expressions:
De Morgan’s Laws for Quantifiers

• The rules for negations for quantifiers are called De Morgan’s laws for
quantifiers
• Recall De Morgan’s identities/Laws:
• Negation of Conjunction: ¬(p1∧p2∧…∧pn) ≡ (¬p1∨¬p2∨…∨¬pn)
• Negation of Disjunction: ¬(p1∨p2∨…∨pn) ≡ (¬p1∧¬p2∧…∧¬pn)

▪ Since the quantifiers are the same as taking a bunch of AND’s (∀) or OR’s (∃),
we have:
• Universal Negation: ¬ ∀x P(x ) ≡ ∃x ¬P(x )

• Existential Negation: ¬ ∃x P(x ) ≡ ∀x ¬P(x )

29
 Translating from English into Logical
Expressions
Example 23 (p.40): Express the statement “Every student in the class has studied
calculus” using predicates and quantifiers.

Solution: First, we rewrite the statement so that we can clearly identify the
appropriate quantifiers to use. Doing so, we obtain:
“For every student in the class, that student has studied calculus”.
Next we introduce a variable x so that our statement becomes –
“For every student x in the class, x has studied calculus”
Continuing, we introduce the predicate Study(x), which is the statement “x has
studied calculus”
Consequently, if the universe of discourse for x consists of the students in the
class, we can translate our statement as ∀x Study(x).

30
Example 23 (p.40)
Note: There are other correct approaches; different domains of discourse and
other predicates can be used. For example, If we change the domain to
consists of all people, we need to express our statement as:
“For every person x, if person x is a student in this class then x has studied
calculus.”
If S(x) represents the statement that person x is in this class, our statement can be
expressed as ∀ x S(x) → C(x) or, ∀ x ( S(x) → C(x) )

Note: For the second way (when the domain is all people),
we always want to use conditional statements with universal quantifiers and
conjunctions with existential quantifiers.

31
Extra Example
• Express the statement “Someone in your school has studied
calculus” using predicates and quantifiers. Let the domain consists
of all people.
• Solution:
Let, S(x) be the propositional functions “ x is in your school” and
C(x) be the propositional function “x has studied calculus”.
So, the given statement can be expressed as ∃x ( S(x) ∧ C(x) )

▪ Note that if the domain consists of the students in your school,

then we can write ∃x C(x)

32
Exercise 9 (p.43)
• Let P(x) be the statement “x can speak Russian” and let Q(x) be the
statement “x knows the computer language C++”, Express each of these
sentences in terms of P(x), Q (x), quantifiers, and logical connectives. The
domain for quantifiers consists of all students at your school.
a) There is a student at your school who can speak Russian and who knows
C++.
b) There is a student at your school who can speak Russian but who doesn’t
know C++.
c) Every student at your school either can speak Russian or knows C++.
d) No student at your school can speak Russian or knows C++

33
Answers

a) ∃ x (p(x) ∧ Q(x))

b) ∃ x (p(x) ∧ ¬ Q(x))

c) ∀ x (P(x ) ∨ Q(x))

d) ∀ x ¬ (P(x ) ∨ Q(x))

34
Exercise 25 (p. 44)
Translate each of the statements into logical expressions
using predicates, quantifiers, and logical connectives.
Let the domain be all people
a) No one is perfect.
b) Not everyone is perfect.
c) All your friends are perfect.
d) At least one of your friends is perfect.
e) Everyone is your friend and is perfect.
f) Not everybody is your friend or someone is not perfect.

35
Solution

Let P(x) be “x is perfect”; let F(x) be “x is your friend”.

a) ∀x ¬ P(x )
b) ¬ ∀x P(x )
c) ∀x ( F(x) 🡪P (x) )
d) ∃ x (F(x) ∧ P(x))

(¬∀x (F(x )) ∨ (∃ x ¬P(x ))

e) ∀ x (F(x ) ∧ P(x))
f)

36