目录 1
第一章 集合论、逻辑与算法基础 1
1.1 集合 1
1.1.1 文氏图 6
1.1.2 集合运算 7
1.1.3 有序对与笛卡儿叉积 14
1.1.4 集合的计算机表示 15
课堂练习 18
本节小结 21
习题1.1 22
1.2 数理逻辑 25
1.2.1 非 26
1.2.2 合取 27
1.2.3 析取 28
1.2.4 蕴涵 29
1.2.5 双向蕴涵 30
1.2.6 命题公式（公式） 31
课堂练习 37
本节小结 40
习题1.2 41
1.3 论证有效性 43
1.3.1 一些有效论证形式 45
课堂练习 48
本节小结 51
习题1.3 51
1.4 量词与一阶逻辑 53
1.4.1 谓词求非 57
1.4.2 其他推理规则 58
课堂练习 59
本节小结 61
习题1.4 61
1.5 证明方法 63
1.5.1 直接证明 64
1.5.2 间接证明 65
1.5.3 反证法 66
1.5.4 证明双向蕴涵 67
1.5.5 证明等价命题 68
1.5.6 证明中的错误 69
课堂练习 70
本节小结 71
习题1.5 71
1.6 算法 73
1.6.1 伪码约定 74
1.6.2 多项式运算 80
课堂练习 84
本节小结 85
习题1.6 85
编程练习 86
第二章 整数与数学归纳法 87
2.1 整数 89
2.1.1 除法算法 92
2.1.2 最大公约数 97
2.1.3 最小公倍数 102
课堂练习 103
本节小结 106
习题2.1 106
2.2 计算机中的整数表示 108
2.2.1 二进制数运算 113
课堂练习 124
本节小结 127
习题2.2 128
2.3 数学归纳法 129
2.3.1 应用：循环不变量（程序正确性） 133
课堂练习 137
习题2.3 143
本节小结 143
2.4 素数 146
2.4.1 正整数因子分解 153
课堂练习 156
本节小结 158
习题2.4 158
2.5 线性丢番图方程 159
课堂练习 164
本节小结 167
习题2.5 167
编程练习 168
3.1 关系 169
第三章 关系与偏序集 169
3.1.1 关系的域与值域 173
3.1.2 等价关系 177
3.1.3 等价类与划分 181
3.1.4 闭包 184
课堂练习 190
本节小结 195
习题3.1 197
3.2 偏序集 200
3.2.1 词典序 202
3.2.2 偏序集的有向图 203
3.2.3 哈塞图 204
3.2.4 极小元与极大元 206
3.2.5 格 208
课堂练习 212
本节小结 215
习题3.2 216
3.3 应用：关系型数据库 219
3.3.1 结构化查询语言 223
课堂练习 224
本节小结 226
习题3.3 226
编程练习 227
第四章 矩阵与关系闭包 228
4.1 矩阵 228
4.1.1 矩阵转置 238
4.1.2 对称矩阵 238
4.1.3 布尔（0-1）矩阵 239
课堂练习 243
本节小结 248
习题4.1 250
4.2 关系矩阵与闭包 253
4.2.1 求传递闭包的Warshall算法 262
课堂练习 269
本节小结 273
习题4.2 274
编程练习 276
第五章 函数 277
5.1 函数 277
5.1.1 单射、满射和——映射 284
5.1.2 复合 286
课堂练习 290
本节小结 294
习题5.1 295
5.2.1 函数的逆 298
5.2 特殊函数与集合的基数 298
5.2.2 限制、扩展、映像和预映像 301
5.2.3 弱取整函数与强取整函数 303
5.2.4 集合的基数 305
课堂练习 309
本节小结 312
习题5.2 313
5.3 序列与字符串 314
5.3.1 特殊数列 318
5.3.2 求和 319
5.3.3 索引变量的改变 320
5.3.4 积 323
5.3.6 在计算机内存中表示字符串 324
5.3.5 字符串（单词） 324
课堂练习 326
本节小结 329
习题5.3 330
5.4 元运算 332
课堂练习 336
本节小结 339
习题5.4 340
编程练习 341
6.1 同余 342
第六章 同余 342
6.1.1 整除测试 348
6.1.2 同余类的加法与乘法 352
课堂练习 353
本节小结 356
习题6.1 357
6.2 校验位 358
6.2.1 ISBN 359
6.2.2 UPC-A与EAN-13 364
6.2.3 信用卡的校验位 370
课堂练习 371
本节小结 375
习题6.2 376
6.3 线性同余 377
6.3.1 中国余数定理 381
6.3.2 整数的模（余）表示 383
6.3.3 循环赛 386
6.3.4 散列函数 389
课堂练习 394
本节小结 398
习题6.3 399
6.4 特殊同余定理 401
6.4.1 密码学 405
课堂练习 409
本节小结 413
习题6.4 413
编程练习 414
第七章 计数原理 416
7.1 基本计数原理 416
7.1.1 加法原理 417
7.1.2 乘法原理 418
7.1.3 同时使用加法与乘法原理 421
7.1.4 容斥原理 423
课堂练习 426
本节小结 428
习题7.1 429
7.2 鸽巢原理 431
课堂练习 434
本节小结 436
习题7.2 436
7.3 排列 437
课堂练习 439
本节小结 441
习题7.3 441
7.4 组合 442
课堂练习 444
本节小结 447
习题7.4 447
7.5 广义排列与组合 448
课堂练习 452
本节小结 454
习题7.5 455
7.6 二项式系数 455
7.6.1 计算阶乘与C（n，r）的算法 461
课堂练习 466
习题7.6 468
本节小结 468
7.7 生成排列与组合 469
课堂练习 474
本节小结 475
习题7.7 476
7.8 离散概率 476
7.8.1 公理方法 480
7.8.2 条件概率 482
课堂练习 483
本节小结 485
习题7.8 486
编程练习 487
第八章 递归关系 488
8.1 数列与递归关系 488
8.1.1 用迭代（替代）法求解递归关系 496
课堂练习 503
本节小结 508
习题8.1 509
8.2 线性齐次递归关系 511
课堂练习 521
本节小结 524
习题8.2 525
8.3 线性非齐次递归关系 526
课堂练习 538
本节小结 542
习题8.3 543
编程练习 543
第九章 算法与时间复杂度 544
9.1 算法分析 544
课堂练习 556
本节小结 557
习题9.1 558
9.2 各种算法 560
9.2.1 顺序查找 560
9.2.2 折半查找 562
9.2.3 选择排序 564
9.2.4 插入排序 566
9.2.5 基于比较的排序算法的下限 570
9.2.6 合并排序 571
9.2.7 合并排序算法分析 577
9.2.8 列表中的最小元素与最大元素 577
9.2.9 Strassen矩阵乘法 579
9.2.10 矩阵连乘 585
9.2.11 chainedMatrixMultipli-cation函数分析 591
课堂练习 593
习题9.2 595
本节小结 595
编程练习 598
第十章 图论 599
10.1 图的定义与符号 600
10.1.1 有向图 605
10.1.2 简单图 606
10.1.3 子图 608
课堂练习 610
本节小结 613
习题10.1 615
10.2 通路、路径与圈 617
10.2.1 匹配 624
课堂练习 627
本节小结 630
习题10.2 631
10.3 图的矩阵表示 634
10.3.1 相邻矩阵 635
10.3.2 关联矩阵 639
课堂练习 640
本节小结 642
习题10.3 642
10.4.1 欧拉回路 644
10.4 特殊回路 644
10.4.2 哈密尔顿圈 652
课堂练习 656
本节小结 658
习题10.4 659
10.5 同构 661
课堂练习 665
本节小结 668
习题10.5 668
10.6 图算法 670
10.6.2 Diikstra最短路径算法 671
10.6.1 最短路径算法 671
10.6.3 拓扑排序 678
课堂练习 683
本节小结 684
习题10.6 684
10.7 平面图与图着色 685
10.7.1 平面图 685
10.7.2 图着色 692
课堂练习 698
本节小结 701
习题10.7 702
编程练习 704
第十一章 树与网络 705
11.1 树 705
11.1.1 树的同构 709
课堂练习 711
本节小结 712
习题11.1 712
11.2 有根树 713
11.2.1 二叉树 714
11.2.2 二叉树遍历 717
11.2.3 二叉搜索树 719
11.2.4 二叉搜索树分析 722
11.2.5 表达式树 723
11.2.6 二叉树的同构 726
课堂练习 727
本节小结 729
习题1 1.2 730
11.3 生成树 731
11.3.1 最小生成树 735
课堂练习 740
本节小结 742
习题11.3 742
11.4 网络 744
11.4.1 （再谈）匹配 760
课堂练习 762
本节小结 764
习题11.4 766
编程练习 767
第十二章 布尔代数与组合电路 769
12.1 二元布尔代数 769
课堂练习 781
本节小结 782
习题12.1 783
12.2 布尔代数 786
课堂练习 792
本节小结 794
习题12.2 795
12.3 逻辑门与组合电路 796
12.3.1 Kamaugh图与布尔表达式的最小化 810
12.3.2 涉及三个变量的K-图和布尔表达式的最小化 813
12.3.3 涉及四个变量的K-图与布尔表达式的最小化 815
课堂练习 817
本节小结 821
习题12.3 822
编程练习 824
第十三章 有限自动机与语言 825
13.1 有限自动机与规则语言 825
13.1.1 确定有限自动机 827
13.1.2 源引理的应用 834
13.1.3 规则语言的代数性质 835
13.1.4 非确定有限自动机 836
课堂练习 842
本节小结 846
习题13.1 848
13.2 带输入和输出的有限状态机 853
课堂练习 858
本节小结 860
习题13.2 861
13.3 文法与语言 863
课堂练习 871
本节小结 874
习题13.3 876
编程练习 877
附录 878
部分习题答案与提示 881
符号表 909
参考文献 917