Lecture Notes on Discrete Mathematics
July 30, 2019
T
AF
DR
, 2
DR
AF
T
,Contents
1 Basic Set Theory 7
1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Operations on sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Composition of functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Equivalence relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 The Natural Number System 25
2.1 Peano Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Other forms of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . 28
2.3 Applications of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . 31
2.4 Well Ordering Property of Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . 33
T
AF
2.5 Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6 Construction of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
DR
2.7 Construction of Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Countable and Uncountable Sets 43
3.1 Finite and infinite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Families of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Constructing bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Cantor-Schröder-Bernstein Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5 Countable and uncountable sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4 Elementary Number Theory 61
4.1 Division algorithm and its applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5 Combinatorics - I 71
5.1 Addition and multiplication rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2 Permutations and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2.1 Counting words made with elements of a set S . . . . . . . . . . . . . . . . . . 73
5.2.2 Counting words with distinct letters made with elements of a set S . . . . . . . 74
5.2.3 Counting words where letters may repeat . . . . . . . . . . . . . . . . . . . . . 75
5.2.4 Counting subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.5 Pascal’s identity and its combinatorial proof . . . . . . . . . . . . . . . . . . . . 77
3
, 4 CONTENTS
5.2.6 Counting in two ways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.3 Solutions in non-negative integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.4 Binomial and multinomial theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.5 Circular arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.6 Set partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.7 Number partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.8 Lattice paths and Catalan numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6 Combinatorics - II 103
6.1 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2 Principle of Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.3 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3.1 Generating Functions and Partitions of n . . . . . . . . . . . . . . . . . . . . . 116
6.4 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.5 Generating Function from Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . 124
7 Introduction to Logic 133
7.1 Logic of Statements (SL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.2 Formulas and truth values in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.3 Equivalence and Normal forms in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.4 Inferences in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.5 Predicate logic (PL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
T
7.6 Equivalences and Validity in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
AF
7.7 Inferences in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
DR
8 Partially Ordered Sets, Lattices and Boolean Algebra 161
8.1 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
8.3 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.4 Axiom of choice and its equivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
9 Graphs - I 191
9.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.2 Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
9.3 Isomorphism in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
9.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
9.5 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
9.6 Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
9.7 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
9.8 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.9 Vertex coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
10 Graphs - II 221
10.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
10.2 Matching in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
10.3 Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
10.4 Degree sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
July 30, 2019
T
AF
DR
, 2
DR
AF
T
,Contents
1 Basic Set Theory 7
1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Operations on sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Composition of functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Equivalence relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 The Natural Number System 25
2.1 Peano Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Other forms of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . 28
2.3 Applications of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . 31
2.4 Well Ordering Property of Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . 33
T
AF
2.5 Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6 Construction of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
DR
2.7 Construction of Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Countable and Uncountable Sets 43
3.1 Finite and infinite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Families of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Constructing bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Cantor-Schröder-Bernstein Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5 Countable and uncountable sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4 Elementary Number Theory 61
4.1 Division algorithm and its applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5 Combinatorics - I 71
5.1 Addition and multiplication rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2 Permutations and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2.1 Counting words made with elements of a set S . . . . . . . . . . . . . . . . . . 73
5.2.2 Counting words with distinct letters made with elements of a set S . . . . . . . 74
5.2.3 Counting words where letters may repeat . . . . . . . . . . . . . . . . . . . . . 75
5.2.4 Counting subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.5 Pascal’s identity and its combinatorial proof . . . . . . . . . . . . . . . . . . . . 77
3
, 4 CONTENTS
5.2.6 Counting in two ways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.3 Solutions in non-negative integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.4 Binomial and multinomial theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.5 Circular arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.6 Set partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.7 Number partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.8 Lattice paths and Catalan numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6 Combinatorics - II 103
6.1 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2 Principle of Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.3 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3.1 Generating Functions and Partitions of n . . . . . . . . . . . . . . . . . . . . . 116
6.4 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.5 Generating Function from Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . 124
7 Introduction to Logic 133
7.1 Logic of Statements (SL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.2 Formulas and truth values in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.3 Equivalence and Normal forms in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.4 Inferences in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.5 Predicate logic (PL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
T
7.6 Equivalences and Validity in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
AF
7.7 Inferences in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
DR
8 Partially Ordered Sets, Lattices and Boolean Algebra 161
8.1 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
8.3 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.4 Axiom of choice and its equivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
9 Graphs - I 191
9.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.2 Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
9.3 Isomorphism in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
9.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
9.5 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
9.6 Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
9.7 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
9.8 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.9 Vertex coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
10 Graphs - II 221
10.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
10.2 Matching in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
10.3 Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
10.4 Degree sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
