Skip to main content

Subsection 6.1.4 Multiply Nested Quantifiers

We’ve already seen a lot of examples that exploit multiply nested quantifiers. But we’ll do a few more here for practice.

When you use multiple quantifiers, keep the following things in mind:

  • If the quantifiers are the same, it doesn’t matter what order you write them in.

  • If they are different, it does matter. In particular:

  • ∃x (∀y (P(x, y)) means that there must be at least one x such that P(x, y) holds for every y.

  • ∀y (∃x (P(x, y)) means that there may be a different x for each y.

Exercises Exercises

1.

We want to encode the fact that any color that isn’t black has a darker version. To say this precisely, we need to exploit some terminology that is standard in describing colors:

  • Hue: Where the color is on the color wheel. Hues include red, blue, green, and yellow.

  • Brightness (also called value): The amount of light. 100 is maximum (i.e., white). 0 is none (i.e., black).

  • Saturation: The purity of the color. Think of low saturation as being greyer than high saturation.

Define one predicate:

Color(x): True if x is a color.

And define these functions, which are defined for colors:

hue(x): The hue of x.

brightness(x): The brightness of x. White will have 100 as its value. Black will have 0.

saturation(x): The saturation of x. Clear colors will have 100 as their value. Greyer colors will have lower values.

Which (one or more) of the following logical expressions encodes our claim?

I. ∀x ((Color(x) ∧ (brightness(x) ≠ 0)) → ∃y (Color(y) ∧ (hue(y) = hue(x)) ∧

(saturation(y) = saturation(x)) ∧

(brightness(y) < brightness(x))))

II. ∀x ((Color(x) ∧ (brightness(x) = 0)) → ¬∃y (Color(y) ∧ (hue(y) = hue(x)) ∧

(saturation(y) = saturation(x)) ∧

(brightness(y) < brightness(x))))

III. ∃x (Color(x) ∧ ∀y (Color(y) → ((hue(y) = hue(x)) ∧ (saturation(y) = saturation(x)) ∧ (brightness(y) > brightness(x)))))

  1. Just I.

  2. Just II.

  3. Just III.

  4. Just I and II.

  5. Just II and III.

Answer.
Correct answer is A.
Solution.
Explanation: I is correct. It says that, if x isn’t black, then there exists a color with the same hue and saturation but lower brightness (i.e., it’s darker). II says that if x is black then there doesn’t exist a darker color. That happens to be true, but it’s not the claim that we said we wanted to make. III says that there exists a color such that all other colors have the same hue and saturation as it but are brighter than it. This is clearly false.

2.

Suppose that we want to encode the following definition:

Anything anyone eats and isn’t killed by is food.

Define: Food(x): True if x is a food.

Eats(x, y) True if x eats y.

KilledBy(x, y): True if x is killed by y.

Consider the following statements:

I. ∀x ((∃y (Eats(y, x) ∧ ¬KilledBy(y, x))) → Food(x))

II. ∀x (∃y ((Eats(y, x) ∧ ¬KilledBy(y, x)) ∨ Food(x)))

III. ∀x (∀y ((¬Eats(y, x) ∨ KilledBy(y, x)) ∨ Food(x)))

Which (one or more) of those statements corresponds to our definition of food?

  1. Just I.

  2. Just II.

  3. Just III.

  4. I and II.

  5. II and III.

Answer.
Correct answer is E.
Solution.
Explanation: I and III are correct. Read I as: For every x, if there exists a y who eats x and isn’t killed by it, then x must be a food. Read III as: For every x and every y, either y doesn’t eat x or is killed by it or x must be a food. II is a little hard to make sense of. Read it as: For every x, either there exists a y such that y eats x and isn’t killed by it, or x must be a food. To see why this one has a different meaning than the other two, consider Tree. Assume no one eats trees. Then neither is it the case that there exists someone who eats trees and lives to tell about it, nor are trees food. So the statement is false. Contrast with, say, III. Again, assume that no one eats trees. Then since we have a three part disjunction and the first part is true, the complete statement is true.

3.

We want to encode a policy of our bank: Every loan without collateral has at least two signers. Define:

Loan(x): True if x is a loan.

Collat(x): True if there is collateral for x.

Signer(x, y): True if x signed y.

Which (one or more) of the following logical expressions encodes our claim?

I. ¬∃x (Loan(x) ∧ Collat(x) ∧ (∃y, z (Signer(y, x) ∧ Signer(z, x) ∧ (y ≠ z))))

II. ∀x ((Loan(x) ∧ ¬Collat(x)) → (∃y, z (Signer(y, x) ∧ Signer(z, x) ∧ (y ≠ z))))

III. ∃y, z (∃x (Loan(x) ∧ ¬Collat(x) ∧ Signer(y, x) ∧ Signer(z, x) ∧ (y ≠ z)))

  1. Just I.

  2. Just II.

  3. Just III.

  4. I and II.

  5. II and III.

Answer.
Correct answer is B
Solution.
Explanation: II is correct. It says that if x is an uncollateralized loan then there exist two distinct signers. I says that there doesn’t exist a collateralized loan that has at least two signers. III says that there exists an uncollateralized loan with two distinct signers.

4.

Define:

Loan(x): True if x is a loan.

Collat(x): True if there is collateral for x.

Signer(x, y): True if x signed y.

Match each logical expression:

  1. ∃x (∀y (Loan(y) → Signer(x, y)))

  2. ∀x (∀y (Signer(x, y) → Loan(y)))

  3. ∀x (Loan(x) → ∃y (Signer(x, y)))

  4. ∃x (∀y (¬Signer(x, y) ∨ ¬Loan(y)))

  5. ∀x (∃y (Loan(y) ∧ Signer(x, y)))

  6. ∃x (¬∃y (Loan(x) ∧ Signer(y, x)))

To its corresponding English sentence:

  1. There’s at least one unsigned loan.

  2. There’s someone who has signed every loan.

  3. There’s no one who hasn’t signed a loan.

  4. The only signed things are loans.

  5. All loans have been signed.

  6. There’s someone who hasn’t signed any loans.

Answer.

x (y (Loan(y)  Signer(x, y))) There’s someone who has signed every loan.

x (y (Signer(x, y)  Loan(y))) The only signed things are loans.

x (Loan(x)  y (Signer(y, x))) All loans have been signed.

x (y (Signer(x, y)  Loan(y))) There’s someone who hasn’t signed any loans.

x (y (Loan(y)  Signer(x, y))) There’s no one who hasn’t signed a loan.

x (y (Loan(x)  Signer(y, x))) There’s at least one unsigned loan.

5.

We want to encode the claim that no one likes anyone who doesn’t tell the truth. Define:

Likes(x, y): True if x likes y.

TruthTeller(x): True if x is a truth teller.

Which (one or more) of the following logical expressions encodes our claim?

I. ∀x (∀y ((¬TruthTeller(y) → ¬Likes(x, y)))

II. ∀x (¬∃y (¬TruthTeller(y) ∧ Likes(x, y)))

III. ¬∃x (∃y (¬TruthTeller(y) ∧ Likes(x, y)))

  1. Just I.

  2. Just II.

  3. Just III.

  4. Just I and III.

  5. All three.

Answer.
Correct answer is E.
Solution.
Explanation. All three are equivalent and correct. Perhaps the most obviously correct one is I. For any pair (of people, assuming that people are the relevant universe), if y isn’t a truth teller, x doesn’t like him. You should be able to derive II and then III from that using identities.