离散数学（第八版）

目 录
第1章 集合与逻辑 1
1．1 集合 1
1．2 命题 13
1．3 条件命题与逻辑等价 20
1．4 论证和推理规则 29
1．5 量词 35
1．6 嵌套量词 46
本章注释 56
本章复习 56
本章自测题 58
上机练习 60
第2章 证明 61
2．1 数学系统、直接证明和反例 61
2．2 更多的证明方法 70
2．3 归结证明 83
2．4 数学归纳法 86
2．5 强数学归纳法和良序性 103
本章注释 110
本章复习 110
本章自测题 111
上机练习 111
第3章 函数、序列与关系 112
3．1 函数 112
3．2 序列和串 131
3．3 关系 143
3．4 等价关系 154
3．5 关系矩阵 163
3．6 关系数据库 168
本章注释 173
本章复习 173
本章自测题 175
上机练习 176
第4章 算法 178
4．1 简介 178
4．2 算法示例 182
4．3 算法的分析 188
4．4 递归算法 208
本章注释 215
本章复习 216
本章自测题 217
上机练习 218
第5章 数论 219
5．1 因子 219
5．2 整数的表示和整数算法 228
5．3 欧几里得算法 240
5．4 RSA公钥密码系统 252
本章注释 254
本章复习 254
本章自测题 255
上机练习 255
第6章 计数方法与鸽巢原理 256
6．1 基本原理 256
6．2 排列与组合 269
6．3 广义的排列与组合 284
6．4 排列组合生成算法 289
6．5 离散概率简介 296
6．6 离散概率论 300
6．7 二项式系数和组合恒等式 311
6．8 鸽巢原理 317
本章注释 322
本章复习 323
本章自测题 324
上机练习 325
第7章 递推关系 326
7．1 简介 326
7．2 求解递推关系 338
7．3 在算法分析中的应用 354
7．4 最小距点对问题 368
本章注释 374
本章复习 374
本章自测题 375
上机练习 376
第8章 图论 378
8．1 简介 378
8．2 路径和回路 388
8．3 Hamilton回路和旅行商问题 400
8．4 最短路径算法 410
8．5 图的表示 414
8．6 图的同构 419
8．7 平面图 427
8．8 顿时错乱问题 434
本章注释 438
本章复习 439
本章自测题 440
上机练习 442
第9章 树 444
9．1 简介 444
9．2 树的术语和性质 451
9．3 生成树 458
9．4 最小生成树 465
9．5 二叉树 471
9．6 树的遍历 478
9．7 决策树和最短时间排序 484
9．8 树的同构 490
9．9 博弈树 498
本章注释 507
本章复习 508
本章自测题 509
上机练习 512
第10章 网络模型 514
10．1 简介 514
10．2 最大流算法 519
10．3 最大流最小割定理 527
10．4 匹配 530
本章注释 537
本章复习 538
本章自测题 539
上机练习 540
第11章 Boole代数与组合电路 541
11．1 组合电路 541
11．2 组合电路的性质 547
11．3 Boole代数 553
11．4 Boole函数与电路合成 560
11．5 应用 565
本章注释 573
本章复习 574
本章自测题 575
上机练习 577
第12章 自动机、文法和语言 578
12．1 时序电路和有限状态机 578
12．2 有限状态自动机 584
12．3 语言和文法 589
12．4 不确定有限状态自动机 599
12．5 语言和自动机之间的关系 605
本章注释 610
本章复习 611
本章自测题 611
上机练习 613
附录A 矩阵 614
附录B 代数学复习 618
附录C 伪代码 628
部分练习答案 633
参考文献 746