1lec 1W.1September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Mathematics for Computer Science6.042J/18.062JWELCOME!Prof. Albert R. Meyer Prof. Ronitt Rubinfeldhttp://theory.lcs.mit.edu/classes/6.042“Proof, Proofs & More Proofs”lec 1W.2September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Quick Summary1.Fundamental Concepts of Discrete Mathematics.2.Discrete Mathematical Structures(like trees or lists)3.Discrete Probability Theory.lec 1W.3September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.VocabularyQuickie:What does “discrete” mean?(≠ “discreet”)lec 1W.4September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Online Tutor Problems 1Due Friday, 1pm:Part 1.1:Course RegistrationDue Monday, 1pm:Part 1.2: Diagnostic Questionnairelec 1W.5September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Reading AssignmentReading: see course calendarEmail comments:due Wednesday 11amlec 1W.6September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Course Organization• Web site: All course handouts.• Problem Sets: up to 30% of grade (see course info).2lec 1W.7September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.• Studio-Lecture Style:mix of mini-lectures &team problem-solving;preparation & attendancerequired (25% of grade)Course Organizationlec 1W.8September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Active LecturesSay “hello” to your neighbors -- you’ll be working with them .lec 1W.9September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Active LecturesQuickie question:Where was your neighbor born?lec 1W.10September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Getting started: Pythagorean theorem 222abc+=Familiar? Yes!Obvious? No!cbalec 1W.11September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.A Cool Proof(Many many proofs: http://www.cut-the-knot.com)cbaRearrange into: (i) a c×c square, and then(ii) an a×a & a b×b squarecc×cc×b-ab-alec 1W.12September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.A Cool Proofcccabc3lec 1W.13September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.A Cool Proofbaablec 1W.14September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.A False Proof:Getting Rich By Diagram1110111111111110lec 1W.15September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.11Profit!101011111111A False Proof:Getting Rich By Diagramlec 1W.16September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.The bug:are not right triangles!The top and bottom line of the “rectangle”is not straight!Getting Rich1011111lec 1W.17September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Another False ProofTheorem: Every polynomial,has two roots over C.Proof (by calculation): cbxax ++2aacbbr2421−+−=aacbbr2422−−−=The polynomialandhas roots2,ax bx c++lec 1W.18September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Another False proofCounter-examples: The bug: divide by zero error.The fix: assume a ≠ 0.2011xx++has 1 root.1002++ xxhas 0 roots.4lec 1W.19September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Another false proofCounter-example:The bug:r1 = r2The fix: need hypothesis D ≠ 0where1x2 + 0x + 0 has 1 root.2:: 4Dbac=−lec 1W.20September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Another false proofAmbiguity when D < 0:x2+ 1 has roots i, -i.Which is r1, which is r2?lec 1W.21September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.1 = -1 ?The ambiguity causes problems:()211 (1)(1) 11 1 1==−−=−−=− =−Moral: “mindless” calculation not safe.1. Be sure rules are properly applied.2. Calculation is a risky substitute for understanding. lec 1W.22September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.½= −½ (multiply by ½)2 = 1 (add )Consequences of 1= −1“Since I and the Pope are clearly 2, we conclude thatI and the Pope are 1.That is, I am the Pope.”-- Bertrand Russell23lec 1W.23September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.Consequences of 1= −1Bertrand Russell (1872 - 1970)(Picture source: http://www.users.drew.edu/~jlenz/brs.html)lec 1W.24September 7, 2005Copyright © Albert R. Meyer, 2005 All rights reserved.In-class ProblemsPROBLEMS 1 &
View Full Document