Negating Quantified Statements
What You'll Learn
You'll learn how negation flips universal quantifiers (∀) into existential quantifiers (∃) and vice versa—De Morgan's laws for quantifiers.
The Core Idea
When you negate a quantified statement, the quantifier switches types:
- Negating "for all" (∀) gives "there exists" (∃)
- Negating "there exists" (∃) gives "for all" (∀)
Think of it like disagreeing with sweeping claims:
- If someone says "All students passed the exam," you disprove it by finding just one student who failed.
- If someone says "Some student failed," you disprove it by showing every student passed.
The Rules
De Morgan's Laws for Quantifiers:
-
¬(∀x P(x))is equivalent to∃x ¬P(x)- "Not all x satisfy P" = "There exists an x that doesn't satisfy P"
-
¬(∃x P(x))is equivalent to∀x ¬P(x)- "There doesn't exist an x satisfying P" = "All x don't satisfy P"
Examples
Original: ∀x (x > 0)
"All numbers are positive"
Negated: ∃x ¬(x > 0) or ∃x (x ≤ 0)
"There exists a number that is not positive"
Original: ∃x (x is even)
"Some number is even"
Negated: ∀x ¬(x is even) or ∀x (x is odd)
"All numbers are odd"
Why It Matters
In algorithms and proofs, you often need to disprove statements. Knowing how to correctly negate quantifiers helps you construct counterexamples and logical arguments.
Key Takeaway: Negation flips the quantifier (∀ ↔ ∃) and negates the predicate—just like De Morgan's laws flip AND/OR in Boolean logic.