FOL 07 · Translating & Negating Nested Quantifiers

5-step method (slides)

  1. Read and understand the statement.
  2. Fix the domain of discourse.
  3. Find the quantifiers needed.
  4. Rewrite the sentence so domain and quantifiers are visible (“For every … if … then …”).
  5. 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


Prev ← FOL 06 Nested Quantifiers · Next → FOL 08 Resolution