Discrete Mathematics and its Applications, Seventh Edition, is intended for one- or two-term introductory discrete mathematics courses taken by students from a wide variety of majors, including computer science, mathematics, and engineering. This renowned best-selling text, which has been used at over 500 institutions around the world, gives a focused introduction to the primary themes in a discrete mathematics course and demonstrates the relevance and practicality of discrete mathematics to a wide a wide variety of real-world applications…from computer science to data networking, to psychology, to chemistry, to engineering, to linguistics, to biology, to business, and to many other important fields.
Author(s): Kenneth Rosen
Edition: 7
Publisher: McGraw-Hill Science/Engineering/Math
Year: 2011
Language: English
Pages: 1072
Tags: Математика;Дискретная математика;
Cover Page......Page 1
Title Page......Page 2
Copyright Page......Page 3
Contents......Page 4
About the Author......Page 7
Preface......Page 8
The Companion Website......Page 17
To the Student......Page 19
1.1 Propositional Logic......Page 22
1.2 Applications of Propositional Logic......Page 37
1.3 Propositional Equivalences......Page 46
1.4 Predicates and Quantifiers......Page 57
1.5 Nested Quantifiers......Page 78
1.6 Rules of Inference......Page 90
1.7 Introduction to Proofs......Page 101
1.8 Proof Methods and Strategy......Page 113
End-of-Chapter Material......Page 130
2.1 Sets......Page 136
2.2 Set Operations......Page 148
2.3 Functions......Page 159
2.4 Sequences and Summations......Page 177
2.5 Cardinality of Sets......Page 191
2.6 Matrices......Page 198
End-of-Chapter Material......Page 206
3.1 Algorithms......Page 212
3.2 The Growth of Functions......Page 225
3.3 Complexity of Algorithms......Page 239
End-of-Chapter Material......Page 253
4.1 Divisibility and Modular Arithmetic......Page 258
4.2 Integer Representations and Algorithms......Page 266
4.3 Primes and Greatest Common Divisors......Page 278
4.4 Solving Congruences......Page 295
4.5 Applications of Congruences......Page 308
4.6 Cryptography......Page 315
End-of-Chapter Material......Page 327
5.1 Mathematical Induction......Page 332
5.2 Strong Induction andWell-Ordering......Page 354
5.3 Recursive Definitions and Structural Induction......Page 365
5.4 Recursive Algorithms......Page 381
5.5 Program Correctness......Page 393
End-of-Chapter Material......Page 398
6.1 The Basics of Counting......Page 406
6.2 The Pigeonhole Principle......Page 420
6.3 Permutations and Combinations......Page 428
6.4 Binomial Coefficients and Identities......Page 436
6.5 Generalized Permutations and Combinations......Page 444
6.6 Generating Permutations and Combinations......Page 455
End-of-Chapter Material......Page 460
7.1 An Introduction to Discrete Probability......Page 466
7.2 Probability Theory......Page 473
7.3 Bayes’ Theorem......Page 489
7.4 Expected Value and Variance......Page 498
End-of-Chapter Material......Page 515
8.1 Applications of Recurrence Relations......Page 522
8.2 Solving Linear Recurrence Relations......Page 535
8.3 Divide-and-Conquer Algorithms and Recurrence Relations......Page 548
8.4 Generating Functions......Page 558
8.5 Inclusion–Exclusion......Page 573
8.6 Applications of Inclusion–Exclusion......Page 579
End-of-Chapter Material......Page 586
9.1 Relations and Their Properties......Page 594
9.2 n-ary Relations and Their Applications......Page 604
9.3 Representing Relations......Page 612
9.4 Closures of Relations......Page 618
9.5 Equivalence Relations......Page 628
9.6 Partial Orderings......Page 639
End-of-Chapter Material......Page 654
10.1 Graphs and Graph Models......Page 662
10.2 Graph Terminology and Special Types of Graphs......Page 672
10.3 Representing Graphs and Graph Isomorphism......Page 689
10.4 Connectivity......Page 699
10.5 Euler and Hamilton Paths......Page 714
10.6 Shortest-Path Problems......Page 728
10.7 Planar Graphs......Page 739
10.8 Graph Coloring......Page 748
End-of-Chapter Material......Page 756
11.1 Introduction to Trees......Page 766
11.2 Applications of Trees......Page 778
11.3 Tree Traversal......Page 793
11.4 Spanning Trees......Page 806
11.5 Minimum Spanning Trees......Page 818
End-of-Chapter Material......Page 824
12.1 Boolean Functions......Page 832
12.2 Representing Boolean Functions......Page 840
12.3 Logic Gates......Page 843
12.4 Minimization of Circuits......Page 849
End-of-Chapter Material......Page 864
13.1 Languages and Grammars......Page 868
13.2 Finite-State Machines with Output......Page 879
13.3 Finite-State Machines with No Output......Page 886
13.4 Language Recognition......Page 899
13.5 Turing Machines......Page 909
End-of-Chapter Material......Page 920
1 Axioms for the Real Numbers and the Positive Integers......Page 926
2 Exponential and Logarithmic Functions......Page 932
3 Pseudocode......Page 936
Suggested Readings......Page 942
Answers to Odd-Numbered Exercises......Page 950
Photo Credits......Page 1047
Index of Biographies......Page 1049
Index......Page 1050
