A.3 Strategies of Proving Theorems 609(PS-3') TO PROVE A THEOREM BY ITS CONTRAPOSITIVE:
To prove a theorem:H,:.C,
we prove the equivalent theorem:(PS-4) TO PROVE A DISJUNCTION:
To prove a theorem:we prove the equivalent theorem:
That is, to prove P or Q, we prove the implication ,__,p => Q. Alternatively,
we could prove t he equivalent theorem:
(PS-5) INDIRECT PROOF (PROOF BY CONTRADICTION):
By a contradiction, we mean any proposition of the form "R /\ "'R,''
which always has truth-value F. By the truth table defining "=>,'' a ny implica-
tion of the form H => [R /\ "'R] is true only when H is false. Thus, if we a re
able to prove tha t "'P => [ R /\ "'R], we know that P is true. That is the basis
of "proof by contradiction."
To prove a theorem:we prove the equivalent theorem:
H1, H2, ···, H n , :."'P => [R /\ "'R],
or
H1, H2, · · · , H n, ,__,p, :. [R /\ "'R].That is, to prove P we add ,__,p as a hypothesis, and show that this leads to a
contradiction.
(PS-6) PROOF BY CASES:
We b egin with the following observation:Theorem A.3.2 [(P V Q) /\ {(P => R) /\ (Q => R)}] =>Risa tautology.