Section 1.5: Problem 3 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.
Just to remind, is the majority connective so that is tautologically equivalent to . If the set is not complete, then one cannot represent all binary connectives using just these connective symbols, in particular, one cannot represent either or , as otherwise the set would be complete. There are two ways to show that these connectors can’t be expressed using .
First, consider any wff using just two sentence symbols and and connective symbols from only (we do not have to consider any wffs using more sentence symbols in their construction, as we try to represent a binary connective , and all other sentence symbols can be ignored, according to Exercise 4, Section 1.1). Looking at the construction tree from the bottom up, let us find all nodes that use only negation below them. Then, each such node has a wff that is tautologically equivalent to one of the four wffs: , , and (for example, is tautologically equivalent to the first one etc.). Now, consider the first node that uses . If two children of are tautologically equivalent to the same wff, then the result of by the majority rule is also tautologically equivalent to the same wff. If all three operands of are different, then two of them are tautologically equivalent to either and , or and . In either case, for any truth assignment, the values of these two operands are opposite, meaning that the third operand decides the value of . Again, we have that is tautologically equivalent to one of its operands. Hence, the node is equivalent to one of its children, i.e. one of the four wffs listed above. We conclude that every wff that has two sentence symbols and connective symbols from only, is tautologically equivalent to , , or . More formally, we could have proved this by induction. It is true for sentence symbols. Now, if it is true for , and , then it is true for and by the argument outlined above.
Second, we may note that both and are such that . In particular, this implies that is not tautologically equivalent to . In other words, neither nor satisfies the property that “if we change all truth values assigned to sentence symbols to their opposites, the result will change to the opposite as well”. However, both and satisfy this property. Moreover, by induction, we see that, since all sentence symbols satisfy this property, and if , and satisfy this property, so do and , any wff based on only satisfies the property. Hence, using connective symbols from only, no wff can represent or (or any other connective that does not satisfy the property, for example, , , , , , , , , and ).