Exam (elaborations) DISCRETE MATHEMATICS (SMA3111)

Notes on
Discrete Mathematics


Miguel A. Lerma

,
, Contents

Introduction 5
Chapter 1. Logic, Proofs 6
1.1. Propositions 6
1.2. Predicates, Quantifiers 11
1.3. Proofs 13
Chapter 2. Sets, Functions, Relations 19
2.1. Set Theory 19
2.2. Functions 27
2.3. Relations 32
Chapter 3. Algorithms, Integers 38
3.1. Algorithms 38
3.2. The Euclidean Algorithm 48
3.3. Modular Arithmetic, RSA Algorithm 52
Chapter 4. Induction, Recurences 59
4.1. Sequences and Strings 59
4.2. Mathematical Induction 62
4.3. Recurrence Relations 65
Chapter 5. Counting 69
5.1. Basic Principles 69
5.2. Combinatorics 71
5.3. Generalized Permutations and Combinations 73
5.4. Binomial Coefficients 75
5.5. The Pigeonhole Principle 77
Chapter 6. Probability 78
6.1. Probability 78
Chapter 7. Graph Theory 82
7.1. Graphs 82
7.2. Representations of Graphs 88
7.3. Paths and Circuits 91
3

, CONTENTS 4

7.4. Planar Graphs 97
Chapter 8. Trees 100
8.1. Trees 100
8.2. Binary Trees 102
8.3. Decision Trees, Tree Isomorphisms 104
8.4. Tree Transversal 113
8.5. Spanning Trees 116
Chapter 9. Boolean Algebras 122
9.1. Combinatorial Circuits 122
9.2. Boolean Functions, Applications 127
Chapter 10. Automata, Grammars and Languages 133
10.1. Finite State Machines 133
10.2. Languages and Grammars 137
10.3. Language Recognition 144
Appendix A. 150
A.1. Efficient Computation of Powers Modulo m 150
A.2. Machines and Languages 152