Schaums Outline of Discrete Mathematics, Revised Third Edition

Contents......Page 8
1.2 Sets and Elements, Subsets......Page 16
1.3 Venn Diagrams......Page 18
1.4 Set Operations......Page 19
1.5 Algebra of Sets, Duality......Page 22
1.6 Finite Sets, Counting Principle......Page 23
1.7 Classes of Sets, Power Sets, Partitions......Page 25
Solved Problems......Page 27
Supplementary Problems......Page 33
2.2 Product Sets......Page 38
2.3 Relations......Page 39
2.4 Pictorial Representatives of Relations......Page 40
2.5 Composition of Relations......Page 42
2.6 Types of Relations......Page 43
2.7 Closure Properties......Page 45
2.8 Equivalence Relations......Page 46
2.9 Partial Ordering Relations......Page 48
Solved Problems......Page 49
Supplementary Problems......Page 55
3.2 Functions......Page 58
3.3 One-to-One, Onto, and Invertible Functions......Page 61
3.4 Mathematical Functions, Exponential and Logarithmic Functions......Page 62
3.5 Sequences, Indexed Classes of Sets......Page 65
3.6 Recursively Defined Functions......Page 67
3.7 Cardinality......Page 70
3.8 Algorithms and Functions......Page 71
3.9 Complexity of Algorithms......Page 72
Solved Problems......Page 75
Supplementary Problems......Page 81
4.2 Propositions and Compound Statements......Page 85
4.3 Basic Logical Operations......Page 86
4.4 Propositions and Truth Tables......Page 87
4.6 Logical Equivalence......Page 89
4.8 Conditional and Biconditional Statements......Page 90
4.9 Arguments......Page 91
4.10 Propositional Functions, Quantifiers......Page 92
4.11 Negation of Quantified Statements......Page 94
Solved Problems......Page 97
Supplementary Problems......Page 101
5.2 Basic Counting Principles......Page 103
5.3 Mathematical Functions......Page 104
5.4 Permutations......Page 106
5.5 Combinations......Page 108
5.6 The Pigeonhole Principle......Page 109
5.8 Tree Diagrams......Page 110
Solved Problems......Page 111
Supplementary Problems......Page 118
6.2 Combinations with Repetitions......Page 122
6.4 Inclusion–Exclusion Principle Revisited......Page 123
6.5 Pigeonhole Principle Revisited......Page 125
6.6 Recurrence Relations......Page 126
6.7 Linear Recurrence Relations with Constant Coefficients......Page 128
6.8 Solving Second-Order Homogeneous Linear Recurrence Relations......Page 129
6.9 Solving General Homogeneous Linear Recurrence Relations......Page 131
Solved Problems......Page 133
Supplementary Problems......Page 136
7.2 Sample Space and Events......Page 138
7.3 Finite Probability Spaces......Page 141
7.4 Conditional Probability......Page 142
7.5 Independent Events......Page 144
7.6 Independent Repeated Trials, Binomial Distribution......Page 145
7.7 Random Variables......Page 147
7.8 Chebyshev’s Inequality, Law of Large Numbers......Page 150
Solved Problems......Page 151
Supplementary Problems......Page 164
8.1 Introduction, Data Structures......Page 169
8.2 Graphs and Multigraphs......Page 171
8.3 Subgraphs, Isomorphic and Homeomorphic Graphs......Page 173
8.4 Paths, Connectivity......Page 174
8.5 Traversable and Eulerian Graphs, Bridges of Königsberg......Page 175
8.7 Complete, Regular, and Bipartite Graphs......Page 177
8.8 Tree Graphs......Page 179
8.9 Planar Graphs......Page 181
8.10 Graph Colorings......Page 183
8.11 Representing Graphs in Computer Memory......Page 186
8.12 Graph Algorithms......Page 188
8.13 Traveling-Salesman Problem......Page 191
Solved Problems......Page 193
Supplementary Problems......Page 206
9.2 Directed Graphs......Page 216
9.3 Basic Definitions......Page 217
9.4 Rooted Trees......Page 219
9.5 Sequential Representation of Directed Graphs......Page 221
9.6 Warshall’s Algorithm, Shortest Paths......Page 224
9.7 Linked Representation of Directed Graphs......Page 226
9.8 Graph Algorithms: Depth-First and Breadth-First Searches......Page 228
9.9 Directed Cycle-Free Graphs, Topological Sort......Page 231
9.10 Pruning Algorithm for Shortest Path......Page 233
Solved Problems......Page 236
Supplementary Problems......Page 243
10.2 Binary Trees......Page 250
10.3 Complete and Extended Binary Trees......Page 252
10.4 Representing Binary Trees in Memory......Page 254
10.5 Traversing Binary Trees......Page 255
10.6 Binary Search Trees......Page 257
10.7 Priority Queues, Heaps......Page 259
10.8 Path Lengths, Huffman’s Algorithm......Page 263
10.9 General (Ordered Rooted) Trees Revisited......Page 266
Solved Problems......Page 267
Supplementary Problems......Page 274
11.1 Introduction......Page 279
11.2 Order and Inequalities, Absolute Value......Page 280
11.3 Mathematical Induction......Page 281
11.4 Division Algorithm......Page 282
11.5 Divisibility, Primes......Page 284
11.6 Greatest Common Divisor, Euclidean Algorithm......Page 285
11.7 Fundamental Theorem of Arithmetic......Page 288
11.8 Congruence Relation......Page 289
11.9 Congruence Equations......Page 293
Solved Problems......Page 298
Supplementary Problems......Page 314
12.2 Alphabet,Words, Free Semigroup......Page 318
12.3 Languages......Page 319
12.4 Regular Expressions, Regular Languages......Page 320
12.5 Finite State Automata......Page 321
12.6 Grammars......Page 325
Solved Problems......Page 329
Supplementary Problems......Page 334
13.2 Finite State Machines......Page 338
13.4 Turing Machines......Page 341
13.5 Computable Functions......Page 345
Solved Problems......Page 346
Supplementary Problems......Page 349
14.2 Ordered Sets......Page 352
14.3 Hasse Diagrams of Partially Ordered Sets......Page 355
14.5 Supremum and Infimum......Page 357
14.7 Well-Ordered Sets......Page 359
14.8 Lattices......Page 361
14.9 Bounded Lattices......Page 363
14.10 Distributive Lattices......Page 364
14.11 Complements, Complemented Lattices......Page 365
Solved Problems......Page 366
Supplementary Problems......Page 375
15.2 Basic Definitions......Page 383
15.3 Duality......Page 384
15.5 Boolean Algebras as Lattices......Page 385
15.7 Sum-of-Products Form for Sets......Page 386
15.8 Sum-of-Products Form for Boolean Algebras......Page 387
15.9 Minimal Boolean Expressions, Prime Implicants......Page 390
15.10 Logic Gates and Circuits......Page 392
15.11 Truth Tables, Boolean Functions......Page 396
15.12 Karnaugh Maps......Page 398
Solved Problems......Page 404
Supplementary Problems......Page 418
A.2 Vectors......Page 424
A.3 Matrices......Page 425
A.4 Matrix Addition and Scalar Multiplication......Page 426
A.5 Matrix Multiplication......Page 427
A.7 Square Matrices......Page 429
A.8 Invertible (Nonsingular) Matrices, Inverses......Page 430
A.9 Determinants......Page 431
A.10 Elementary Row Operations, Gaussian Elimination (Optional)......Page 433
A.11 Boolean (Zero-One) Matrices......Page 437
Solved Problems......Page 438
Supplementary Problems......Page 444
B.2 Operations......Page 447
B.3 Semigroups......Page 450
B.4 Groups......Page 453
B.5 Subgroups, Normal Subgroups, and Homomorphisms......Page 455
B.6 Rings, Internal Domains, and Fields......Page 458
B.7 Polynomials Over a Field......Page 461
Solved Problems......Page 465
Supplementary Problems......Page 476
Index......Page 482
C......Page 484
F......Page 485
M......Page 486
R......Page 487
V......Page 488
Z......Page 489