第1章 基础：逻辑和证明 1
1.1 命题逻辑 1
1.1.1 引言 1
1.1.2 命题 1
1.1.3 条件语句 4
1.1.4 复合命题的真值表 8
1.1.5 逻辑运算符的优先级 8
1.1.6 逻辑运算和位运算 8
练习 10
1.2 命题逻辑的应用 15
1.2.1 引言 15
1.2.2 语句翻译 15
1.2.3 系统规范说明 16
1.2.4 布尔搜索 16
1.2.5 逻辑谜题 17
1.2.6 逻辑电路 18
练习 19
1.3 命题等价式 22
1.3.1 引言 22
1.3.2 逻辑等价式 23
1.3.3 德·摩根律的运用 25
1.3.4 构造新的逻辑等价式 25
1.3.5 命题的可满足性 26
1.3.6 可满足性的应用 27
1.3.7 可满足性问题求解 29
练习 30
1.4 谓词和量词 32
1.4.1 引言 32
1.4.2 谓词 33
1.4.3 量词 35
1.4.4 约束论域的量词 37
1.4.5 量词的优先级 38
1.4.6 变量绑定 38
1.4.7 涉及量词的逻辑等价式 38
1.4.8 量化表达式的否定 39
1.4.9 语句到逻辑表达式的翻译 40
1.4.10 系统规范说明中量词的使用 42
1.4.11 选自路易斯·卡罗尔的例子 42
1.4.12 逻辑程序设计 43
练习 44
1.5 嵌套量词 49
1.5.1 引言 49
1.5.2 理解涉及嵌套量词的语句 49
1.5.3 量词的顺序 50
1.5.4 数学语句到嵌套量词语句的翻译 51
1.5.5 嵌套量词到自然语言的翻译 52
1.5.6 汉语语句到逻辑表达式的翻译 52
1.5.7 嵌套量词的否定 53
练习 54
1.6 推理规则 59
1.6.1 引言 59
1.6.2 命题逻辑的有效论证 60
1.6.3 命题逻辑的推理规则 61
1.6.4 使用推理规则建立论证 62
1.6.5 消解律 63
1.6.6 谬误 64
1.6.7 量化命题的推理规则 64
1.6.8 命题和量化命题推理规则的组合使用 66
练习 66
1.7 证明导论 69
1.7.1 引言 69
1.7.2 一些专用术语 70
1.7.3 理解定理是如何陈述的 70
1.7.4 证明定理的方法 70
1.7.5 直接证明法 71
1.7.6 反证法 71
1.7.7 归谬证明法 73
1.7.8 证明中的错误 75
1.7.9 良好的开端 76
练习 77
1.8 证明的方法和策略 78
1.8.1 引言 78
1.8.2 穷举证明法和分情形证明法 78
1.8.3 存在性证明 81
1.8.4 唯一性证明 84
1.8.5 证明策略 84
1.8.6 寻找反例 86
1.8.7 证明策略实践 86
1.8.8 拼接 87
1.8.9 开放问题的作用 89
1.8.10 其他证明方法 90
练习 90
关键术语和结论 92
复习题 94
补充练习 95
计算机课题 97
计算和探索 97
写作课题 98
第2章 基本结构：集合、函数、序列、求和与矩阵 99
2.1 集合 99
2.1.1 引言 99
2.1.2 文氏图 101
2.1.3 子集 102
2.1.4 集合的大小 103
2.1.5 幂集 103
2.1.6 笛卡儿积 104
2.1.7 使用带量词的集合符号 105
2.1.8 真值集和量词 106
练习 106
2.2 集合运算 108
2.2.1 引言 108
2.2.2 集合恒等式 110
2.2.3 扩展的并集和交集 112
2.2.4 集合的计算机表示 114
练习 115
2.3 函数 118
2.3.1 引言 118
2.3.2 一对一函数和映上函数 120
2.3.3 反函数和函数组合 122
2.3.4 函数的图 124
2.3.5 一些重要的函数 125
2.3.6 部分函数 127
练习 128
2.4 序列与求和 132
2.4.1 引言 132
2.4.2 序列 133
2.4.3 递推关系 134
2.4.4 特殊的整数序列 136
2.4.5 求和 137
练习 141
2.5 集合的基数 144
2.5.1 引言 144
2.5.2 可数集 145
2.5.3 不可数集合 147
练习 149
2.6 矩阵 151
2.6.1 引言 151
2.6.2 矩阵算术 152
2.6.3 矩阵的转置和幂 153
2.6.4 0-1矩阵 153
练习 155
关键术语和结论 158
复习题 160
补充练习 160
计算机课题 162
计算和探索 163
写作课题 163
第3章 算法 164
3.1 算法 164
3.1.1 引言 164
3.1.2 搜索算法 166
3.1.3 排序 167
3.1.4 贪婪算法 170
3.1.5 停机问题 172
练习 173
3.2 函数的增长 176
3.2.1 引言 176
3.2.2 大O记号 176
3.2.3 一些重要函数的大O估算 179
3.2.4 函数组合的增长 182
3.2.5 大Ω与大Θ记号 183
练习 184
3.3 算法的复杂度 187
3.3.1 引言 187
3.3.2 时间复杂度 188
3.3.3 矩阵乘法的复杂度 190
3.3.4 算法范型 191
3.3.5 理解算法的复杂度 192
练习 195
关键术语和结论 198
复习题 199
补充练习 200
计算机课题 203
计算和探索 203
写作课题 203
第4章 数论和密码学 204
4.1 整除性和模算术 204
4.1.1 引言 204
4.1.2 除法 204
4.1.3 除法算法 205
4.1.4 模算术 206
4.1.5 模m算术 208
练习 208
4.2 整数表示和算法 210
4.2.1 引言 210
4.2.2 整数表示 210
4.2.3 整数运算算法 213
4.2.4 模指数运算 216
练习 217
4.3 素数和最大公约数 219
4.3.1 引言 219
4.3.2 素数 220
4.3.3 试除法 220
4.3.4 埃拉托斯特尼筛法 221
4.3.5 关于素数的猜想和开放问题 224
4.3.6 最大公约数和最小公倍数 225
4.3.7 欧几里得算法 227
4.3.8 gcd的线性组合表示 228
练习 230
4.4 求解同余方程 233
4.4.1 引言 233
4.4.2 线性同余方程 233
4.4.3 中国剩余定理 235
4.4.4 大整数的计算机算术 236
4.4.5 费马小定理 237
4.4.6 伪素数 238
4.4.7 原根和离散对数 239
练习 240
4.5 同余应用 243
4.5.1 散列函数 243
4.5.2 伪随机数 244
4.5.3 校验码 244
练习 246
4.6 密码学 248
4.6.1 引言 248
4.6.2 古典密码学 248
4.6.3 公钥密码学 251
4.6.4 RSA密码系统 251
4.6.5 RSA加密 252
4.6.6 RSA解密 253
4.6.7 用RSA作为公钥系统 254
4.6.8 密码协议 254
练习 255
关键术语和结论 257
复习题 259
补充练习 260
计算机课题 262
计算和探索 262
写作课题 263
第5章 归纳与递归 264
5.1 数学归纳法 264
5.1.1 引言 264
5.1.2 数学归纳法 265
5.1.3 为什么数学归纳法是有效的 266
5.1.4 数学归纳法的优点与缺点 266
5.1.5 利用数学归纳法证明的例子 266
5.1.6 使用数学归纳法时犯的错误 275
5.1.7 运用数学归纳法证明的原则 276
练习 276
5.2 强归纳法与良序性 281
5.2.1 引言 281
5.2.2 强归纳法 282
5.2.3 利用强归纳法证明的例子 283
5.2.4 计算几何学中使用强归纳法 285
5.2.5 利用良序性证明 287
练习 288
5.3 递归定义与结构归纳法 291
5.3.1 引言 291
5.3.2 递归地定义函数 291
5.3.3 递归地定义集合与结构 294
5.3.4 结构归纳法 298
5.3.5 广义归纳法 300
练习 300
5.4 递归算法 305
5.4.1 引言 305
5.4.2 证明递归算法的正确性 307
5.4.3 递归与迭代 308
5.4.4 归并排序 309
练习 312
5.5 程序正确性 314
5.5.1 引言 314
5.5.2 程序验证 314
5.5.3 推理规则 315
5.5.4 条件语句 315
5.5.5 循环不变量 316
练习 318
关键术语和结论 319
复习题 320
补充练习 321
计算机课题 325
计算和探索 325
写作课题 326
第6章 计数 327
6.1 计数的基础 327
6.1.1 引言 327
6.1.2 基本的计数原则 327
6.1.3 比较复杂的计数问题 331
6.1.4 减法法则（两个集合的容斥原理） 332
6.1.5 除法法则 333
6.1.6 树图 333
练习 334
6.2 鸽巢原理 338
6.2.1 引言 338
6.2.2 广义鸽巢原理 339
6.2.3 鸽巢原理的几个简单应用 341
练习 342
6.3 排列与组合 344
6.3.1 引言 344
6.3.2 排列 345
6.3.3 组合 346
练习 348
6.4 二项式系数和恒等式 351
6.4.1 二项式定理 351
6.4.2 帕斯卡恒等式和三角形 353
6.4.3 其他的二项式系数恒等式 354
练习 355
6.5 排列与组合的推广 358
6.5.1 引言 358
6.5.2 有重复的排列 358
6.5.3 有重复的组合 358
6.5.4 具有不可区别物体的集合的排列 361
6.5.5 把物体放入盒子 362
练习 364
6.6 生成排列和组合 367
6.6.1 引言 367
6.6.2 生成排列 368
6.6.3 生成组合 369
练习 370
关键术语和结论 371
复习题 372
补充练习 373
计算机课题 376
计算和探索 376
写作课题 377
第7章 离散概率 378
7.1 离散概率引论 378
7.1.1 引言 378
7.1.2 有限概率 378
7.1.3 事件组合的概率 381
7.1.4 概率的推理 381
练习 382
7.2 概率论 384
7.2.1 引言 384
7.2.2 概率指派 384
7.2.3 事件的组合 385
7.2.4 条件概率 386
7.2.5 独立性 387
7.2.6 伯努利试验与二项分布 388
7.2.7 随机变量 389
7.2.8 生日问题 390
7.2.9 蒙特卡罗算法 391
7.2.10 概率方法 392
练习 393
7.3 贝叶斯定理 396
7.3.1 引言 396
7.3.2 贝叶斯定理 396
7.3.3 贝叶斯垃圾邮件过滤器 399
练习 401
7.4 期望值和方差 403
7.4.1 引言 403
7.4.2 期望值 404
7.4.3 期望的线性性质 405
7.4.4 平均情形下的计算复杂度 407
7.4.5 几何分布 408
7.4.6 独立随机变量 409
7.4.7 方差 410
7.4.8 切比雪夫不等式 413
练习 414
关键术语和结论 416
复习题 417
补充练习 418
计算机课题 422
计算和探索 422
写作课题 422
第8章 高级计数技术 424
8.1 递推关系的应用 424
8.1.1 引言 424
8.1.2 用递推关系构造模型 425
8.1.3 算法与递推关系 429
练习 431
8.2 求解线性递推关系 435
8.2.1 引言 435
8.2.2 求解常系数线性齐次递推关系 436
8.2.3 常系数线性非齐次的递推关系 439
练习 441
8.3 分治算法和递推关系 444
8.3.1 引言 444
8.3.2 分治递推关系 445
练习 450
8.4 生成函数 452
8.4.1 引言 452
8.4.2 关于幂级数的有用事实 452
8.4.3 计数问题与生成函数 455
8.4.4 使用生成函数求解递推关系 458
8.4.5 使用生成函数证明恒等式 459
练习 459
8.5 容斥 464
8.5.1 引言 464
8.5.2 容斥原理 464
练习 467
8.6 容斥原理的应用 468
8.6.1 引言 468
8.6.2 容斥原理的另一种形式 469
8.6.3 埃拉托色尼筛 469
8.6.4 映上函数的个数 470
8.6.5 错位排列 471
练习 472
关键术语和结论 473
复习题 474
补充练习 475
计算机课题 478
计算和探索 478
写作课题 479
第9章 关系 480
9.1 关系及其性质 480
9.1.1 引言 480
9.1.2 函数作为关系 481
9.1.3 集合的关系 481
9.1.4 关系的性质 482
9.1.5 关系的组合 484
练习 485
9.2 n元关系及其应用 489
9.2.1 引言 489
9.2.2 n元关系 489
9.2.3 数据库和关系 490
9.2.4 n元关系的运算 491
9.2.5 SQL 493
练习 493
9.3 关系的表示 495
9.3.1 引言 495
9.3.2 用矩阵表示关系 495
9.3.3 用图表示关系 497
练习 498
9.4 关系的闭包 500
9.4.1 引言 500
9.4.2 闭包 501
9.4.3 有向图中的路径 501
9.4.4 传递闭包 502
9.4.5 沃舍尔算法 505
练习 507
9.5 等价关系 509
9.5.1 引言 509
9.5.2 等价关系 509
9.5.3 等价类 510
9.5.4 等价类与划分 512
练习 514
9.6 偏序 518
9.6.1 引言 518
9.6.2 字典顺序 520
9.6.3 哈塞图 521
9.6.4 极大元与极小元 522
9.6.5 格 524
9.6.6 拓扑排序 525
练习 527
关键术语和结论 532
复习题 533
补充练习 534
计算机课题 538
计算和探索 538
写作课题 538
第10章 图 540
10.1 图和图模型 540
10.1.1 图模型 543
练习 546
10.2 图的术语和几种特殊的图 549
10.2.1 引言 549
10.2.2 基本术语 549
10.2.3 一些特殊的简单图 551
10.2.4 二分图 552
10.2.5 二分图和匹配 553
10.2.6 特殊类型图的一些应用 556
10.2.7 从旧图构造新图 557
练习 559
10.3 图的表示和图的同构 563
10.3.1 引言 563
10.3.2 图的表示 563
10.3.3 邻接矩阵 563
10.3.4 关联矩阵 565
10.3.5 图的同构 566
10.3.6 判定两个简单图是否同构 566
练习 568
10.4 连通性 573
10.4.1 引言 573
10.4.2 通路 573
10.4.3 无向图的连通性 575
10.4.4 图是如何连通的 576
10.4.5 有向图的连通性 578
10.4.6 通路与同构 579
10.4.7 计算顶点之间的通路数 580
练习 580
10.5 欧拉通路与哈密顿通路 585
10.5.1 引言 585
10.5.2 欧拉通路与欧拉回路 585
10.5.3 哈密顿通路与哈密顿回路 589
10.5.4 哈密顿回路的应用 592
练习 593
10.6 最短通路问题 597
10.6.1 引言 597
10.6.2 最短通路算法 599
10.6.3 旅行商问题 603
练习 604
10.7 平面图 607
10.7.1 引言 607
10.7.2 欧拉公式 609
10.7.3 库拉图斯基定理 611
练习 612
10.8 图着色 614
10.8.1 引言 614
10.8.2 图着色的应用 618
练习 619
关键术语和结论 622
复习题 625
补充练习 626
计算机课题 630
计算和探索 631
写作课题 631
第11章 树 633
11.1 树的概述 633
11.1.1 有根树 634
11.1.2 树作为模型 637
11.1.3 树的性质 638
练习 641
11.2 树的应用 643
11.2.1 引言 643
11.2.2 二叉搜索树 643
11.2.3 决策树 646
11.2.4 前缀码 647
11.2.5 博弈树 649
练习 653
11.3 树的遍历 656
11.3.1 引言 656
11.3.2 通用地址系统 656
11.3.3 遍历算法 657
11.3.4 中缀、前缀和后缀记法 662
练习 665
11.4 生成树 667
11.4.1 引言 667
11.4.2 深度优先搜索 669
11.4.3 宽度优先搜索 671
11.4.4 回溯的应用 672
11.4.5 有向图中的深度优先搜索 674
练习 675
11.5 最小生成树 678
11.5.1 引言 678
11.5.2 最小生成树算法 678
练习 681
关键术语和结论 683
复习题 685
补充练习 686
计算机课题 688
计算和探索 689
写作课题 689
第12章 布尔代数 690
12.1 布尔函数 690
12.1.1 引言 690
12.1.2 布尔表达式和布尔函数 691
12.1.3 布尔代数恒等式 692
12.1.4 对偶性 694
12.1.5 布尔代数的抽象定义 694
练习 695
12.2 布尔函数的表示 696
12.2.1 积之和展开式 696
12.2.2 函数完备性 698
练习 698
12.3 逻辑门电路 699
12.3.1 引言 699
12.3.2 门的组合 699
12.3.3 电路的例子 700
12.3.4 加法器 702
练习 703
12.4 电路的极小化 704
12.4.1 引言 704
12.4.2 卡诺图 705
12.4.3 无需在意的条件 710
12.4.4 奎因-莫可拉斯基方法 712
练习 715
关键术语和结论 716
复习题 718
补充练习 718
计算机课题 720
计算和探索 720
写作课题 720
第13章 计算模型 722
13.1 语言和文法 722
13.1.1 引言 722
13.1.2 短语结构文法 723
13.1.3 短语结构文法的类型 725
13.1.4 派生树 726
13.1.5 巴克斯-诺尔范式 727
练习 728
13.2 带输出的有限状态机 732
13.2.1 引言 732
13.2.2 带输出的有限状态机 733
练习 736
13.3 不带输出的有限状态机 738
13.3.1 引言 738
13.3.2 串的集合 738
13.3.3 有限状态自动机 738
13.3.4 有限状态机的语言识别 739
13.3.5 非确定性的有限状态自动机 743
练习 746
13.4 语言的识别 750
13.4.1 引言 750
13.4.2 克莱因定理 751
13.4.3 正则集合和正则文法 754
13.4.4 一个不能由有限状态自动机识别的集合 756
13.4.5 一些更强大的机器 756
练习 757
13.5 图灵机 759
13.5.1 引言 759
13.5.2 图灵机的定义 760
13.5.3 用图灵机识别集合 762
13.5.4 用图灵机计算函数 763
13.5.5 不同类型的图灵机 763
13.5.6 丘奇-图灵论题 764
13.5.7 计算复杂度、可计算性和可判定性 764
练习 767
关键术语和结论 769
复习题 770
补充练习 771
计算机课题 773
计算和探索 773
写作课题 773
附录A 实数和正整数的公理 775
附录B 指数与对数函数 779
附录C 伪代码 781
推荐读物 785
参考文献 789