Reduction of any Boolean function to disjunctive normal form.

Question

How can any Boolean function be reduced to disjunctive normal form ? With examples it's clear, but can anyone help me with a general proof ? Thanks in advance.

Answer 1

Any Boolean function, no matter how complex, can be expressed with $\land$, $\lor$, and $\neg$.

To demonstrate this, consider the fact that any Boolean function can be represented by a truth-table. For example, suppose we have a Boolean function whose truth-conditions are given by the following table:

\begin{array}{ccc|c} P&Q&R&f(P,Q,R)\\ \hline T&T&T&F\\ T&T&F&T\\ T&F&T&F\\ T&F&F&T\\ F&T&T&T\\ F&T&F&F\\ F&F&T&F\\ F&F&F&F\\ \end{array}

This function is true in row $2$, where $P$ and $Q$ are True, but $R$ is False. As such, we can 'capture' this row by the term $P \land Q \land \neg R$. The function is also true in rows $4$ and $5$, for which the corresponding terms are $P \land \neg Q \land \neg R$ and $\neg P \land Q \land R$ respectively.

Note that each of these terms 'picks out' (i.e. is true in ) exactly the row that we used to generate the term, as shown by the truth-table below.

\begin{array}{ccc|c|c|c} P&Q&R&P \land Q \land \neg R&P \land \neg Q \land \neg R&\neg P \land Q \land R\\ \hline T&T&T&F&F&F\\ T&T&F&\color{red}T&F&F\\ T&F&T&F&F&F\\ T&F&F&F&\color{red}T&F\\ F&T&T&F&F&\color{red}T\\ F&T&F&F&F&F\\ F&F&T&F&F&F\\ F&F&F&F&F&F\\ \end{array}

Hence, the disjunction of all these terms:

$$(P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R)$$

should give us back the original function, as shown below:

\begin{array}{ccc|c} P&Q&R&(P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R)\\ \hline T&T&T&F\\ T&T&F&\color{red}T\\ T&F&T&F\\ T&F&F&\color{red}T\\ F&T&T&\color{red}T\\ F&T&F&F\\ F&F&T&F\\ F&F&F&F\\ \end{array}

Now, this is just an example, but I think it should be clear that you can follow this same process for any truth-function. That is, generate a term, which is a conjunction of literals, for each row where the function evaluates to $T$. And then disjunct all these terms together for the final expression. There is one special case: if there is no row where the function evaluates to $T$, then just use the expression $P \land \neg P$,

The result is a generalized disjunction, where each disjunct is a generalized conjunction of literals, and is therefore in Disjunctive Normal Form (DNF). Note the special case of $P \land \neg P$ is in DNF as well, as it can be seen as a generalized disjunction with only one disjunct that is a conjunction of two literals. Thus, every Boolean function can be put into DNF.

Now, just for completeness, I also want to point out that you can follow a similar procedure to put any Boolean function into CNF.

Let's go back to the original example function and its truth-table, but now focus on the cases where the function evaluates to False, rather than True. As such, we see the function is False exactly when:

$$(P \land Q \land R) \lor (P \land \neg Q \land R) \lor (\neg P \land Q \land \neg R) \lor (\neg P \land \neg Q \land R) \lor (\neg P \land \neg Q \land \neg R)$$

is True. But that means that the function is true exactly when:

$$\neg [(P \land Q \land R) \lor (P \land \neg Q \land R) \lor (\neg P \land Q \land \neg R) \lor (\neg P \land \neg Q \land R) \lor (\neg P \land \neg Q \land \neg R)]$$

is True. By DeMorgan, this is equivalent to:

$$(\neg P \lor \neg Q \lor \neg R) \land (\neg P \lor Q \lor \neg R) \land (P \lor \neg Q \lor R) \land (P \lor Q \lor \neg R) \land (P \lor Q \lor R)$$

and that expression is in CNF.

In fact, once you see the pattern here, you don't have to explicitly go through the whole process of doing DeMorgan's. Instead, when generating the terms, implicitly use DeMorgan's already. For example, with the function being False in row where, where $P$, $Q$, and $R$ are all true, generate a term that is the exact opposite of what you would do for the DNF: generate the term $\neg P \lor \neg Q \lor \neg R$. And again, do this for all rows, and then just conjunct all terms together at the end. Done!

Answer 2

The function that returns $1$ for one specific combination of inputs and $0$ otherwise can be expressed using a multi-input AND gate (which itself can be replaced with chained two-input AND gates). The inputs to this AND gate are the function inputs, but an input that is $0$ in the combination producing $1$ is negated.

Any function can then be expressed as the OR of these subcircuits over every input combination that produces $1$, i.e. a disjunctive normal form.