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 About the Book: This text can be used by the students of mathematics and computer science as an introduction to the fundamentals of discrete mathematics. The book is designed in accordance with the syllabi of B.E., B. Tech., MCA and M.Sc. (Computer Science) prescribed in most of the universities of India. Each chapter is supplemented with a number of worked example as well as a number of problems to be solved by the students. This would help in a better understanding of the subject. Contents: Mathematical Logic Set Theory Relations Functions and Recurrence Relations Boolean Algebra Logic Gates Elementary Combinatorics Graph Theory Algebraic Structures Finite State Machines