FOL 05 · Translating English into FOL
The #1 rule
∀ goes with →, ∃ goes with ∧
English FOL ❌ Common wrong version All S are P — says everything is S and P Some S are P — true if anything at all is not S No S is P ≡ Not all S are P ≡
Why?
- ∀ with ∧ forces everyone in the domain to be an S — almost never intended.
- ∃ with → is almost always true trivially: pick any x that isn’t an S and the implication is vacuously true.
Memory — " All-Arrow, Some-and"
The domain choice changes the formula
“Every student of XYZ University has studied DM.”
- Domain = students of XYZ:
- Domain = all people: with P(x): x is a student of XYZ
- Two-place predicate S(x, y): “x has studied subject y”:
“Some students in XYZ have studied DM.”
- Domain = students of XYZ:
- Domain = all people:
Slide examples
Lions (domain: all creatures)
P(x): lion, Q(x): fierce, R(x): drinks coffee
- All lions are fierce →
- Some lions do not drink coffee →
- Some fierce creatures do not drink coffee →
(This argument is actually valid: the lion that doesn’t drink coffee is fierce.)
Hummingbirds (domain: all birds)
P(x): hummingbird, Q(x): large, R(x): lives on honey, S(x): richly colored
- All hummingbirds are richly colored →
- No large birds live on honey → ≡
- Birds that do not live on honey are dull in color →
- ∴ Hummingbirds are small →
"None of my friends are perfect" (GATE 2013)
Translation traps
Watch these words
- “and” in the subject means or in the formula: “Gold and silver ornaments are precious” = anything gold or silver is precious → . (GATE 2009) Same for “Tigers and lions attack…” (GATE 2006).
- “Only S are P” = — the arrow flips (like “only if”).
- “Not every” / “not all” = , NOT .
- “None / no one” = or .
- “A / an” can mean ∀ (“A dog is loyal” = all dogs) or ∃ (“A dog bit me” = some dog). Use context.
🏠 Slide homework — solved
"There is a student who has taken more than 21 credit hours in a semester and received all A's."
Domain: students. Let : x took more than 21 credit hours in a semester, : x received all A’s: More precise (same semester): with ranging over semesters, .
Prev ← FOL 04 Negating Quantifiers · Next → FOL 06 Nested Quantifiers