# Section 2.4: Problem 17 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)
.

(a) We need to show
. By deduction, it is sufficient to show that
. By contraposition, it is sufficient to show that
. By MP, it is sufficient to show that
. By axiom group 3 and generalization theorem, it is sufficient to show that
. By axiom group 2,
. So, that
, and, using MP for the tautology
, we deduct
from
.

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

*defined*this way.
So, we need to show that
and
.

For the first formula, using the deduction, contraposition and generalization theorems, as well as axiom group 1 (for tautology
), it is sufficient to show that
. By the deduction theorem, it is sufficient to show that
. Now,
and
(axiom group 2), therefore, by MP,
.

For the second formula, using the deduction, contraposition theorems, it is sufficient to show that
. Using the deduction theorem and MP, it is sufficient to show that
. By axiom group 3, MP and generalization theorem, it is sufficient to show
. By MP, it is sufficient to show that
, which is a tautology.