Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 3.2 Disjunctive normal form

It is often desired (e.g. in computer programming or logic circuit design) to reverse the process: starting with a desired truth table, can we construct a Boolean polynomial with the same outputs?

Worked Example 3.2.1.

Determine a Boolean polynomial \(p(x,y)\) that has the truth table below.
\(x\) \(y\) \(p(x,y)\)
\(1\) \(1\) \(1\)
\(1\) \(0\) \(0\)
\(0\) \(1\) \(0\)
\(0\) \(0\) \(1\)
Solution.
We want a “true” output when the inputs match the first or fourth rows, and only then. The inputs match the first row precisely when both \(x\) and \(y\) are true (i.e. when the conjunction \(x \lgcand y\) is true), and they match the fourth row precisely when both \(x\) is not true and \(y\) is not true (i.e. when the conjunction \(x' \lgcand y'\) is true). So take the disjunction of these two conjunctions: \(p(x,y) = (x \lgcand y) \lgcor (x' \lgcand y')\text{.}\)

Remark 3.2.2.

In the solution to the above worked example, it might seem like we should take a conjunction of the two conjunctions instead of a disjunction, since we see an output of \(1\) in the first row and in the fourth row. However, we cannot be in the input “state” described by those two rows simultaneously, since neither \(x\) nor \(y\) can be both \(1\) and \(0\) simultaneously. So you should think of it this way instead: if we see an output state of \(1\text{,}\) then we know we must be either in the input state of the first row or of the fourth row.
disjunctive normal form
a Boolean polynomial in variables \(x_1,x_2,\dotsc,x_n\) which is the disjunction of distinct terms of the form \(a_1 \lgcand a_2 \lgcand \dotsb \lgcand a_n\text{,}\) where each \(a_i\) is either \(x_i\) or \(x_i'\text{.}\)

Convention 3.2.3.

The zero polynomial is also considered to be in disjunctive normal form.

Note 3.2.4.

Disjunctive normal form is usually not the “nicest” or “simplest” Boolean polynomial with a desired truth table, but there is a relatively simple procedure to produce it.

Worked Example 3.2.6.

Determine a Boolean polynomial \(p(x,y,z)\) that has the truth table below.
\(x\) \(y\) \(z\) \(p(x,y,z)\)
\(1\) \(1\) \(1\) \(0\)
\(1\) \(1\) \(0\) \(0\)
\(1\) \(0\) \(1\) \(0\)
\(1\) \(0\) \(0\) \(1\)
\(0\) \(1\) \(1\) \(1\)
\(0\) \(1\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(1\)
\(0\) \(0\) \(0\) \(1\)
Solution.
The fourth, fifth, seventh, and eigth rows have outcome \(1\text{.}\) The corresponding conjunctions are
fourth row
\(x \lgcand y' \lgcand z'\text{;}\)
fifth row
\(x' \lgcand y \lgcand z\text{;}\)
seventh row
\(x' \lgcand y' \lgcand z\text{;}\) and
eigth row
\(x' \lgcand y' \lgcand z'\text{.}\)
Therefore, the Boolean polynomial
\begin{equation*} p(x,y,z) = (x \lgcand y' \lgcand z') \lgcor (x' \lgcand y \lgcand z) \lgcor (x' \lgcand y' \lgcand z) \lgcor (x' \lgcand y' \lgcand z') \end{equation*}
is both in disjunctive normal form and will have the desired truth table.

Worked Example 3.2.7.

Determine a Boolean polynomial \(q(x,y,z)\) that has the truth table below.
\(x\) \(y\) \(z\) \(q(x,y,z)\)
\(1\) \(1\) \(1\) \(1\)
\(1\) \(1\) \(0\) \(1\)
\(1\) \(0\) \(1\) \(0\)
\(1\) \(0\) \(0\) \(1\)
\(0\) \(1\) \(1\) \(1\)
\(0\) \(1\) \(0\) \(1\)
\(0\) \(0\) \(1\) \(1\)
\(0\) \(0\) \(0\) \(1\)
Solution 1.
Every row except the third has outcome \(1\text{,}\) so we must form conjunctions for all rows except that one:
first row
\(x \lgcand y \lgcand z\text{;}\)
second row
\(x \lgcand y \lgcand z'\text{;}\)
fourth row
\(x \lgcand y' \lgcand z'\text{;}\)
fifth row
\(x' \lgcand y \lgcand z\text{;}\)
sixth row
\(x' \lgcand y \lgcand z'\text{;}\)
seventh row
\(x' \lgcand y' \lgcand z\text{;}\) and
eigth row
\(x' \lgcand y' \lgcand z'\text{.}\)
Therefore, the Boolean polynomial
\begin{align*} q(x,y,z) \amp = (x \lgcand y \lgcand z) \lgcor (x \lgcand y \lgcand z') \lgcor (x \lgcand y' \lgcand z') \lgcor (x' \lgcand y \lgcand z)\\ \amp \phantom{=} \lgcor (x' \lgcand y \lgcand z') \lgcor (x' \lgcand y' \lgcand z) \lgcor (x' \lgcand y' \lgcand z') \end{align*}
is both in disjunctive normal form and will have the desired truth table.
Solution 2. Alternative solution
We can get a much simpler expression for \(q(x,y,z)\) by not using the procedure (though of course the result will not be in disjunctive normal form).
Notice that we want the third row to have output value \(0\text{.}\) In logic terms, we want that combination (and only that combination) of input values to result in an output that is “not true”. So the Boolean polynomial
\begin{equation*} q(x,y,z) = (x \lgcand y' \lgcand z)' = x' \lgcor y \lgcor z' \end{equation*}
will produce the desired truth table.

Note 3.2.8.

The polynomials in the solutions to the preceding examples are in disjunctive normal form, but the alternative solution to the second example is not.

Worked Example 3.2.10. Converting a polynomial into disjunctive normal form.

Rewrite the Boolean polynomial \(p(x,y,z) = (x \lgcand z)' \lgcor (x'\lgcand y)\) in disjunctive normal form.
Solution.
First, produce the truth table.
\(x\) \(y\) \(z\) \(x\lgcand z\) \(x' \lgcand y\) \(p(x,y,z)\)
1 \(1\) \(1\) \(1\) \(0\) 0
1 \(1\) \(0\) \(0\) \(0\) 1
1 \(0\) \(1\) \(1\) \(0\) 0
1 \(0\) \(0\) \(0\) \(0\) 1
0 \(1\) \(1\) \(0\) \(1\) 1
0 \(1\) \(0\) \(0\) \(1\) 1
0 \(0\) \(1\) \(0\) \(0\) 1
0 \(0\) \(0\) \(0\) \(0\) 1
Then apply the disjunctive normal form procedure to obtain
\begin{align*} p(x,y,z) \amp = (x \lgcand y \lgcand z') \lgcor (x \lgcand y' \lgcand z') \lgcor (x' \lgcand y \lgcand z)\\ \phantom{p(x,y,z)} \amp \phantom{= (} \lgcor (x' \lgcand y \lgcand z') \lgcor (x' \lgcand y' \lgcand z) \lgcor (x' \lgcand y' \lgcand z')\text{.} \end{align*}

Check your understanding.

What do you think conjunctive normal form should mean? Can you come up with a procedure which takes a truth table and determines a Boolean polynomial in conjunctive normal form with the desired truth table?
<Prev^TopNext>