Section 1.2: Problem 9 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
(Duality) Let
be a wff whose only connective symbols are
,
, and
. Let
be the result of interchanging
and
and replacing each sentence symbol by its negation. Show that
is tautologically equivalent to
. Use the induction principle.
Remark: It follows that if
and
then
and
.
Let
be the set of all sentence symbols. Let
be the set of wffs
such that
is tautologically equivalent to
. Now, since a wff
consisting of a single sentence symbol
does not include any connective symbols,
, i.e. all sentence symbols are in
. Suppose that
. Then,
, as we do the substitutions inside the
only, and the latter is tautologically equivalent to
. Further,
, where
and
, and the latter is tautologically equivalent to
, which is equivalent to
(see De Morgan’s laws at p.27). In summary, we conclude that
, and, by induction,
consists of at least those wffs that use the connective symbols
,
and
, in particular,
.