Nested Quantifiers: Maria Tamoor

Nested Quantifiers
Maria Tamoor
Nested quantifiers
Nested quantifiers commonly occur in mathematics and
computer science.
Nested quantifiers, where one quantifier is within the scope
of another, such as
Assume that the domain for the variables x and y consists of all
real numbers. The statement
∀x∀y(x + y = y + x) says that x + y = y + x for all real numbers
x and y. This is the commutative law for addition
of real numbers. Likewise, 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.
This states that every real number has an additive inverse.
Translate into English the statement
∀x∀y((x > 0) ∧ (y < 0) → (xy < 0))
where the domain for both variables consists of all real
numbers.
“The product of a positive real number and a negative
real number is always a negative real number.”
Let Q(x, y) denote “x + y = 0.” What are the truth values of the
quantifications ∃y∀xQ(x, y) and ∀x∃yQ(x, y), where the domain
for all variables consists of all real numbers?
∃y∀xQ(x, y) denotes the proposition
“There is a real number y such that for every real number x, Q(x,
y).”
so its false
∀x∃yQ(x, y)
denotes the proposition
“For every real number x there is a real number y such that Q(x,
y).”
so its true
“The sum of two positive integers is always positive”
into a logical expression.
∀x∀y((x > 0) ∧ (y > 0) → (x +y > 0)),
where the domain for both variables consists of all
integers
Nesting of Quantifiers
Example: Let the u.d. of x & y be people.

Let L(x,y)=“x likes y” (a predicate with two free
variables)
Then ∃y L(x,y) =
“There is someone whom x likes.” (A predicate w. 1
free variable, x)
Then ∀x (∃y L(x,y)) =
“Everyone has someone whom they like.” (A
proposition with 0 free variables.)
Quantifier Exercise
If R(x,y)=“x relies upon y,” express the
following in unambiguous English:
∀x(∃y R(x,y))=
∃y(∀x R(x,y))=
∃x(∀y R(x,y))=
∀y(∃x R(x,y))=
∀x(∀y R(x,y))=
Quantifier Exercise
If R(x,y)=“x relies upon y,” express the following in
unambiguous English:
∀x(∃y R(x,y))= Everyone has someone to rely on.
∃y(∀x R(x,y))= There’s someone whom
everyone relies upon
∃x(∀y R(x,y))= There’s some person who relies
upon everybody.
∀y(∃x R(x,y))= Everyone has someone who relies
upon them.
∀x(∀y R(x,y))=Everyone relies upon everybody.
For each of these statements find a domain for which
the
statement is true and a domain for which the statement is
false.
a) Everyone speaks Hindi.
b) There is someone older than 21 years.
c) Every two people have the same first name.
Quantifier Equivalence Laws
Definitions of quantifiers: If u.d.=a,b,c,…

∀x P(x) ⇔ P(a) ∧ P(b) ∧ P(c) ∧ …
∃x P(x) ⇔ P(a) ∨ P(b) ∨ P(c) ∨ …
From those, we can prove the laws:
¬ (∀x P(x)) ⇔ ∃x ¬P(x)
¬ (∃x P(x)) ⇔ ∀x ¬P(x)
Quantifier Equivalence Laws
∀x ∀y P(x,y) ⇔ ∀y ∀x P(x,y)

∃x ∃y P(x,y) ⇔ ∃y ∃x P(x,y)
∀x (P(x) ∧ Q(x)) ⇔ (∀x P(x)) ∧ (∀x Q(x))
∃x (P(x) ∨ Q(x)) ⇔ (∃x P(x)) ∨ (∃x
Q(x))
Home work questions
Question # 5,6,7,13,14,15,21,26,27
Translate the statement into English
∀x(C(x) ∨ ∃y(C(y) ∧ F(x, y))) 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.
Solution
every student in your school has a computer or has a
friend who has a computer.
Example
“If a person is female and is a parent, then this person
is someone’s mother”
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)) → ∃yM(x, y)).
we can move ∃y to the left so that it appears just after
∀x, because y does not appear in F(x) ∧ P(x). We
obtain the logically equivalent expression
∀x∃y((F (x) ∧ P(x)) → M(x, y)).
truth value of each of these statements if the domain for all
variables consists of all integers.
a) ∀n∃m(n2 < m)
b) ∃n∀m(n < m2)
c) ∀n∃m(n + m = 0)
d) ∃n∀m(nm = m)
e) ∃n∃m(n2 + m2 = 5)
f ) ∃n∃m(n2 + m2 = 6)
g) ∃n∃m(n + m = 4 ∧ n − m = 1)
h) ∃n∃m(n + m = 4 ∧ n − m = 2)
i) ∀n∀m∃p(p = (m + n)/2)
Logic programming
Prolog (from Programming in Logic), developed in the
1970s by computer scientists working in the area of
artificial intelligence, is an example of such a language
consisting of two types of statements, Prolog facts
and Prolog rules. Prolog facts define predicates by
specifying the elements that satisfy these predicates.
Prolog rules are used to define new predicates using
those already defined by Prolog facts.
instructor(p, c) and enrolled(s, c) to represent that professor p is the
instructor of course c and that student s is enrolled in course c, respectively.
For example, the Prolog facts in such a program might include:
instructor(chan,math273)
instructor(patel,ee222)
instructor(grossman,cs301)
enrolled(kevin,math273)
enrolled(juana,ee222)
enrolled(juana,cs301)
enrolled(kiko,math273)
enrolled(kiko,cs301)
(Lowercase letters have been used for entries because Prolog considers names
beginning with an uppercase letter to be variables.)
A new predicate teaches(p, s), representing that
professor p teaches student s, can be defined using the
Prolog rule
teaches(P,S) :- instructor(P,C), enrolled(S,C) which
means that teaches(p, s) is true if there exists a class c
such that professor p is the instructor of class c and
student s is enrolled in class c.
?enrolled(kevin,math273) produces the response
yes
Examples
?enrolled(X,math273) produces the response
kevin
Kiko
similarly
?teaches(X,juana)
This query returns
patel
grossman

Nested Quantifiers: Maria Tamoor

Uploaded by

Copyright:

Available Formats

Nested Quantifiers: Maria Tamoor

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: Maria Tamoor

Uploaded by

Copyright:

Available Formats

Nested Quantifiers

Example: Let the u.d. of x & y be people.

Definitions of quantifiers: If u.d.=a,b,c,…

∀x ∀y P(x,y) ⇔ ∀y ∀x P(x,y)

You might also like