Subsection 3.3.12 Normal Forms
The identities that we’ve just been working with give us a way to transform a Boolean statement into another, equivalent one. We’ve seen that we might want to do that, for example, to produce a simpler expression that we’ll have an easier time working with.
Recall that we have just shown that p (s p) can be simplified to F.
But we can also exploit the identities if we want to assure that all the statements we’re working with have some sort of special form. Depending on what we plan to do with the statements, guaranteeing a special form might make life easier.
For example, we might want to require that all nots be atomic, by which we mean that they apply to just a single variable. So, we’d require that:
\(\neg (a \vee b \vee c) \)
be rewritten (using De Morgan’s Laws) as this equivalent statement:
\(\neg a \wedge \neg b \wedge \neg c \)
The “Atomic Nots” form has the property that every Boolean expression can be rewritten into it.
But what about requiring that there be no nots at all? Now there are things we can’t say. For example, there’s no way to say:
\(a \vee \neg b \vee c \)
We’ll say that a form constraint is a normal form for some original set of objects just in case every original object has an equivalent representation that does satisfy the constraint. So:
We can call “Atomic Nots” a normal form for Boolean expressions.
We cannot call “No Nots” a normal form for Boolean expressions.
By the way, normal forms are useful in applications that range from logic to parsing computer programs to handling data base queries. The notion of an “equivalent” representation necessarily depends on what our purpose is for working with the objects we’re manipulating. For our purposes, it means, “have the same truth value”.
Nifty AsideConjunctive Normal Form (or CNF) is probably the most widely used normal form for logical expressions. An expression is in CNF if it is the conjunction of disjuncts.
The formula:
\((p \vee q) \wedge (a \vee q \vee \neg c) \wedge \neg r \)
is in CNF. All nots are atomic, all top level operators are ands, and inside parentheses there are only ors.
CNF is the basis for an important computational logic technique called resolution. It also plays a key role in a large collection of proofs about computational complexity.
Nifty AsideDisjunctive Normal Form (or DNF) is a sort of opposite of CNF. An expression is in DNF if it is the disjunction of conjuncts.
The formula:
\((p \wedge q) \vee (a \wedge q \wedge \neg c) \vee \neg r \)
is in DNF. All nots are atomic, all top level operators are ors, and inside parentheses there are only ands.
DNF is the basis for a very useful way to specify database queries