NESTED QUANTIFIERS

Lecture # 16

1
 NESTED QUANTIFIER
 Nested Quantifier, where one quantifier is within the
scope of another, such as:

xy (x + y = 0).

 Note:
Everything within the scope of a quantifier can be thought of
as a propositional function.

2
 Example:
xy (x + y = 0) is the same as x Q(x),

where
Q(x) = y P(x, y)
where
P(x, y) = x + y = 0

3
 UNDERSTANDING STATEMENTS
INVOLVING NESTED QUANTIFIERS
 Example: Assume that the domain of the variables x and
y consists of all real numbers. The statement

x y (x + y = y + x)

 The statement says that (x + y = y + x) for all real

numbers x and y. This is the commutative law for
addition of real numbers.

4
 UNDERSTANDING NESTED
QUANTIFIER
 Consider the statement

x y (x + y = 0)

 Says that for every real number x, there is a real number

y such that x + y = 0.

5
 Consider the statement:

x y z (x + (y + z) = (x + y) + z)

 Says that every real number has an additive inverse.

6
 TRANSLATE INTO ENGLISH
 Translate into English the statement:

x  y ((x > 0)  (y < 0) → (xy < 0))

 Where the domain for both variables consists of all real nos.

For all real number x and for all real number y. If x > 0 and y < 0, then
xy < 0.
OR
For all real number x and y. If x is positive real no. and y is negative
real no, then xy is a negative.
OR
The product of a positive real no. and a negative real no is always a
negative real number.
7
 EXAMPLE
 Translate into English the statement:

x y ((x ≥ 0)  (y ≥ 0) → (xy ≥ 0))

 Where the domain for both variables consists of all real nos.

For all real number x and for all real number y. If x ≥ 0 and y ≥ 0, then
xy ≥ 0.
OR
For all real number x and y. If x is positive real no. and y is positive
real no, then xy is a positive real number.
OR
The product of a two non-negative real numers is always non-negative.
8
 EXAMPLE
 Translate into English the statement

xy (xy = y)

 Where the domain for both variables consists of all real

nos.

“There exist a real number x for all real number y such

that xy = y”

9
 EXAMPLE
 Translate into English the statement

xyz(x = y + z)

 Where the domain for each variables consists of all real

nos.

“For every real number x and y, there exist a real number

z such that x = y + z.”

10
 EXAMPLE
 Translate into English the statement:

xy (((x≠0)  (y≠0)) ↔ (xy ≠ 0))

 Where the domain for each variables consists of all real

nos.

“The product of two non-zero numbers is non-zero if and

only if, both numbers are non-zero.”

11
 THE ORDER OF QUANTIFIERS
 Many mathematical statements involve multiple
quantifications of propositional functions involve more
than one variable.

 The order of quantifiers is important, unless all the

quantifiers are universal quantifiers or all are existential
quantifiers.

12
 EXAMPLE
 Let P(x, y) be the statement “x + y = y + x”. What are the
truth values of the quantifications:

xy P(x, y) and yx P(x, y)

where the domain for all variables consists of all real

numbers?

13
 SOLUTION
The quantification xy P(x, y) denotes the proposition:
“For all real numbers x, for all real numbers y,
x + y = y + x.”

The quantification yx P(x, y) denotes the proposition:

“For all real numbers y, for all real numbers x,
x + y = y + x.”

 That is, xy P(x, y) and yx P(x, y) have the same
meaning and both are true.

14
 Principle
 This illustrate the principle that the order of nested
universal quantifiers in a statement without other
quantifiers can be changed without changing the meaning
of the quantified statement.

15
 EXAMPLE
 Let Q(x, y) denote “x + y = 0”. What are the truth values of
the quantification yxQ(x, y) and xyQ(x, y), where the
domain for all variables consists of all real numbers?

 Solution:
yxQ(x, y) denotes the proposition:

“There is a real number y such that for every real number x,

Q(x, y)”

 The statement is yxQ(x, y) is false. Because what value of

y is chosen, there is only one value of x for which x + y = 0.
16
 The quantification xyQ(x, y) denotes the proposition:

“For every real number x there is a real number y such

that Q(x, y).”

 Given a real number x, there is a real number y such that x

+ y = 0; namely x = - y.

 Hence the statement xyQ(x, y) is True.

17
 OBSERVATION
 From these observations in previous example, it follows
that if yx P(x, y) is true, then xyP(x, y) must also be
true.

 However, If xy P(x, y) is true, it is not necessary for

yx P(x, y) to be true.

18
19
 EXAMPLE
 Let Q(x, y, z) be the statement “x + y = z.” What are the
truth values of the statement xyz Q(x, y, z) and
zxy Q(x, y, z), where the domain of all variables
consists of all real numbers?

 Solution:
 The quantification xyz Q(x, y, z) denotes that:

“For all real numbers x and for all real numbers y there is
a real number z such that x + y = z” is true.

20
 zxy Q(x, y, z) which is the statement:

“There is a real number z such that for all real numbers x

and for all real numbers y such that x + y = z.” is False.

Because there is no value of z that satisfies the equation

x + y = z.

21
TRANSLATING MATHEMATICAL STATEMENTS INTO
STATEMENTS INVOLVING NESTED QUANTIFIERS
 EXAMPLE: Translate the statement into a logical expression.
“The sum of two positive integers is always positive”

 Solution:
Step 1: Rephrase it so that Quantifiers and Domain are shown:
“For every two integers, if these integers are both positive, then
the sum of these integers is positive.”

Step 2: Introduce variables x and y.

“For all positive integers x and y, if x > 0 and y > 0, then x + y
is positive.”

22
 Step 3: Propositional Function
P(x) = x > 0
Q(x) = y > 0
R(x) = x + y > 0
Domain = All integers

 Step 4:
xy ((x > 0)  (y > 0) → (x + y > 0))
xy (P(x)  Q(y)) → R(x))

23
 EXAMPLE
 Translate the statement into a logical expression.
“Every real number except zero has a multiplicative inverse”
(A multiplicative inverse of a real number x and y is xy = 1)

 Solution:
Step 1: Rephrase
“For every real number x except zero, x has a multiplicative
inverse.”

Step 2: Introduce variables

“For every real number x, if x ≠ 0, then there exists a real number
y such that xy = 1”
24
 Step 3: Propositional Function
P(x) = x ≠ 0
Q(x) = xy = 1
Domain = All real numbers.
 Step 4:
x ((x ≠ 0) → y(xy = 1))
x (P(x) → yQ(x)))

25
 EXAMPLE
 Translate the statement into a logical expression.
“The difference of two positive integers is not necessarily
positive”

 Solution:
Step 1: Rephrase
“For every positive integers x and y, the difference is not
necessarily positive.”

Step 2:
“For every integer x and y, the x – y > 0 or x – y < 0”

26
 Step 3:
xy (((x > 0)  (y > 0)) → ((x – y > 0)  (x – y < 0)))

OR

¬x y ((x > 0)  (y > 0) → (x – y > 0))

27
 EXAMPLE
 Translate the statement into a logical expression.
“The absolute value of the product of two integers is the product
of their absolute values.”

 Solution:
Step 1: Rephrase
“For every positive integers x and y, the absolute value of product
of two values x and y is product of their absolute values.”

Step 2:
“For every integer x and y, the |x.y| = |x||y|”

28
 Step 3:
x y (|x.y| = |x||y|)

29
 EXAMPLE
 Translate the statement into a logical expression.
“Every positive integer is the sum of the squares of four integers.”

 Solution:
Step 1: Rephrase
“For every positive integers x , there exist four integers a, b, c and
d such that every integer x is equal to sum of four integers.”

Step 2:
“For every positive integer x, there exist four integers a, b, c and d

such that x = a² + b² + c² + d².”

30
 Step 3:
x a b c d ((x > 0) → x = a² + b² + c² + d²)

31
 TRANSLATING FROM NESTED
QUANTIFIERS INTO ENGLISH
 Expression with nested quantifiers expressing statements
in English can be quite complicated.

 Step 1:
Write out Quantifiers and Predicates.

 Step 2:
Express the meaning in simple sentence.

32
 EXAMPLE
 Translate the statement
x (C(x)  y(C(y)  F(x,y)))

where
C(x) = x has a computer
F(x, y) = x and y are friends
Domain = All students in the school

33
 SOLUTION
 The statement says that “for every student x in your
school, x has a computer or there is a student y such that y
has a computer and x and y are friends”.

 In other words,
Every student in your school has a computer or has a
friend who has a computer.

34
 EXAMPLE
 Translate the statement
xyz ((F(x, y)  F(x, z)  (y ≠ z)) → ¬F(y, z))

where
F(a, b) = means a and b are friends.
Domain = all students in the school

35
 SOLUTION
 First examine ((F(x, y)  F(x, z)  (y ≠ z)) → ¬F(y, z))
This expression says that “if student x and y are friends
and student x and z are friends, and furthermore if y and z
are not same student, then y and z are not friends”

 It follows that the original statement, which is triply

quantified, says that
“There is a student in the school who's friends are not
friends of each other.”

36
 EXAMPLE
 Translate the statement
xyz ((x ≠ y)  (W(x, z)  W(y, z)))

where
W(x, z) = student x has visited website z.
Domain for x and y = All students in the school
Domain for z = All websites.

37
 SOLUTION
 First examine ((x ≠ y)  (W(x, z)  W(y, z)))
This expression says that: “x and y are not the same and
student x has visited a website z if and only if student y
has visited a website z.”

 It follows that the original statement, which is triply

quantified, says that:
“There are two students in the school who have visited
exactly same websites.”

38
 In other words,
Two different people who have visited the exactly same
website.

39
 TRANSLATING ENGLISH SENTENCES
INTO LOGICAL EXPRESSIONS
 Example: Express the statement as a logical expression
involving predicates and quantifiers with a domain
consisting of all people.

“If a person is female and is a parent, then this person is

someone’s mother.”

40
 SOLUTION
Step 1: Rephrase so that domain and quantifier can be
shown.

“For every person, if person is female and person is

parent, then there exist a person such that person is the
mother of person.”

Step 2: Introducing variables.

“For every person x, if person x is female and person x is
parent, then there exist a person y such that person x is the
mother of person y. ”
41
 Step 3: Propositional Function
F(x) = x is female
P(x) = x is a parent
M(x, y) = x is the mother of y

Step 4:
x ((F(x)  P(x)) → y M(x, y))
OR
x y(((F(x)  P(x)) → M(x, y))

42
 EXAMPLE
 Let
S(x) = “x is a student”
F(x) = “x is a faculty member”
A(x, y) = “x has asked y a question”
Domain = all people associated with your school.

 Use quantifiers to express each of these statements.

43
 Lois has asked Professor Michaels a question.
 A(Lois, Professor Michaels)

 Every Student has asked Professor Gross a question.

 x (S(x) → A(x, Professor Gross))

 Every faculty member has either asked Professor Miller a

question or been asked a question by Prof. Miller.
 x (F(x) → (A(x, Professor Miller)  A(Professor Miller, x)))

44
 Some student has not asked any faculty member a question.
 x (S(x)  y(F(y) → ¬A(x, y)))

 There is a faculty member who has never been asked a

question by a student.
 x (F(x)  y(S(y) → ¬A(y, x)))

 Some student has asked every faculty member a question.

 y (F(y) → x(S(x)  A(x, y)))
 x (S(x)  y(F(y) → A(x, y)))

45
 There is a faculty member who has asked every other
faculty member a question.
 x (F(x)  y((F(y)  (y ≠ x)) → A(x, y)))

 Some student has never been asked a question by a faculty

member.
 x (S(x)  y((F(y) → ¬A(y, x)))

46
 EXAMPLE
 Express the statement as a logical expression involving
predicates and quantifiers with a domain consisting of all
people.

“There is a man who has taken a flight on every airline in

the world.”

Solution:
Step 1: Rephrase
“There is a man, the man has taken a flight, on every
airline in the world.”
47
 Step 2: Introducing variables.
“There is a man x, the man x has taken a flight f, on every airline
in the world.”

 Step 3: Propositional Function

P(m, f) = m has taken flight f
Q(f, a) = f is a flight on airline a
Domain m, f and a = all the men in the world, all
airplane flights, and all airlines
respectively.
 Step 4:
m a f (P(m, f)  Q(f, a))
48
 NEGATING NESTED QUANTIFIERS
 EXAMPLE: Express the negation of the statement
xy (xy = 1).

Solution:

 ¬xy (xy = 1) Given

 x¬y (xy = 1) De-Morgan’s Law
 xy ¬(xy = 1) De-Morgan’s Law
 xy (xy ≠ 1)

49
 EXAMPLE
 Use Quantifiers to express the negation of the statement
that:
“There does not exist a man who has taken a flight on
every airline in the world.”

 Solution:
The statement is negation of the statement
“There is a man who has taken a flight on every airline in
the world.”
¬waf (P(w, f)  Q(f, a))

50
  ¬waf (P(w, f)  Q(f, a)) Given
 w¬af (P(w, f)  Q(f, a))De-Morgan’s Law
 wa¬f (P(w, f)  Q(f, a))De-Morgan’s Law
 waf ¬(P(w, f)  Q(f, a))De-Morgan’s Law
 waf (¬P(w, f)  ¬Q(f, a)) De-Morgan’s Law

51
 EXAMPLE
 Express the negation of the statement
xy P(x, y)  xy Q(x, y).

Solution:

 ¬[xy P(x, y)  xy Q(x, y)] Given

 ¬xy P(x, y)  ¬xy Q(x, y) De-Morgan’s Law
 x¬y P(x, y)  x¬y Q(x, y) De-Morgan’s Law
 xy¬P(x, y)  xy¬Q(x, y) De-Morgan’s Law

52
 EXAMPLE
 Express the negation of the statement
xy (Q(x, y)  Q(y, x)).

Solution:

 ¬[xy (Q(x, y)  Q(y, x))] Given

 x¬y (Q(x, y)  Q(y, x)) De-Morgan’s Law
 xy¬(Q(x, y)  Q(y, x)) De-Morgan’s Law
 xy¬[(Q(x, y) → Q(y, x))  (Q(y, x) → Q(x, y))] As we
know that p  q  (p q)  (q p)

53
 xy ¬(Q(x, y) → Q(y, x))  ¬(Q(y, x) → Q(x, y))
De-Morgan’s Law
 xy ¬[¬(Q(x, y)  ¬Q(y, x))]  ¬[¬(Q(y, x)  ¬Q(x, y))]
As we know that p q  ¬(p  ¬q)
 xy ¬[¬Q(x, y)  ¬Q(y, x)]  ¬[¬Q(y, x)  ¬Q(x, y)]
De-Morgan’s Law
º xy [¬¬Q(x, y)  ¬¬Q(y, x)]  [¬¬Q(y, x)  ¬¬Q(x, y)]

De-Morgan’s Law
 xy [Q(x, y)  Q(y, x)]  [Q(y, x)  Q(x, y)]
Double Negation Law
54