6.042J/18.062J 2. Proof by Contradiction

1 February 5, 2010 Albert R Meyer Mathematics for Computer Science MIT 6.042J/18.062J Proof by Cases Proof by Contradiction lec 1F.1 February 5, 2010 Albert R Meyer If so,1332 ≤ 113 Proof by Contradiction Is 1332 3 ≤11? That’s not true, so lec 1F.3 1331 February 5, 2010 Albert R Meyer If an assertion implies something false, then the assertion itself must be false! Proof by Contradiction lec 1F.4 February 5, 2010 Albert R Meyer Proof by Contradiction • Suppose was rational • So have n, d integers without common prime factors such that • We will show that n & d are both even. This contradicts no common factor. Theorem: is irrational. lec 1F.5 February 5, 2010 Albert R Meyer Proof by Contradiction so can assume So d is even So n is even Theorem: is irrational. lec 1F.6 February 5, 2010 Albert R Meyer Quickie Proof assumes that if n2 is even, then n is even. Why is this true? lec 1F.7 2 February 5, 2010 Albert R Meyer Mathematics for Computer Science MIT 6.042J/18.062J Proof by Cases lec 1F.8 February 5, 2010 Albert R Meyer Java Logical Expression if ((x>0) || (x <= 0 && y>100))  (more code) lec 1F.9 if ((x>0) || y>100)  (more code) better: OR  AND  February 5, 2010 Albert R Meyer Case 1: x > 0 lec 1F.10 true true so both are true if ((x>0) || (x <= 0 && y>100)) if ((x>0) || y>100) OR  OR  AND  February 5, 2010 Albert R Meyer Case 2: x ≤ 0 lec 1F.11 false false if ((x>0) || (x <= 0 && y>100)) if ((x>0) || y>100) OR  OR  AND  February 5, 2010 Albert R Meyer if (x <= 0 && y>100) lec 1F.12 ((x>0) || true if ( y>100) AND  Case 2: x ≤ 0 February 5, 2010 Albert R Meyer if ( y>100) lec 1F.13 ((x>0) || so both still the same if ( y>100) Case 2: x ≤ 0 3 February 5, 2010 Albert R Meyer Proof by Cases Reasoning by cases can break a complicated problem into easier subproblems. Some philosophers* think reasoning this way is worrisome. lec 1F.25 *intuitionists February 5, 2010 Albert R Meyer $1,000,000 Question lec 2M.28 Is P = NP ? February 5, 2010 Albert R Meyer The answer is on my desk! (Proof by Cases) lec 1F.30 $1,000,000 Question February 5, 2010 Albert R Meyer Team Problems Problems 1―4 lec 1F.31 MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.