Skip to main content

Subsection 5.1.6 Quantifier Exchange

We’ve already seen that we can get a lot of mileage out of our Boolean reasoning techniques. But not quite enough. To reason with quantified statements, we need one new pair of identities and four new inference rules.

First, we’ll introduce the two identities. They are variously called:

  • Quantifier exchange, or

  • Pushing nots through quantifiers.

Here are they are:

[Quantifier Exchange A] ¬(∀x (P(x))) \equiv ∃x (¬P(x))

[Quantifier Exchange B] ¬(∃x (P(x))) \equiv ∀x (¬P(x))

Let’s read these to see what they say:

  1. Suppose that we have that it’s not the case that P(x) is true for all values of x. An equivalent way of saying the same thing is that there must be at least one value of x for which it’s false.

  2. Suppose we have that there is no value of x for which P is true. An equivalent way of saying the same thing is that P(x) is false for all values of x.

As we work with logical expressions, we often want to “reduce the scope of nots.” By this we mean that we want nots to apply to simple subexpressions rather than complex ones. It’s often easier to work with the overall expression once it’s in that form. So one way that describes how these rules are often used is:

You can push a not rightward across a quantifier by doing two things:

  1. Flip the quantifier. In other words, ∀ becomes ∃ and ∃ becomes ∀. Then:

  2. Apply the not to the entire scope of the original quantifier.

For example, we might start with the claim that it’s not true that everyone is the mother of someone. Then we can reason as follows:

[1] \(\neg\) \(\forall\)x (\(\exists\)y (MotherOf(x, y))) Premise

[2] \(\neg\)x (\(\neg\)\(\exists\)y (MotherOf(x, y))) Quantifier Exchange [A] [1]

[3] \(\exists\)x (\(\forall\)y (\(\neg\)MotherOf(x, y))) Quantifier Exchange [B] [2]

To get [2], we pushed the not through \(\forall\text{,}\) which changed it to \(\exists\) and landed the \(\neg\) just inside the outermost parentheses. To get [3], we did a second quantifier exchange. This time we pushed the not through \(\exists\text{,}\) which changed it to \(\forall\) and landed the \(\neg\) just inside one more level of parenthesization.

Now we have the equivalent claim that there exists someone who fails to be the mother of every single person (assuming people is our domain).

Recall that we’ve already observed that:

  • The quantifier ∀ is a shorthand for a large conjunction. When we say ∀x (P(x)), what we’re really saying is:

[1] P(x1) ∧ P(x2) ∧ P(x3) ∧ … ∧ P(xn), where n is the number of objects in our domain.

  • The quantifier ∃ is a shorthand for a large disjunction. When we say ∃x (P(x)), what we’re really saying is:

[2] P(x1) ∨ P(x2) ∨ P(x3) ∨ … ∨ P(xn), where n is the number of objects in our domain.

When we look at the quantifiers in this way, what we see is that our quantifier exchange rules are simply giant versions of the Boolean De Morgan’s laws. Recall that those laws are:

[De Morgan 1] (¬(p ∧ q)) \equiv (¬p ∨ ¬q) Push not through and.

[De Morgan 2] (¬(p ∨ q)) \equiv (¬p ∧ ¬q) Push not through or.

As given here, each of De Morgan’s laws applies in the case of a conjunction or disjunction of exactly two terms. Suppose that the generalization to n (for any value of n) terms were true:

[Generalized De Morgan 1] (¬(p1 ∧ p2 ∧ p3 ∧ … ∧ pn)) \equiv (¬p1 ∨ ¬p2 ∨ ¬p3 ∨ … ∧ ¬pn)

[Generalized De Morgan 2] (¬(p1 ∨ p2 ∨ p3 ∨ … ∨ pn)) \equiv (¬p1 ∧ ¬p2 ∧ ¬p3 ∧ … ∧ ¬pn)

(Note that we’ve left out a lot of parentheses here. They’re not necessary since both and and or are associative. So we’ve used this more readable form rather than our usual, fully parenthesized one.) It turns out that both of these generalized claims are true. This can be proved straightforwardly using a proof technique called induction that we’ll consider later in this course. For now, assume that they’re true.

Now let’s rewrite our new Generalized De Morgan’s laws using quantifiers. Assume that our domain contains n objects and that P(x) is equivalent to the Boolean expression px. (For example, P(1) and p1 are just two ways of saying the same thing.)

Look at the left hand side of Generalized De Morgan 1. It’s the not of a large conjunction. Since the universal quantifier ∀ is a shorthand for a large conjunction, we can use it here. Our left hand side becomes:

¬∀x (P(x))

And the right hand side is simply a large disjunction (each term of which happens to be negated). Our shorthand for that is the existential quantifier ∃. So our right hand side becomes:

∃x (¬P(x))

Putting the two sides together and then doing a similar thing for Generalized De Morgan 2, we get:

[Quantified Generalized De Morgan 1] ¬∀x (P(x)) \equiv ∃x (¬P(x))

[Quantified Generalized De Morgan 2] ¬∃x (P(x)) \equiv ∀x (¬P(x))

Compare these two equivalences to the two Quantifier Exchange rules at the top of this slide. They look the same. There actually is one difference: we derived our Generalized De Morgan rules assuming some finite sized set (we called the size n). The Quantifier Exchange rules at the top of this slide, however, don’t make that assumption. They work for any size set, finite or infinite. That’s why they’re new rules for reasoning in predicate logic. They’re not just another way of writing something that we could have done in our Boolean framework.

So what we see now is that the Quantifier Exchange rules are generalizations to any size set, including infinite ones, of De Morgan’s laws.

Since Quantifier Exchange and De Morgan’s laws do the same thing, we’ll often see that it’s useful to combine them. In particular, if we apply Quantifier Exchange and are able to produce a wff that contains no more quantifiers, we may continue to simplify by treating the wff as a Boolean expression and applying De Morgan’s laws.

For example, suppose that we start with the (obviously true) statement that there’s no one who both hates chocolate and is trustworthy. Then we can reason as follows:

[1] \(\neg\) \(\exists\)x (Hates(x, Chocolate) \(\wedge\) Trustworthy(x)) Premise

[2] \(\forall\)x (\(\neg\)(Hates(x, Chocolate) \(\wedge\) Trustworthy(x))) Quantifier Exchange B [1]

[3] \(\forall\)x ( \(\neg\)Hates(x, Chocolate) \(\vee\) \(\neg\)Trustworthy(x)) (Boolean) De Morgan [2]

Now we’ve reduced the scope of not to individual predicates. We have derived a new universal rule: One doesn’t hate chocolate or one isn’t trustworthy

From now on, we’ll lump Quantifier Exchange A and Quantifier Exchange B together as a single identity called simply Quantifier Exchange.

Exercises Exercises

Exercise Group.

1.

Consider the plight of a poor talent scout for a musical. She moaned, “It’s hopeless. Everyone who tried out sounds like a cat in heat or has two left feet.” We’ll simplify a bit. Define:

S(x): True if x can sing. Alternatively: True if x does not sound like a cat in heat.

D(x): True if x can dance. Alternatively: True if x does not have two left feet.

Assume that x ranges over the set of people who tried out. Which one or more of the following expressions correspond(s) to the scout’s lament? (Hint: Write out one expression that captures the meaning. Then use the Quantifier Exchange rules to see what other expression(s) are equivalent to yours.)

I. ∀x (¬S(x) ∨ ¬D(x))

II. ∀x (¬(S(x) ∨ D(x)))

III. ¬∃x (S(x) ∧ D(x))

  1. Just I.

  2. Just II.

  3. Just III.

  4. I and II.

  5. I and III.

Answer.
Correct answer is E.
Solution.
Explanation: I says that everyone has the property that either they can’t sing or they can’t dance. III says that there doesn’t exist anyone who can both sing and dance. II is wrong. It says that everyone has the property that it’s not true that they can sing or dance. We didn’t say that. We assume that many (most) of the people can do one or the other.
2.

Consider this sign (often seen on the doors of greedy movie theaters). Exactly what does it mean? First, let’s assume that the adjective “outside” applies to both food and drink.

English Aside

Yet another way in which English suffers from a lack of explicit parentheses is that it’s ambiguous whether modifiers attach just to the thing they’re closest too or whether they have wider scope. In the case of our sign, we’re assuming (since this is consistent with maximum greediness) that the intent is:

• No outside (food or drink).

But suppose that we’d said, “No smelly food or drink.” Now (given the lack of smell of most drinks) the most likely interpretation is:

• No (smelly food) or drink.

Define:

Outside(x): True if x is from outside.

Food(x): True if x is food.

Drink(x): True if x is a drink.

Assume that the job of the sign is to make a claim that must be true of objects that are brought into the theater.

Which (one or more) of the following expressions correspond(s) to the intended meaning of this sign? (Hint: Write out one expression that captures the meaning. Then use the Quantifier Exchange rules to see what other expression(s) are equivalent to yours.)

I. ∀x (¬(Outside(x) ∧ (Food(x) ∨ Drink(x)))

II. ∀x (¬Outside(x) ∨ ¬(Food(x) ∨ Drink(x)))

III. ¬∃x (Outside(x) ∧ (Food(x) ∨ Drink(x)))

IV. ∀x (¬Outside(x) ∨ (¬Food(x) ∧ ¬Drink(x)))

  1. All except I.

  2. All except II.

  3. All except III.

  4. All except IV.

  5. All of them

Answer.
Correct answer is E.
Solution.
Explanation: They are all equivalent.
3.

Let the universe of discourse be the natural numbers. Let P(x, y) correspond to the claim that x > y. What are the truth values of each of the following expressions? Justify your answer.

  1. ∀x (∀y (P(x, y)))

  2. ∀x (∃y (P(x, y)))

  3. ∃x,y (P(x, y))

  4. ¬∃x (∀y (P(x, y)))

Answer.

  1. False

  2. False

  3. True

  4. True

Solution.

Explanation

  1. Explanation: We can show that a universal claim is false with a single counterexample. Let x = 1 and y = 2.

  2. Explanation. Let x = 1. Then there is no natural number that x is greater than.

  3. Explanation: Let x = 3 and y = 2.

  4. Explanation: Using Quantifier Exchange twice, we can rewrite this expression as:

    \(\neg \) \(\exists \) x (\(\forall \)y (P(x, y)))

    \(\forall \)x \(\neg \)(\(\forall \)y (P(x, y)))

    \(\forall \)x (\(\exists \)y \(\neg \)(P(x, y)))

    So we are claiming that for every x, there is some y such that x is not greater than y. That y can simply be x.

4.

Consider the following expression:

¬∃x (∀y (¬(P(x) ∨ Q(x)) ∧ ¬R(x, y)))

Using the Quantifier Exchange rules and the rules of Boolean logic, we can construct an equivalent expression that contains no instances of ¬.

Which of the following is such an expression:

  1. ∀x (∃y ((P(x) ∧ Q(x)) ∨ R(x, y)))

  2. ∀x (∃y ((P(x) ∨ Q(x)) ∨ R(x, y)))

  3. ∃x (∀y ((P(x) ∧ Q(x)) ∨ R(x, y)))

  4. ∃x (∀y ((P(x) ∨ Q(x)) ∨ R(x, y)))

  5. ∀x (∃y (P(x) ∧ (Q(x) ∨ R(x, y))))

Answer.
Correct answer is B.
Solution.

Explanation:

Using Quantifier Exchange twice, we get: \(\forall \)x (\(\exists \)y \(\neg \)(\(\neg \)(P(x) \(\vee \) Q(x)) \(\wedge \) \(\neg \)R(x, y)))

Using De Morgan, we get: \(\forall \)x (\(\exists \)y (\(\neg \)\(\neg \)(P(x) \(\vee \) Q(x)) \(\vee \) \(\neg \)\(\neg \)R(x, y)))

Using Double Negation twice, we get: \(\forall \)x (\(\exists \)y ((P(x) \(\vee \) Q(x)) \(\vee \) R(x, y)))

Notice that the \(\vee \) between P(x) and Q(x) doesn’t get converted to \(\wedge\) because we never push a \(\neg \) through the expression (P(x) \(\vee \) Q(x)). The original \(\neg \) outside it goes away with Double Negation.

5.

Prove that these two expressions are equivalent by using Quantifier Exchange, plus Boolean identities, to transform the first into the second:

[1] ¬∃x (∀y (∃z (P(x, y) ∧ P(y, z))))

[2] ∀x (∃y (∀z (P(x, y) → ¬P(y, z))))

Answer.
Querium ---PsQs50