离散数学及应用（第2版）

　　离散数学是现代数学的一个重要分支，是计算机专业和软件工程专业的基础主干课程，是进一步学习后续课程以及进行研究和开发的基础。本书根据作者多年教学经验编写而成，着重讲解离散数学的基本概念、基本方法及其应用，给出了大量的典型例题和习题，以及若干综合专题、应用案例和实验项目。全书共10章，内容包括朴素集合论、数论基础、计数基础、命题逻辑、谓词逻辑、二元关系、函数、偏序关系与格、代数结构、图论与树、形式语言、自动机与正则表达式等。附录给出综合性研讨专题、综合实验、名词中英文对照表等。　本书结构紧凑，内容精练，体系严谨，语言流畅，讲解详细，可作为高等院校计算机或软件工程专业本科生的“离散数学”课程教材，也可供其他专业学生和科技人员阅读参考。

暂缺《离散数学及应用（第2版）》作者简介

　　
　　
　　
　　
　　
　　
　　　　　第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.1 EAN-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.5 Chomp游戏 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.1 Prolog基础 473
E.2 典型逻辑问题 479
参考文献??/ 483
　　
　　
VIII
离散数学及应用（第2版）
　　
IX
目录