(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 $\alpha$ 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 $\neg\alpha$ (according to the exercise). So, if we make the same substitution in the disjunctive normal form of $\neg\alpha$ , we obtain the conjunctive normal form of $\alpha$ .

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 $\beta_{1}\vee\ldots\vee\beta_{n}$ has to be false for specific values of $A_{1},A_{2},\ldots$ only, then we must take $\beta_{i}$ to be $A_{i}$ if the corresponding value of $A_{i}$ is $F$ , and $\neg A_{i}$ otherwise.

Now, $A\leftrightarrow B\leftrightarrow C$ is assigned $T$ iff an odd number of sentence symbols are assigned $T$ (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 $ABC$ is $FFF$ , $FTT$ , $TFT$ or $TTF$ . Therefore, the conjunctive normal form is $(A\vee B\vee C)\wedge(A\vee\neg B\vee\neg C)$ $\wedge(\neg A\vee B\vee\neg C)\wedge(\neg A\vee\neg B\vee C)$ . As noted above, we could have considered $\neg(A\leftrightarrow B\leftrightarrow C)$ , which is true iff an even number of connective symbols is true, i.e. for $ABC$ ’s as before, and its disjunctive normal form is, therefore,$(\neg A\wedge\neg B\wedge\neg C)\vee(\neg A\wedge B\wedge C)$ $\vee(A\wedge\neg B\wedge C)\vee(A\wedge B\wedge\neg C)$ , 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 $\neg\alpha$ and make substitutions according to Exercise 9 of Section 1.2, or find all truth assignments that assign $F$ to $\alpha$ , and for each take the disjunction of each sentence symbol if it is assigned $F$ or its negation if it is assigned $T$ (the second method, similar to the Theorem 15B, requires us to consider the special case where $\alpha$ is a tautology, in which case $\alpha$ is tautologically equivalent to, say, $A_{1}\vee\neg A_{1}$ ).