Discrete Mathematics Structures

Preface to the Second Edition......Page 8
Preface to the First Edition......Page 10
Contents......Page 12
1.3 Laws of Formal Logic......Page 20
1.4 Connectives and Compound Statements......Page 21
1.6 Solved Examples......Page 23
Exercise 1.1......Page 25
1.7 Conditional Statements......Page 28
1.8 Well Formed Formulas......Page 30
1.13 Solved Examples......Page 31
1.14 Laws of Logic......Page 33
1.16 Solved Examples......Page 34
1.17 Logical Implication......Page 36
1.18 Other Connectives......Page 37
1.19 Normal Forms......Page 39
Exercise 1.2......Page 41
1.20 Solved Examples......Page 44
Exercise 1.3......Page 45
1.21 Quantifiers......Page 47
1.22 Methods of Proof......Page 50
Exercise 1.4......Page 61
2.2 Sets and Operations on Sets......Page 63
2.3 Subsets......Page 64
2.5 Singleton......Page 65
2.10 Disjoints Sets......Page 66
2.13 Properties of Union Operations......Page 67
2.15 Properties of Intersection Operation......Page 70
2.16 Distributive Laws......Page 72
2.18 Properties of Complementation......Page 73
2.19 Properties of Difference......Page 75
2.21 Properties of Symmetric Difference......Page 76
2.22 Venn Diagrams......Page 77
Exercise 2.1......Page 78
2.25 Sets of Numbers......Page 81
2.26 Cardinality......Page 82
2.27 Cartesian Product of Sets......Page 84
Exercise 2.2......Page 86
3.1 Concept of Relation......Page 88
3.2 Properties of Relations......Page 89
3.3 Miscellaneous Examples......Page 90
3.7 Universal Relation......Page 91
3.10 Equivalence Classes......Page 92
3.12 Tabular Form of a Relation......Page 94
3.14 Transitive Closure......Page 96
3.15 Matrix Representation of Relations......Page 98
3.16 Relations and Digraphs......Page 99
3.17 Composition of Relations......Page 103
Exercise 3.1......Page 104
4.2 Function......Page 109
4.3 One-to-One Mapping (Injection One-to-One Function )......Page 110
4.7 Composition of Functions......Page 111
4.10 Inverse Mapping......Page 112
4.12 Solved Examples......Page 115
Exercise 4.1......Page 117
4.13 Recursion and Recurrence Relations......Page 119
4.14 Recurrence Relations and Solutions of Recurrence Relations......Page 126
4.15 Generating Functions......Page 127
4.16 Solution of Non-Homogeneous Linear Recurrence Relations......Page 132
Exercise 4.3......Page 135
5.3 Totally Ordered Set......Page 137
5.5 Hasse Diagram......Page 138
5.6 Lexicographic Ordering......Page 140
5.8 Least and Greatest Elements
......Page 141
5.9 Minimal and Maximal Elements (Members)
......Page 142
5.10 Upper and Lower Bounds......Page 143
5.13 Choice Functions......Page 146
5.16 Lattices......Page 147
5.17 Some Properties of Lattices......Page 148
5.19 Bounded Lattices......Page 149
5.20 Sub Lattices, Direct Products
......Page 151
Exercise 5.1......Page 154
5.21 Boolean Algebra......Page 156
5.22 Sub-Boolean Algebra......Page 160
5.25 Atoms of Boolean Algebra......Page 161
5.26 Boolean Expressions and Minimization of Boolean Functions......Page 162
5.27 Minimization of Boolean Expressions......Page 167
Exercise 5.2......Page 180
6.1 Introduction......Page 182
6.2 Gates and Boolean Algebra......Page 184
6.3 Applications......Page 192
6.4 Special Sequences......Page 198
Exercise 6.1......Page 199
7.2 Basics of Counting......Page 203
Exercise 7.1......Page 205
7.3 Permutations and Combinations......Page 206
7.4 Solved Examples......Page 208
7.5 Permutations with Like Elements
......Page 209
7.6 Circular Permutations......Page 210
Exercise 7.2......Page 212
7.7 Combinations......Page 214
7.8 Power Set......Page 215
7.9 Basic Identities......Page 217
7.10 Partition and Cross Partitions......Page 219
7.11 Permutations and Combinations with Unlimited Repetitions......Page 221
Exercise 7.3......Page 223
7.12 The Pigeonhole Principle......Page 225
7.13 Binomial Theorem......Page 227
7.14 Solved Examples......Page 232
7.15 Multinomial Theorem......Page 234
Exercise 7.5......Page 235
8.2 Basic Definitions......Page 237
8.3 Incidence and Degree......Page 240
8.5 Size of a Graph......Page 244
8.6 Solved Examples......Page 247
Exercise 8.1......Page 252
8.8 Adjacency......Page 256
8.9 Matrix Representation of Graphs......Page 257
8.10 Linked Representation (or Adjacency Structure)......Page 259
8.11 The Cycle Matrix......Page 260
8.12 Path Matrix......Page 261
Exercise 8.2......Page 262
8.13 Walks, Paths and Circuits......Page 268
8.14 Subgraphs......Page 271
8.15 Removal of Vertices and Edges from a Graph......Page 272
8.17 Operations on Graphs......Page 273
8.18 Complement of a Graph......Page 276
8.19 Connected Graph......Page 277
8.20 Partitions......Page 278
8.23 Wheel Graph......Page 281
8.24 Bipartite Graph......Page 282
8.25 Solved Examples......Page 283
8.26 Isomorphism
......Page 284
8.27 Solved Examples......Page 285
Exercise 8.3......Page 290
8.28 Forest......Page 293
8.31 Cut Set......Page 294
8.33 Labled and Weighted Graphs......Page 295
8.34 Connectivity......Page 296
8.35 Trees and Some Properties of Trees......Page 299
8.36 Distance......Page 301
8.37 Spanning Tree......Page 304
8.38 Rooted Tree......Page 311
8.40 Binary Tree......Page 313
8.41 Solved Examples......Page 316
8.43 High Balanced Binary Tree......Page 317
8.45 Distance between Spanning Trees of a Graph......Page 318
8.47 Rank and Nullity
......Page 319
8.48 Planar Graphs......Page 322
8.49 Homeomorphic Graphs......Page 328
8.50 Dual of a Graph......Page 329
8.51 Solved Examples......Page 331
Exercise 8.6......Page 332
8.52 Eulers Graphs......Page 333
Exercise 8.7......Page 337
8.53 Hamiltonian Graphs......Page 338
Exercise 8.8......Page 344
8.54 Graph Colouring......Page 346
Exercise 8.9......Page 355
8.55 Digraphs......Page 357
8.56 Relations and Diagraphs......Page 359
8.57 Arborescence......Page 361
8.58 Warshall'a Algorithm......Page 362
Exercise 8.10......Page 364
9.3 General Properties......Page 366
Exercise 9.1......Page 368
9.5 Algebraic Structures (Algebraic Systems)
......Page 369
9.7 Homomorphism of Semi-Groups......Page 370
9.9 Monoid......Page 371
9.11 Groups......Page 372
9.12 Solved Examples......Page 373
9.13 Addition Modulo m......Page 377
9.14 Multiplication Modulo P......Page 378
9.16 Congruences......Page 379
Exercise 9.2......Page 380
9.17 Elementary Properties of Groups......Page 381
9.18 Alternative Postulates for a Group......Page 384
9.19 Order of an Element......Page 385
9.20 Sub-Group......Page 387
9.22 Cosets......Page 389
9.23 Index of a Sub-Group......Page 392
Exercise 9.3......Page 393
9.24 Isomorphism
......Page 394
9.25 Properties of Isomerphism......Page 395
9.26 Cyclic Groups
......Page 396
Exercise 9.4......Page 398
9.27 Normal Sub-Groups
......Page 399
9.28 Permutation Groups......Page 401
9.29 Cyclic Permutation
......Page 404
9.30 Group Homomorphism......Page 408
9.31 Kernal of a Homomorphism......Page 409
9.32 Solved Examples......Page 411
Exercise 9.5......Page 413
9.33 Algebraic System with two Binary Operations......Page 414
9.34 Special Types of Rings......Page 415
9.35 Properties of Rings......Page 416
9.37 Coefficients and Exponents......Page 418
Exercise 9.6......Page 421
10.1 Introduction......Page 423
10.2 Transition Table......Page 424
10.3 Transition Diagram (State Diagram)......Page 425
10.4 Finite State Machine (Alternative Definition)......Page 426
10.5 Equivalence of Finite State Machines......Page 429
10.6 Covering......Page 430
10.7 Finite State Homomorphism......Page 433
Exercise 10.1......Page 435
10.8 Formal Language, Grammer......Page 438
10.9 Finite Automata......Page 442
Exercise 10.2......Page 447
10.10 Non-Deterministic Finite Automation (NDFA)......Page 448
10.11 Finite Automata with Outputs......Page 452
Bibliography......Page 454
Index......Page 455