Discrete Mathematical Structures: A Succinct Foundation
By B. V. Senthil Kumar and Hemen Dutta
Contents
Preface ix
Authors xi
1 Logics and Proofs 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Compound Propositions . . . . . . . . . . . . . . . . . . . . . 1
1.4 Truth Table . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Logical Operators . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5.1 Negation . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5.2 Conjunction . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5.3 Disjunction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5.4 Molecular Statements . . . . . . . . . . . . . . . . . . 3
1.5.5 Conditional Statement [If . . . then] [ ! ] . . . . . . . 3
1.5.6 Biconditional [If and only if or i_] [ $ or ] . . . . . 4
1.5.7 Solved Problems . . . . . . . . . . . . . . . . . . . . . 4
1.5.8 Tautology . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5.9 Contradiction . . . . . . . . . . . . . . . . . . . . . . . 6
1.5.10 Contingency . . . . . . . . . . . . . . . . . . . . . . . 6
1.5.11 Equivalence Formulas . . . . . . . . . . . . . . . . . . 6
1.5.12 Equivalent Formulas . . . . . . . . . . . . . . . . . . . 7
1.5.13 Duality Law . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.14 Tautological Implication . . . . . . . . . . . . . . . . . 7
1.5.15 Some More Equivalence Formulas . . . . . . . . . . . . 7
1.5.16 Solved Problems . . . . . . . . . . . . . . . . . . . . . 8
1.6 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6.1 Principal Disjunctive Normal Form or Sum of Products Canonical Form . . . . . . . . . . . . . . . 9
1.6.2 Principal Conjunctive Normal Form or Product of Sum Canonical Form . . . . . . . . . . . . . . . . . 10
1.6.3 Solved Problems . . . . . . . . . . . . . . . . . . . . . 10
1.7 Inference Theory . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1 Rules of Inference . . . . . . . . . . . . . . . . . . . . 14
1.7.2 Solved Problems . . . . . . . . . . . . . . . . . . . . . 15
1.8 Indirect Method of Proof . . . . . . . . . . . . . . . . . . . . 19
1.8.1 Method of Contradiction . . . . . . . . . . . . . . . . 19
1.8.2 Solved Problems . . . . . . . . . . . . . . . . . . . . . 19
1.9 Method of Contrapositive . . . . . . . . . . . . . . . . . . . . 21
1.9.1 Solved Problems . . . . . . . . . . . . . . . . . . . . . 21
1.10 Various Methods of Proof . . . . . . . . . . . . . . . . . . . . 21
1.10.1 Trivial Proof . . . . . . . . . . . . . . . . . . . . . . . 21
1.10.2 Vacuous Proof . . . . . . . . . . . . . . . . . . . . . . 22
1.10.3 Direct Proof . . . . . . . . . . . . . . . . . . . . . . . 22
1.11 Predicate Calculus . . . . . . . . . . . . . . . . . . . . . . . . 22
1.11.1 Quantiers . . . . . . . . . . . . . . . . . . . . . . . . 23
1.11.2 Universe of Discourse, Free and Bound Variables . . . 23
1.11.3 Solved Problems . . . . . . . . . . . . . . . . . . . . . 24
1.11.4 Inference Theory for Predicate Calculus . . . . . . . . 28
1.11.5 Solved Problems . . . . . . . . . . . . . . . . . . . . . 28
1.12 Additional Solved Problems . . . . . . . . . . . . . . . . . . 32
2 Combinatorics 39
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . 39
2.2.1 Principle of Mathematical Induction . . . . . . . . . . 39
2.2.2 Procedure to Prove that a Statement P(n) is True for all Natural Numbers . . . . . . . . . . . . . . . . . . . 40
2.2.3 Solved Problems . . . . . . . . . . . . . . . . . . . . . 40
2.2.4 Problems for Practice . . . . . . . . . . . . . . . . . . 56
2.2.5 Strong Induction . . . . . . . . . . . . . . . . . . . . . 57
2.2.6 Well-Ordering Property . . . . . . . . . . . . . . . . . 57
2.3 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . 58
2.3.1 Generalized Pigeonhole Principle . . . . . . . . . . . . 58
2.3.2 Solved Problems . . . . . . . . . . . . . . . . . . . . . 58
2.3.3 Another Form of Generalized Pigeonhole Principle . . 60
2.3.4 Solved Problems . . . . . . . . . . . . . . . . . . . . . 61
2.3.5 Problems for Practice . . . . . . . . . . . . . . . . . . 69
2.4 Permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.4.1 Permutations with Repetitions . . . . . . . . . . . . . 71
2.4.2 Solved Problems . . . . . . . . . . . . . . . . . . . . . 72
2.4.3 Problems for Practice . . . . . . . . . . . . . . . . . . 79
2.5 Combination . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.5.1 Solved Problems . . . . . . . . . . . . . . . . . . . . . 81
2.5.2 Problems for Practice . . . . . . . . . . . . . . . . . . 85
2.5.3 Recurrence Relation . . . . . . . . . . . . . . . . . . . 87
2.5.4 Solved Problems . . . . . . . . . . . . . . . . . . . . . 87
2.5.5 Linear Recurrence Relation . . . . . . . . . . . . . . . 88
2.5.6 Homogenous Recurrence Relation . . . . . . . . . . . . 88
2.5.7 Recurrence Relations Obtained from Solutions . . . . 89
2.6 Solving Linear Homogenous Recurrence Relations . . . . . . 90
2.6.1 Characteristic Equation . . . . . . . . . . . . . . . . . 91
2.6.2 Algorithm for Solving kth-order Homogenous Linear Recurrence Relations . . . . . . . . . . . . . . . . . . . 91
2.6.3 Solved Problems . . . . . . . . . . . . . . . . . . . . . 92
2.7 Solving Linear Non-homogenous Recurrence Relations . . . . 95
2.7.1 Solved Problems . . . . . . . . . . . . . . . . . . . . . 96
2.7.2 Problems for Practice . . . . . . . . . . . . . . . . . . 102
2.8 Generating Functions . . . . . . . . . . . . . . . . . . . . . . 103
2.8.1 Solved Problems . . . . . . . . . . . . . . . . . . . . . 103
2.8.2 Solution of Recurrence Relations Using Generating Function . . . . . . . . . . . . . . . . . . . 106
2.8.3 Solved Problems . . . . . . . . . . . . . . . . . . . . . 106
2.8.4 Problems for Practice . . . . . . . . . . . . . . . . . . 116
2.9 Inclusion{Exclusion Principle . . . . . . . . . . . . . . . . . . 117
2.9.1 Solved Problems . . . . . . . . . . . . . . . . . . . . . 118
2.9.2 Problems for Practice . . . . . . . . . . . . . . . . . . 131
3 Graphs 135
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.2 Graphs and Graph Models . . . . . . . . . . . . . . . . . . . 135
3.3 Graph Terminology and Special Types of Graphs . . . . . . 138
3.3.1 Solved Problems . . . . . . . . . . . . . . . . . . . . . 140
3.3.2 Graph Colouring . . . . . . . . . . . . . . . . . . . . . 145
3.3.3 Solved Problems . . . . . . . . . . . . . . . . . . . . . 145
3.4 Representing Graphs and Graph Isomorphism . . . . . . . . 149
3.4.1 Solved Problems . . . . . . . . . . . . . . . . . . . . . 151
3.4.2 Problems for Practice . . . . . . . . . . . . . . . . . . 155
3.5 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
3.5.1 Connected and Disconnected Graphs . . . . . . . . . . 158
3.6 Eulerian and Hamiltonian Paths . . . . . . . . . . . . . . . . 161
3.6.1 Hamiltonian Path and Hamiltonian Circuits . . . . . . 163
3.6.2 Solved Problems . . . . . . . . . . . . . . . . . . . . . 164
3.6.3 Problems for Practice . . . . . . . . . . . . . . . . . . 169
3.6.4 Additional Problems for Practice . . . . . . . . . . . . 169
4 Algebraic Structures 173
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
4.2 Algebraic Systems . . . . . . . . . . . . . . . . . . . . . . . . 173
4.2.1 Semigroups and Monoids . . . . . . . . . . . . . . . . 174
4.2.2 Solved Problems . . . . . . . . . . . . . . . . . . . . . 175
4.2.3 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 183
4.2.4 Solved Problems . . . . . . . . . . . . . . . . . . . . . 186
4.2.5 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.2.6 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . 193
4.2.7 Homomorphisms . . . . . . . . . . . . . . . . . . . . . 195
4.2.8 Cosets and Normal Subgroups . . . . . . . . . . . . . 197
4.2.9 Solved Problems . . . . . . . . . . . . . . . . . . . . . 202
4.2.10 Permutation Functions . . . . . . . . . . . . . . . . . . 208
4.2.11 Solved Problems . . . . . . . . . . . . . . . . . . . . . 211
4.2.12 Problems for Practice . . . . . . . . . . . . . . . . . . 216
4.2.13 Rings and Fields . . . . . . . . . . . . . . . . . . . . . 217
4.2.14 Solved Problems . . . . . . . . . . . . . . . . . . . . . 220
4.2.15 Problems for Practice . . . . . . . . . . . . . . . . . . 222
5 Lattices and Boolean Algebra 223
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
5.2 Partial Ordering and Posets . . . . . . . . . . . . . . . . . . 223
5.2.1 Representation of a Poset by Hasse Diagram . . . . . 224
5.2.2 Solved Problems . . . . . . . . . . . . . . . . . . . . . 226
5.2.3 Problems for Practice . . . . . . . . . . . . . . . . . . 230
5.3 Lattices, Sublattices, Direct Product, Homomorphism
of Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
5.3.1 Properties of Lattices . . . . . . . . . . . . . . . . . . 231
5.3.2 Theorems on Lattices . . . . . . . . . . . . . . . . . . 233
5.3.3 Solved Problems . . . . . . . . . . . . . . . . . . . . . 236
5.3.4 Problem for Practice . . . . . . . . . . . . . . . . . . . 240
5.4 Special Lattices . . . . . . . . . . . . . . . . . . . . . . . . . 240
5.4.1 Solved Problems . . . . . . . . . . . . . . . . . . . . . 242
5.4.2 Problems for Practice . . . . . . . . . . . . . . . . . . 247
5.5 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . 248
5.5.1 Solved Problems . . . . . . . . . . . . . . . . . . . . . 252
5.5.2 Problems for Practice . . . . . . . . . . . . . . . . . . 255
Bibliography 257
Index 259