Normal Forms
127
Example 7. Let * be the formula
* = -((p -- (q V r)) A (-q) A (-r) A p)
Find a CNF for *1.
Solution. The negation of * is equivalent to
(p - (q V r)) A (--q) A (-"r) A p
which in Example 3 was shown to have F as a DNE So, * is equivalent to -F, and
pushing negations inward gives the CNF formula T.
U
2.5.4 Application: CNF and Combinatorial Networks
To interpret the CNF for a boolean expression, we view a clause as a meet of a set of
literals. The CNF for a formula is viewed as a join of a set of clauses. The CNF for a
boolean expression gives us another option to use when designing combinatorial circuits.
Example 8. Let x, y be elements of a boolean algebra. Use the CNF for the boolean
expression (x A y) V (-,x A --y) to design a combinatorial circuit.
Solution. The truth table for the expression is
x
y Ix Ay
('-,x A-y)
(x Ay) V(-X A-"y)
S
T
F
T
T F
F
F
F
F T
F
F
F
S
F
T
T
The DNF for - ((x A y) V (-,x A -,y)) is just
(x A -y) V (--x A y)
Therefore, the CNF for (x A y) V (-,x A -y) is
-- ((x A -y) V (-.x A y)) = -'(x A -y) A -- (-'x A y)
=(--X V •--y) A (----X V -y)
= (-'x V y) A (x V -y)
The combinatorial circuit for this boolean expression is
Y
X
X V -
(X V -,y) "A (-X V y)
x @••
xv Y F
y
U
2.5.5 Testing Satisfiability and Validity
It turns out to be very easy to tell when a formula in DNF is satisfiable. This is one reason
why a DNF is often nice to work with.