离散数学

　　“大学计算机教育国外著名教材系列（影印版）”专题本书通过大量示例深入浅出地介绍了离散数学的主要内容，包括集合、序与函数，基础逻辑，关系，归纳与递归，计数，图与树，递归、树与算法，有向图，离散概率，布尔代数，代数结构，谓词演算与无限集等。各章节配有相当数量的练习题，书后给出了提示和答案，为教师授课和读者迅速掌握有关知识很有帮助。本书内容丰富，结构清晰、系统，讲解通俗易懂，而且注重实用性，既可作为计算机科学和计算数学等专业的本科生和研究生的教科书，又可作为工程技术人员的参考书。

暂缺《离散数学》作者简介

Preface to the Fifth Edition ix
To the Student Especially xiii
 1  Sets, Sequences, and Functions
 1.1   Some Warm-up Questions  1
 1.2   Factors and Multiples  7
 Office Hours  15
 1.3   Some Special Sets  16
 1.4   Set Operations  22
 1.5   Functions  28
 1.6   Sequences  34
 1.7   Properties of Functions  39
 Office Hours  46
 Supplementary Exercises  48
 2  Elementary Logic  50
 2.1   Informal Introduction  50
 2.2   Propositional Calculus  58
 2.3   Getting Started with Proofs  66
 2.4  Methods of Proof 71
 Office Hours  76
 2.5   Logic in Proofs  77
 2.6   Analysis of Arguments  86
 Supplementary Exercises  94
 3  Relations  95
 3.1   Relations  95
 3.2   Digraphs and Graphs  100
 3.3   Matrices  106
 3.4   Equivalence Relations and Partitions  112
 3.5   The Division Algorithm and Integers Mod p  119
 Supplementary Exercises  127
 4  Induction and Recursion  128
 4.1   Loop Invariants  128
 4.2   Mathematical Induction  137
 Office Hours  144
 4.3  Big-Oh Notation  145
 4.4  Recursive Definitions  153
 4.5   Recurrence Relations  160
 4.6   More Induction  167
 4.7   The Euclidean Algorithm  171
 Supplementary Exercises  179
 5  Counting  181
 5.l   Basic Counting Techniques  181
 5.2   Elementary Probability  189
 5.3   Inclusion-Exclusion and Binomial Methods  197
 5.4   Counting and Partitions  204
 Office Hours  212
 5.5   Pigeon-Hole Principle  213
 Supplementary Exercises  220
 6  Introduction to Graphs and Trees
 6.1   Graphs  225
 6.2   Edge Traversal Problems  232
 6.3   Trees  239
 6.4   Rooted Trees  244
 6.5   Vertex Traversal Problems  251
 6.6   Minimum Spanning Trees  257
 Supplementary Exercises  266
 7  Recursion, Trees, and Algorithms
 7.1   General Recursion  269
 7.2   Recursive Algorithms  277
 7.3   Depth-First Search Algorithms  286
 7.4   Polish Notation  298
 7.5   Weighted Trees  304
 Supplementary Exercises  315
 8  Digraphs  318
 8.1   Digraphs Revisited  318
 8.2   Weighted Digraphs and Scheduling Networks  325
 Office Hours  333
 8.3   Digraph Algorithms  333
 Supplementary Exercises  347
 9  Discrete Probability 349
 9.1   Independence in Probability  349
 9.2   Random Variables  359
 9.3   Expectation and Standard Deviation  366
 9.4   Probability Distributions  374
 Supplementary Exercises  387
 10  Boolean Algebra  389
 10.1  Boolean Algebras  389
 10.2  Boolean Expressions  398
 10.3  Logic Networks  405
 10.4  KamaughMaps  412
 10.5  Isomorphisms of Boolean Algebras  417
 Supplementary Exercises  422
 11  More on Relations 424
 11.1 Partially Ordered Sets 424
 11.2  Special Orderings  433
 11.3  Multiplication of Matrices  439
 11.4  Properties of General Relations  446
 11.5  Closures of Relations  452
 Supplementary Exercises  459
 12  Algebraic Structures  462
 12.1  Groups Acting on Sets  462
 12.2  Fixed Points and Subgroups  470
 12.3  Counting Orbits  476
 12.4  Group Homomorphisms  487
 12.5  Semigroups  495
 12.6  Other Algebraic Systems  501
 Supplementary Exercises  512
 13  Predicate Calculus and Infinite Sets
 13.1  Quantifiers and Predicates  515
 13.2  Elementary Predicate Calculus  522
 13.3 Infinite Sets 527
Supplementary Exercises  534
Dictionary 536
Answers and Hints  538
Index 607