Saturday 29 November 2014

Prove using Contrapositive

We already know that "If P implies Q" is logically equivalent to its contrapositive "Not Q implies not P". Therefore, the contrapositive would be equivalent to proving the original statement. In fact, this is sometimes easier to do, and should be used. In class, we used the example "Prove that if x2 is odd then x is odd for all natural numbers x". This becomes much simpler to prove if we prove the contrapositive. We just need to remember to indicate that we are proving the contrapositive, and state the contrapositive in the final prove.

For statements like "if x is odd then x2 is odd", the antecedent is equivalent to the consequence. To prove that two statements are equivalent, we would need to prove that each statement implies the other. First we prove P implies Q, then we prove Q implies P. Another way to prove equivalence is to use a chain of equivalence, whereby P is equivalent to a second statement which links to a chain of equivalent statements until Q.

No comments:

Post a Comment