Negating Quantified Statements (Predicate-Logic De Morgan)

Intuition

Negating a first-order sentence is purely mechanical: move $\neg$ rightward through the whole prefix, flipping each quantifier as it passes, until it lands on the atomic predicate, then negate the connectives inside. "Not everyone is happy" becomes "someone is unhappy"; nothing needs cleverness — only the swap rules below.

The two quantifier rules (De Morgan for $\forall,\exists$)

$\neg\,\forall x\,P(x) \;\equiv\; \exists x\,\neg P(x), \qquad \neg\,\exists x\,P(x) \;\equiv\; \forall x\,\neg P(x).$ Apply them repeatedly, left to right, so every $\forall$ in the prefix becomes $\exists$ and vice versa, in the same order. For example: $\neg\,\forall x\,\exists y\,\forall z\,Q \;\equiv\; \exists x\,\forall y\,\exists z\,\neg Q.$

Negating the connectives inside

Once $\neg$ reaches the matrix, use ordinary propositional De Morgan:

The implication line is the one most people miss: $\neg(p\to q)\equiv p\wedge\neg q$ — a conjunction, never another implication.

Bounded / restricted quantifiers

"All $A$'s are $B$" and "some $A$ is $B$" hide an implication and a conjunction; their negations swap the two:

Equivalently, the shorthand forms obey $\neg\,\forall x\!\in\! S\,P(x)\equiv\exists x\!\in\! S\,\neg P(x)$ and $\neg\,\exists x\!\in\! S\,P(x)\equiv\forall x\!\in\! S\,\neg P(x)$ — the domain restriction $x\in S$ is untouched; only the quantifier and the body flip.

Worked mini-example

Negate "not all humans are intelligent" is really asking for $\neg\big(\forall x\,(A(x)\to B(x))\big)$ where $A$ = human, $B$ = intelligent: $\neg\,\forall x\,(A(x)\to B(x)) \;\equiv\; \exists x\,\neg(A(x)\to B(x)) \;\equiv\; \exists x\,(A(x)\wedge\neg B(x)),$ read "there is a human who is not intelligent." A wrong-but-tempting answer keeps the implication as $\exists x\,(A(x)\to\neg B(x))$ — a vacuously-true statement about non-humans, so it is not equivalent.

Application: negating a compound definition

Definitions built from several quantifiers negate the same way. A function $f:A\to B$ is bijective iff injective $\wedge$ surjective, so its negation is a disjunction of the two failures: $\neg(\text{inj}\wedge\text{surj}) \equiv \neg(\text{inj})\vee\neg(\text{surj}).$

• Injective $\forall a,a'\,(a\neq a'\to f(a)\neq f(a'))$ negates (via $\neg(p\to q)$) to $\exists a,a'\,(a\neq a'\wedge f(a)=f(a'))$ — "two distinct inputs collide."
• Surjective $\forall b\,\exists a\,(f(a)=b)$ negates (flip both quantifiers in order) to $\exists b\,\forall a\,(f(a)\neq b)$ — "some target is never hit."

Pitfall: Two classic traps. (1) When negating $p\to q$ inside a $\forall$, it becomes $p\wedge\neg q$, not $p\to\neg q$. (2) Flip each quantifier's type in order — $\neg\,\forall b\,\exists a$ is $\exists b\,\forall a$, never $\forall a\,\exists b$ — and remember a negated $\wedge$ turns into $\vee$.