FOL 14 · Memory Tricks & Traps
🧠 Memory tricks
| To remember | Trick |
|---|---|
| ∀ pairs with →, ∃ pairs with ∧ | “All-Arrow, Some-and” |
| ∀ / ∃ over finite domains | ∀ = big AND, ∃ = big OR |
| Distribution | ”∀ loves ∧, ∃ loves ∨” — matching pairs distribute, mismatched don’t |
| De Morgan for quantifiers | ”Push ¬ through, flip the quantifier” ∀ ↔ ∃ |
| Negating restricted statements | → and ∧ swap when ¬ passes: ¬∀(S→P) = ∃(S∧¬P) |
| ∀ false / ∃ true | One counterexample kills ∀; one witness proves ∃ |
| Nested order | Game: ∀ = opponent, ∃ = you, play left to right; you see earlier moves |
| ∃y∀x vs ∀x∃y | ”One-for-all beats each-has-one”: ∃y∀x ⇒ ∀x∃y |
| ∀x∃y | ”y may depend on x" |
| "and” in a subject | ”Tigers and lions” = tiger OR lion |
| ”only” | Only flips the arrow (same as “only if”) |
| Stronger ⇒ weaker | Separate ∀s (∀P ∨ ∀Q) are stronger; joint ∃ (∃(P∧Q)) is stronger |
| Quantifier pulled from an antecedent | ”Leaving the left side flips”: ∀x(P(x)→A) = ∃xP(x)→A |
| Inference rules | Instantiate = drop the quantifier, Generalize = add it; UG needs arbitrary, EI needs fresh |
| Resolution | ”Cancel ONE clash, OR the rest”; refute by adding ¬conclusion |
⚠️ Edge cases & traps
Domain
- Truth depends on the domain: is F over positive integers, T over integers.
- is T over integers but F over reals (x = ½).
- Standard FOL assumes a non-empty domain. If empty: ∀ is T, ∃ is F.
- : F over naturals (x = 0), T over integers.
Translation
- ∀ with ∧ (“∀x(S ∧ P)”) claims everything is an S — almost always wrong.
- ∃ with → (“∃x(S → P)”) is true whenever something isn’t an S — almost always wrong.
- “Gold and silver ornaments” / “tigers and lions” → ∨ in the antecedent.
- “Not every S is P” = ∃(S ∧ ¬P) — NOT ∀(S → ¬P) (that’s “no S is P”).
- “None of” = ¬∃(… ∧ …).
- “Only S are P” = ∀x(P → S).
- “Most / many / few” are not FOL quantifiers.
- Apply ∀/→ and ∃/∧ at each nesting level separately (GATE 2004).
Equivalences
- ∀x(P ∨ Q) ≢ ∀xP ∨ ∀xQ. ∃x(P ∧ Q) ≢ ∃xP ∧ ∃xQ.
- ∀x(P → Q) ⇒ (∀xP → ∀xQ) is valid, the converse is not (GATE IT 2005).
- (∀xP ↔ ∀xQ) does NOT give ∀x(P ↔ Q).
- Pulling a quantifier out of an antecedent flips it.
- Same letter under two quantifiers = two different variables.
- — the second x is free (scope ends early).
Nested quantifiers
- ∀x∃y ≠ ∃y∀x. Only ∃y∀x ⇒ ∀x∃y.
- Same-type quantifiers commute (∀∀, ∃∃); mixed ones don’t.
- ∃y∀x is true only if there’s a universal y (like 0 for multiplication).
- ∀x∃y B(x, y) does not mean “exactly one” — add uniqueness.
- “At most one” is true when none exist.
Negation
- Negate nested quantifiers one at a time, outside in.
- is used in “except” statements (Libya example).
- The negation of “visited every country except Libya” needs only one missed country — not “visited none”.
Resolution
- Resolve on exactly one complementary pair per step.
- “Neither s nor t” = ¬s ∧ ¬t = two clauses (the slides’ Superman problem gets this wrong).
- Always add the negated conclusion, not the conclusion.
Inference
- UG only from an arbitrary element — never from a specific one (“Socrates is mortal” ⇏ “everyone is mortal”).
- EI must use a fresh constant — two ∃ statements give two different constants.
- Universal affirming the conclusion (Ria example) is a fallacy.
Prev ← FOL 13 Flashcards · Next → FOL 15 Cheat Sheet