Worked Examples
Quantifiers and their SQL equivalents.
1Worked Example
Problem
Translate: "Every student has at least one advisor."
Domain: students. A(x,y) = y advises x.
Domain: students. A(x,y) = y advises x.
1
"Every student" → Universal quantifier over students: ∀x
2
"Has at least one advisor" → Existential over advisors: ∃y A(x,y)
3
Answer:
∀x ∃y A(x,y)4
SQL:
NOT EXISTS (
SELECT * FROM students s
WHERE NOT EXISTS (
SELECT * FROM advises WHERE student_id = s.id
)
)2Worked Example
Problem
What's the negation of "All birds can fly"?
Let B(x) = bird, F(x) = can fly.
Let B(x) = bird, F(x) = can fly.
1
Original:
∀x(B(x) → F(x))2
Negate:
¬∀x(B(x) → F(x))3
Push negation in:
∃x ¬(B(x) → F(x))4
Simplify ¬(P→Q) = P ∧ ¬Q:
∃x(B(x) ∧ ¬F(x))5
English: "Some bird can't fly" (penguins, ostriches!)
3Worked Example
Problem
Distinguish: ∀x∃y L(x,y) vs ∃y∀x L(x,y) where L = "loves"
1
∀x∃y L(x,y): For each person x, there exists someone y that x loves.
2
English: "Everyone loves someone" (possibly different people)
3
∃y∀x L(x,y): There exists a person y such that everyone loves y.
4
English: "There's someone everyone loves" (same person!)
⚠
Watch Out!
Quantifier order MATTERS. The outer quantifier's variable can depend on inner choices.