1.5Quantifiers and first-order translation
The idea
Quantifiers talk about a whole domain: ∀x P(x) says P holds for every x, ∃x P(x) says it holds for at least one. The order of nested quantifiers changes the meaning.
Think of it like this: "Everyone has a mother" (∀∃) is true; "someone is everyone's mother" (∃∀) is not.
Why it exists
English-to-logic translation and quantifier-order questions are the typical first-order-logic marks.
How it works
- Negation flips the quantifier: ¬∀x P ≡ ∃x ¬P and ¬∃x P ≡ ∀x ¬P.
- "All A are B" → ∀x (A(x) → B(x)). "Some A is B" → ∃x (A(x) ∧ B(x)).
- ∃y ∀x P(x, y) implies ∀x ∃y P(x, y), but not the reverse.
- ∀ distributes over ∧, ∃ distributes over ∨; the other way round fails.
Worked example: "Some students are not smart"
It is ∃x (S(x) ∧ ¬M(x)). It is the negation of "all students are smart", ∀x (S(x) → M(x)).
Now play with it
- →Load "everyone loves someone" and see ∀∃ true while ∃∀ is false.
- →Flip cells until both orders become true.
Domain {1, 2, 3}. Click a cell to flip P(x, y). Rows are x, columns are y.
| x \ y | 1 | 2 | 3 |
|---|---|---|---|
| 1 | F | T | F |
| 2 | F | F | T |
| 3 | T | F | F |
Look: ∀x ∃y is true but ∃y ∀x is false. The order of quantifiers matters; the converse of "∃∀ ⇒ ∀∃" fails.
| English | First-order logic | Common wrong version |
|---|---|---|
| All students are smart | ∀x (S(x) → M(x)) | ∀x (S(x) ∧ M(x)) |
| Some student is smart | ∃x (S(x) ∧ M(x)) | ∃x (S(x) → M(x)) |
| No student is smart | ∀x (S(x) → ¬M(x)) ≡ ¬∃x (S(x) ∧ M(x)) | ¬∀x (S(x) → M(x)) |
| Not every student is smart | ∃x (S(x) ∧ ¬M(x)) | ∀x (S(x) → ¬M(x)) |
| Everyone has a friend | ∀x ∃y F(x, y) | ∃y ∀x F(x, y) |
| There is one person everybody likes | ∃y ∀x L(x, y) | ∀x ∃y L(x, y) |
The partner of ∀ is →, the partner of ∃ is ∧. Using the other partner is the most common error.
Check yourself
Which expresses "No student is smart"?
Exam notes (the dense version)
∀x P(x) is true if P holds for every element of the domain; ∃x P(x) if for at least one. Negation: ¬∀x P ≡ ∃x ¬P and ¬∃x P ≡ ∀x ¬P. Translating: "all A are B" is ∀x (A(x) → B(x)); "some A is B" is ∃x (A(x) ∧ B(x)). Order matters: ∃y ∀x P(x,y) ⇒ ∀x ∃y P(x,y), but not the other way round. ∀ distributes over ∧, ∃ distributes over ∨, but not vice versa.
Previous year questions: Propositional & First-Order Logic (25)
PYQs are grouped by topic, so this is the full set for Propositional & First-Order Logic; try the ones that match this subtopic. Open all 25 on the topic page.