2.3 THEOREMS OF THE PROPOSITIONAL CALCULUS 75q: If a, b, and p are integers and if p divides ab, then either p divides a or p
divides 6.
(g') [Some abstract algebra background is necessary to be able to answer (ii).]
p: If a finite group G is cyclic, then G is abelian.
q: If a group G (finite or infinite) is cyclic, then G is abelian.
(a) For each of the following parts of Remark 1, determine which tautology or
tautologies from Theorem 1 or Theorem 2 provide justification.
0) l(e) (ii) l(f)
(iii) l(j) (iv) 2(d)
(v) 3(b)
(b) Give a specific nonmathematical example to show that the tautology (p + q) t,
(-p v q) (part (0) of Theorem 1) is intuitively reasonable.
- The law of syllogism, which states that [(p -+ q) A (q -+ r)] + (p -+ r) is a tautol-
ogy, is important in logic and represents a common form of an argument in or-
dinary discourse. Consider three possible alternative definitions for "conditionals,"
denoted +T for i = 1, 2, 3, defined by the table in Figure 2.8. The first two rows
in each case, of course, seem reasonable and agree with the corresponding rows of
the definition of the "honest" conditional. The last two rows may seem arbitrary,
but actually represent all other possible definitions of a "conditional" connective.
Show that the law of syllogism fails for all three of these possible definitions. - (a) Prove that the compound statement forms p v q, p -+ q, and p t, q are each
logically equivalent to statement forms in p and q involving the connectives not
and and only. [Hint: See parts (c), (o), and (m) of Theorem 1.)
(b) Based on your answers to (a), express each of the following compound state-
ment forms in terms of - and A only: - The main thrust of Exercise 10 is that the five connectives v, A, -, -+, and
- are not all needed for the propositional calculus. Any statement form that can
be expressed in terms of any of these five connectives has an equivalent representation
Figure 2.8 ~hree possible, but incorrect,
deJinitions of the conditional connective. The law
of syllogism fails to be a tautology if-+ is deJined
in any of these thred ways.
I------ I I .-I