Discrete Mathematical Structures: A Succinct Foundation PDF by B. V. Senthil Kumar and Hemen Dutta

By

Discrete Mathematical Structures: A Succinct Foundation

By B. V. Senthil Kumar and Hemen Dutta

Discrete Mathematical Structures

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

This book is US$10
To get free sample pages OR Buy this book


Share this Book!

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.