CS 0441 Lecture Notes - Lecture 7: Counterexample, Rational Number, Contraposition

• School: Pitt
• Department: Computer Science
• Course: CS 0441
• Professor: William Garrison

Document Summary

Mathematical theorems are often stated in the form of an implication. Example: if x > y, where x and y are positive real numbers, then x2. > y2. x,y[(x>0) (y>0) (x>y) (x2 >y2)] x,y p(x,y) q(x,y) In a direct proof, we prove p q by showing that if p is true, then q must necessarily be true. Example: prove that if n is an odd integer, then n2 is an odd integer. That is n = (2k + 1) for some integer k. We can factor the above to get 2(2k2 + 2k) + 1. Since the above quantity is one more than even number, we know that n2 is odd. Direct proofs are not always the easiest way to prove a given conjecture. In this case, we can try proof by contraposition. Recall that p q q p. Therefore, a proof of q p is also a proof of p q.