Section 1.2: 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
(Duality) Let be a wff whose only connective symbols are , , and . Let be the result of interchanging and and replacing each sentence symbol by its negation. Show that is tautologically equivalent to . Use the induction principle.
Remark: It follows that if and then and .
Let be the set of all sentence symbols. Let be the set of wffs such that is tautologically equivalent to . Now, since a wff consisting of a single sentence symbol does not include any connective symbols, , i.e. all sentence symbols are in . Suppose that . Then, , as we do the substitutions inside the only, and the latter is tautologically equivalent to . Further, , where and , and the latter is tautologically equivalent to , which is equivalent to (see De Morgan’s laws at p.27). In summary, we conclude that , and, by induction, consists of at least those wffs that use the connective symbols , and , in particular, .