# Section 2.4: Problem 15 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 deductions (from
) of the following formulas exist:

(a)
.

(b)
.

Note, that
is tautologically equivalent to
, and
is tautologically equivalent to
. By tautologically equivalent we do not imply that one uses these first-order tautologies in the proves of the above equations (for example, you cannot use tautologies to substitute subformulas of quantified formulas), but rather that these connectives are

*defined*this way.
(a) We need to show that
and
. By deduction and contraposition theorems, it is sufficient to show that
and
.

For the first one it is sufficient to show that
and
(using Rule T for
). By MP, it is sufficient to show that
and
, and, by axiom group 3, MP and generalization theorem, it is sufficient to show that
and
. Both are tautologies.

For the second one, by the generalization and contraposition theorems, it is sufficient to show that
. By the deduction theorem, it is sufficient to show that
. By RAA, it is sufficient to conclude that
is inconsistent. Now, by axiom group 2,
and
, and, by MP,
.

(b) We need to show that
. By deduction, generalization and contraposition theorems, it is sufficient to show that
. For this, it is sufficient to show that
and
(using Rule T for
), or that both
and
are inconsistent. By axiom group 2,
and
, and
and
are tautologies, so that, by Rule T,
and
.