This is the best e-book in discrete mathematics. in this book include the exercise and solutions, that let you guys easy to understand of discrete mathematics.
Contents in this book:
CHAPTER 1 Set Theory 1
1.1 Introduction 1
1.2 Sets and Elements, Subsets 1
1.3 Venn Diagrams 3
1.4 Set Operations 4
1.5 Algebra of Sets, Duality 7
1.6 Finite Sets, Counting Principle 8
1.7 Classes of Sets, Power Sets, Partitions 10
1.8 Mathematical Induction 12
Solved Problems 12
Supplementary Problems 18
CHAPTER 2 Relations 23
2.1 Introduction 23
2.2 Product Sets 23
2.3 Relations 24
2.4 Pictorial Representatives of Relations 25
2.5 Composition of Relations 27
2.6 Types of Relations 28
2.7 Closure Properties 30
2.8 Equivalence Relations 31
2.9 Partial Ordering Relations 33
Solved Problems 34
Supplementary Problems 40
CHAPTER 3 Functions and Algorithms 43
3.1 Introduction 43
3.2 Functions 43
3.3 One-to-One, Onto, and Invertible Functions 46
3.4 Mathematical Functions, Exponential and Logarithmic Functions 47
3.5 Sequences, Indexed Classes of Sets 50
3.6 Recursively Defined Functions 52
3.7 Cardinality 55
3.8 Algorithms and Functions 56
3.9 Complexity of Algorithms 57
Solved Problems 60
Supplementary Problems 66
vii
For more information about this title, click here
viii CONTENTS
CHAPTER 4 Logic and Propositional Calculus 70
4.1 Introduction 70
4.2 Propositions and Compound Statements 70
4.3 Basic Logical Operations 71
4.4 Propositions and Truth Tables 72
4.5 Tautologies and Contradictions 74
4.6 Logical Equivalence 74
4.7 Algebra of Propositions 75
4.8 Conditional and Biconditional Statements 75
4.9 Arguments 76
4.10 Propositional Functions, Quantifiers 77
4.11 Negation of Quantified Statements 79
Solved Problems 82
Supplementary Problems 86
CHAPTER 5 Techniques of Counting 88
5.1 Introduction 88
5.2 Basic Counting Principles 88
5.3 Mathematical Functions 89
5.4 Permutations 91
5.5 Combinations 93
5.6 The Pigeonhole Principle 94
5.7 The Inclusion–Exclusion Principle 95
5.8 Tree Diagrams 95
Solved Problems 96
Supplementary Problems 103
CHAPTER 6 Advanced Counting Techniques, Recursion 107
6.1 Introduction 107
6.2 Combinations with Repetitions 107
6.3 Ordered and Unordered Partitions 108
6.4 Inclusion–Exclusion Principle Revisited 108
6.5 Pigeonhole Principle Revisited 110
6.6 Recurrence Relations 111
6.7 Linear Recurrence Relations with Constant Coefficients 113
6.8 Solving Second-Order Homogeneous Linear Recurrence
Relations 114
6.9 Solving General Homogeneous Linear Recurrence Relations 116
Solved Problems 118
Supplementary Problems 121
CHAPTER 7 Probability 123
7.1 Introduction 123
7.2 Sample Space and Events 123
7.3 Finite Probability Spaces 126
7.4 Conditional Probability 127
7.5 Independent Events 129
7.6 Independent Repeated Trials, Binomial Distribution 130
7.7 Random Variables 132
CONTENTS ix
7.8 Chebyshev’s Inequality, Law of Large Numbers 135
Solved Problems 136
Supplementary Problems 149
CHAPTER 8 Graph Theory 154
8.1 Introduction, Data Structures 154
8.2 Graphs and Multigraphs 156
8.3 Subgraphs, Isomorphic and Homeomorphic Graphs 158
8.4 Paths, Connectivity 159
8.5 Traversable and Eulerian Graphs, Bridges of Königsberg 160
8.6 Labeled andWeighted Graphs 162
8.7 Complete, Regular, and Bipartite Graphs 162
8.8 Tree Graphs 164
8.9 Planar Graphs 166
8.10 Graph Colorings 168
8.11 Representing Graphs in Computer Memory 171
8.12 Graph Algorithms 173
8.13 Traveling-Salesman Problem 176
Solved Problems 178
Supplementary Problems 191
CHAPTER 9 Directed Graphs 201
9.1 Introduction 201
9.2 Directed Graphs 201
9.3 Basic Definitions 202
9.4 Rooted Trees 204
9.5 Sequential Representation of Directed Graphs 206
9.6 Warshall’s Algorithm, Shortest Paths 209
9.7 Linked Representation of Directed Graphs 211
9.8 Graph Algorithms: Depth-First and Breadth-First Searches 213
9.9 Directed Cycle-Free Graphs, Topological Sort 216
9.10 Pruning Algorithm for Shortest Path 218
Solved Problems 221
Supplementary Problems 228
CHAPTER 10 Binary Trees 235
10.1 Introduction 235
10.2 Binary Trees 235
10.3 Complete and Extended Binary Trees 237
10.4 Representing Binary Trees in Memory 239
10.5 Traversing Binary Trees 240
10.6 Binary Search Trees 242
10.7 Priority Queues, Heaps 244
10.8 Path Lengths, Huffman’s Algorithm 248
10.9 General (Ordered Rooted) Trees Revisited 251
Solved Problems 252
Supplementary Problems 259
x CONTENTS
CHAPTER 11 Properties of the Integers 264
11.1 Introduction 264
11.2 Order and Inequalities, Absolute Value 265
11.3 Mathematical Induction 266
11.4 Division Algorithm 267
11.5 Divisibility, Primes 269
11.6 Greatest Common Divisor, Euclidean Algorithm 270
11.7 Fundamental Theorem of Arithmetic 273
11.8 Congruence Relation 274
11.9 Congruence Equations 278
Solved Problems 283
Supplementary Problems 299
CHAPTER 12 Languages, Automata, Grammars 303
12.1 Introduction 303
12.2 Alphabet,Words, Free Semigroup 303
12.3 Languages 304
12.4 Regular Expressions, Regular Languages 305
12.5 Finite State Automata 306
12.6 Grammars 310
Solved Problems 314
Supplementary Problems 319
CHAPTER 13 Finite State Machines and Turing Machines 323
13.1 Introduction 323
13.2 Finite State Machines 323
13.3 Gödel Numbers 326
13.4 Turing Machines 326
13.5 Computable Functions 330
Solved Problems 331
Supplementary Problems 334
CHAPTER 14 Ordered Sets and Lattices 337
14.1 Introduction 337
14.2 Ordered Sets 337
14.3 Hasse Diagrams of Partially Ordered Sets 340
14.4 Consistent Enumeration 342
14.5 Supremum and Infimum 342
14.6 Isomorphic (Similar) Ordered Sets 344
14.7 Well-Ordered Sets 344
14.8 Lattices 346
14.9 Bounded Lattices 348
14.10 Distributive Lattices 349
14.11 Complements, Complemented Lattices 350
Solved Problems 351
Supplementary Problems 360
CONTENTS xi
CHAPTER 15 Boolean Algebra 368
15.1 Introduction 368
15.2 Basic Definitions 368
15.3 Duality 369
15.4 Basic Theorems 370
15.5 Boolean Algebras as Lattices 370
15.6 Representation Theorem 371
15.7 Sum-of-Products Form for Sets 371
15.8 Sum-of-Products Form for Boolean Algebras 372
15.9 Minimal Boolean Expressions, Prime Implicants 375
15.10 Logic Gates and Circuits 377
15.11 Truth Tables, Boolean Functions 381
15.12 Karnaugh Maps 383
Solved Problems 389
Supplementary Problems 403
APPENDIX A Vectors and Matrices 409
APPENDIX B Algebraic Systems 432
Download: Click here to download
