Negation Normal Form of Any Statement

Theorem

Any statement form can be expressed in negation normal form (NNF).

Proof

A simple statement is already trivially in negation normal form (NNF).

So we consider the general compound statement $S$.

In the following, $P$ and $Q$ are to stand for general statement forms, simple or compound.

First, from Functionally Complete Logical Connectives we have that:

$\left\{{\neg, \land, \lor}\right\}$

forms a functionally complete set of logical connectives.

So we can convert $S$ so that:

• By the definition of material equivalence, instances of $P \iff Q$ can be converted into $\left({P \implies Q}\right) \land \left({Q \implies P}\right)$;
• By the rule of material implication, instances of $P \implies Q$ can be converted into $\neg P \lor Q$.

Other connectives can likewise be treated appropriately.

Thus $S$ will contain nothing but connectives from $\left\{{\neg, \land, \lor}\right\}$.

Next we can replace:

• Instances of $\neg \left({P \land Q}\right)$ with $\neg P \lor \neg Q$, by de Morgan;
• Instances of $\neg \left({P \lor Q}\right)$ with $\neg P \land \neg Q$, by de Morgan;
• Instances of $\neg \neg P$ with $P$ by Double Negation Elimination.

At any stage where a negation appears before a parenthesis, it will then appear before the statements inside the parenthesis.

Thus the negation signs gradually move inwards or are eliminated.

Eventually all remaining negation signs will appear next to simple statements.

Hence the result.

$\blacksquare$