Discrete Mathematics for Computer Science

128 CHAPTER 2 Formal Logic

Example 9.

(a) Show that

4 = (a A -'b) V (-'a A -"C A b) V (a A -'a)

is satisfiable.

(b) Show that

¢ -(a A --b A b) v (--a A -c A b A c) V (a A -a)

is unsatisfiable.

Solution.

(a) To find an interpretation I where 1 (4) = T, it is enough to find an interpretation where

one of the terms is true. In this case, there is an interpretation where the first term is

true. If I (a) = T and I (b) = F, then I (a A -b) = T and, hence, 1(40) = T.

(b) In this case, 4 is unsatisfiable, because every term is F in every interpretation L. For

example, in the first term, we require both I (-b) and I (b) to be T in an interpretation.

In the second term, we require both I (c) and I (-'c) to be T in an interpretation. In

the third term, we require both I(a) and I (-a) to be T in an interpretation. These

conditions are clearly impossible in any interpretation. U

Similarly, it is easy to tell when a formula in CNF is a tautology.

Example 10.

(a) Show that

4 = (a V -b) A (-a V -c V b) A (a V -a)

is not a tautology.

(b) Show that

4 - (a V -b V b) A (-a V -c V b V c) A (a V -a)

is a tautology.

Solution.

(a) If I(a) = F and I(b) = T, then l(a v-b) = F, so 1(0) = F.

(b) The first clause is a tautology, since b v -b alone is a tautology. The second clause is

a tautology, since c V -c alone is a tautology. The third clause is also a tautology.

Theorem 3.

(a) Let 41,42 ..... 4k be clauses for k e N. Let

4 =41 A42 A--. A4k

Then, 4 is a tautology if and if every 4i is a tautology.

(b) Let k.,.2 ...... km be literals for some m. Let

Oi = )11 V X 2 V .- Vm