# Section 1.2: Problem 8 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

(Substitution) Consider a sequence
of wffs. For each wff
let
be the result of replacing the sentence symbol
by
, for each
.

(a) Let
be a truth assignment for the set of all sentence symbols; define
to be the truth assignment for which
. Show that
. Use the induction principle.

(b) Show that if
is a tautology, then so is
. (For example, one of our selected tautologies is
. From this we can conclude, by substitution, that
is a tautology, for any wffs
and
.)

(a) Let
be the set of all sentence symbols. Let
be the set of all wffs
such that
. Then, by assumption, all sentence symbols are in
(here we assume that if there is a sentence symbol
different from all
, then
, though, I think, what is meant here is that
’s form the set of all sentence symbols, as was defined earlier in the text). Now, if
, then
, where, by definition,
and
, and, similarly,
, where, by definition,
is valuated according to the truth tables. One thing to mention here is that we used equalities
and
which simply mean that the substitution in a formula is equivalent to the substitution in its components, which is easy to accept or show using induction. Finally, by the induction principle, we conclude that
, and
.

(b) (
is a tautology) iff (every truth assignment
on
implies
) THEN (here is where iff does not work) (every truth assignment
on
implies
, where
is defined as in (a)) iff (
is a tautology). To see that the other direction does not work, consider, for example, the wff
, which is not a tautology, together with the substitution
. Then,
, which

*is*a tautology.