Existence of Conjunctive Normal Form of Statement

Theorem

So we consider the general propositional formula $S$.

Now $S$ will be of the form:

$P_1 \land P_2 \land \cdots \land P_n$

where $P_1, P_2, \ldots, P_n$ are either:

or:

statements of the form $\paren {Q_1 \lor Q_2 \lor \ldots \lor Q_n}$.

If all the $Q_1, \ldots, Q_n$ are literals we have finished.

Otherwise they will be of the form:

$Q_j = \paren {R_1 \land R_2 \land \ldots \land R_m}$

If the latter is the case, then use the Disjunction Distributes over Conjunction to convert:

$Q_1 \lor Q_2 \lor \ldots \lor \paren {R_1 \land R_2 \land \ldots \land R_m} \ldots \lor Q_n$

into:

$\ds $

$\ds \paren {Q_1 \lor Q_2 \lor \ldots \lor Q_n \lor R_1}$

$\ds $

$\land$

$\ds \paren {Q_1 \lor Q_2 \lor \ldots \lor Q_n \lor R_2}$

$\ds $

$\land$

$\ds \ldots$

$\ds $

$\land$

$\ds \paren {Q_1 \lor Q_2 \lor \ldots \lor Q_n \lor R_m}$

It can be seen then that each of the

$\paren {Q_1 \lor Q_2 \lor \ldots \lor Q_n \lor R_k}$

are terms in the CNF expression required.

If any terms are still not in the correct format, then use the above operation until they are.

$\blacksquare$