Translating From Nested Quantifiers Into English

Translating from Nested Quantifiers into English: Expressions with nested quantifiers expressing statements in English can be quite complicated. The first step in translating such an expression is to write out what the quantifiers and predicates in the expression mean. The next step is to express this meaning in a simpler sentence.

EXAMPLE 1 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.
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.

EXAMPLE 2 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.
Solution: We first examine the expression (F (x, y) ∧ F(x, z) ∧ (y = z))→¬F(y, z). This expression 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. It follows that the original statement, which is triply quantified, says that 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.

Translating English Sentences into Logical Expressions
Quantifiers can be used to translate sentences into logical expressions. However, we avoided sentences whose translation into logical expressions required the use of nested quantifiers.We now address the translation of such sentences.

EXAMPLE 3 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.
Solution: The statement “If a person is female and is a parent, then this person is someone’s mother” 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.” 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)) → ∃yM(x, y)).
Using the null quantification rule in part (b) of Exercise 47 in Section 1.4, 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)).

EXAMPLE 4 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.
Solution: The statement “Everyone has exactly one best friend” can be expressed as “For every person x, person x has exactly one best friend.” Introducing the universal quantifier, we see that this statement is the same as “∀x(person x has exactly one best friend),” where the domain consists of all people.

To say that x has exactly one best friend means that there is a person y who is the best friend of x, and furthermore, that for every person z, if person z is not person y, then z is not the best friend of x. 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))).

Negating Nested Quantifiers: Statements involving nested quantifiers can be negated by successively applying the rules for negating statements involving a single quantifier. This is illustrated in Examples 14–16.

EXAMPLE 5 Express the negation of the statement ∀x∃y(xy = 1) so that no negation precedes a quantifier.
Solution: By successively applying De Morgan’s laws for quantifiers we can move the negation in ¬∀x∃y(xy = 1) inside all the quantifiers. We find that ¬∀x∃y(xy = 1) is equivalent to ∃x¬∃y(xy = 1), which is equivalent to ∃x∀y¬(xy = 1). Because ¬(xy = 1) can be expressed more simply as xy = 1, we conclude that our negated statement can be expressed as ∃x∀y(xy = 1).

EXAMPLE 6 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: This statement is the negation of the statement “There is a woman who has taken a flight on every airline in the world” from Example 13. By Example 13, our statement can be expressed as ¬∃w∀a∃f (P(w, f ) ∧ Q(f, a)), where P(w, f ) is “w has taken f ” and Q(f, a) is “f is a flight on a.” By successively applying De Morgan’s laws for quantifiers to move the negation inside successive quantifiers and by applying De Morgan’s law for negating a conjunction in the last step, we find that our statement is equivalent to each of this sequence of statements:
∀w¬∀a∃f (P(w, f ) ∧ Q(f, a)) ≡ ∀w∃a¬∃f (P(w, f ) ∧ Q(f, a))
≡ ∀w∃a∀f¬(P (w, f ) ∧ Q(f, a))
≡ ∀w∃a∀f (¬P(w, f )∨¬Q(f, a)).
This last statement states “For every woman there is an airline such that for all flights, this woman has not taken that flight or that flight is not on this airline.”