Logical Equivalences with Quantifiers
What you'll learn: You'll discover how quantifiers can be rearranged and combined using specific logical rules, just like we did with propositional logic.
The Core Idea
Just as we learned that propositions have equivalence laws (like De Morgan's Laws, Distributive Laws), quantified statements also follow certain equivalence rules. These rules let us transform complex predicate logic expressions into simpler or more useful forms without changing their meaning.
Key Equivalences
Distribution of Negation (Already Familiar!)
You've seen how negation flips quantifiers:
¬∀x P(x)≡∃x ¬P(x)(Not everyone likes pizza ≡ Someone doesn't like pizza)¬∃x P(x)≡∀x ¬P(x)(Nobody likes broccoli ≡ Everyone dislikes broccoli)
Commuting Quantifiers of the Same Type
When quantifiers are the same type, they can swap positions:
∀x ∀y P(x, y)≡∀y ∀x P(x, y)(Everyone likes everyone ≡ Everyone is liked by everyone)∃x ∃y P(x, y)≡∃y ∃x P(x, y)(Someone knows someone ≡ Someone is known by someone)
Warning: Mixing ∀ and ∃ does not commute! ∀x ∃y Loves(x, y) ("everyone loves someone") is NOT the same as ∃y ∀x Loves(x, y) ("there's someone everyone loves").
Distribution of Quantifiers Over Logical Operators
∀x (P(x) ∧ Q(x))≡∀x P(x) ∧ ∀x Q(x)(Everyone is tall AND smart ≡ Everyone is tall, and everyone is smart)∃x (P(x) ∨ Q(x))≡∃x P(x) ∨ ∃x Q(x)(Someone is tall OR smart ≡ Someone is tall, or someone is smart)
Key Takeaway: Quantifiers follow specific equivalence rules: same-type quantifiers commute, negation flips quantifiers (De Morgan's for quantifiers), and some logical operators distribute over quantifiers—letting you transform and simplify predicate logic expressions systematically.