Discrete Structures Lecture Notes

← Back to document page

Discrete StructuresLecture NotesVladlen Koltun1Winter 20081Computer Science Department, 353 Serra Mall, Gates 374, Stanford University, Stanford, CA94305, Sets and Defining sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Set operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . More sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42 Introducing induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Strong induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Why is the induction principle true? . . . . . . . . . . . . . . . . . . . . . .83 More proof Proofs by contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Direct proofs.

2 shortly. The proofs for π and e require mathematical analysis and are outside our scope.) On being formal. Were the above definitions formal enough? The answer is: it depends. For example, defining the natural numbers is an important and non-trivial accomplishment of mathematics. After all, what do these symbols “1”, “2”, “3 ...

  Structure, Proof, Discrete, Mathematical, Discrete structures