5.1 Predicates and Quantifiers
Propositional logic cannot express "every prime greater than 2 is odd" — it has no way to talk about all or some objects. A predicate P(x) is a statement containing variables that becomes a proposition once values are substituted or the variables are quantified over a domain (universe of discourse).
| Quantifier | Notation | Reading | True when | False when |
|---|---|---|---|---|
| Universal | ∀x P(x) | "for all x, P(x)" | P holds for every domain element | at least one counterexample exists |
| Existential | ∃x P(x) | "there exists x with P(x)" | at least one witness exists | P fails for every element |
Over a finite domain {a1, ..., an}: ∀x P(x) ≡ P(a1) ∧ ... ∧ P(an) and ∃x P(x) ≡ P(a1) ∨ ... ∨ P(an) — quantifiers are giant conjunctions/disjunctions.
The domain matters. ∀x (x^2 ≥ x) is true over Z but false over R (take x = 0.5: 0.25 < 0.5).
5.2 Translation Patterns (and the Classic Trap)
| English | Correct Logic | Wrong Version |
|---|---|---|
| "All lions are fierce" | ∀x (Lion(x) → Fierce(x)) | ∀x (Lion(x) ∧ Fierce(x)) — claims everything is a lion |
| "Some students are smart" | ∃x (Student(x) ∧ Smart(x)) | ∃x (Student(x) → Smart(x)) — true even with no students |
| "No CS student fails" | ∀x (CS(x) → ¬Fails(x)) | equivalently ¬∃x (CS(x) ∧ Fails(x)) |
Rule of thumb: ∀ pairs with →, ∃ pairs with ∧.
5.3 Negating Quantifiers (Generalized De Morgan)
- ¬∀x P(x) ≡ ∃x ¬P(x) — "not everyone" means "someone fails".
- ¬∃x P(x) ≡ ∀x ¬P(x) — "no one" means "everyone fails".
To negate nested quantifiers, push ¬ inward flipping every quantifier it passes: ¬∀x∃y P(x, y) ≡ ∃x∀y ¬P(x, y).
5.4 Worked Example 1 — Nested Quantifiers and Order
Let the domain be Z and consider P(x, y): x + y = 0.
- ∀x∃y (x + y = 0): for each x choose the witness y = −x ∈ Z. True.
- ∃y∀x (x + y = 0): demands one fixed y that works for every x simultaneously. If y worked for x = 0 then y = 0, but then 1 + 0 ≠ 0. False.
- Conclusion: ∀∃ and ∃∀ are not interchangeable. (Over the domain N, even statement 1 fails: for x = 1 the required y = −1 ∉ N.)
- Negation practice: ¬∀x∃y (x + y = 0) ≡ ∃x∀y (x + y ≠ 0) — "some x has no additive inverse", exactly the sentence that is true over N.
5.5 Rules of Inference
| Rule | Schema |
|---|---|
| Modus Ponens | p → q, p ⊢ q |
| Modus Tollens | p → q, ¬q ⊢ ¬p |
| Hypothetical Syllogism | p → q, q → r ⊢ p → r |
| Disjunctive Syllogism | p ∨ q, ¬p ⊢ q |
| Addition / Simplification | p ⊢ p ∨ q; p ∧ q ⊢ p |
| Universal Instantiation (UI) | ∀x P(x) ⊢ P(c) for any c in the domain |
| Universal Generalization (UG) | P(c) for arbitrary c ⊢ ∀x P(x) |
| Existential Instantiation (EI) | ∃x P(x) ⊢ P(c) for some fresh name c |
| Existential Generalization (EG) | P(c) ⊢ ∃x P(x) |
5.6 Worked Example 2 — A Formal Deduction
Argument: "Every CS student knows logic. Everyone who knows logic can debug. Priya is a CS student. Therefore Priya can debug."
Let C(x): x is a CS student, L(x): x knows logic, D(x): x can debug.
- ∀x (C(x) → L(x)) — premise
- ∀x (L(x) → D(x)) — premise
- C(Priya) — premise
- C(Priya) → L(Priya) — UI on (1)
- L(Priya) — Modus Ponens (3), (4)
- L(Priya) → D(Priya) — UI on (2)
- D(Priya) — Modus Ponens (5), (6) ∎
This mechanical style is exactly how Prolog resolves queries and how proof assistants (Coq, Lean) check software correctness.
5.7 Common Mistakes & CS Applications
- Using EI with a name already in use — the witness must be fresh.
- Applying UG to a constant that was not arbitrary (e.g., one obtained from EI).
- Swapping quantifier order as if it were harmless (Example 1 shows it is not).
- Applications: SQL's EXISTS/NOT EXISTS are ∃/¬∃ over rows; ∀ is expressed via double negation (NOT EXISTS ... NOT ...); loop invariants are ∀-statements over iterations; array-bounds verification is ∀i (0 ≤ i < n → safe(a[i])).
🎯 Exam Focus
- Let P(x): "x > 3", with domain R. Determine the truth values of ∀x P(x), ∃x P(x), ∃x ¬P(x).
- Translate into predicate logic: "Every student in this class has visited Delhi or Mumbai."
- Negate and simplify: ∀x∃y (x < y). What does the negation assert about the domain?
- Determine, with justification, the truth of ∀x∃y (x·y = 1) over R and over R − {0}.
- Show using rules of inference: premises p → q, ¬q, p ∨ r entail r. Name every rule.
- Explain with an example why ∃x (P(x) ∧ Q(x)) is not implied by ∃x P(x) ∧ ∃x Q(x).