离散数学及其应用（英文精编版·原书第8版）

　　本书是经典的离散数学教材，被全球数百所大学广为采用。英文精编版为满足本科教学需求而缩减了篇幅，保留的主要内容包括：逻辑和证明，集合、函数、序列、求和与矩阵，计数，关系，图，树，布尔代数。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的例题、图表、应用实例和练习。第8版做了与时俱进的更新，成为更加实用的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材，也可作为科技领域从业人员的参考书。

　　肯尼思·H. 罗森（Kenneth H. Rosen） 于1972年获密歇根大学安娜堡分校数学学士学位，1976年获麻省理工学院数学博士学位。Rosen曾就职于科罗拉多大学、俄亥俄州立大学、缅因大学和蒙茅斯大学，教授离散数学、算法设计和计算机安全方面的课程；他还曾加盟贝尔实验室，并且是AT&T贝尔实验室的杰出技术人员。他的著作《初等数论及其应用》和《离散数学及其应用》均被翻译成多种语言，在全球数百所大学中广为采用。

The Adapter's Words
Preface
Online Resources
To the Student
About the Author
List of Symbols
1 The Foundations: Logic and Proofs 1
1.1　Propositional Logic 1
1.2　Applications of Propositional Logic 15
1.3　Propositional Equivalences 22
1.4　Predicates and Quantifiers 34
1.5　Nested Quantifiers 51
1.6　Rules of Inference 62
1.7　Introduction to Proofs 72
1.8　Proof Methods and Strategy 84
End-of-ChapterMaterial (Online)
2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 101
2.1　Sets 101
2.2　Set Operations 111
2.3　Functions 124
2.4　Sequences and Summations 140
2.5　Cardinality of Sets 153
2.6　Matrices 161
End-of-ChapterMaterial (Online)
3 Counting 169
3.1　The Basics of Counting 169
3.2　The Pigeonhole Principle 182
3.3　Permutations and Combinations 189
3.4　Binomial Coefficients and Identities 197
3.5　Generalized Permutations and Combinations 204
3.6　Generating Permutations and Combinations 215
End-of-ChapterMaterial (Online)
4 Advanced Counting Techniques 221
4.1　Applications of Recurrence Relations 221
4.2　Solving Linear Recurrence Relations 232
4.3　Divide-and-Conquer Algorithms and Recurrence Relations 244
4.4　Generating Functions 253
4.5　Inclusion朎xclusion 268
4.6　Applications of Inclusion朎xclusion 273
End-of-ChapterMaterial (Online)
5 Relations 281
5.1　Relations and Their Properties 281
5.2　n-ary Relations and Their Applications 292
5.3　Representing Relations 302
5.4　Closures of Relations 308
5.5　Equivalence Relations 317
5.6　Partial Orderings 327
End-of-ChapterMaterial (Online)
6 Graphs 343
6.1　Graphs and Graph Models 343
6.2　Graph Terminology and Special Types of Graphs 354
6.3　Representing Graphs and Graph Isomorphism 371
6.4　Connectivity 380
6.5　Euler and Hamilton Paths 393
6.6　Shortest-Path Problems 405
6.7　Planar Graphs 415
6.8　Graph Coloring 423
End-of-ChapterMaterial (Online)
7 Trees 431
7.1　Introduction to Trees 431
7.2　Applications of Trees 442
7.3　Tree Traversal 456
7.4　Spanning Trees 468
7.5　Minimum Spanning Trees 481
End-of-ChapterMaterial (Online)
8 Boolean Algebra 487
8.1　Boolean Functions 487
8.2　Representing Boolean Functions 494
8.3　Logic Gates 497
8.4　Minimization of Circuits 503
End-of-ChapterMaterial (Online)
Suggested Readings (Online)
Answers to Odd-Numbered Exercises (Online)