Skip to main content

Subsection 4.1.10 Practice Using Nested Quantifiers

To use the language of logic effectively requires being able to translate back and forth between it and ideas (possibly expressed as sentences in English or some other natural language). It takes practice to be able to do that.

In particular, when we use nested quantifiers, the order in which we write them often (but not always – more on that later) matters.

Video cover image

Exercises Exercises

1.

1. Suppose that we’d like to describe one small piece of an ideal world and say that everyone has someplace to live. Assume the domain of people. Define:

AddressOf(x, y): True if x lives at address y.

Which (one or more) of the following statements say(s) that everyone has an address:

I. ∃x (∀y (AddressOf(x, y)))

II. ∀x (∃y (AddressOf(x, y)))

III. ∀x (∀y (AddressOf(x, y)))

IV. ∃x (∃y (AddressOf(x, y)))

  1. 1

  2. 2

  3. 3

  4. 4

Answer.
Correct answer is A.
Solution.
Explanation: I says that there exists someone (x) who lives everywhere. II is correct. III says that everyone lives everywhere. And IV says that someone lives somewhere.

2.

Bad Movie We want to claim that there’s a movie that everyone in our class hates. Define:

Movie(x): True if x is a movie.

InClass(x): True if x is in our class

Hates(x, y): True if x hates y.

Note: As you read these definitions, as well as the statements below, remember that variable names are arbitrary. We tend to reuse the same one-letter ones. The only thing that matters is that they be used consistently throughout an expression. So, for example, an equivalent definition of hates would be:

Hates(y, x): True if y hates x.

Which (one or more) of the following statements says that there’s a movie that everyone in our class hates:

  1. ∃x (Movie(x) ∧ ∀y (InClass(y) → Hates(y, x)))

  2. ∃x (Movie(x) ∧ ∀x (InClass(x) → Hates(x, x)))

  3. ∀x (Movie(x) → ∃y (InClass(y) → Hates(y, x)))

  4. ∀x (Movie(x) ∧ ∀y (InClass(y)) → Hates(y, x)))

  1. 1

  2. 2

  3. 3

  4. 4

Answer.
Correct answer is A.
Solution.
Explanation: I is correct. Read I as, “There exists something (x) such that x is a movie and, for all y, if y is in our class, then y hates x”. II uses the same variable name for a second quantifier inside the scope of the first one. III says that, for any movie, there exists someone in the class who hates it. But it need not be the same movie for everyone. IV says that everything is a movie and everyone in our class hates all movies.

3.

Suppose that we want to represent the fact that every pen has a color. Consider the following predicate logic expressions:

I. ∀x (Pen(x) → ∃y (ColorOf(y, x)))

II. ∃x (∀y (Pen(x) → ColorOf(y, x)))

III. ∀x (∀y (Pen(x) → ColorOf(y, x)))

IV. ∃x (∃y (Pen(x) → ColorOf(y, x)))

Which (one or more) of these expressions captures our fact?

  1. Just I.

  2. Just II.

  3. Just III.

  4. Two of them.

  5. All of them.

Answer.
Correct answer is A.
Solution.
Explanation: Only I says that, for every pen it has some color. II says that there exists a pen that has every color. III says that every pen has every color. And IV says that there exists a pen with a color.