70 LOGIC, PART I: THE PROPOSITIONAL CALCULUS Chapter 2
The tautology in Example 5, known as modus ponens, is a particularly
important principle of logic, and is actually the cornerstone of the relevance
of the implication connective to mathematical theorem-proving. We can
conclude the truth of a desired proposition q if we can derive q as a logical
consequence of some statement p, where p in turn is known to be true.
Perhaps, in a particular problem, we may wish to prove q and find that q
can be proved as a consequence of p, where p is some well-known theorem.
In such a case we say that q is a corollary to p. On the other hand, we may
wish to prove q where it is evident that q follows from a statement p, where
the truth of p, however, is not known. In such a case the burden of proof
shifts from proving q directly to trying somehow to prove p. A statement
p in this context (assuming it can be proved) is often referred to as a lemma.
In such proofs phrasing like "in order to prove q, it is clearly sufficient
to prove p, where p is the statement.. ." is common.
In Theorem 2 we provide a list of selected implications of the proposi-
tional calculus. These statements can be verified on a selective basis [see
Exercise 2(b)] by using truth tables.
THEOREM 2
The following statement forms, each having the conditional as main connective,
are all tautologies (and hence are implications):
(reflexive property of implication)
(law of syllogism; transitive property
of implication)
(law of simplification)
(law of addition)
(law of detachment; modus ponens)
(indirect proof; proof by contrapositive;
modus tollens)
(indirect proof; proof by contradiction;
reductio ad absurdurn)
(symmetric property of equivalence)
(transitive property of equivalence)(law of disjunction; modus tollendo
ponens)In addition to the implications stated in Theorem 2, each equivalence
in Theorem 1 yields a new tautology if the biconditional connective is re-
placed by the conditional in either direction (because of part (n) of Theorem
2, which asserts formally that the biconditional is stronger than the con-