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

(a) Show that
is complete.

(b) Show that no proper subset is complete.

*Remark*: is the ternary

*parity*connective; the condition for is that for an

*odd*number of ’s. is the binary parity connective. The function in the proof of Theorem 15B is the 3-place parity function.

(a) Note that
is tautologically equivalent to
. Together with
we have a complete system of connectives.

(b) Now, similar to the previous exercise, we look for some properties of connectives such that the set of wffs satisfying each such property is closed under connectives, but not all connectives satisfy the property, in particular,
and
do not. To show that no proper subset is complete, for each connective in the set we need to find such property that all the other connectives satisfy it, but not the given one. In other words, there should be something unique in each connective that makes the set complete. In the previous exercises we have already listed some such properties.

is the only connective that is not evaluated to
when all operands are evaluated to
.

Similarly,
is the only connective that is not evaluated to
when all operands are evaluated to
.

For
we could proceed in two possible ways. First, similar to the first solution of Exercise 3, we could consider all wffs in two sentence symbols
and
using
only, and show that we cannot construct any wffs tautologically equivalent to
or
. It seems that, eventually, we would have to show that the set of wffs generated by
,
under
is the same as the one generated by
,
under
, which is not complete according to Exercise 5. Second, the first solution suggests that we can apply ideas of Exercise 5. Namely, we can consider
on the set of sentence symbols
. Similar to Exercise 5, we call a wff in
and
even, if the number of truth assignments that evaluates the wff to
is even. Then, all sentence symbols are even,
is even (
’s),
is even (
’s), and if for
,
and
the number of truth assignments that evaluate
,
,
to
, where
, is, respectively,
,
and
(
,
and
are even), then
is even as well (
’s). Hence, the set of all even wffs in
and
contains the set of wffs generated by
under
, yet it does not cover all wffs in
and
, such as
and
. We conclude that
is not complete.

is a bit harder as we did not use any property in the previous exercises that would distinguish
from the set of others. Indeed, two properties used in Exercise 2 are already used for
and
. Another property used in Exercise 2, which is dependance on no more than 1 sentence symbol, satisfies the first two connectives only. The property used in Exercises 3 and 4 (self-duality) satisfies
only. And the property used in Exercise 5 is already used. However, in this case the method of Exercise 3 (the first solution) is most applicable. We just note that the set of wffs
is closed under
in the sense that the application of any connectives from
to any wffs that are tautologically equivalent to some wffs in
, results in a wff that is again tautologically equivalent to one from
. If the connective is
or
then the result is immediate, and if
and
are tautologically equivalent to some wffs from
, then
is also tautologically equivalent to some wff from
(we need to consider cases such as
being tautologically equivalent to
,
to
,
to itself, and
to
). Hence, by induction, noting that all sentence symbols are in
, we conclude that the set of wffs generated from
using
consists of wffs that are tautologically equivalent to one of those in
, but since not all wffs are equivalent to one of those, the set
is not complete.

Another way to see that
is necessary for completeness, is to note that all connectives in
are “increasing” in the sense that changing the truth assignment for any sentence symbol from
to
never results in changing of the evaluation of a wff built with these connectives from
to
(it may not change at all, or increase, but never decrease). This property is also inherited by wffs from sentence symbols, if the connectives used in the wff satisfy this property. And
do satisfy this condition, while, for example,
or
do not.