Discrete Structures
Topic 5 – Logic: Nested Quantifiers
(Ch. 1.5)*
CMPS 211 – American University of Beirut
* Extracted from Discrete Mathematics and It’s Applications book
slides
1
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 additive inverse” can be
expressed as x y(x + y = 0) where the domains of x
and y are the real numbers
We can also think of nested propositional
functions
x y(x + y = 0) can be viewed as x Q(x) where Q(x)
is y P(x, y) where P(x, y) is (x + y = 0)
2
Order of Quantifiers
Examples:
Let P(x,y) be the statement “x + y = y + x” and
assume that U is the real numbers. Then
x y P(x,y) is true
y x P(x,y) is true
Let Q(x,y) be the statement “x + y = 0” and
assume that U is the real numbers. Then
x y Q(x,y) is true
y x Q(x,y) is false
3
recipe
Decide on your variables
Decide on u.o.d. for each
Define the predicate
Decide on the quantification on each variable
Wrap up
4
Questions on Order of Quantifiers
Example:
Let U be the real numbers
Define P(x,y) : x ∙ y = 0
What is the truth value of the following:
x y P(x,y)
false
x y P(x,y)
true
x y P(x,y)
true
x y P(x,y)
true
5
Quantifications of Two Variables
Statement When True? When False
P(x,y) is true for There is a pair x, y
every pair x,y for which P(x,y) is
false
For every x there is a There is an x such
y for which P(x,y) is that P(x,y) is false for
true every y
There is an x for For every x there is a
which P(x,y) is true y for which P(x,y) is
for every y false
There is a pair x, y P(x,y) is false for
for which P(x,y) is every pair x,y
true
6
Translating Mathematical Statements into
Statements with Nested Quantifiers
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
7
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 P(w,f,a) be “w has taken flight f on airline
a”
2. The domain of w is all women,
the domain of f is all flights, and
the domain of a is all airlines
3. Then the statement can be expressed as:
w a f P(w, f, a)
8
Translating Nested Quantifiers into
English
Example 1:
Translate the statement
x y z ((F(x, y)∧ F(x,z) ∧ (y ≠z))→¬F(y,z))
where
F(x,y) is “x and y are friends” and
The domain for both x, y and z consists of all students
in your school
Solution:
There is a student none of whose friends are also
friends with each other
9
Translating Nested Quantifiers into
English
Example 2:
Translate the statement x (C(x )∨ y (C(y ) ∧
F(x, y))) where
C(x) is “x has a computer”, and
F(x,y) is “x and y are friends” and
The domain for both x and y consists of all students in
your school
Solution:
Every student has a computer or is a friend with
someone who has a computer
10
Exercises on Translation from English
Choose the obvious predicates and express in predicate
logic
“Brothers are siblings”
x y (B(x,y) → S(x,y))
“Siblinghood is symmetric”
x y (S(x,y) ↔ S(y,x))
“Everybody loves somebody”
x y L(x,y)
“There is someone who is loved by everyone”
y x L(x,y)
“There is someone who loves someone”
x y L(x,y)
“Everyone loves himself”
x L(x,x)
“Everyone loves exactly one other person”
x y (L(x, y) ∧ z (y ≠z→¬L(x,z)))
11
Negating Nested Quantifiers
Statements involving nested quantifiers can be negated by
successively applying the rules for negating statements
involving a single quantifier
Example:
Recall the logical expression developed few slides back
w a f P(w,f,a )
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:
¬w a f P(w,f,a )
w a f ¬P(w,f,a )
In other words, the statements says: “Every women hasn’t taken
any flight on at least one airline in the world”
12
Any Questions?
13