CSM2127: Discrete Mathematics

Predicates and Quantifiers

Presented By:
Professor Dr. Md. Rakib Hassan
Department of Computer Science and Mathematics
Email: rakib@bau.edu.bd
Propositional Logic is Not Enough
❖ Propositional logic cannot adequately express the meaning of all
statements in mathematics and in natural language.
❖ If we have:
“All men are mortal.”
“Socrates is a man.”

❖ Does it follow that “Socrates is mortal?”

o No
o It can’t be represented in propositional logic. We need a language that talks about
objects, their properties, and their relations.
▪ This language is called Predicate Logic.

❖ Predicate logic can be used to express the meaning of a wide range of

statements in mathematics and computer science in ways that permit us to
reason and explore relationships between objects.

2
Predicate
❖ To understand predicate logic, we need to understand predicate.
❖ Statements involving variables are neither true nor false when the values of the
variables are not specified. For example,
o “𝑥 > 3,” “𝑥 = 𝑦 + 3,” “𝑥 + 𝑦 = 𝑧”
o “Computer x is under attack by an intruder”
o “Computer x is functioning properly”
❖ The statement “𝑥 is greater than 3” has two parts:
o The first part, the variable 𝑥, is the subject of the statement.
o The second part—the predicate, “is greater than 3”—refers to a property that the
subject of the statement can have.
❖ We can denote the statement “𝑥 is greater than 3” by 𝑃(𝑥), where 𝑃 denotes
the predicate “is greater than 3” and 𝑥 is the variable.
❖ The statement 𝑃(𝑥) is also said to be the value of the propositional function 𝑃
at 𝑥.

3
Predicate Logic
❖ Predicate logic uses the following new features:
o Variables: 𝑥, 𝑦, 𝑧
o Predicates: 𝑃(𝑥), 𝑀(𝑥)
o Quantifiers: (to be covered in a few slides)

❖ Propositional functions are a generalization of propositions.

o They contain variables and a predicate, e.g., 𝑃(𝑥)
o Variables can be replaced by elements from their domain.

4
Propositional Functions
❖ Propositional functions become propositions (and have truth values) when
their variables are each replaced by a value from the domain (or bound by a
quantifier, as we will see later).
❖ The statement P(x) is said to be the value of the propositional function P at
x.
❖ For example, let P(x) denote “x > 0” and the domain be the integers. Then:
o P(-3) is false.
o P(0) is false.
o P(3) is true.

❖ Often the domain is denoted by U. So, in this example, U is the integers.

5
Examples of Propositional Functions
❖ Let “x + y = z” be denoted by R(x, y, z) and U (for all three variables) be the
integers. Find these truth values:
o R(2,-1,5)
▪ Solution: F
o R(3,4,7)
▪ Solution: T
o R(x, 3, z)
▪ Solution: Not a Proposition

❖ Now let “x - y = z” be denoted by Q(x, y, z), with U as the integers. Find these
truth values:
o Q(2,-1,3)
▪ Solution: T
o Q(3,4,7)
▪ Solution: F
o Q(x, 3, z)
▪ Solution: Not a Proposition

6
Compound Expressions
❖ Connectives from propositional logic carry over to predicate logic.
❖ If P(x) denotes “x > 0,” find these truth values:
o 𝑃(3) ∨ 𝑃(−1)
▪ Solution: T
o 𝑃(3) ∧ 𝑃(−1)
▪ Solution: F
o 𝑃(3) → 𝑃(−1)
▪ Solution: F
o 𝑃(3) → ¬𝑃(−1)
▪ Solution: T

❖ Expressions with variables are not propositions and therefore do not have
truth values. For example,
o 𝑃(3) ∧ 𝑃(𝑦)
o 𝑃(𝑥) → 𝑃(𝑦)
❖ When used with quantifiers (to be introduced next), these expressions
(propositional functions) become propositions.

7
Quantifiers Charles Peirce (1839-1914)

❖ We need quantifiers to express the meaning of English words including all

and some:
o “All men are Mortal.”
o “Some cats do not have fur.”

❖ The two most important quantifiers are:

o Universal Quantifier, “For all,” symbol: 

o Existential Quantifier, “There exists,” symbol: 

❖ We write as in 𝑥𝑃(𝑥) and 𝑥𝑃(𝑥).

❖ 𝑥𝑃(𝑥) asserts 𝑃(𝑥) is true for every x in the domain.
❖ 𝑥𝑃(𝑥) asserts 𝑃(𝑥) is true for some x in the domain.
❖ The quantifiers are said to bind the variable x in these expressions.

8
Universal Quantifier
❖ x P(x) is read as “For all x, P(x)” or “For every x, P(x)”
❖ Examples:
o If P(x) denotes “x > 0” and U is the integers, then x P(x) is false.
o If P(x) denotes “x > 0” and U is the positive integers, then x P(x) is true.
o If P(x) denotes “x is even” and U is the integers, then  x P(x) is false.

9
Existential Quantifier
❖ x P(x) is read as “For some x, P(x)”, or as “There is an x such that P(x),” or
“For at least one x, P(x).”
❖ Examples:
o If P(x) denotes “x > 0” and U is the integers, then x P(x) is true. It is also true if U
is the positive integers.
o If P(x) denotes “x < 0” and U is the positive integers, then x P(x) is false.
o If P(x) denotes “x is even” and U is the integers, then x P(x) is true.

10
Quantifiers

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 P(x) is false for every x.
true.

11
Uniqueness Quantifier
❖!x P(x) means that P(x) is true for one and only one x in the
universe of discourse.
❖This is commonly expressed in English in the following
equivalent ways:
o “There is a unique x such that P(x).”
o “There is one and only one x such that P(x)”

❖Examples:
1. If P(x) denotes “x + 1 = 0” and U is the integers, then !x P(x) is true.
2. But if P(x) denotes “x > 0,” then !x P(x) is false.

12
Thinking about Quantifiers
❖When the domain of discourse is finite, we can think of
quantification as looping through the elements of the domain.
❖To evaluate 𝑥 𝑃(𝑥), loop through all 𝑥 in the domain.
o If at every step 𝑃(𝑥) is true, then 𝑥 𝑃(𝑥) is true.
o If at a step 𝑃(𝑥) is false, then 𝑥 𝑃(𝑥) is false and the loop terminates.
❖To evaluate 𝑥 𝑃 𝑥 , loop through all x in the domain.
o If at some step, 𝑃(𝑥) is true, then 𝑥 𝑃(𝑥) is true and the loop
terminates.
o If the loop ends without finding an x for which 𝑃(𝑥) is true, then 𝑥 𝑃(𝑥)
is false.
❖Even if the domains are infinite, we can still think of the
quantifiers in this fashion, but the loops will not terminate in
some cases.

13
Properties of Quantifiers
❖The truth value of 𝑥 𝑃(𝑥) and 𝑥 𝑃(𝑥) depend on both the
propositional function 𝑃(𝑥) and on the domain 𝑈.
❖Examples:
1. If 𝑈 is the positive integers and 𝑃(𝑥) is the statement “𝑥 < 2”, then
x 𝑃(𝑥) is true, but 𝑥 𝑃(𝑥) is false.
2. If U is the negative integers and 𝑃(𝑥) is the statement “𝑥 < 2”, then
both 𝑥 𝑃(𝑥) and 𝑥 𝑃(𝑥) are true.
3. If 𝑈 consists of 3, 4, and 5, and 𝑃(𝑥) is the statement “𝑥 > 2”, then
both 𝑥 𝑃(𝑥) and 𝑥 𝑃(𝑥) are true. But if P(x) is the statement
“𝑥 < 2”, then both 𝑥 𝑃(𝑥) and 𝑥 𝑃(𝑥) are false.

14
Precedence of Quantifiers
❖The quantifiers  and  have higher precedence than all the
logical operators.
❖For example, 𝑥 𝑃(𝑥) ∨ 𝑄(𝑥) means (𝑥 𝑃(𝑥)) ∨ 𝑄(𝑥)
❖𝑥 (𝑃(𝑥) ∨ 𝑄(𝑥)) means something different.
❖Therefore, do not write 𝑥 𝑃(𝑥) ∨ 𝑄(𝑥) when we want to
mean 𝑥 (𝑃(𝑥) ∨ 𝑄(𝑥)).

15
Translating from English to Logic
Example 1: Translate the following sentence into predicate logic:
“Every student in this class has taken a course in C.”
Solution:
First decide on the domain U.
Solution 1: If U is all students in this class, define a propositional function C(x)
denoting “𝑥 has taken a course in C” and translate as 𝑥 𝐶(𝑥).
Solution 2: But if U is all people, also define a propositional function S(x)
denoting “𝑥 is a student in this class” and translate as 𝑥 (𝑆(𝑥) → 𝐶(𝑥)).
𝑥 (𝑆(𝑥) ∧ 𝐶(𝑥)) is not correct. What does it mean?

16
Translating from English to Logic
Example 2: Translate the following sentence into predicate logic:
“Some student in this class has taken a course in C.”
Solution:
First decide on the domain 𝑈.
Solution 1: If 𝑈 is all students in this class, translate as
𝑥 𝐶(𝑥)
Solution 2: But if 𝑈 is all people, then translate as 𝑥 (𝑆(𝑥) ∧ 𝐶(𝑥))
𝑥 (𝑆(𝑥) → 𝐶(𝑥)) is not correct. What does it mean?

17
Returning to the Socrates Example
❖Introduce the propositional functions 𝑀𝑎𝑛(𝑥) denoting “𝑥 is a
man” and 𝑀𝑜𝑟𝑡𝑎𝑙(𝑥) denoting “𝑥 is mortal.” Specify the
domain as all people.
❖The two premises are:
𝑥 𝑀𝑎𝑛 𝑥 → 𝑀𝑜𝑟𝑡𝑎𝑙 𝑥
𝑀𝑎𝑛(𝑆𝑜𝑐𝑟𝑎𝑡𝑒𝑠)
❖The conclusion is:
𝑀𝑜𝑟𝑡𝑎𝑙(𝑆𝑜𝑐𝑟𝑎𝑡𝑒𝑠)
❖Later we will show how to prove that the conclusion follows
from the premises.

18
Equivalences in Predicate Logic
❖Statements involving predicates and quantifiers are logically
equivalent if and only if they have the same truth value
❖The notation 𝑆 ≡ 𝑇 indicates that 𝑆 and 𝑇 are logically
equivalent.
❖Example: 𝑥 ¬¬𝑆(𝑥) ≡ 𝑥 𝑆(𝑥)

19
Thinking about Quantifiers as
Conjunctions and Disjunctions
❖If the domain is finite,
o a universally quantified proposition is equivalent to a conjunction
of propositions without quantifiers
o an existentially quantified proposition is equivalent to a
disjunction of propositions without quantifiers.
❖If U consists of the integers 1,2, and 3:
𝑥 𝑃 𝑥 ≡ 𝑃 1 ∧ 𝑃 2 ∧ 𝑃 3
∃𝑥 𝑃(𝑥) ≡ 𝑃 1 ∨ 𝑃 2 ∨ 𝑃 3
❖Even if the domains are infinite, you can still think of the
quantifiers in this fashion, but the equivalent expressions
without quantifiers will be infinitely long.

20
Negating Quantified Expressions
❖Consider 𝑥 𝐶(𝑥)
“Every student in your class has taken a course in C.”
Here C(x) is “x has taken a course in C” and
the domain is students in your class.

❖Negating the original statement gives “It is not the case that
every student in your class has taken C.” This implies that
“There is a student in your class who has not taken C.”
Symbolically ¬𝑥 𝐶(𝑥) and 𝑥 ¬𝐶(𝑥) are equivalent

21
Negating Quantified Expressions
(continued)
❖ Now Consider 𝑥 𝐶(𝑥)
“There is a student in this class who has taken a course in C.”
Where C(x) is “x has taken a course in C.”

❖ Negating the original statement gives “It is not the case that there is a
student in this class who has taken C.” This implies that “Every student in
this class has not taken C”
Symbolically ¬𝑥 𝐶(𝑥) and 𝑥 ¬𝐶(𝑥) are equivalent

22
De Morgan’s Laws for Quantifiers
❖The rules for negating quantifiers are:
De Morgan’s Laws for Quantifiers
Equivalent
Negation When Is Negation True? When False?
Statement
¬∃𝑥𝑃(𝑥) ∀𝑥¬𝑃(𝑥) For every x, P(x) is false There is an x for which
P(x) is true
¬∀𝑥𝑃(𝑥) ∃𝑥¬𝑃(𝑥) There is an x for which P(x) is P(x) is true for every x
false

❖The reasoning in the table shows that:

¬∀𝑥 𝑃 𝑥 ≡ ∃𝑥¬𝑃(𝑥)
¬∃𝑥 𝑃 𝑥 ≡ ∀𝑥¬𝑃(𝑥)
❖These are important.

23
Translation from English to Logic
Examples:
1. “Some student in this class has visited Mexico.”
Solution: Let M(x) denote “x has visited Mexico” and S(x) denote “x is a
student in this class,” and U be all people.
𝑥 (𝑆(𝑥) ∧ 𝑀(𝑥))

2. “Every student in this class has visited Canada or Mexico.”

Solution: Add C(x) denoting “x has visited Canada.”
𝑥 (𝑆(𝑥) → (𝑀(𝑥) ∨ 𝐶(𝑥)))

24
System Specification Example
❖Predicate logic is used for specifying properties that systems
must satisfy.
❖For example, translate into predicate logic:
o “Every mail message larger than one megabyte will be compressed.”
o “If a user is active, at least one network link will be available.”
❖Decide on predicates and domains (left implicit here) for the
variables:
o Let L(m, y) be “Mail message m is larger than y megabytes.”
o Let C(m) denote “Mail message m will be compressed.”
o Let A(u) represent “User u is active.”
o Let S(n, x) represent “Network link n is in state x.
❖Now we have:
∀𝑚 𝐿 𝑚, 1 → 𝐶 𝑚
∃𝑢 𝐴 𝑢 → ∃𝑛 𝑆(𝑛, 𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒)

25
Lewis Carroll Example Charles Lutwidge Dodgson (AKA Lewis Caroll)
(1832-1898)

❖ The first two are called premises and the third is called the conclusion.
o Premises
1. “All lions are fierce.”
2. “Some lions do not drink coffee.”
o Conclusion
1. “Some fierce creatures do not drink coffee.”

❖ Here is one way to translate these statements to predicate logic. Let P(x),
Q(x), and R(x) be the propositional functions “x is a lion,” “x is fierce,” and
“x drinks coffee,” respectively.
1. 𝑥 (𝑃(𝑥) → 𝑄(𝑥))
2. 𝑥 (𝑃(𝑥) ∧ ¬𝑅(𝑥))
3. 𝑥 (𝑄(𝑥) ∧ ¬𝑅(𝑥))

26
Nested Quantifiers
❖Nested quantifiers are often necessary to express the meaning
of sentences in English as well as important concepts in
computer science and mathematics.
Example: “Every real number has an inverse” is
𝑥 𝑦(𝑥 + 𝑦 = 0)
where the domains of x and y are the real numbers.

❖We can also think of nested propositional functions:

𝑥 𝑦(𝑥 + 𝑦 = 0) can be viewed as 𝑥 𝑄(𝑥) where 𝑄(𝑥) is

𝑦 𝑃(𝑥, 𝑦) where 𝑃(𝑥, 𝑦) is (𝑥 + 𝑦 = 0)

27
Order of Quantifiers
Examples:
1. Let 𝑃(𝑥, 𝑦) be the statement “𝑥 + 𝑦 = 𝑦 + 𝑥.” Assume that U is the real
numbers. Then 𝑥 𝑦𝑃(𝑥, 𝑦) and 𝑦 𝑥𝑃(𝑥, 𝑦) have the same truth
value.
2. Let 𝑄(𝑥, 𝑦) be the statement “𝑥 + 𝑦 = 0.” Assume that 𝑈 is the real
numbers. Then 𝑥 𝑦 𝑄(𝑥, 𝑦) is true, but 𝑦 𝑥 𝑄(𝑥, 𝑦) is false.

28
Questions on Order of Quantifiers
Example 1: Let 𝑈 be the real numbers,
Define 𝑃(𝑥, 𝑦): 𝑥 ∙ 𝑦 = 0
What is the truth value of the following:
1. 𝑥 𝑦 𝑃(𝑥, 𝑦)
Answer: False
2. 𝑥 𝑦 𝑃(𝑥, 𝑦)
Answer: True
3. 𝑥 𝑦 𝑃(𝑥, 𝑦)
Answer: True
4. 𝑥 𝑦 𝑃(𝑥, 𝑦)
Answer: True

29
Questions on Order of Quantifiers
Example 2: Let U be the real numbers,
Define 𝑃(𝑥, 𝑦) ∶ 𝑥/𝑦 = 1
What is the truth value of the following:
1. 𝑥 𝑦 𝑃 𝑥, 𝑦
➢ Answer: False
2. 𝑥 𝑦 𝑃 𝑥, 𝑦
➢ Answer: False
3. 𝑥 𝑦 𝑃 𝑥, 𝑦
➢ Answer: False
4. 𝑥 𝑦 𝑃 𝑥, 𝑦
➢ Answer: True

30
Quantifications of Two Variables
Statement When True? When False
∀𝑥∀𝑦𝑃(𝑥, 𝑦) There is a pair x, y for which
𝑃(𝑥, 𝑦) is true for every pair 𝑥, 𝑦
∀𝑦∀𝑥𝑃(𝑥, 𝑦) P(x,y) is false
For every 𝑥 there is a 𝑦 for which There is an x such that P(x,y)
∀𝑥∃𝑦𝑃(𝑥, 𝑦)
P(x,y) is true is false for every y
There is an x for which P(x,y) is true For every x there is a y for
∃𝑥∀𝑦𝑃(𝑥, 𝑦)
for every y which P(x,y) is false
∃𝑥∃𝑦𝑃(𝑥, 𝑦) There is a pair x, y for which P(x,y) is
P(x,y) is false for every pair x,y
∃𝑦∃𝑥𝑃(𝑥, 𝑦) true

31
Translating Nested Quantifiers into
English
Example 1: Translate the statement
𝑥 (𝐶(𝑥) ∨ 𝑦 (𝐶(𝑦) ∧ 𝐹(𝑥, 𝑦)))
where 𝐶(𝑥) is “𝑥 has a computer,” and 𝐹(𝑥, 𝑦) is “𝑥 and 𝑦 are friends,” and
the domain for both 𝑥 and 𝑦 consists of all students in your school.
Solution: Every student in your school has a computer or has a
friend who has a computer.

Example 2: Translate the statement

𝑥𝑦 𝑧 ((𝐹(𝑥, 𝑦) ∧ 𝐹(𝑥, 𝑧) ∧ (𝑦 ≠ 𝑧)) → ¬𝐹(𝑦, 𝑧))
Solution: There is a student none of whose friends are also
friends with each other.

32
Translating Mathematical Statements
into Predicate Logic
Example : Translate “The sum of two positive integers
is always positive” into a logical expression.
Solution:
1. Rewrite the statement to make the implied quantifiers and
domains explicit:
“For every two integers, if these integers are both positive, then the
sum of these integers is positive.”
2. Introduce the variables x and y, and specify the domain, to
obtain:
“For all positive integers x and y, x + y is positive.”
3. The result is:
x  y ((x > 0)∧ (y > 0)→ (x + y > 0))
where the domain of both variables consists of all integers

33
Translating English into Logical
Expressions Example
Example: Use quantifiers to express the statement “There is a
woman who has taken a flight on every airline in the world.”
Solution:
1. Let 𝑃(𝑤, 𝑓) be “𝑤 has taken 𝑓” and 𝑄(𝑓, 𝑎) be “𝑓 is a
flight on 𝑎.”
2. The domain of 𝑤 is all women, the domain of 𝑓 is all
flights, and the domain of a is all airlines.
3. Then the statement can be expressed as:
𝑤 𝑎 𝑓 (𝑃(𝑤, 𝑓) ∧ 𝑄(𝑓, 𝑎))

34
 Questions on Translation from English
Choose the obvious predicates and express in predicate logic.
Example 1: “Brothers are siblings.”
Solution: 𝑥 𝑦 (𝐵(𝑥, 𝑦) → 𝑆(𝑥, 𝑦))
Example 2: “Siblinghood is symmetric.”
Solution: 𝑥 𝑦 (𝑆(𝑥, 𝑦) → 𝑆(𝑦, 𝑥))
Example 3: “Everybody loves somebody.”
Solution: 𝑥 𝑦 𝐿(𝑥, 𝑦)
Example 4: “There is someone who is loved by everyone.”
Solution: 𝑦 𝑥 𝐿(𝑥, 𝑦)
Example 5: “There is someone who loves someone.”
Solution: 𝑥 𝑦 𝐿(𝑥, 𝑦)
Example 6: “Everyone loves himself”
Solution: 𝑥 𝐿(𝑥, 𝑥)

35
 Negating Nested Quantifiers
Example 1: There is a woman who has taken a flight on every airline in the world:
𝑤 𝑎 𝑓 (𝑃(𝑤, 𝑓) ∧ 𝑄(𝑓, 𝑎))
Part 1: Use quantifiers to express the statement that “There does not exist a woman
who has taken a flight on every airline in the world.”
Solution:
¬𝑤 𝑎 𝑓 𝑃 𝑤, 𝑓 ∧ 𝑄 𝑓, 𝑎
Part 2: Now use De Morgan’s Laws to move the negation as far inwards as possible.
Solution:
1. ¬𝑤 𝑎 𝑓 (𝑃(𝑤, 𝑓) ∧ 𝑄(𝑓, 𝑎))
2. 𝑤 ¬ 𝑎 𝑓 (𝑃(𝑤, 𝑓 ) ∧ 𝑄(𝑓, 𝑎)) by De Morgan’s for 
3. 𝑤 𝑎 ¬ 𝑓 (𝑃(𝑤, 𝑓 ) ∧ 𝑄(𝑓, 𝑎)) by De Morgan’s for 
4. 𝑤 𝑎 𝑓 ¬(𝑃(𝑤, 𝑓 ) ∧ 𝑄(𝑓, 𝑎)) by De Morgan’s for 
5. 𝑤 𝑎 𝑓 (¬𝑃(𝑤, 𝑓 ) ∨ ¬ 𝑄(𝑓, 𝑎)) by De Morgan’s for ∧.
Part 3: Can you translate the result back into English?
Solution:
“For every woman there is an airline such that for all flights, this woman has not
taken that flight or that flight is not on this airline”

36
37