Discrete Mathematics for Computer Science

124 CHAPTER 2 Formal Logic

The reader should observe that these terms have the desired properties. That is, Io

satisfies p A q A r, and all seven other interpretations do not satisfy p A q A r.

Now, breaking into the cases where *r is T, we construct a disjunction of terms with

one corresponding to each interpretation where *f is T."

(p A q A r) V (p A q A -r) V (-p A q A r) V (-'p A q A -r)

v(-p A -q A r) V (-p A -q A -r)

Clearly, 4¢ is in DNF. The only question is whether 0*, is logically equivalent to r.

As a result of the construction, however, each term of 0* is T for exactly one of the

interpretations for which * is T, whereas 4r is F in all other interpretations. So, 4O, is T

when 0 is T. Each term of 0* is F in each interpretation for which *r is F. Therefore, 0*

is F in each interpretation for which V1 is F. Thus, Ok is logically equivalent to UM'.

Example 3. Let *' be the formula

*r = (p -* (q V r)) A (-q) A (-r) A p

Find a DNF for 4'.

Solution. It is easy to see that Vf is unsatisfiable. We see this from the truth table for 4'

shown in Table 2.9.

Table 2.9 Abbreviated Truth Table for *'

Interpretation p q r p--. (qvr) -q -r (p-- (qvr))A(-q)A(-r)Ap

1o T T T T F F F

I1 TTF T F T F

12 T F T T T F F

13 T F F F T T F

14 F T T T F F F

15 F T F T F T F

16 F F T T T F F

17 FFF T T T F

Since at least one of the formulas p -- (q V r), -q, -'r, and p is F in each interpre-

tation, the disjunct of these terms is always F. Therefore, the construction as in Example

2 that formed terms for interpretations satisfying 4', would construct no terms. Accord-

ingly, the formula generated as in Example 2 would be a disjunction of zero terms, which,

by convention, is the formula F. The formula F is in DNF and is logically equivalent

to '. U

2.5.2 Application: DNF and Combinatorial Networks

To interpret the DNF for a boolean expression, we view a term as a product or a join of

a set of literals. The DNF for a formula is viewed as a sum or a meet of a set of terms.

The DNF for a boolean expression gives us an option to use when designing combinatorial

circuits.