目　　录
Connecting Discrete Mathematics and Computer Science, Second Edition
赞誉
译者序
中文版序
致谢
第1章?本书要旨　　1
1.1?它因何吸引你　　1
1.2?如何使用本书　　2
1.3?本书内容　　3
第2章?基础数据类型　　5
2.1?它因何吸引你　　5
2.2?布尔值、数和算术　　6
2.2.1?布尔值：真与假　　7
2.2.2?数：整数、实数和有理数　　7
2.2.3?绝对值、下取整和上取整　　9
2.2.4?指数　　10
2.2.5?对数　　12
2.2.6?模运算和除法　　13
2.2.7?求和与求积　　15
2.3?集合：无序之整体　　26
2.3.1?从零开始构建集合　　28
2.3.2?由其他集合构建集合　　30
2.3.3?集合的比较　　32
2.3.4?集合的集合　　34
2.4?序列、向量和矩阵：有序之整体　　42
2.4.1?向量　　44
2.4.2?矩阵　　48
2.5?函数　　59
2.5.1?基本定义　　59
2.5.2?映上函数和一对一函数　　64
2.5.3?多项式　　68
2.5.4?算法　　70
2.6?本章回顾　　75
第3章?逻辑　　77
3.1?它因何吸引你　　77
3.2?命题逻辑简介　　78
3.2.1?命题与真值　　78
3.2.2?原子命题与复合命题　　79
3.2.3?逻辑联结词　　80
3.2.4?逻辑联结词的组合　　84
3.2.5?真值表　　86
3.3?命题逻辑：一些扩展　　92
3.3.1?重言式与可满足性　　93
3.3.2?逻辑等价　　95
3.3.3?命题表示：电路和范式　　98
3.4?谓词逻辑简介　　107
3.4.1?谓词　　107
3.4.2?量词　　110
3.4.3?谓词逻辑中的定理与证明　　113
3.4.4?定理和证明示例　　115
3.5?谓词逻辑：嵌套量词　　125
3.5.1?量化的顺序　　126
3.5.2?嵌套量词的否定　　129
3.5.3?思考嵌套量词的两种新
方式　　130
3.6?本章回顾　　138
第4章?证明　　140
4.1?它因何吸引你　　140
4.2?关于证明的扩展应用：纠错码　　141
4.2.1?形式化简介　　142
4.2.2?距离与码率　　145
4.2.3?重复码　　149
4.2.4?Hamming码　　150
4.2.5?码率的上界　　154
4.3?证明与证明技术　　163
4.3.1?证明技术　　164
4.3.2?关于证明策略的几点思考　　172
4.3.3?关于书写漂亮证明的几点
思考　　173
4.4?部分证明示例　　179
4.4.1?关于命题逻辑的一个证明：
合取范式、析取范式　　179
4.4.2?勾股定理　　183
4.4.3?素数　　185
4.4.4?不可计算性　　186
4.5?证明中的常见错误　　195
4.6?本章回顾　　206
第5章?数学归纳法　　208
5.1?它因何吸引你　　208
5.2?数学归纳法　　209
5.2.1?数学归纳法概述　　209
5.2.2?一些数值示例：几何级数、
算术级数和调和级数　　216
5.2.3?更多示例　　220
5.3?强数学归纳法　　229
5.3.1?定义及第一个示例　　230
5.3.2?强数学归纳法的更多示例　　231
5.4?递归定义的结构与结构归纳法　　243
5.4.1?递归定义的结构　　243
5.4.2?结构归纳法　　245
5.4.3?结构归纳法的更多示例：
命题逻辑　　248
5.4.4?递归定义的整数　　251
5.5?本章回顾　　255
第6章?算法分析　　257
6.1?它因何吸引你　　257
6.2?渐近表示　　258
6.2.1?大O符号　　259
6.2.2?其他渐近关系：?、Θ、ω
与o　　263
6.3?算法的渐近分析　　272
6.3.1?最差情况下的分析　　273
6.3.2?部分其他类型分析　　278
6.4?递推关系：递归算法的分析　　285
6.4.1?递推关系　　287
6.4.2?求解递推式：归纳法　　289
6.4.3?斐波那契数　　293
6.5?扩展：形式的
??递推关系　　302
6.5.1?求解形式的
???递推式：一些直观认识　　302
6.5.2?形式化陈述及若干示例　　306
6.5.3?定理6.21的证明　　307
6.6?本章回顾　　312
第7章?数论　　314
7.1?它因何吸引你　　314
7.2?模算术　　315
7.2.1?余数：回顾　　315
7.2.2?计算n mod k和　　 317
7.2.3?同余、因子与公因子　　318
7.2.4?计算最大公因子　　321
7.3?素性与互素　　328
7.3.1?素性（回顾）与互素（引入）　　329
7.3.2?一个结构性事实及扩展欧几
里得算法　　332
7.3.3?素分解的唯一性　　335
7.3.4?中国剩余定理　　336
7.4?乘法逆元　　345
7.4.1?基本定义　　345
7.4.2?乘法逆元何时存在（以及如何
找到它们）　　348
7.4.3?费马小定理　　349
7.5?密码编码学　　355
7.5.1?RSA密码系统　　358
7.5.2?RSA的正确性　　360
7.6?本章回顾　　366
第8章?关系　　368
8.1?它因何吸引你　　368
8.2?形式化引入　　369
8.2.1?关系的形式化定义　　370
8.2.2?二元关系的逆和复合　　372
8.2.3?作为关系的函数　　376
8.2.4?n元关系　　377
8.3?关系的性质：自反性、对称性和
传递性　　385
8.3.1?自反性　　386
8.3.2?对称性　　387
8.3.3?传递性　　389
8.3.4?渐近关系的性质　　390
8.3.5?关系的闭包　　392
8.4?特殊的关系：等价关系、偏序与
全序　　400
8.4.1?等价关系　　401
8.4.2?偏序与全序　　404
8.4.3?拓扑排序　　409
8.5?本章回顾　　417
第9章?计数　　419
9.1?它因何吸引你　　419
9.2?并集和序列的计数　　420
9.2.1?基础：加法法则与乘法法则　　421
9.2.2?容斥原理：非不相交集合的
并集　　425
9.2.3?广义乘法法则　　429
9.2.4?乘法法则与加法法则相
结合　　431
9.3?使用函数进行计数　　443
9.3.1?映射法则　　444
9.3.2?除法法则　　447
9.3.3?鸽巢原理　　451
9.4?组合与排列　　462
9.4.1?从n个选项中选择k个的四
种不同方法　　464
9.4.2?的某些性质与组合证明　　469
9.4.3?二项式定理　　472
9.4.4?Pascal三角　　474
9.5?本章回顾　　484
第10章?概率　　487
10.1?它因何吸引你　　487
10.1.1?哈希：一个实例　　488
10.2?概率、结果和事件　　489
10.2.1?结果与概率　　490
10.2.2?事件　　492
10.2.3?概率的树形图　　495
10.2.4?常见的概率分布　　498
10.3?独立性与条件概率　　509
10.3.1?事件的独立性与相关性　　510
10.3.2?条件概率　　515
10.3.3?贝叶斯法则与条件概率的
计算　　521
10.4?随机变量与期望　　533
10.4.1?随机变量　　533
10.4.2?期望　　535
10.4.3?期望的线性性　　539
10.4.4?条件期望　　545
10.4.5?与期望的偏差　　546
10.5?本章回顾　　558
第11章?图与树　　560
11.1?它因何吸引你　　560
11.2?形式化引入　　561
11.2.1?邻接关系与度数　　563
11.2.2?图的表示：数据结构　　567
11.2.3?图之间的关系：同构与
子图　　570
11.2.4?特殊类型的图：完全图、二
部图、正则图和平面图　　573
11.3?道路、连通性与距离　　585
11.3.1?无向图中的连通性　　587
11.3.2?有向图中的连通性　　589
11.3.3?最短道路和距离　　591
11.3.4?寻路：广度优先搜索　　592
11.3.5?寻路：深度优先搜索　　596
11.4?树　　603
11.4.1?圈　　604
11.4.2?树的概述　　606
11.4.3?树的遍历　　610
11.4.4?支撑树　　612
11.5?赋权图　　621
11.5.1?赋权图中的最短道路：
Dijkstra算法　　622
11.5.2?赋权图中的支撑树：最小支
撑树　　626
11.6?本章回顾　　633
第12章?展望未来　　636
参考文献　　639