Section 1.5: Problem 2 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 and are the only binary connectives that are complete by themselves.
I solved this problem once just for fun walking home. A 0-ary connective cannot be complete as it always results in the same value. An unary connective cannot be complete as there are four unary connectives, among which two are constant, one returns the same initial value no matter how many times we apply it, and the fourth one returns either the initial value or its opposite depending on whether we apply the connective even or odd number of times in the formula. In either case, it follows that neither unary connective is capable to represent even some other unary connectives.
Now, binary connectives. Suppose that is complete.
(a) and . Indeed, suppose that . Consider any wff using only. For the truth assignment that assigns to all sentence symbols, the result of the wff is then necessarily true. Hence, even something as simple as cannot be represented by such wffs. Similarly, for the case .
(b) . Indeed, now instead of 16 possible connectives we have 4 only. Among these connectives, two are such that either and or vice versa. Consider such a connective. We have and . Hence, the connective results simply in the negation of the second operand. Now, given any wff using only, it is easy to see by induction, that the result will be either the value or its negation of the rightmost sentence symbol in the expression. Again, no such wff would be able to represent something like etc.
(c) is either or . Now we have these two possible binary connectives only. Both are complete, as was shown in the text.
-ary connectives. First, an -ary connective, , can depend on two sentence symbols only, and essentially be reducible to or . Second, there are irreducible (in the sense that they depend on all their connective symbols) -ary complete connectives. For example, is a complete ternary connective. Indeed, it depends on all three sentence symbols, as and , and is tautologically equivalent to , which is just . Hence, is complete.
It seems that for this more general case to find all complete connectives we would need to argue against some connectives similar to what we did for . For example, we could still use the same argument we used in (a) for any . Similarly, we would want to exclude all connectives that depend on one sentence symbol only, as in (b), or, more generally, that depend on any number of sentence symbols less than (as those, essentially, can be reduced to -ary connectives for some ). However, we would probably need more rules to reject connectives.