DISCRETE MATHEMATICS

(0714 02CSE1103)

NESTED QUANTIFIERS

Course Teacher

Anupam Kumar Bairagi, PhD

Professor
Computer Science and Engineering Discipline
Khulna University, Khulna-9208, Bangladesh
 Nested Quantifiers

 Two quantifiers are nested if one is within the scope

of other quantifier.
 Example:
∀𝑥∃𝑦 𝑥 + 𝑦 = 0

∀𝑥∀𝑦 𝑥 + 𝑦 = 𝑦 + 𝑥

∀𝑥∀𝑦∀𝑧 𝑥 + 𝑦 + 𝑧 = 𝑥 + 𝑦 + 𝑧

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 Translating Statements involving Nested Quantifiers

 Complicated expressions involving quantifiers arise in

many contexts
 To understand these statements involving many
quantifiers, we need to unravel what the quantifiers
and predicates that appear mean.
 Example 1: Let the universe of discourse for the
variable x and y consists of all real numbers. Then the
statement
∀𝑥∀𝑦 𝑥 + 𝑦 = 𝑦 + 𝑥
says that 𝑥 + 𝑦 = 𝑦 + 𝑥 for all the real numbers x and y.

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 Translating Statements involving Nested Quantifiers

 However, the statement

∀𝑥∃𝑦 𝑥 + 𝑦 = 0
says that for every real number x there is a real number y such
that 𝑥 + 𝑦 = 0.
 Example 2: ∀𝑥∀𝑦 𝑥 > 0 ∧ (𝑦 < 0) → (𝑥𝑦 < 0) , where
the universe of discourse for both variables consists of all real
numbers.
Solution: This statement says that for every real number x and
for every real number y, if 𝑥 > 0 and 𝑦 < 0, then 𝑥𝑦 < 0.

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 Translating Statements involving Nested Quantifiers

 Example 3: ∀𝑥(𝐶(𝑥) ∨ ∃𝑦(𝐶(𝑦) ∧ 𝐹(𝑥, 𝑦)), where 𝐶(𝑥) is “x

has a computer”, 𝐹(𝑥, 𝑦) is “x and y are friends” and the
universe of discourse for both x and y consists of all students
in your class.
Solution: This statement says that for every student x in your
class has a computer or there is a student y such that y has a
computer and x and y are friends.

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 Translating Statements involving Nested Quantifiers

 Example 4: ∃𝑥∀𝑦∀𝑧( 𝐹 𝑥, 𝑦 ∧ 𝐹 𝑥, 𝑧 ∧ 𝑦 ≠ 𝑧 →
¬𝐹 𝑦, 𝑧 ), where 𝐹(𝑎, 𝑏) means a and b are friends and the
universe of discourse for x, y and z consists of all students in
your class.
Solution: This statement says that if students x and y are
friends, and students x and z are friends, and furthermore, if y
and z are not the same student, then y and z are not friends.

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 Translating Sentences into Logical Expressions
 Example 5: Express the statement “if a person is female and
is a parent, then this person is someone’s mother” as a
logical expression.
Solution: The original statement can be expressed as “For
every person x, if person x is female and person x is a parent,
then there exists a person y such that person x is the mother of
person y”. Now, predicate F(x): “x is female”, P(x): “ x is a
parent”, and M(x, y): “x is the mother of y”. Thus, finally
∀𝑥( 𝐹 𝑥 ∧ 𝑃 𝑥 → ∃𝑦𝑀 𝑥, 𝑦 )
We can rearrange this as: ∀𝑥∃𝑦( 𝐹 𝑥 ∧ 𝑃 𝑥 → 𝑀 𝑥, 𝑦 )

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 Translating Sentences into Logical Expressions
 Example 6: Express the statement “The sum of two positive
integers is positive” as a logical expression.
Solution: The original statement can be expressed as “For
all positive integers x and y, x + y is positive”. Now, we can
express this statement as:
∀𝑥∀𝑦((𝑥 > 0) ∧ (𝑦 > 0) → (𝑥 + 𝑦 > 0))
where the universe of discourse for both variables consists of
all integers.

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 Translating Sentences into Logical Expressions
 Example 7: Express the statement “Every real number
except zero has a multiplicative inverse” as a logical
expression.
Solution: The original statement can be expressed as “For
every real number x, if 𝑥 ≠ 0, then there exists a real number y
such that xy=1”. Now, we can express this statement as:
∀𝑥 ((𝑥 ≠ 0) → ∃𝑦(𝑥𝑦 = 1))

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 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:

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 Negating Multiple Quantifiers
 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”

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 The Order of Quantifiers
 It is important to note that the order of the
quantifiers is important, unless all the quantifiers
are universal quantifiers or all are existential
quantifiers.
 Case 1: ∀𝑥∀𝑦𝑃 𝑥, 𝑦 ≡ ∀𝑦∀𝑥𝑃 𝑥, 𝑦 , P(x, y): x + y = y +x
 Example: For all real numbers x and for all real
numbers y, x + y = y + x. This is true.

 Case 2: ∃𝑥∃𝑦𝑃 𝑥, 𝑦 ≡ ∃𝑦∃𝑥𝑃 𝑥, 𝑦 , P(x, y): x + y = 0

 Example: There is a pair x and y for which P(x,y) is true.

Anupam Kumar Bairagi, PhD CSE, KU [Link]

 The Order of Quantifiers
 Case 3: ∀𝑥∃𝑦𝑃 𝑥, 𝑦 ≢ ∃𝑦∀𝑥𝑃 𝑥, 𝑦 , P(x, y): x + y = 0
 Example: “For every real numbers x there is a real
number y such that x + y = 0”. This is true.
 However, “There is a real number y such that for
every real number x, x + y = 0”. This is false.

Anupam Kumar Bairagi, PhD CSE, KU [Link]

Thanks for your Attention