离散数学

分四部分讲解：数理逻辑、集合论、代数结构、图论

结合建构主义教学理论，设计不同离散数学应用案例，提供学习《离散数学》的应用场景

各章穿插大量有意义的范例和实验项目

  离散数学是计算机学科的核心课程，是一门理论抽象、内容广泛、结构严谨的计算机相关专业的基础课程。它不仅与后续课程，如数据结构、数据库原理、操作系统、人工智能等有紧密联系，而且对于训练和培养学生的抽象和逻辑思维能力，提高学生的科研素质方面都有着十分重要的作用。

  为了适应省级示范性软件学院及计算机相关专业《离散数学》教学改革的需要，提高学生应用理论知识解决实际问题能力的需要，根据教育部高等学校计算机科学与技术教学指导委员会颁布的计算机相关专业教学基本要求，针对地方院校的教学对象、教学特点和方法进行研究，我们提出了“《离散数学》软件工程化教学改革”研究课题和编写应用型《离散数学》教材任务，并得到教育主管部门的立项支持。为了编写好本教材，参考了美国俄克拉荷马（Oklahoma）大学的Beseme项目出版的《软件工程数学》等教材。编写教材内容注重理论知识的讲解和逻辑推理的训练，也注重应用离散数学知识分析专业课程的实际问题，讨论离散数学对后续专业课的影响，引入软件工程化应用范例和实践性内容，加强实践能力的培养。

  本书包含数据逻辑、集合论、代数结构、图论四部分内容。每部分内容结合建构主义教学理论，设计不同离散数学应用案例，提供学习《离散数学》的应用场景。每一章选择了有意义的范例和实验项目，有利于学生通过编程实践增进对离散数学知识的理解和应用，提高学生的学习兴趣。全书体系严谨、叙述深入浅出。每部分内容都分为基础知识章节和高级应用章节（带*部分），便于教师根据学时要求选讲章节内容，适合不同学时的授课（删除带**章节，可采用90学时教学，再删除带*章节，可采用70学时教学），也方便软件开发人员参考应用。

  本书的数理逻辑部分（第1～3章）由邱晓红编写，集合论部分（第四4～7章）由李光泉编写，代数结构部分（第8～10章）由艾施荣编写，图论部分（第11～13章）由熊焕亮编写。全书由邱晓红教授进行组织整理和统一风格。本书配套的实验程序源代码和演示范例，很多出自教学过程中指导学生参加各类软件大赛的作品，有些内容是“《离散数学》软件工程化教学改革”（JXJG-08-4-28）、“教学与科研有机结合提高教学质量和学生综合素质的研究”（2008B2ZB04）、“实施本科生全程导师制教育培养模式的研究——以江西省高校软件学院为例”（08YB078）等教改课题的研究成果，在此特别感谢有关单位领导和作者的支持。在编写过程中还参阅了大量的离散数学书籍和有关教学研究论文资料，在此向有关作者表示衷心的感谢。南昌大学幸冬梅博士审阅全稿，提出了宝贵的意见和建议，在此深表谢意。

  由于时间仓促及编辑者水平有限，恳请广大读者及同行专家批评指正。

 

前言
第一部分  数理逻辑
第1章  命题逻辑 3
1.1  命题及其表示 3
1.1.1  命题的基本概念 3
1.1.2  命题分类 4
1.1.3  命题标识符 4
1.2  逻辑联结词 5
1.2.1  否定联结词 5
1.2.2  合取联结词 5
1.2.3  析取联结词 6
1.2.4  条件联结词 7
1.2.5  双条件联结词 7
1.2.6  字位运算与布尔检索 8
1.3  命题公式与解释 9
1.3.1  命题公式 9
1.3.2  命题的符号化 10
1.4  真值表与等价公式 12
1.4.1  真值表 12
1.4.2  等价公式 13
1.5  命题公式的分类与蕴含式 17
1.5.1  命题公式的分类 17
1.5.2  重言式与矛盾式的性质 18
1.5.3  蕴含式 18
1.6  其他逻辑联结词和最小功能完备联结词组 21
1.6.1  其他逻辑联结词 21
1.6.2  最小功能完备联结词组 22
1.6.3  联结词的逻辑电路表示 23
1.7  对偶与范式 24
1.7.1  对偶式与对偶原理 24
1.7.2  命题公式的范式 26
1.7.3  命题公式的主析取范式和主合取范式 28
1.8  推理理论 37
1.8.1  直接证法 38
1.8.2  间接证法 40
习题一 42
实验一  真值表的程序计算 47
第2章  谓词逻辑 49
2.1  谓词的基本概念 49
2.1.1  个体和谓词 49
2.1.2  量词 51
2.2  谓词公式与解释 52
2.2.1  谓词公式 52
2.2.2  谓词公式的解释 53
2.3  变元的约束 54
2.3.1  约束变元和自由变元 54
2.3.2  换名规则 55
2.3.3  代替规则 56
2.4  谓词演算的等价式与蕴含式 56
2.4.1  谓词公式的赋值 56
2.4.2  谓词公式的分类 57
2.4.3  谓词演算的等价式 58
2.4.4  谓词演算的蕴含式 62
2.5  谓词公式范式 64
2.5.1  前束范式 64
2.5.2  斯柯林范式 65
2.6  谓词演算的推理理论 66
2.6.1  US规则（全称指定规则）（Universal Specification） 66
2.6.2  UG（全称推广规则）（Universal Generalization） 66
2.6.3  ES（存在指定规则）（Existential Specification） 66
2.6.4  EG（存在推广规则）（Existential Generalization） 67
习题二 71
实验二  命题逻辑简单推理系统 73
第3章  基于归结原理的推理证明** 75
3.1  谓词公式与子句集 75
3.1.1  斯柯林（Skolem）标准范式 75
3.1.2  子句与子句集 76
3.1.3  不可满足意义下的一致性 76
3.1.4  P＝P1∧P2∧…∧Pn的子句集 76
3.2  海伯伦（HERBRAND）理论 77
3.2.1  H域 77
3.2.2  原子集 77
3.2.3  H域上的解释 77
3.3  归结原理（RESOLUTION METHOD） 78
3.3.1  置换与合一 78
3.3.2  命题逻辑中的归结原理 79
3.3.3  一阶谓词逻辑中的归结原理 80
3.3.4  归结原理的完备性 81
3.3.5  利用归结原理进行定理证明 81
3.3.6  应用归结原理进行问题求解 81
3.4  归结过程的控制策略 83
3.4.1  引入控制策略 83
3.4.2  归结控制策略及其应用举例 83
习题三 84
实验三  归结原理的程序实现 85
第二部分  集合论
第4章  集合及其运算 89
4.1  集合的概念及其表示 89
4.1.1  集合的概念 89
4.1.2  集合与集合间的关系 90
4.1.3  幂集（Power Set） 91
4.2  集合的基本运算 91
4.2.1  集合的并（Union）运算 91
4.2.2  集合的交（Intersection）运算 92
4.2.3  集合的交运算与并运算之间的关系 93
4.2.4  集合的补（Substraction）运算 93
4.2.5  集合的对称差（Symmetric Difference）运算 94
4.2.6  集合的计算机表示 96
4.3  集合中元素的计数 97
4.3.1  两个基本原理 97
4.3.2  排列、组合 97
4.3.3  容斥原理 98
4.4  集合的应用 100
4.4.1  数据表的并（∪）运算 101
4.4.2  数据表的差（-）运算 101
4.4.3  数据表的交（∩）运算 101
习题四 102
实验四  集合的基本运算 104
第5章  二元关系 106
5.1  集合的笛卡儿积 106
5.1.1  序偶（Ordered Pair） 106
5.1.2  笛卡儿积（Cartesian Product） 107
5.2  二元关系 109
5.2.1  二元关系的基本概念 109
5.2.2  二元关系的表示 109
5.2.3  关系的运算 110
5.2.4  关系的性质 114
5.2.5  关系的闭包（Closure）运算 116
5.3  等价关系与集合的划分 122
5.3.1  集合的划分（Partion of Set） 122
5.3.2  等价关系（Equivalent Relation）与等价类 124
5.4  相容关系与集合的覆盖* 127
5.4.1   集合的覆盖（Covering） 127
5.4.2  相容关系（Consistent Relation）与相容类 127
5.5  偏序关系 130
5.5.1  偏序关系（Partial Relation）与偏序集的概念 130
5.5.2  偏序集的哈斯（Hasse）图 131
5.5.3  偏序集中的特殊元 132
5.5.4  全序关系（Complete Partial Relation）及其应用 134
5.6  关系的应用 135
5.6.1  等价关系在计算机中的应用 135
5.6.2  序关系在项目管理中的应用 136
习题五 137
实验五  求关系的闭包 140
第6章  函数 142
6.1  函数的概念 142
6.1.1  函数（Function）的概念 142
6.1.2  几类特殊函数 143
6.2  逆函数与复合函数 145
6.2.1  逆函数 145
6.2.2  复合函数 146
习题六 147
实验六  函数的图形可视化 150
第7章  集合的基数** 151
7.1  集合的等势与优势 151
7.2  基数、可数集与不可数集 151
7.2.1  基数 152
7.2.2  可数集与不可数集 153
7.2.3  基数的比较 157
习题七 159
实验七  自然数性质的可视化表示 160
第三部分  代数结构
第8章  半群、语言和自动机 163
8.1  半群和语言 163
8.2  语言和文法 166
8.3  有限状态机 168
8.4  有限状态自动机 170
8.5  语言与自动机的关系* 174
习题八 178
实验八  设计输出状态自动机实验 182
第9章  代数系统 184
9.1  代数系统的概念 184
9.2  代数系统的运算及其性质 186
9.3  群与子群 191
9.4  同态与同构* 196
9.5  交换群与循环群、置换群 203
9.5.1  交换群 203
9.5.2  循环群 204
9.5.3  置换群 205
9.6  子群与群的陪集分解* 207
9.7  环与域* 210
习题九 215
实验九  代数系统的基本运算 219
第10章  格与布尔代数* 221
10.1  格的概念 221
10.2  分配格 229
10.3  有补格 233
10.4  布尔代数与布尔表达式** 235
10.5  数字电路逻辑运算 244
习题十 247
实验十  代数系统综合课程设计 248
第四部分  图论
第11章  图的基本概念 252
11.1  图的概念 252
11.1.1  无向图和有向图 252
11.1.2  简单图、多重图和同构图 253
11.1.3  完全图和正则图 255
11.1.4  几种特殊的图 256
11.1.5  子图 257
11.1.6  图的操作 258
11.2  图的连通性 259
11.2.1  通路与回路 259
11.2.2  连通图 261
11.2.3  二部图 263
11.3  图的矩阵表示 264
11.3.1  关联矩阵 265
11.3.2  邻接矩阵 266
11.3.3  可达矩阵 268
11.4  图的运算 268
11.5  欧拉图 269
11.5.1  欧拉通路和回路 269
11.5.2  半欧拉图和欧拉图 270
11.5.3  哥尼斯堡七桥问题 273
11.6  哈密顿图 273
11.6.1  哈密顿图 274
11.6.2  哈密顿图的充分条件 275
11.7  带权图 278
11.8  平面图 278
11.8.1  平面图的基本概念及性质 278
11.8.2  库拉托夫基定理 280
11.8.3  平面图着色及应用 281
11.8.4  边着色 283
11.9  应用举例* 285
11.9.1  中国邮路问题 285
11.9.2  冰箱分隔问题 287
11.9.3  排课表问题 287
习题十一 288
实验十一  应用邻接矩阵方法求解锁具装箱问题 292
第12章  树 294
12.1  树的概念及性质 294
12.1.1  树的定义 294
12.1.2  树的一些性质 294
12.2  最小生成树 295
12.2.1  生成树 295
12.2.2  最小代价生成树 297
12.3  根树 298
12.3.1  根树的定义 298
12.3.2  根树的分类 299
12.4  树的应用* 300
12.4.1  决策树 300
12.4.2  博奕树 300
习题十二 301
实验十二  应用生成树算法求解旅行商问题 304
第13章  支配集、覆盖集、独立集与匹配理论* 305
13.1  支配集、覆盖集、独立集概念 305
13.1.1  支配集 305
13.1.2  覆盖集 305
13.1.3  独立集 306
13.2  边覆盖集与匹配 307
13.3  二部图中的匹配 310
13.4  图论的综合应用举例** 311
13.4.1  会议议程安排问题 311
13.4.2  大中型工程项目的优化 314
习题十三 319
实验十三  程序求解支配集、独立集问题 321
《离散数学》常用符号表 322
参考文献 326

1. 教学的智慧—高三数学落实核心素养教法指导 [王春红 等 编著]
2. 应用数学 [吴小宁]
3. 大学生创新创业实践——数学类 [主编 吴天庆]
4. 工程数学 [主编 郭立娟 王海]
5. 应用数学 [梁玮 蔡超 高志]
6. 大学应用数学 [主编 郭立娟]
7. 高等数学导学篇（下册） [主编 李文婧 胡雷 尹金生]
8. 高等数学导学篇（上册） [主编 李文婧 胡雷 尹金生]
9. 高等数学（下册） [主编 李爱芹 胡雷 尹金生]
10. 高等数学（上册） [主编 李爱芹 胡雷 尹金生]
11. 高等数学（下册） [秦红兵]
12. 应用数学 [主编 刘东海 刘丽瑶]
13. 高等数学（上册） [主编 白莉 秦红兵]
14. 高等数学（下册）（第二版） [主编 何春江]
15. 高等数学（上册）（第二版） [主编 何春江]
16. 高等数学 [主编 刘彦辉 张 静]
17. 应用数学（第二版） [主编 刘丽瑶]
18. 数学（下册） [单凤娟 刘艳平 李杨 马秀芬 ]
19. 数学（上册） [单凤娟 刘艳平 李杨 马秀芬 ]
20. 应用数学基础 [主编 刘彦辉 李先明]
21. 高等数学学习辅导与习题解答（第三版） [主编 翟秀娜]
22. 离散数学（第二版） [主编 贾振华]
23. 数学（二）职业模块 [李丽君 吴白旺 杨勇]
24. 高等数学（下册） [何春江]
25. 数学（一）职业模块 [主编 杨勇 海敏娟 禇丽娜]
26. 高等数学（上册） [何春江]
27. 应用数学（第二版•下册） [主 编 孙振营 徐自立]
28. 应用数学（第二版•上册） [主编 孙振营 夏云青]
29. 数学（一）职业模块 [主编 杨勇 海敏娟 禇丽娜]
30. 计算机数学基础（第二版） [主编 何春江]