第1章 集合 1
1.1 概述 1
1.2 集合、元素与子集 1
1.2.1 集合的表示 1
1.2.2 子集 2
1.2.3 全集与空集 3
1.2.4 不相交集 3
1.3 维恩图 3
1.3.1 维恩图与证明 4
1.4 集合运算 4
1.4.1 并集与交集 5
1.4.2 补、差与对称差 6
1.4.3 基本积 7
1.5 集合的代数运算与对偶性 8
1.5.1 代数运算规律 8
1.5.2 对偶性 8
1.6 有限集与计数原理 9
1.6.1 计算有限集中的元素数量 9
1.6.2 容斥原理 10
1.7 集族、幂集与划分 11
1.7.1 幂集 11
1.7.2 划分 12
1.7.3 集合运算的推广 12
1.8 数学归纳法 13
1.8.1 数学归纳法Ⅰ 13
1.8.2 数学归纳法Ⅱ 13
本章习题 14
补充题 22
补充题答案 26
第2章 关系 29
2.1 概述 29
2.2 积集 29
2.3 关系 30
2.3.1 定义 30
2.3.2 逆关系 31
2.4 关系的图形表示 31
2.4.1 实数R上的关系 31
2.4.2 集合上关系的有向图 32
2.4.3 有限集上关系的图示 32
2.5 关系的合成 33
2.5.1 关系合成 33
2.5.2 关系的合成与关系矩阵 34
2.6 关系的类型 34
2.6.1 自反关系 34
2.6.2 对称关系与反对称关系 35
2.6.3 传递关系 36
2.7 闭包性质 36
2.7.1 P-闭包 36
2.7.2 自反闭包与对称闭包 37
2.7.3 传递闭包 37
2.8 等价关系 38
2.8.1 等价关系的定义 38
2.8.2 等价关系与划分 39
2.9 偏序关系 40
2.10 n-元关系 40
本章习题 41
补充题 48
补充题答案 50
第3章 函数与算法 52
3.1 概述 52
3.2 函数 52
3.2.1 作为关系的函数 53
3.2.2 复合函数 54
3.3 单射函数、满射函数与可逆函数 55
3.3.1 单射函数与满射函数的几何特征 56
3.3.2 排列 57
3.4 数学函数、指数函数与对数函数 57
3.4.1 下限函数与上限函数 57
3.4.2 整数值函数与绝对值函数 57
3.4.3 余项函数与模运算 58
3.4.4 指数函数 58
3.4.5 对数函数 59
3.4.6 指数函数与对数函数之间的关系 60
3.5 序列与集合的索引类 60
3.5.1 序列 61
3.5.2 求和符号与求和 61
3.5.3 集合的索引类 62
3.6 递归定义函数 63
3.6.1 阶乘函数 63
3.6.2 层号 64
3.6.3 斐波纳契序列 64
3.6.4 阿克曼函数 65
3.7 基数／集合的容量 65
3.7.1 基数 65
3.7.2 不等式与基数 66
3.8 算法与函数 67
3.9 算法的复杂度 68
3.9.1 线性查找 69
3.9.2 增长率与大O记号 70
3.9.3 著名算法的复杂度 71
本章习题 71
补充题 82
补充题答案 84
第4章 逻辑与命题演算 86
4.1 引言 86
4.2 命题与复命题 86
4.2.1 命题 86
4.2.2 复合命题 86
4.3 基本逻辑运算 87
4.3.1 合取 87
4.3.2 析取 88
4.3.3 否定 88
4.4 命题与真值表 89
4.4.1 命题与真值表 89
4.4.2 构造真值表的另一方法 90
4.5 永真式与永假式 90
4.6 逻辑等价 91
4.7 命题代数 92
4.8 条件语句与双条件语句 92
4.9 论证 93
4.10 命题函数与量词 95
4.10.1 命题函数 95
4.10.2 全称量词 95
4.10.3 存在量词 96
4.11 量化命题的否定 96
4.11.1 反例 98
4.11.2 多变量命题函数 98
4.11.3 多变量量化命题的否定 99
本章习题 99
补充题 105
补充题答案 106
第5章 计数技术 108
5.1 概述 108
5.2 基本计数原理 108
5.3 数学函数 109
5.3.1 阶乘函数 109
5.3.2 二项式系数 109
5.3.3 二项式系数与杨辉三角形 110
5.4 排列 111
5.4.1 一般排列 111
5.4.2 可重复排列 112
5.4.3 有序抽样 113
5.5 组合 113
5.6 鸽巢原理 114
5.6.1 鸽巢原理 114
5.6.2 一般鸽巢原理 115
5.7 容斥原理 115
5.8 树形图 116
本章习题 117
补充题 126
补充题答案 131
第6章 高级计数技术与递推 134
6.1 概述 134
6.2 有重组合 134
6.3 有序划分与无序划分 135
6.3.1 有序划分 135
6.3.2 无序划分 135
6.4 再现容斥原理 136
6.4.1 满射函数的数量 136
6.4.2 错位排列 137
6.5 再现鸽巢原理 138
6.6 递推关系 139
6.7 具有常系数的线性递推关系 141
6.8 二阶齐次线性递推关系的解 142
6.8.1 通解 142
6.8.2 特征多项式具有相等根时的解 144
6.9 一般齐次线性递推关系的解 145
本章习题 146
补充题 151
补充题答案 153
第7章 概率论 155
7.1 概述 155
7.2 样本与事件 155
7.3 有限概率空间 158
7.3.1 有限概率空间的定义 158
7.3.2 等概率空间 158
7.3.3 有限概率空间相关定理 159
7.4 条件概率 160
7.4.1 条件概率定义 160
7.4.2 条件概率的乘法定理 161
7.5 独立事件 162
7.6 独立重复试验与二项分布 163
7.6.1 独立重复试验 163
7.6.2 具有两个结果的重复试验、伯努利试验与二项试验 164
7.7 随机变量 165
7.7.1 随机变量定义 165
7.7.2 随机变量的和与积及其记号 165
7.7.3 随机变量的概率分布 166
7.7.4 随机变量的期望值 167
7.7.5 随机变量的方差与标准差 167
7.7.6 二项分布 168
7.8 切比雪夫不等式与大数定律 169
7.8.1 切比雪夫不等式 169
7.8.2 样本均值与大数定律 170
本章习题 170
补充题 188
补充题答案 193
第8章 图论 195
8.1 概述与数据结构 195
8.1.1 概述 195
8.1.2 链表与指针 195
8.1.3 堆栈、队列与优先队列 197
8.2 图与多重图 198
8.2.1 图 198
8.2.2 多重图 198
8.2.3 顶点的度（次数） 199
8.2.4 有限图与平凡图 199
8.3 子图、同构图与同胚图 200
8.3.1 子图 200
8.3.2 同构图 200
8.3.3 同胚图 200
8.4 路径与连通性 201
8.4.1 路径 201
8.4.2 连通性与连通分支 202
8.4.3 距离与直径 202
8.4.4 割点与桥 203
8.5 可遍历图、欧拉图与柯尼斯堡桥 203
8.5.1 可遍历图 203
8.5.2 哈密顿图 204
8.6 标号图与加权图 204
8.7 完全图、正则图与二部图 205
8.7.1 完全图 205
8.7.2 正则图 206
8.7.3 二部图 206
8.8 树图 207
8.8.1 树 207
8.8.2 生成树 208
8.8.3 最小生成树 208
8.9 平面图 209
8.9.1 地图与区域 210
8.9.2 欧拉公式 211
8.9.3 非平面图与库拉托夫斯基定理 211
8.10 图的着色 212
8.10.1 着色 212
8.10.2 对偶地图与四色定理 214
8.11 图在计算机存储器中的表示 215
8.11.1 邻接矩阵 215
8.11.2 图G的链接表示 216
8.12 图算法 218
8.12.1 深度优先搜索 218
8.12.2 广度优先搜索 220
8.13 旅行推销员问题 221
8.13.1 问题定义 221
8.13.2 最近邻算法 222
本章习题 223
补充题 240
补充题答案 246
第9章 有向图 251
9.1 概述 251
9.2 有向图 251
9.2.1 有向图定义 251
9.2.2 子图 252
9.3 基本定义 253
9.3.1 顶点度 253
9.3.2 路径 253
9.3.3 连通性 254
9.4 有根树 255
9.4.1 有根树定义 255
9.4.2 有序根树 256
9.5 有向图的序列表示 257
9.5.1 序列表示的定义 257
9.5.2 有向图与关系、邻接矩阵 257
9.5.3 路径矩阵 259
9.5.4 传递闭包与路径矩阵 260
9.6 沃舍尔算法与最短路径 260
9.6.1 沃舍尔算法 260
9.6.2 最短路径算法 262
9.7 有向图的链接表示 263
9.8 图的算法：深度优先与广度优先查找 265
9.8.1 深度优先查找 266
9.8.2 广度优先查找 267
9.9 有向无回路图与拓扑排序 269
9.9.1 有向无回路图 269
9.9.2 拓扑排序 269
9.10 最短路径的修剪算法 271
9.10.1 问题引出 271
9.10.2 修剪算法 272
本章习题 274
补充题 283
补充题答案 289
第10章 二叉树 293
10.1 概述 293
10.2 二叉树 293
10.2.1 二叉树的图示 293
10.2.2 相似二叉树 294
10.2.3 相关术语 294
10.3 完全二叉树与扩充（展）二叉树 295
10.3.1 完全二叉树 295
10.3.2 扩充（展）二叉树：2-树 296
10.3.3 代数式与波兰表示法 296
10.4 二叉树在存储器中的表示 297
10.4.1 二叉树的链接表示 297
10.4.2 二叉树的序列表示 298
10.5 遍历二叉树 299
10.6 二叉查找树 301
10.6.1 二叉查找树中的查找与插入 302
10.6.2 二叉查找树中的删除 303
10.6.3 二叉查找树算法的复杂性 304
10.7 优先队列与堆 304
10.7.1 堆的定义 304
10.7.2 向堆中插入节点 305
10.7.3 从堆中删除根节点 307
10.7.4 堆算法的复杂性 308
10.8 路径长度与哈夫曼算法 308
10.8.1 加权路径长度 309
10.8.2 哈夫曼算法 309
10.8.3 哈夫曼算法的计算机实现 311
10.8.4 编码中的应用 312
10.9 一般（有序有根）树的回顾 312
10.9.1 一般树的定义 312
10.9.2 森林 314
10.9.3 一般树与二叉树 314
本章习题 314
补充题 323
补充题答案 327
第11章 整数的性质 329
11.1 概述 329
11.2 次序、不等式与绝对值 330
11.2.1 次序 330
11.2.2 绝对值 331
11.3 数学归纳法 331
11.3.1 数学归纳法原理 331
11.3.2 良序原理 332
11.4 带余除法 333
11.4.1 带余除法定理 333
11.4.2 应用计算器的带余除法 333
11.5 整除与质数 334
11.5.1 整除 334
11.5.2 质数 335
11.6 最大公约数与欧几里德算法 336
11.6.1 最大公约数 336
11.6.2 欧几里德算法 337
11.6.3 最小公倍数 338
11.7 算术基本定理 338
11.7.1 互质 339
11.7.2 算术基本定理 339
11.8 同余关系 340
11.8.1 同余关系 340
11.8.2 剩余类 341
11.8.3 同余运算 342
11.8.4 剩余类的计算 342
11.8.5 模m整数 343
11.8.6 同余的消去律 343
11.8.7 简化剩余系与欧拉φ函数 344
11.9 同余方程 345
11.9.1 同余方程 345
11.9.2 线性同余方程：ax≡1（mod m） 346
11.9.3 线性同余方程：ax≡b（mod m） 346
11.9.4 孙子（中国）剩余定理 348
本章习题 350
补充题 374
补充题答案 379
第12章 语言、自动机与语法 381
12.1 概述 381
12.2 字母表、字与自由半群 381
12.2.1 字与字母表 381
12.2.2 连接 381
12.2.3 子字与初始段 382
12.2.4 自由半群与自由类群 382
12.3 语言 382
12.3.1 语言的定义 382
12.3.2 语言上的运算 383
12.4 正则表达式与正则语言 384
12.4.1 正则表达式 384
12.4.2 语言与正则语言 384
12.5 有限状态自动机 385
12.5.1 有限状态自动机的定义 385
12.5.2 自动机的状态图 386
12.5.3 自动机确定的语言 387
12.5.4 泵作用引理 388
12.6 语法 389
12.6.1 语法的定义 389
12.6.2 语法G的语言L（G） 390
12.6.3 语法的类型 391
12.6.4 上下文无关语法的推导树 392
12.6.5 巴克斯-诺尔形式 393
12.6.6 自动机与语法 393
本章习题 394
补充题 401
补充题答案 404
第13章 有限状态机与图灵机 406
13.1 概述 406
13.2 有限状态机 406
13.2.1 有限状态机的定义 406
13.2.2 有限状态机的状态表与状态图 407
13.2.3 输入带与输出带 407
13.2.4 二进制加法 408
13.3 哥德尔数 409
13.4 图灵机 410
13.4.1 基本定义 410
13.4.2 采用图灵机计算 412
13.4.3 具有输入的图灵机 413
13.4.4 语言与图灵机 413
13.5 可计算函数 414
13.5.1 定义 414
13.5.2 多元函数 415
本章习题 416
补充题 420
补充题答案 422
第14章 有序集与格 424
14.1 概述 424
14.2 有序集 424
14.2.1 偏序 424
14.2.2 对偶序 425
14.2.3 有序子集 425
14.2.4 拟序 425
14.2.5 可比较性与线性有序集 425
14.2.6 积集与积序 426
14.2.7 克林闭包与次序 426
14.3 偏序集的哈塞图 427
14.3.1 哈塞图定义 427
14.3.2 极小元素、极大元素、首元素（最小元素）、末元素（最大元素） 428
14.4 相容枚举 429
14.5 上确界与下确界 430
14.6 同构有序集（相似有序集） 432
14.7 良序集 432
14.7.1 良序集定义 432
14.7.2 超限归纳法 433
14.7.3 选择公理与良序定理 434
14.8 格 434
14.8.1 格的定义公理 435
14.8.2 对偶性与幂等律 435
14.8.3 格与次序 435
14.8.4 子格与同构格 436
14.9 有界格 437
14.10 分配格 437
14.10.1 分配格定义 437
14.10.2 并不可约元与原子 438
14.11 补元与有补格 439
14.11.1 补元 439
14.11.2 有补格 439
本章习题 440
补充题 451
补充题答案 457
第15章 布尔代数 461
15.1 概述 461
15.2 基本定义 461
15.2.1 布尔代数 461
15.2.2 子代数、同构布尔代数 462
15.3 对偶性 463
15.4 基本定理 463
15.5 布尔代数作为格 464
15.6 表示定理 464
15.7 集合的积和形式 465
15.8 布尔代数的积和形式 466
15.8.1 积和形式的定义 466
15.8.2 求积和形式的算法 467
15.8.3 完全积和形式 468
15.9 极小布尔表达式与素项 469
15.9.1 极小积和 469
15.9.2 素项 469
15.9.3 基本积的一致 470
15.9.4 一致法求素项 470
15.9.5 求极小积和形式 471
15.10 逻辑门与逻辑电路 472
15.10.1 逻辑门 472
15.10.2 逻辑电路 474
15.10.3 逻辑电路作为布尔代数 474
15.10.4 与或电路 474
15.10.5 与非门和或非门 475
15.11 真值表与布尔函数 476
15.11.1 真值表 476
15.11.2 布尔函数 478
15.12 卡诺图 479
15.12.1 卡诺图定义 479
15.12.2 二元情形 480
15.12.3 三元情形 481
15.12.4 四元情形 483
本章习题 485
补充题 503
补充题答案 507
附录A 向量与矩阵 510
A.1 概述 510
A.2 向量 510
A.2.1 向量定义 510
A.2.2 向量运算 510
A.2.3 列向量 511
A.3 矩阵 511
A.4 矩阵的加法与标量乘法 512
A.5 矩阵乘法 514
A.5.1 矩阵乘法的定义 514
A.5.2 矩阵乘法与线性方程组 515
A.6 转置矩阵 516
A.7 方阵 516
A.7.1 方阵定义 516
A.7.2 方阵的代数运算 517
A.8 可逆（非奇异）矩阵和逆矩阵 518
A.9 行列式 519
A.9.1 行列式的定义 519
A.9.2 行列式的一般定义 520
A.9.3 行列式与2×2矩阵的逆矩阵 520
A.10 初等行变换与高斯消去法 521
A.10.1 初等行变换 521
A.10.2 阶梯矩阵 521
A.10.3 矩阵形式中的高斯消去法 522
A.10.4 线性方程组的矩阵解法 524
A.10.5 n×n矩阵的逆矩阵 525
A.11 布尔（0-1）矩阵 526
本章习题 527
补充题 538
补充题答案 542
附录B 代数系统 543
B.1 概述 543
B.2 运算 543
B.2.1 定义 543
B.2.2 运算性质 544
B.3 半群 546
B.3.1 半群的定义 546
B.3.2 自由半群与自由么半群 547
B.3.3 子半群 547
B.3.4 同余关系与商结构 547
B.3.5 半群的同态 548
B.3.6 半群同态基本定理 549
B.3.7 半群积 550
B.4 群 550
B.4.1 群的定义 550
B.4.2 对称群Sn 551
B.4.3 MAP（A）、PERM（A）与AUT（A） 552
B.5 子群、正规子群与同态 552
B.5.1 子群 552
B.5.2 陪集 553
B.5.3 正规子群 553
B.5.4 模m整数 554
B.5.5 循环子群 554
B.5.6 生成集和生成元 555
B.5.7 同态 555
B.6 环、整环（整域）与域 556
B.6.1 环与子环的定义 556
B.6.2 特殊的环：整环与域 557
B.6.3 理想 558
B.6.4 环同态 559
B.6.5 整环上的整除性 559
B.7 域上的多项式 559
B.7.1 基本定义 560
B.7.2 欧几里德算法与多项式的根 561
B.7.3 K［t］作为PID（主理想域）与UFD（唯一析因整环） 562
B.7.4 代数基本定理 563
本章习题 564
补充题 581
补充题答案 587