608 Appendix A • Logic and Proofs
Proof. Use a truth table to show that [P =? Q and Q =? R] =? [P =? R] is
a tautology. •
Here's how we use Theorem A.3.1 to give a direct proof of the theorem:
H1, H2, ···, Hn, :.C:
Let H denote the conjunction of all the hypotheses; that is, H = (H 1 and
H 2 and · · · and H n). In a direct proof, we try to string together a sequence of
implications:
Then, by the transitivity of implication, H =? C, and we have proved the
theorem.
(PS-2) TO PROVE AN IMPLICATION (CONDITIONAL PROOF):
To prove a theorem:we prove the equivalent theorem:
That is, to prove P =? Q, add P as a hypothesis and prove Q.(PS-3) TO PROVE AN IMPLICATION BY ITS CONTRAPOSI-
TIVE:
To prove a theorem:
we prove the equivalent theorem:
That is, to prove P =? Q, we prove the contrapositive, rvQ =? rvP.