Predicate Logic & Quantifiers
∴Why This Matters
Propositional logic can't express "All humans are mortal" or "Some birds can't fly". Predicate logic adds quantifiers and predicates to handle these structures—the same structures you use in SQL queries every day.
Predicates
Mortal(x) is true if x is mortal.Quantifiers
Universal: ∀
∀x P(x)
"For all x, P(x) is true"
SQL equivalent:
NOT EXISTS (... WHERE NOT P)
Existential: ∃
∃x P(x)
"There exists an x where P(x) is true"
SQL equivalent:
EXISTS (SELECT * WHERE P)
Negating Quantifiers
¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)
"Not all are P" = "At least one is not P"
"None exist with P" = "All lack P"
SQL Parallels
| Logic | English | SQL Pattern |
|---|---|---|
| ∃x P(x) | Some x has P | WHERE ... LIMIT 1 |
| ∀x P(x) | All x have P | NOT EXISTS (... WHERE NOT P) |
| ∀x(A(x)→B(x)) | All A are B | NOT EXISTS (A WHERE NOT B) |
?Quick Check
∀x∃y Loves(x,y) vs ∃y∀x Loves(x,y) — are these the same?
✦Tip
When reading nested quantifiers, work outside-in. The outer quantifier has the larger scope.