2.3 THEOREMS OF THE PROPOSITIONAL CALCULUS 67form is logically equivalent to that of the original. Examples 1 and 2 pro-
vide some specific illustrations of how this principle may be applied. Ex-
ample 2(b), for instance, indicates that if we must prove a theorem whose
conclusion has the form "either q or r" (with hypothesis p), we may do so
by assuming q false (i.e., assuming -q is true) and trying to deduce r from
the expanded hypothesis p A - q. A practical application of this principle
is the theorem about real numbers "if xy = 0, then x = 0 or y = 0." We
can approach the proof of this result by assuming that x # 0 (so that we
now have two hypotheses to work with, xy = 0 and x # 0) and attempting
to conclude that y must equal zero (the full proof is found in Article 6.2).
The other two equivalences in Examples 1 and 2 are of even greater
importance for theorem-proving. The tautology in 2(a) says that we may
divide an "if and only if" proof into two parts, namely, "if p, then q" and
"if q, then p," and carry out the proof by proving each of these two parts
separately. This is the approach most often taken to prove a theorem
whose statement involves the biconditional (Examples 9 and 10, Article 4.1,
illustrate another approach to proving such theorems). The tautology in
Example 1 is the basis of proof by contrapositive, a form of indirect proof.
Instead of proving directly that q follows from p, we may instead proceed
by assuming the conclusion q to be false and trying to show that it follows
that p must be false.
In summary, many logical equivalences correspond to possible strategies
for approaching proofs of mathematical theorems. We will look in detail
at several such methods of proof, as well as a wealth of specific proofs, in
Chapters 4 through 6. But for now, the important idea that you should
be beginning to sense is: The rules of the propositional calculus, a part of
logic, are crucial to mainstream mathematics!
Equivalents to the negation of the five connectives. Earlier we suggested a
method of proof, proof by contrapositive, that involves assuming the nega-
tion of a desired conclusion. Suppose we wish to use this approach to
prove a result whose conclusion is itself a compound statement form, say
p A q or p -, q. In the latter case, for instance, we would have to begin the
proof by stating "suppose the conclusion p -+ q is false." At this point,
before we could effectively use that assumption, we would need to know
some statement involving p and q that is thereby true. Thus it would clearly
be of value to have-at our disposal "positive" statement forms (i.e., statement
forms in which negation is not the main connective) equivalent to the nega-
tion of each of the five connectives, that is, equivalent to - (- p), - (p A q),
-(p v q), - (p -+ q), and - (p +-+ q). In Theorem 1 we will give a list of
tautologies of the propositional calculus whose main connective is the bi-
conditional (i.e., equivalences); parts (b) through (f) of this theorem give
equivalents to the negation of each of the five connectives.
Part (b) of Theorem 1 asserts that the negation of the negation of a state-
ment is the statement itself. Parts (c) and (d) state that the negation of