Section 1.2: Problem 2 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
(a) Is
a tautology?
(b) Define
recursively as follows:
and
. For which values of
is
a tautology? (Part (a) corresponds to k = 2.)
(a) It can be false only if
is false, but then
is true, and
is false, implying the whole expression is true. Contradiction, hence, it is a tautology.
(b) If
, then it is obviously not a tautology. If
, and
is false, then
is false, but then
is true (regardless of the value assigned to
),
is false,
is true, etc. Hence, it is a tautology for even values of
, except for
.