3.4 Propositional logic: normal forms

Cnf, dnf,(enuff already!)

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.

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.

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 DNF formula results from looking at a truth table, and focusing on the rows where the function is true:As if sayingI'm in this row, or in this row, or: For each row where the function is true,form a conjunction of the propositions. ( E.g. , for the row where $a$ is $\mbox{false}$ , and $b$ is $\mbox{true}$ , form $\neg a\land b$ .) Now, form the disjunction of all those conjunctions.
• A CNF formula is the pessimistic approach, focusing on the rows where the function is false:I'm not in this row, and not in this row, and. For each row where the function is false,create a formula fornot in this row: ( E.g. , if in this row $a$ is $\mbox{false}$ and $b$ is $\mbox{true}$ form $\neg (\neg a\land b)$ ; then notice that by DeMorgan's law, this is $a\lor \neg b$ a disjunct. Now, form the conjunction of all those disjunctions.

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.

Notation for dnf, cnf

Sometimes you'll see the form of CNF and DNF expressed in a notation with subscripts.

• DNF is ${}_i{}_i$ ,where each clause ${}_i$ is ${}_j_j$ , where each $$ is a propositional variable ( $\mathrm{Prop}$ ), or a negation of one ( $\neg \mathrm{Prop}$ ).
• CNF is ${}_i_i$ , where each clause $_i$ is ${}_j_j$ , where each $$ is again a propositional variable ( $\mathrm{Prop}$ ), or a negation of one ( $\neg \mathrm{Prop}$ ).

One question this notation brings up:

• What is the disjunction of a single clause? Well, it's reasonable to say that $\equiv$ . Note that this is also equivalent to $\lor \mbox{false}$ .
• What is the disjunction of zero clauses? Well, if we start with $\equiv \lor \mbox{false}$ and remove the $$ , that leaves us with $\mbox{false}$ ! Alternately, imagine writing a function which takes a list of booleans,and returns the $$ of all of themthe natural base case for this recursive list-processing program turns out to be $\mbox{false}$ . Indeed, this is the accepted definition of the empty disjunction.It follows from $\mbox{false}$ being the identity element for $$ . Correspondingly, a conjunction of zero clauses is true.

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 \land z\lor \neg z$ is equivalent to $\left(a\land b\land c\land \land y\land z\right)\lor \left(a\land b\land c\land \land y\land \neg z\right)\lor \left(a\land b\land c\land \land \neg y\land z\right)\lor \lor \left(\neg a\land \neg b\land \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!