Lehman E, Leighton T - Mathematics for Computer Science (Lecture Notes)(MIT 2004)(339s).pdf

文档介绍：Mathematics puter Science
Eric Lehman and Tom Leighton
2004
2
Contents
1 What is a Proof? 15
Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Logical Deductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Examples of Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
A Tautology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
A Proof by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . 22
2 Induction I 23
A Warmup Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Using Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
A Divisibility Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
A Faulty Induction Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Courtyard Tiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Another Faulty Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 Induction II 35
Good Proofs and Bad Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
A Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Unstacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Analyzing the Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3
4 CONTENTS
4 Number Theory I 45
A Theory of the Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Divisibility . . . . . . . . . . . . . . . . . .