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

Add the 0-place connectives
,
to our language. For each wff
and sentence symbol
, let
be the wff obtained from
by replacing
by
. Similarly for
. Then let
. Prove the following:

(a)
.

(b) If
and
does not appear in
, then
.

(c) The formula
is satisfiable iff
is satisfiable.

*Remarks*: We can think of as trying to say everything says, but without being able to use the symbol . Parts (a) and (b) state that is the strongest -free consequence of . The formulas and are not tautologically equivalent in general, but they are “equally satisfiable” by part (c). The operation of forming from is (in another context) called

*resolution*on .

We are going to use the following fact (*): for any truth assignment
that includes all sentence symbols of
, if
then
, otherwise
. Also, we note that (**) for any truth assignment
,
.

(a) If a truth assignment
satisfies
then, according to (*), depending on the value of
,
or
is
, and, hence, according to (**),
.

(b) Exercise 4 of Section 1.2 tells us that
iff
is a tautology. Now, according to Exercise 8 of Section 1.2, we can substitute
or
for
in this expression (or, since that exercise was proved for the language without
and
, substitute
or
for
), and the resulting wff will still be a tautology. Now, note that in the first case we obtain
, while in the other case we obtain
(we actually need to prove that substituting
or
is equivalent to substituting
or
, but we will skip this part). So, both are tautologies (we could use an argument using truth assignments to avoid referring to previous exercises). Now, for any truth assignment
such that
satisfies
, we can consider the truth assignment
restricted to all sentence symbols of
except for
such that
still satisfies
(see Exercise 6 of Section 1.2 for more details), and we can extend the truth assignment
to
or
by letting
and
. Then, according to Exercise 6 of Section 1.2,
, and according to (**), at least one of
or
is
. Hence,
satisfies
.

(c) One direction follows from (a). Now, assume that
is satisfiable. If
is not satisfiable then every wff is tautologically implied by
, including
. But then, by (b),
is tautologically implied by
, which is not true as
is satisfiable. Therefore,
is satisfiable as well.

To conclude this exercise, we illustrate the concept by some examples. First, consider
.
which is tautologically equivalent to
. We can think of it as the best we can say if
is known to be true but we cannot express
, or, alternatively, without using
, is that
is true. Similarly,
is tautologically equivalent to
, as in this case, without mentioning
all we can say is that
is true, in other words, we can say nothing specific.