FOL 14 · Memory Tricks & Traps

🧠 Memory tricks

To rememberTrick
∀ 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 / ∃ trueOne counterexample kills ∀; one witness proves ∃
Nested orderGame: ∀ = 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 ⇒ weakerSeparate ∀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 rulesInstantiate = 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