Section 1.5: Problem 8 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
Let be the ternary connective such that is assigned the value iff exactly one of the formulas , , is assigned the value . Show that there are no binary connectives and such that is equivalent to .
Intuitively, given and , is true iff is true when both and is false, or is false if exactly one of and is true. Therefore, we have three cases, when neither nor is true, when exactly one of and is true, and when both are true. In the first case results in iff is assigned , in the second case iff is assigned , and in the third case never. At the same time, is true for some values of and , where we cannot distinguish the three cases for and , i.e. can be either false or true, which does not tell us in which case we are, but then the result of should depend on this.
More formally, suppose that where (in the usual sense in terms of evaluations). Then, and . Now, suppose that where . Then, and . Finally, assume that where . Then, and . Note, that and . Hence, and , which is not possible as .