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, ).