<< Chapter < Page | Chapter >> Page > |
In high school algebra, you saw that while $x^{3}-4x$ and $x(x-2)(x+2)$ are equivalent, the second form is particularly useful in letting you quickly know the roots of the equation.Similarly, in Boolean algebra there are certain canonicalnormalforms which have nice properties.
A formula in Conjunctive Normal Form , or CNF , is the conjunction of CNF clauses . Each clause is a formula of a simple form:a disjunction of possibly-negated propositions.
$c\implies (a\land b)$ is equivalent to $a\lor \neg c\land b\lor \neg c$ . This latter formula is in CNF, since it is the conjunction ofdisjunctions, and each disjunction consists only of propositions and negated propositions.
The conjunctions and disjunctions need not be binary. The following formula is also is CNF.
$\neg a\land a\lor b\lor \neg c\land b\lor \neg d\lor e\lor f$
Note that its first clause is just one negated proposition. It is still appropriate to think of this as a disjunction, since $\equiv \lor $ .
Another format, Disjunctive Normal Form , or DNF is the dual of conjunctive normal form. A DNF formula is the disjunction of DNF clauses , each a conjunction of possibly-negated propositions.
$(a\land b)\implies c$ is equivalent to $\neg a\lor \neg b\lor c$ which is in DNF: three disjunctions, each being a clause with only one term.(It also happens to be in CNFa single clause with three terms!) It is also equivalent to the more fleshed out DNF formulawhere we insist that each clause include all three variables. We end up with a formula that includes each possibleclause except $a\land b\land \neg c$ : That is, the formula $\left(a\land b\land c\right)\lor \left(a\land \neg b\land c\right)\lor \left(a\land \neg b\land \neg c\right)\lor \left(\neg a\land b\land c\right)\lor \left(\neg a\land b\land \neg c\right)\lor \left(\neg a\land \neg b\land c\right)\lor \left(\neg a\land \neg b\land \neg c\right)$ .
Any Boolean function can be represented in CNF and in DNF. One way to obtain CNF and DNF formulasis based upon the truth table for the function.
$a$ | $b$ | $c$ | Unknown function |
---|---|---|---|
$\mbox{false}$ | $\mbox{false}$ | $\mbox{false}$ | $\mbox{false}$ |
$\mbox{false}$ | $\mbox{false}$ | $\mbox{true}$ | $\mbox{false}$ |
$\mbox{false}$ | $\mbox{true}$ | $\mbox{false}$ | $\mbox{true}$ |
$\mbox{false}$ | $\mbox{true}$ | $\mbox{true}$ | $\mbox{true}$ |
$\mbox{true}$ | $\mbox{false}$ | $\mbox{false}$ | $\mbox{false}$ |
$\mbox{true}$ | $\mbox{false}$ | $\mbox{true}$ | $\mbox{true}$ |
$\mbox{true}$ | $\mbox{true}$ | $\mbox{false}$ | $\mbox{false}$ |
$\mbox{true}$ | $\mbox{true}$ | $\mbox{true}$ | $\mbox{false}$ |
For CNF, the false rows give us the following five clauses:
For DNF, the true rows give us the following three clauses:
This shows that, for any arbitrarily complicated WFF, we can find an equivalent WFF in CNF or DNF. These provide uswith two very regular and relatively uncomplicated forms to use.
The above example produced CNF and DNF formulas for a Boolean function, but they are not the simplest such formulas. For fun, can you find simpler ones?
Sometimes you'll see the form of CNF and DNF expressed in a notation with subscripts.
One question this notation brings up:
Note that often one of these forms might be more concise than the other.Here are two equivalently verbose ways of encoding $\mbox{true}$ , in CNF and DNF respectively: $a\lor \neg a\land b\lor \neg b\land \text{}\land z\lor \neg z$ is equivalent to $\left(a\land b\land c\land \text{}\land y\land z\right)\lor \left(a\land b\land c\land \text{}\land y\land \neg z\right)\lor \left(a\land b\land c\land \text{}\land \neg y\land z\right)\lor \text{}\lor \left(\neg a\land \neg b\land \text{}\land \neg y\land \neg z\right)$ . The first version corresponds to enumerating the choices for each locationof a WaterWorld board; it has 26 two-variable clauses. This may seem like a lot, but compare it to the second version, whichcorresponds to enumerating all possible WaterWorld boards explicitly: it has all possible 26-variable clauses;there are $2^{26}$ 64 billion of them!
Notification Switch
Would you like to follow the 'Pdf generation test course' conversation and receive update notifications?