# 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
).