FOL 03 · Equivalences Involving Quantifiers
Definition
Two statements with predicates and quantifiers are logically equivalent if they have the same truth value for every choice of predicates and every domain.
The two distributive equivalences
| ✅ Equivalent | ❌ NOT equivalent (only one direction holds) |
|---|---|
Memory — " ∀ loves ∧, ∃ loves ∨"
∀ is a big AND, so it merges with ∧. ∃ is a big OR, so it merges with ∨. Mismatched pairs don’t distribute.
Why the mismatched ones fail (slide counter-models)
Domain: students {Mark, Joe}. P(x): studied DM, Q(x): scored > 60%.
∀ over ∨: Mark studied DM but scored ≤ 60%; Joe didn’t study DM but scored > 60%.
| P (DM) | Q (>60%) | |
|---|---|---|
| Mark | ✓ | ✗ |
| Joe | ✗ | ✓ |
- : each student did at least one → T
- : not everyone did DM, not everyone scored → F
∃ over ∧: same table.
- : someone did DM (Mark), someone scored (Joe) → T
- : nobody did both → F
The one-way implications (valid directions)
| Valid ⇒ | Converse fails |
|---|---|
| ✗ | |
| ✗ | |
| ✗ (GATE IT 2005) | |
| ✗ | |
| ✗ (assuming a non-empty domain) |
Memory — " Separate is stronger for ∀∨; together is stronger for ∃∧"
- “Everyone did P, or everyone did Q” is a stronger claim than “everyone did P-or-Q”.
- “Someone did both” is stronger than “someone did P and someone did Q”. Stronger ⇒ weaker is always valid.
Testing an equivalence fast
Build a 2-element domain {a, b} and pick P, Q values that break it — exactly the Mark/Joe trick. Most GATE “which is valid” options die to a 2-element counter-model.
More rules (pulling quantifiers past constants, prenex form) → FOL 10 Beyond the Slides.
Prev ← FOL 02 Quantifiers · Next → FOL 04 Negating Quantifiers