Section 1.5: Problem 5 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
Show that is not complete. Suggestion: Show that any wff using these connectives and the sentence symbols and has an even number of ’s among the four possible values of .
Remark: Another approach uses the algebra of the field . Any Boolean function realizable with these connectives has a certain linearity property.
Remember that is the “exclusive or” connector. Again, similar to the two previous exercises, we look for a property such that a) it holds for sentence symbols, b) it holds for , , whenever it holds for and , and c) it does not hold for any connective, in particular, for and . We consider the property as suggested, and call any wff using sentence symbols and only and satisfying the property, “even”. We are going to use induction. Let . Let be the set of all even wffs. We have four possible truth assignments on . Among those is assigned to twice, and is assigned to twice as well. Therefore, both sentence symbols are even wffs, i.e. . Suppose, and are even having and -values, correspondingly, and truth assignments such that both are true ( and are even, does not have to be). Then, is even ( ’s), is even ( ’s), is even ( ’s), is even ( ’s), and is even ( ’s). By induction, contains all the wffs that can be built using connective symbols only. Note, that is not empty, as neither nor is even. Hence, those cannot be tautologically equivalent to any wffs built using connectives from only.