3.2: Disjunctive Normal Form
- Page ID
- 83410
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?
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 \land 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' \land y'\) is true). So take the disjunction of these two conjunctions: \(p(x,y) = (x \land y) \lor (x' \land y')\text{.}\)
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.
a Boolean polynomial in variables \(x_1,x_2,\ldots,x_n\) which is the disjunction of distinct terms of the form \(a_1 \land a_2 \land \cdots \land a_n\text{,}\) where each \(a_i\) is either \(x_i\) or \(x_i'\text{.}\)
The zero polynomial is also considered to be in disjunctive normal form.
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.
Given a truth table with nonzero output, we may obtain a Boolean polynomial in disjunctive normal form with that truth table as follows.
- Identify rows the in truth table for which the desired output is \(1\)
- For each such row, form the conjunction of all variables, but negate those variables that have input value \(0\) for that row.
- Form a polynomial by taking the disjunction of all those conjunctions.
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 \land y' \land z'\text{;}\)
fifth row
\(x' \land y \land z\text{;}\)
seventh row
\(x' \land y' \land z\text{;}\) and
eigth row
\(x' \land y' \land z'\text{.}\)
Therefore, the Boolean polynomial
is both in disjunctive normal form and will have the desired truth table.
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 \land y \land z\text{;}\)
second row
\(x \land y \land z'\text{;}\)
fourth row
\(x \land y' \land z'\text{;}\)
fifth row
\(x' \land y \land z\text{;}\)
sixth row
\(x' \land y \land z'\text{;}\)
seventh row
\(x' \land y' \land z\text{;}\) and
eigth row
\(x' \land y' \land z'\text{.}\)
Therefore, the Boolean polynomial
\begin{align*} q(x,y,z) & = (x \land y \land z) \lor (x \land y \land z') \lor (x \land y' \land z') \lor (x' \land y \land z)\\ & \phantom{=} \lor (x' \land y \land z') \lor (x' \land y' \land z) \lor (x' \land y' \land 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 \land y' \land z)' = x' \lor y \lor z' \end{equation*}
will produce the desired truth table.
The polynomials in the solutions to the preceding examples are in disjunctive normal form, but the alternative solution to the second example is not.
From Procedure \(\PageIndex{1}\), it is easy to see that any Boolean polynomial can be expressed in disjunctive normal form.
Rewrite the Boolean polynomial \(p(x,y,z) = (x \land z)' \lor (x'\land y)\) in disjunctive normal form.
Solution
First, produce the truth table.
| \(x\) | \(y\) | \(z\) | \(x\land z\) | \(x' \land 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) =& (x \land y \land z') \lor (x \land y' \land z') \lor (x' \land y \land z)\\ & \lor (x' \land y \land z') \lor (x' \land y' \land z) \lor (x' \land y' \land 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?
- Hint
-
Extend the idea of the Alternative solution for Worked Example \(\PageIndex{3}\)