Schaum's outline of theory and problems of discrete mathematics

Contents......Page 9
1.2 Sets and Elements, Subsets......Page 17
1.3 Venn Diagrams......Page 19
1.4 Set Operations......Page 20
1.5 Algebra of Sets, Duality......Page 23
1.6 Finite Sets, Counting Principle......Page 24
1.7 Classes of Sets, Power Sets, Partitions......Page 26
Solved Problems......Page 28
Supplementary Problems......Page 34
2.2 Product Sets......Page 39
2.3 Relations......Page 40
2.4 Pictorial Representatives of Relations......Page 41
2.5 Composition of Relations......Page 43
2.6 Types of Relations......Page 44
2.7 Closure Properties......Page 46
2.8 Equivalence Relations......Page 47
2.9 Partial Ordering Relations......Page 49
Solved Problems......Page 50
Supplementary Problems......Page 56
3.2 Functions......Page 59
3.3 One-to-One, Onto, and Invertible Functions......Page 62
3.4 Mathematical Functions, Exponential and Logarithmic Functions......Page 63
3.5 Sequences, Indexed Classes of Sets......Page 66
3.6 Recursively Defined Functions......Page 68
3.7 Cardinality......Page 71
3.8 Algorithms and Functions......Page 72
3.9 Complexity of Algorithms......Page 73
Solved Problems......Page 76
Supplementary Problems......Page 82
4.2 Propositions and Compound Statements......Page 86
4.3 Basic Logical Operations......Page 87
4.4 Propositions and Truth Tables......Page 88
4.6 Logical Equivalence......Page 90
4.8 Conditional and Biconditional Statements......Page 91
4.9 Arguments......Page 92
4.10 Propositional Functions, Quantifiers......Page 93
4.11 Negation of Quantified Statements......Page 95
Solved Problems......Page 98
Supplementary Problems......Page 102
5.2 Basic Counting Principles......Page 104
5.3 Mathematical Functions......Page 105
5.4 Permutations......Page 107
5.5 Combinations......Page 109
5.6 The Pigeonhole Principle......Page 110
5.8 Tree Diagrams......Page 111
Solved Problems......Page 112
Supplementary Problems......Page 119
6.2 Combinations with Repetitions......Page 123
6.4 Inclusion–Exclusion Principle Revisited......Page 124
6.5 Pigeonhole Principle Revisited......Page 126
6.6 Recurrence Relations......Page 127
6.7 Linear Recurrence Relations with Constant Coefficients......Page 129
6.8 Solving Second-Order Homogeneous Linear Recurrence Relations......Page 130
6.9 Solving General Homogeneous Linear Recurrence Relations......Page 132
Solved Problems......Page 134
Supplementary Problems......Page 137
7.2 Sample Space and Events......Page 139
7.3 Finite Probability Spaces......Page 142
7.4 Conditional Probability......Page 143
7.5 Independent Events......Page 145
7.6 Independent Repeated Trials, Binomial Distribution......Page 146
7.7 Random Variables......Page 148
7.8 Chebyshev's Inequality, Law of Large Numbers......Page 151
Solved Problems......Page 152
Supplementary Problems......Page 165
8.1 Introduction, Data Structures......Page 170
8.2 Graphs and Multigraphs......Page 172
8.3 Subgraphs, Isomorphic and Homeomorphic Graphs......Page 174
8.4 Paths, Connectivity......Page 175
8.5 Traversable and Eulerian Graphs, Bridges of Königsberg......Page 176
8.7 Complete, Regular, and Bipartite Graphs......Page 178
8.8 Tree Graphs......Page 180
8.9 Planar Graphs......Page 182
8.10 Graph Colorings......Page 184
8.11 Representing Graphs in Computer Memory......Page 187
8.12 Graph Algorithms......Page 189
8.13 Traveling-Salesman Problem......Page 192
Solved Problems......Page 194
Supplementary Problems......Page 207
9.2 Directed Graphs......Page 217
9.3 Basic Definitions......Page 218
9.4 Rooted Trees......Page 220
9.5 Sequential Representation of Directed Graphs......Page 222
9.6 Warshall's Algorithm, Shortest Paths......Page 225
9.7 Linked Representation of Directed Graphs......Page 227
9.8 Graph Algorithms: Depth-First and Breadth-First Searches......Page 229
9.9 Directed Cycle-Free Graphs, Topological Sort......Page 232
9.10 Pruning Algorithm for Shortest Path......Page 234
Solved Problems......Page 237
Supplementary Problems......Page 244
10.2 Binary Trees......Page 251
10.3 Complete and Extended Binary Trees......Page 253
10.4 Representing Binary Trees in Memory......Page 255
10.5 Traversing Binary Trees......Page 256
10.6 Binary Search Trees......Page 258
10.7 Priority Queues, Heaps......Page 260
10.8 Path Lengths, Huffman's Algorithm......Page 264
10.9 General (Ordered Rooted) Trees Revisited......Page 267
Solved Problems......Page 268
Supplementary Problems......Page 275
11.1 Introduction......Page 280
11.2 Order and Inequalities, Absolute Value......Page 281
11.3 Mathematical Induction......Page 282
11.4 Division Algorithm......Page 283
11.5 Divisibility, Primes......Page 285
11.6 Greatest Common Divisor, Euclidean Algorithm......Page 286
11.7 Fundamental Theorem of Arithmetic......Page 289
11.8 Congruence Relation......Page 290
11.9 Congruence Equations......Page 294
Solved Problems......Page 299
Supplementary Problems......Page 315
12.2 Alphabet, Words, Free Semigroup......Page 319
12.3 Languages......Page 320
12.4 Regular Expressions, Regular Languages......Page 321
12.5 Finite State Automata......Page 322
12.6 Grammars......Page 326
Solved Problems......Page 330
Supplementary Problems......Page 335
13.2 Finite State Machines......Page 339
13.4 Turing Machines......Page 342
13.5 Computable Functions......Page 346
Solved Problems......Page 347
Supplementary Problems......Page 350
14.2 Ordered Sets......Page 353
14.3 Hasse Diagrams of Partially Ordered Sets......Page 356
14.5 Supremum and Infimum......Page 358
14.7 Well-Ordered Sets......Page 360
14.8 Lattices......Page 362
14.9 Bounded Lattices......Page 364
14.10 Distributive Lattices......Page 365
14.11 Complements, Complemented Lattices......Page 366
Solved Problems......Page 367
Supplementary Problems......Page 376
15.2 Basic Definitions......Page 384
15.3 Duality......Page 385
15.5 Boolean Algebras as Lattices......Page 386
15.7 Sum-of-Products Form for Sets......Page 387
15.8 Sum-of-Products Form for Boolean Algebras......Page 388
15.9 Minimal Boolean Expressions, Prime Implicants......Page 391
15.10 Logic Gates and Circuits......Page 393
15.11 Truth Tables, Boolean Functions......Page 397
15.12 Karnaugh Maps......Page 399
Solved Problems......Page 405
Supplementary Problems......Page 419
A.2 Vectors......Page 425
A.3 Matrices......Page 426
A.4 Matrix Addition and Scalar Multiplication......Page 427
A.5 Matrix Multiplication......Page 428
A.7 Square Matrices......Page 430
A.8 Invertible (Nonsingular) Matrices, Inverses......Page 431
A.9 Determinants......Page 432
A.10 Elementary Row Operations, Gaussian Elimination (Optional)......Page 434
A.11 Boolean (Zero-One) Matrices......Page 438
Solved Problems......Page 439
Supplementary Problems......Page 445
B.2 Operations......Page 448
B.3 Semigroups......Page 451
B.4 Groups......Page 454
B.5 Subgroups, Normal Subgroups, and Homomorphisms......Page 456
B.6 Rings, Internal Domains, and Fields......Page 459
B.7 Polynomials Over a Field......Page 462
Solved Problems......Page 466
Supplementary Problems......Page 477
Index......Page 483
C......Page 485
F......Page 486
M......Page 487
R......Page 488
V......Page 489
Z......Page 490