FOL 04 · Negating Quantified Expressions

De Morgan’s laws for quantifiers

StatementNegationNegation true when
some x makes P false
every x makes P false

Memory — " Push ¬ through, flip the quantifier"

¬ walks past a quantifier and flips it: ∀ ↔ ∃. Then keep pushing ¬ inside using propositional De Morgan (08 Logical Equivalences).

Slide reasoning

Domain: students of XYZ University, P(x): x has studied DM.

  • “Every student has studied DM” =
  • Negation: “It is not the case that every student has studied DM” = “There is some student who has not studied DM” =
  • “There is a student who has studied DM” =
  • Negation: “Every student has not studied DM” (= no student has) =

Examples

StatementNegation
All dogs bark.Some dogs do not bark.
There is a dog that barks.No dog barks.
No one is perfect. ()Someone is perfect. ()

"Most" is not FOL

The slides negate “Most cars are inexpensive” as if “most” meant ∃ (“some”), giving “all cars are not inexpensive”. That’s a simplification for the slide only. Standard FOL has only ∀ and ∃; “most”, “many”, “few” can’t be expressed. In GATE, read “most” as a red flag — the question will define what they mean.

Negating with conditions (very common in GATE)

StatementFOLNegation (no ¬ before a quantifier)
All S are P — some S is not P
Some S are P — no S is P
No S is P — some S is P

Note how → and ∧ swap when you negate

. The ∀/→ pair turns into the ∃/∧ pair — consistent with FOL 05 Translating English.


🏠 Slide homework — solved

Express the negation in English.

  1. “All dogs have fleas.”
  1. “There is a horse that can add.”
  1. “No rabbit knows calculus.”

Prev ← FOL 03 Quantifier Equivalences · Next → FOL 05 Translating English