Discrete Mathematics for Computer Science

126 CHAPTER 2 Formal Logic

Example 5.

(a) a v b v -c is a clause.

(b) T is in CNF. It is a conjunction of zero clauses.

(c) F is a clause. It is a disjunction of zero literals.

(d) a is a clause. It is a disjunction of one literal.

(e) The disjunction of clauses shown is in CNF:

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

(f) a v b v -'c and F are in CNE Each is a conjunction of one clause.

Theorem 2. Every formula is logically equivalent to a formula in CNF.

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

Example 6. Find the conjunctive normal form for the formula

V1 = (-'(p -+ q)) - (q A -- r)

Solution. The process starts by finding a formula in DNF that is equivalent to --,r.

The following is an abbreviated truth table for -',*. We will misuse the word

interpretation exactly as we did in Example 2 in Section 2.3.

Interpretation p q r -'((-(p - q)) -+ (q A -,r))

I0 T T T F

Ii T T T F

12 T F T T

13 T F F T

14 F T T F

15 F T F F

16 F F T F

17 F F F F

Now, put --VI into DNF:

0 =* = 02V 03 = (pA-'q Ar) V (pA--q A-'r)

So, *' is logically equivalent to

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

Push the negations inside, first past the v using DeMorgan's Law:

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

then past the internal A's, again using DeMorgan's Law:

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

and finally, eliminate the double negations:

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

Since 0-* was in DNF, negating and pushing the negations inside creates a formula in

CNF logically equivalent to */. 0