Discrete Mathematics for Computer Science

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.