FOL 15 · Cheat Sheet (one-page revision)

Quantifiers

True whenFalse whenFinite domain
every xone counterexample
one witnessno x works

Restricted: ·

Translation

EnglishFOL
All S are P
Some S are P
No S is P
Not all S are P
Only S are P
A and B are P
Exactly one P
At most one P
At least two P

Negation

· ·

Equivalences

✅ Equivalent⇒ only (one way)
⚠️

Counter-model: domain {a, b}, P = (T, F), Q = (F, T).

Nested quantifiers

∀∀ and ∃∃ commute · ∀∃ vs ∃∀ don’t · ∃y∀x ⇒ ∀x∃y

over ℝx + y = 0x · y = 0
∀x∀yFF
∀x∃yTT
∃y∀xFT
∃x∃yTT

Inference

RuleFormCondition
UI∀xP(x) ∴ P(c)any c
UGP(c) ∴ ∀xP(x)c arbitrary
EI∃xP(x) ∴ P(c)c fresh
EGP(c) ∴ ∃xP(x)—
Univ. MP∀x(P→Q), P(c) ∴ Q(c)
Univ. MT∀x(P→Q), ¬Q(c) ∴ ¬P(c)

Resolution

· premises + ¬conclusion ⊢ □ ⇒ valid · one pair per step

Counting

Unary predicate on n elements: interpretations · binary:


Back to hub → FOL README