FOL 04 · Negating Quantified Expressions
De Morgan’s laws for quantifiers
| Statement | Negation | Negation 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
| Statement | Negation |
|---|---|
| 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)
| Statement | FOL | Negation (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.
- “All dogs have fleas.”
👁 Show answer
“Some dog does not have fleas.” ()
- “There is a horse that can add.”
👁 Show answer
“No horse can add.” ()
- “No rabbit knows calculus.”
👁 Show answer
“Some rabbit knows calculus.” ()
Prev ← FOL 03 Quantifier Equivalences · Next → FOL 05 Translating English