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
.