It is often desired (for example, 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?
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 (that is, 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 (that is, when the conjunction \(x' \lgcand y' \) is true). So take the disjunction of these two conjunctions:
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,\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{.}\)
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.
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
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?
