# Section 1.5: Problem 5 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.

*Suggestion*: Show that any wff using these connectives and the sentence symbols and has an even number of ’s among the four possible values of .*Remark*: Another approach uses the algebra of the field . Any Boolean function realizable with these connectives has a certain linearity property.

Remember that
is the “exclusive or” connector. Again, similar to the two previous exercises, we look for a property such that a) it holds for sentence symbols, b) it holds for
,
, whenever it holds for
and
, and c) it does not hold for any connective, in particular, for
and
. We consider the property as suggested, and call any wff using sentence symbols
and
only and satisfying the property, “even”. We are going to use induction. Let
. Let
be the set of all even wffs. We have four possible truth assignments on
. Among those
is assigned to
twice, and
is assigned to
twice as well. Therefore, both sentence symbols are even wffs, i.e.
. Suppose,
and
are even having
and
-values, correspondingly, and
truth assignments such that both are true (
and
are even,
does not have to be). Then,
is even (
’s),
is even (
’s),
is even (
’s),
is even (
’s), and
is even (
’s). By induction,
contains all the wffs that can be built using
connective symbols only. Note, that
is not empty, as neither
nor
is even. Hence, those cannot be tautologically equivalent to any wffs built using connectives from
only.