第1章 基础知识 1
1.1集合与序列 1
1.1.1集合的基本概念 1
1.1.2集合的运算及性质 3
1.1.3序列 6
1.2数论基础 7
1.3计数基础 10
1.3.1加法法则与乘法法则 10
1.3.2排列与组合 11
1.3.3鸽巢原理 16
1.3.4有限集的计数——容斥原理 19
1.3.5递推关系 22
1.4布尔矩阵及其运算 26
习题1 28
第2章 命题逻辑 41
2.1命题逻辑的基本概念 41
2.2命题公式及其分类 45
2.3命题逻辑的等值演算 48
2.4对偶与范式 53
2.4.1对偶 53
2.4.2析取范式和合取范式 54
2.4.3主范式 56
2.5命题联结词的完备集 63
2.6命题逻辑的推理 64
习题2 70
第3章 谓词逻辑 79
3.1谓词与量词 79
3.1.1谓词 79
3.1.2量词 80
3.2谓词公式及分类 81
3.3自然语言形式化 83
3.4谓词逻辑的等值演算 86
3.5前束范式 90
3.6谓词逻辑的推理 91
习题3 98
第4章 二元关系 104
4.1关系及其表示 104
4.1.1有序对与笛卡儿积 104
4.1.2二元关系的定义 106
4.1.3二元关系的表示 109
4.2关系的运算 110
4.2.1关系的基本运算 110
4.2.2关系的幂和道路 113
4.3关系的性质 116
4.3.1关系性质的定义和判断 116
4.3.2关系运算对性质的保持 120
4.4关系的闭包 122
4.5等价关系和集合的划分 127
4.5.1等价关系、等价类和商集 127
4.5.2集合的划分 128
4.5.3等价关系与划分的一一对应 129
4.6相容关系与集合的覆盖 130
4.7关系在计算机中的表示方法 131
习题4 132
第5章 函数 141
5.1函数的定义 141
5.2函数的性质 142
5.3函数的复合 144
5.4逆函数 146
5.5计算机科学中的常用函数 147
5.6双射函数及集合的势 152
习题5 156
第6章 偏序关系 162
6.1偏序关系和偏序集 162
6.1.1偏序关系和偏序集的定义与性质 162
6.1.2积偏序和字典序 164
6.1.3哈斯图 164
6.2偏序集中的特殊元素 166
6.2.1偏序集中的特殊元素 166
6.2.2拓扑排序 169
6.3格与布尔代数 171
6.3.1格的定义 171
6.3.2特殊的格 174
6.3.3布尔代数 177
6.3.4信息流的格模型 179
习题6 181
第7章 代数结构 187
7.1代数结构 187
7.1.1运算与代数结构的定义 187
7.1.2二元运算的性质 189
7.2群 192
7.2.1半群与亚群 192
7.2.2群的概念 193
7.2.3群的性质 196
7.2.4子群 198
7.2.5循环群与置换群 199
7.2.6陪集与拉格朗日定理 200
7.3环与域 203
7.3.1环 203
7.3.2域 205
7.4作为代数结构的格与布尔代数 206
习题7 208
第8章 图论 218
8.1基本概念 218
8.1.1无向图、有向图和握手定理 218
8.1.2图的同构与子图 224
8.1.3道路、回路与连通性 227
8.1.4图的矩阵表示 228
8.2欧拉图 230
8.3哈密顿图 234
8.4平面图 238
8.5顶点支配、独立与覆盖 244
8.6匹配 247
8.6.1匹配与最大匹配 247
8.6.2霍尔定理及其应用 252
8.6.3匹配与覆盖 254
8.6.4二部图中的最佳匹配 258
8.7图的着色 263
8.8网络与流 267
习题8 282
第9章 树及其应用 306
9.1无向树 306
9.2支撑树及其应用 310
9.3最短道路树 321
9.4根树及其应用 325
9.4.1根树的定义和基本概念 325
9.4.2二叉树的遍历 330
9.4.3最优二叉树与赫夫曼编码 332
习题9 335
第10章 形式语言、自动机与正则表达式 342
10.1语言 342
10.2文法 346
10.3巴科斯-诺尔范式和语法图 351
10.4有限状态自动机 353
10.5语言与自动机的关系 359
10.6正则表达式 361
习题10 362
附录A 综合性研讨专题 371
A.1凑邮资、分油、爬台阶与台球桌 371
A.1.1邮资问题 371
A.1.2分油问题 373
A.1.3登阶问题 376
A.1.4台球问题 378
A.2基于模运算的校验码 379
A.2.1EAN-13码 379
A.2.2新版国际标准书号ISBN-13 380
A.2.3第二代身份证 380
A.3应用鸽巢原理的纸牌魔术二则 382
A.3.1纸牌魔术A 382
A.3.2纸牌魔术B 384
A.4完美洗牌法 385
A.5Chomp游戏 388
A.6麻花辫 390
A.7伯恩赛德引理与波利亚定理 394
A.8顿时错乱问题 398
A.9抽芽游戏与抱子甘蓝游戏 402
A.9.1抽芽游戏 402
A.9.2抱子甘蓝游戏 405
A.10汉诺塔杂谈 407
A.10.1汉诺塔图 407
A.10.2汉诺塔的非递归算法 410
A.10.3汉诺塔与普通二进制码 411
A.11存储器轮 412
A.11.1存储器轮及解决方法 412
A.11.2德·布鲁因序列 414
A.12中国邮路问题 417
A.13格雷码、超立方体的哈密顿回路和九连环 420
A.13.1格雷码 420
A.13.2超立方体图中的哈密顿回路 421
A.13.3九连环与格雷码 423
A.14谢尔宾斯基三角 426
附录B 课程综合实验 433
B.1实验一：汉诺塔问题的变体 433
B.1.1实验内容 433
B.1.2实验要求 434
B.1.3扩展阅读 435
B.2实验二：命题演算的计算机实现 435
B.3实验三：二元关系及其应用 436
B.3.1准备工作 436
B.3.2等价关系及其应用 436
B.3.3偏序关系及其应用 437
B.3.4连通性和欧拉道路/回路 439
B.4实验四：村庄修引水渠问题 440
B.4.1实验内容（一） 441
B.4.2实验内容（二） 442
B.4.3讨论与思考 442
B.5实验五：考场安排问题 443
B.5.1实验内容 443
B.5.2实验要求 444
B.6实验六：展览馆的参观与维护 444
B.7实验七：导师和研究生的自动分配 445
B.8实验八：绿色健康城市规划 446
B.9实验九：羽毛球双打配对和住宿安排 446
附录C 名词英汉对照表 448
附录D 使用Mathematica学习离散数学 459
D.1集合、序列与矩阵 459
D.2排列、组合、递推关系与划分 462
D.3关系与有向图 463
D.4图 467
D.5树 471
附录E Prolog语言与逻辑推理 473
E.1Prolog基础 473
E.2典型逻辑问题 479
参考文献 483