Unformatted text preview:

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 Proofbaablec 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

MIT 6 042J - Lecture Slides

Documents in this Course
Counting

Counting

55 pages

Graphs

Graphs

19 pages

Proofs

Proofs

14 pages

Proofs

Proofs

18 pages

Proofs

Proofs

18 pages

Quiz 1

Quiz 1

9 pages

Quiz 2

Quiz 2

11 pages

Load more
Download Lecture Slides
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Slides and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Slides 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?