Existence of Conjunctive Normal Form of Statement

From ProofWiki
Jump to navigation Jump to search

Theorem

Any propositional formula can be expressed in conjunctive normal form (CNF).


Proof

A propositional variable is already trivially in conjunctive normal form (CNF).

So we consider the general propositional formula $S$.


First we convert to negation normal form (NNF).

This is always possible, by Existence of Negation Normal Form of Statement.


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:

  • Literals;
  • Statements of the form $\left({Q_1 \lor Q_2 \lor \ldots \lor Q_n}\right)$

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

Otherwise they will be of the form $Q_j = \left({R_1 \land R_2 \land \ldots \land R_m}\right)$

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

$Q_1 \lor Q_2 \lor \ldots \lor \left({R_1 \land R_2 \land \ldots \land R_m}\right) \ldots \lor Q_n$

into:

\(\displaystyle \) \(\) \(\displaystyle \left({Q_1 \lor Q_2 \lor \ldots \lor Q_n \lor R_1}\right)\)
\(\displaystyle \) \(\land\) \(\displaystyle \left({Q_1 \lor Q_2 \lor \ldots \lor Q_n \lor R_2}\right)\)
\(\displaystyle \) \(\land\) \(\displaystyle \ldots\)
\(\displaystyle \) \(\land\) \(\displaystyle \left({Q_1 \lor Q_2 \lor \ldots \lor Q_n \lor R_m}\right)\)

It is taken for granted that Disjunction is Associative and Disjunction is Commutative.


It can be seen then that each of the

$\left({Q_1 \lor Q_2 \lor \ldots \lor Q_n \lor R_k}\right)$

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$


Sources