# Section 1.5: Problem 9 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Say that a formula
is in

*conjunctive normal form*(abbreviated CNF) iff it is a conjunction where each is a disjunction and each is either a sentence symbol or the negation of a sentence symbol.
(a) Find a formula in conjunctive normal form that is tautologically equivalent to
.

(b) Show that for any formula, we can find a tautologically equivalent formula in conjunctive normal form.

(a) For the disjunctive normal form the intuition was that a disjunction of formulas is true iff at least one of the formulas is true, where each formula represented a separate case when it should be true. Now take any wff
and consider its disjunctive normal form. If we make the substitution as in Exercise 9 of Section 1.2 (Duality), then, by canceling possible double negations of sentence symbols, we obtain the conjunctive normal form of
(according to the exercise). So, if we make the same substitution in the disjunctive normal form of
, we obtain the conjunctive normal form of
.

The intuition here is that the conjunction of formulas is false iff at least one of the formulas is false, and now if a disjunction
has to be false for specific values of
only, then we must take
to be
if the corresponding value of
is
, and
otherwise.

Now,
is assigned
iff an odd number of sentence symbols are assigned
(this is the same expression as the ternary parity connective in Exercise 7). Hence, it is false in all the other cases, i.e. when
is
,
,
or
. Therefore, the conjunctive normal form is
. As noted above, we could have considered
, which is true iff an even number of connective symbols is true, i.e. for
’s as before, and its disjunctive normal form is, therefore,
, which is after the substitution described above becomes the conjunctive normal form found before.

(b) As noted in (a), we can take the disjunctive normal form of
and make substitutions according to Exercise 9 of Section 1.2, or find all truth assignments that assign
to
, and for each take the disjunction of each sentence symbol if it is assigned
or its negation if it is assigned
(the second method, similar to the Theorem 15B, requires us to consider the special case where
is a tautology, in which case
is tautologically equivalent to, say,
).