Nested Quantifiers

Logic & Proofs
(Nested Quantifiers)
Dr. Nirnay Ghosh
1 9/19/2022
Nested Quantifier
 One quantifier is within the scope of another quantifier
 Example: ∀x ∃y (x + y = 0); domain of x, y consists of all real numbers
 For every real number x there is a real number y such that x + y = 0. This states that every real
number has an additive inverse
 Example: ∀x ∀y((x > 0) ∧ (y < 0) → (xy < 0)): domain of x, y consists of all real
numbers
 This statement says that for every real number x and for every real number y, if x > 0 and y < 0,
then xy < 0.
 This can be stated more succinctly as “The product of a positive real number and a negative real
number is always a negative real number”.
 Nested quantifiers can be looked into as loops:
 ∀x ∀y P(x, y): loop through the values for x, and for each x we loop through the values
for y
 ∀x ∃y P(x, y): for each x we loop through the values for y until we find a y for which
P(x, y) is true
 ∃x ∀y P(x, y): we loop through the values for x until we find an x for which P(x, y) is
always true when we loop through all values for y
 ∃x ∃y P(x, y): we loop through the values for x, where for each x we loop through the
values for y until we hit an x for which we hit a y for which P(x, y) is true. 9/19/2022
2
Order of Quantifiers
 The order of nested universal/existential quantifiers in a statement
without other quantifiers can be changed without changing the
meaning of the quantified statement.
3 9/19/2022
Translating English Sentences into Logical
Expressions
 Express the statement “If a person is female and is a parent, then this
person is someone’s mother” as a logical expression involving
predicates, quantifiers with a domain consisting of all people, and
logical connectives.
 We introduce the propositional functions F(x) to represent “x is female,” P(x) to
represent “x is a parent,” and M(x, y) to represent “x is the mother of y.” The
original statement can be represented as ∀x ((F (x) ∧ P(x)) → ∃y M(x, y)).
 Express the statement “Everyone has exactly one best friend” as a
logical expression involving predicates, quantifiers with a domain
consisting of all people, and logical connectives.
 When we introduce the predicate B(x, y) to be the statement “y is the best friend of x,” the
statement that x has exactly one best friend can be represented as ∃y (B(x, y) ∧ ∀z ((z ≠
y)→¬B(x, z))). Consequently, our original statement can be expressed as ∀x ∃y (B(x, y)
∧ ∀z ((z ≠ y)→¬B(x, z))).
4 9/19/2022
Translating English Sentences into Logical
Expressions
 Use quantifiers to express the statement “There is a woman who
has taken a flight on every airline in the world.”
 Let P(w, f ) be “w has taken f ” and Q(f, a) be “f is a flight on a.” We can express the
statement as ∃w ∀a ∃f (P(w, f ) ∧ Q(f, a)), where the domains of discourse
for w, f , and a consist of all the women in the world, all airplane flights, and all
airlines, respectively.
5 9/19/2022
Translating from Nested Quantifiers to
English
 Translate the statement ∀x(C(x) ∨ ∃y(C(y) ∧ F(x, y))) into English,
where C(x) is “x has a computer,” F(x, y) is “x and y are friends,”
and the domain for both x and y consists of all students in your
school.
 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.
 Translate the statement ∃x∀y∀z((F (x, y) ∧ F(x, z) ∧ (y ≠
z))→￢F(y,z)) into English, where F(a, b) means a and b are
friends and the domain for x, y, and z consists of all students in
your school.
 There is a student x such that for all students y and all students z other than y, if
x and y are friends and x and z are friends, then y and z are not friends. In other
words, there is a student none of whose friends are also friends with each other.
6 9/19/2022

Nested Quantifiers

Uploaded by

Copyright:

Available Formats

Nested Quantifiers

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Nested Quantifiers

Uploaded by

Copyright:

Available Formats

Logic & Proofs

Dr. Nirnay Ghosh

You might also like