Disjunctive Normal Form of Any Statement

Theorem

Any statement form can be expressed in disjunctive normal form (DNF).

Proof

A simple statement is already trivially in disjunctive normal form (DNF).

So we consider the general compound statement $S$.

First we convert to negation normal form (NNF).

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

Now $S$ will be of the form:

$P_1 \lor P_2 \lor \cdots \lor P_n$

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

• Literals;
• Statements of the form $\left({Q_1 \land Q_2 \land \ldots \land 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 \lor R_2 \lor \ldots \lor R_m}\right)$

If the latter is the case, then use the Rule of Distribution to convert:

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

into:

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

It can be seen then that each of the

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

are terms in the DNF expression required.

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

$\blacksquare$

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Exercises: Group $\text{III}: 43$