tailieunhanh - DISCRETE MATHEMATICS NOTES

Learning skills and remembering facts in mathematics are important but they are only the means to an end. Facts and skills are not important in themselves. They are important when we need them to solve a problem. Students will remember facts and skills easily when they use them to solve real problems. As well as using mathematics to solve real-life problems, students should also be taught about the different parts of mathematics, and how they fit together. Mathematics can be taught using a step-by-step approach to a topic but it is important to show that many topics are linked, as shown in the diagram on the next page. It is also. | David A. SANTOS dsantos@ July 17 2008 REVISION ii Contents Preface iii GNU Free Documentation License v 1. APPLICABILITY AND DEFINITIONS . v 2. VERBATIM COPYING. v 3. COPYING IN QUANTITY. v 4. MODIFICATIONS. v 5. COMBINING DOCUMENTS. vi 6. COLLECTIONS OF DOCUMENTS . vi 7. AGGREGATION WITH INDEPENDENT WORKS . . vi 8. TRANSLATION. vi 9. TERMINATION. vi 10. FUTURE REVISIONS OF THIS LICENSE. vi 1 Pseudocode 1 Operators. 1 Algorithms . 2 Arrays . 3 If-then-else Statements. 4 The for loop. 5 The while loop . 8 Homework . 10 Answers . 11 2 Proof Methods 14 Proofs Direct Proofs . 14 Proofs Mathematical Induction . 15 Proofs Reductio ad Absurdum. 17 Proofs Pigeonhole Principle . 19 Homework . 20 Answers . 22 3 Logic Sets and Boolean Algebra 26 Logic . 26 Sets. 29 Boolean Algebras and Boolean Operations . 31 Sum of Products and Products of Sums. 33 Logic Puzzles . 34 Homework . 36 Answers . 36 4 Relations and Functions 38 Partitions and Equivalence Relations . 38 Functions . 40 5 Number Theory 44 Division Algorithm. 44 Greatest Common Divisor . 46 Non-decimal Scales. 48 Congruences . 49 Divisibility Criteria. 51 Homework . 53 Answers . 54 6 Enumeration 57 The Multiplication and Sum Rules . 57 Combinatorial Methods . 59 Permutations without Repetitions . 60 Permutations with Repetitions . 62 Combinations without Repetitions . 64 Combinations with Repetitions . 66 Inclusion-Exclusion . 67 Homework . 72 Answers . 73 7 Sums and Recursions 78 Famous Sums . 78 First Order Recursions . 82 Second Order Recursions . 85 Applications of Recursions . 86 Homework . 87 Answers . 88 8 Graph Theory 89 Simple Graphs . 89 Graphic Sequences . 92 Connectivity . 93 Traversability . 93 Planarity . 95 Homework . 97 Answers . 97 Preface These notes started in the Spring of 2004 but contain material that I have used in previous years.