Negation of Compound Statements and Quantifiers

Negating a compound statement correctly is a skill in its own right, because the negation must move inside the connectives, not merely sit in front of the whole sentence. The tools are De Morgan's laws, the conditional equivalence, and involution.

Negation of the basic compounds.

• Conjunction: $\sim(p \wedge q) \equiv \sim p \vee \sim q$ — "not (both $p$ and $q$)" means "$p$ is false or $q$ is false".
• Disjunction: $\sim(p \vee q) \equiv \sim p \wedge \sim q$ — "not (either $p$ or $q$)" means "both are false".
• Conditional: since $p \rightarrow q \equiv \sim p \vee q$, its negation is $\sim(p \rightarrow q) \equiv \sim(\sim p \vee q) \equiv p \wedge \sim q.$ So "it is not the case that if $p$ then $q$" means "$p$ holds and $q$ fails". This is the single most common negation asked, and the one most often got wrong.
• Biconditional: $\sim(p \leftrightarrow q) \equiv (p \wedge \sim q) \vee (\sim p \wedge q)$ — the two parts have different truth values.

Quantifiers. Many mathematical statements make a claim about all or some members of a set. The two quantifiers capture this:

• The universal quantifier $\forall$ reads "for all" / "for every". The statement $\forall x \in A,\ p(x)$ asserts that $p(x)$ is true for every $x$ in the set $A$.
• The existential quantifier $\exists$ reads "there exists" / "for some". The statement $\exists x \in A,\ p(x)$ asserts that $p(x)$ is true for at least one $x$ in $A$.

For example, over the set of natural numbers $\mathbb{N}$, the statement "$\forall x \in \mathbb{N},\ x + 1 > x$" is true, while "$\exists x \in \mathbb{N},\ x + 5 = 2$" is false (no natural number satisfies it). …