FOL 07 · Translating & Negating Nested Quantifiers
5-step method (slides)
- Read and understand the statement.
- Fix the domain of discourse.
- Find the quantifiers needed.
- Rewrite the sentence so domain and quantifiers are visible (“For every … if … then …”).
- Introduce variables and write the formula.
Slide examples
"The sum of two positive integers is always positive." (domain: integers)
Rewrite: “For every two integers x, y, if x and y are positive then x + y is positive.”
"A negative real number does not have a square root that is a real number." (domain: reals)
Rewrite: “For every real x, if x is negative then there is no real y with x = y².”
"Every student of XYZ has a computer or has a friend who has a computer." (domain: XYZ students)
C(x): x has a computer, F(x, y): x and y are friends.
"Every teacher is liked by some student." (GATE 2005)
- ∃y with → (option A) — wrong, ∃ needs ∧.
- (option C) says “some one student likes all teachers” — stronger, wrong.
- (option D) says “everyone is a teacher” — wrong. Also correct:
“Exactly one” — uniqueness
"Everyone has exactly one best friend." B(x, y): y is the best friend of x
is not enough — x could have several best friends. Add “nobody other than y is x’s best friend”: Shorthand with the uniqueness quantifier:
General template
More counting templates (at least two, at most one) → FOL 10 Beyond the Slides.
Negating nested quantifiers
Apply single-quantifier De Morgan repeatedly, outside in. Each ¬ flips one quantifier as it passes.
Negate so no ¬ precedes a quantifier
— “some x has no multiplicative inverse” (true over reals: x = 0).
"Someone has visited every country except Libya." V(x, y): x has visited country y
Negation: (uses ) English: “Everyone has either visited Libya or missed at least one country other than Libya.” ⚠️ The slide’s English (“has not visited any other country except Libya”) is too strong — the negation only needs one missed country, not all.
"No one has climbed every mountain in the Himalayas." C(x, y): x climbed mountain y
≡ Negation: — “Someone has climbed every mountain in the Himalayas.”
🏠 Slide homework — solved
Negate "There is a student in this class who has taken every mathematics course offered at this school."
Domain x: students in this class, y: courses. M(y): y is a maths course offered here, T(x, y): x has taken y. Original: Negation: English: “Every student in this class has missed at least one mathematics course offered at this school.”
Prev ← FOL 06 Nested Quantifiers · Next → FOL 08 Resolution