Discrete Mathematics for Computer Science

Normal Forms 123

Example 1.

(a) a A b A -c is a term.

(b) The formula

(a A b A c) V (-a A -,b A --c) V (a A --c A q)

is in disjunctive normal form.

(c) T is a term. It is a conjunction of zero literals.

(d) a is a term. It is a conjunction of one literal.

(e) a A b A -"c and T are in disjunctive normal form. Each is a disjunction of one term.

(f) F is in disjunctive normal form. It is a disjunction of zero terms.

Theorem 1. Every formula is logically equivalent to a formula in DNE.

The proof of Theorem 1 is just a formalization of what is done in Example 2.

Example 2. Let VV be the formula

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

Determine a DNF for *.

Solution. A formula may have several equivalent formulas in DNF, but we want a sys-

tematic way to find one.

The first step in finding a DNF for * is to find the truth table for all the interpretations

of 4', as shown in Table 2.7.

Table 2.7 Abbreviated Truth Table for 4

Interpretation p q r (-(p -- q)) --* (q A -'r)

Io T T T T

I1 T T F T

12 T F T F

13 T F F F

14 F T T T

15 F T F T

16 F F T T

17 F F F T

The next step is to construct, for each interpretation Ii, 0 < i < 7, a term that is T in
that interpretation and F in all other interpretations. Such terms are listed in Table 2.8.

Interpretation Matching Term

10 pAqAr

I1 pAqA--r

Table 2.8 True Terms 12 p A -q A r

in the Interpretations 13 p A -q A -r

14 -pAqAr

15 -p A q A -r

16 -PA -q A r

17 -p A -q A -r