To disprove a claim you must know exactly what its negation says. For quantified statements the rule is short, and it comes straight from De Morgan's laws.
Key idea
$\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$ and $\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$. To negate, move the $\neg$ past the quantifier, switch the quantifier, and negate what is inside.
Why it works
On a domain $\{a, b, c\}$, $\forall x\, P(x)$ is $P(a) \wedge P(b) \wedge P(c)$. De Morgan turns its negation into $\neg P(a) \vee \neg P(b) \vee \neg P(c)$: at least one fails, which is $\exists x\, \neg P(x)$. The same argument, with "or" and "and" swapped, gives the second rule. In plain words: "not everyone" means "someone doesn't," and "nobody" means "everyone doesn't."
| Statement | Negation |
|---|---|
| Every dog in the park is on a leash. | At least one dog in the park is not on a leash. |
| Some student turned in the homework. | No student turned in the homework. |
| No light in the house is on. | At least one light in the house is on. |
Worked examples
Worked example: Negating a symbolic statement
Negate $\forall x\, (x > 0 \to x^{2} > x)$ and simplify.
- Switch the quantifier: $\exists x\, \neg(x > 0 \to x^{2} > x)$.
- Negate the conditional: $\neg(A \to B) \equiv A \wedge \neg B$. So we get $\exists x\, (x > 0 \wedge x^{2} \le x)$.
- Over the real numbers, $x = \frac{1}{2}$ is a witness: $\frac{1}{2} > 0$ and $\frac{1}{4} \le \frac{1}{2}$. So the negation is true, and the original statement is false.
Answer: $\exists x\, (x > 0 \wedge x^{2} \le x)$
Worked example: Which one is true?
Negate "Every prime number is odd." Which is true: the statement or its negation?
- The negation is "Some prime number is not odd," that is, at least one prime is even.
- $2$ is prime and even, so the negation is true.
- So the original statement is false, and $2$ is the witness.
Answer: The negation is true (because of $2$).
Worked example: Negating "no"
Negate "No integer is both even and odd."
- "No integer is both even and odd" is $\forall n\, \neg(E(n) \wedge O(n))$.
- Its negation is $\exists n\, (E(n) \wedge O(n))$: "Some integer is both even and odd."
- That negation is false, so the original is true. You will prove it later by contradiction.
Answer: Some integer is both even and odd.
Common mistake
Negating "all are" as "none are." The negation of "every dog is on a leash" is not "no dog is on a leash." One dog off the leash is enough to make the original false. Check: the negation must be true in exactly the situations where the original is false. If both "every dog is leashed" and your "negation" can be false at once (say, half the dogs are leashed), you have not found the negation.