FOL 15 · Cheat Sheet (one-page revision)
Quantifiers
| True when | False when | Finite domain | |
|---|---|---|---|
| every x | one counterexample | ||
| one witness | no x works |
Restricted: ·
Translation
| English | FOL |
|---|---|
| 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 = 0 | x · y = 0 |
|---|---|---|
| ∀x∀y | F | F |
| ∀x∃y | T | T |
| ∃y∀x | F | T |
| ∃x∃y | T | T |
Inference
| Rule | Form | Condition |
|---|---|---|
| UI | ∀xP(x) ∴ P(c) | any c |
| UG | P(c) ∴ ∀xP(x) | c arbitrary |
| EI | ∃xP(x) ∴ P(c) | c fresh |
| EG | P(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