本书将离散数学分为数理逻辑、集合论、代数系统和图论四个部分，系统地介绍了命题逻辑、谓词逻辑、集合、关系、函数、代数结构、格与布尔代数、图、特殊图中有关的定义、定理及证明方法，并给出了离散数学中不同知识点在计算机科学中的应用。本书配有课后习题参考答案及电子教案。 全书结构严谨，逻辑清晰，示例丰富，可以作为高等学校计算机大类各专业离散数学必修课教材，也可以作为其他相关专业离散数学课程教材，同时，还可以供从事计算机科学工作的科技人员阅读与参考。

全书结构严谨，逻辑清晰，示例丰富，可以作为高等学校计算机大类各专业离散数学必修课教材，也可以作为其他相关专业离散数学课程教材，同时，还可以供从事计算机科学工作的科技人员及学生阅读与参考。

离散数学研究各种离散量的结构、性质及其关系，是现代数学的一个重要分支。其研究对象一般是有限个或可数个元素，这与计算机科学离散性的特点相符合，因此，离散数学也称为计算机数学，是计算机科学中基础理论的核心课程，与计算机科学中的数据结构、操作系统、编译原理、算法分析、数据库原理、人工智能、大数据、信息安全、计算机网络等课程联系紧密。通过学习离散数学可以为后续课程的学习打下坚实的数学基础；另外，离散数学逻辑严谨，推理缜密，通过离散数学的学习可以培养学生的抽象思维能力和缜密概括能力。
离散数学是随计算机科学的发展而逐步建立的，由多门数学分支组成，每个分支从不同的角度研究离散量之间的关系，都是一个独立的研究领域，但又相互关联，因此国内外的教材对每个分支各有侧重，形成了各种不同的教材特色。本书从为计算机科学服务的角度出发，将离散数学分为四篇： 第一篇数理逻辑、第二篇集合论、第三篇代数系统、第四篇图论。第一篇数理逻辑分为命题逻辑和谓词逻辑两章，第二篇集合论分为集合、关系、函数三章，第三篇代数系统分为代数结构、格与布尔代数两章，第四篇分为图和特殊图两章。各篇章中所涉及的概念、定理清晰易懂，用词严谨，推演详尽，例题与定义定理相结合，题量丰富，并给出了离散数学知识点在计算机科学中的应用实例，每章均有对主要知识点的总结、主要习题类型及解题方法的讲解，课后习题难度渐进，覆盖面广。
本书作者长期从事离散数学教学工作，有丰富的理论知识和实践经验。本书由崔艳荣和黄艳娟任主编，陈勇、胡杰、周张兰、冯伟任副主编。其中第一篇由崔艳荣和陈勇编写，第二篇由胡杰编写，第三篇由黄艳娟和冯伟编写，第四篇由周张兰编写。全书由崔艳荣统稿。编写过程中，参考和引用了国内外的离散数学书籍和资料，在此向这些书籍和资料作者表示感谢！
由于作者水平有限，书中难免会存在不妥之处，敬请读者批评指正。

编者
2019年8月

崔艳荣（第一主编）：长江大学计算机科学学院网络工程系主任，教授、硕士生导师、武汉大学计算机软件与理论专业博士，长期从事离散数学教学，在软件学报等国内外学术期刊上发表论文30多篇，主编《物联网概论》，作为副主编，完成《公用计算机文化基础实验教程》、《公用计算机文化基础》教材的编写，参编教材两部，分别是《C及C 程序设计实验教程》、《计算机网络技术与Internet应用》。三次荣获长江大学教学质量优秀奖。 黄艳娟（主编之一）：长江大学计算机科学学院网络工程系教师，硕士，长期从事离散数学教学，参与《物联网概念》编著，两次荣获长江大学青年教师讲课比赛二等奖。

第一篇数 理 逻 辑
第1章命题逻辑/31.1命题及其表示3
1.1.1命题3
1.1.2命题的表示4
1.2联结词4
1.2.1否定5
1.2.2合取5
1.2.3析取6
1.2.4条件6
1.2.5双条件7
1.3命题公式与翻译8
1.3.1命题公式8
1.3.2翻译9
1.4真值表与等价式10
1.4.1真值表10
1.4.2等价式12
1.5重言式、蕴含式与对偶式14
1.5.1重言式14
1.5.2蕴含式15
1.5.3对偶式17
1.6联结词的完备集18
1.6.1不可兼析取18
1.6.2条件的否定19
1.6.3与非19
1.6.4或非19
1.6.5联结词的完备集20
1.7命题公式的范式21
1.7.1合取范式与析取范式211.7.2主析取范式23
1.7.3主合取范式26
1.7.4主析取范式与主合取范式之间的联系28
1.8推理理论29
1.8.1有效结论与推理规则29
1.8.2判断有效结论的常用方法31
1.9命题逻辑的应用35
1.10本章总结37
1.11本章习题38
〖1〗离散数学目录〖3〗〖3〗第2章谓词逻辑/44
2.1谓词的概念与表示44
2.1.1谓词的定义44
2.1.2n元谓词45
2.2命题函数与量词46
2.2.1命题函数46
2.2.2量词47
2.3谓词公式与翻译48
2.3.1谓词公式48
2.3.2谓词公式的翻译49
2.4变元的约束50
2.4.1约束变元与自由变元50
2.4.2约束变元的换名与自由变元的代入51
2.4.3有限论域客体变元的枚举52
2.5谓词演算的等价式与蕴含式52
2.5.1谓词公式的赋值及分类52
2.5.2谓词演算的等价式53
2.5.3谓词演算的蕴含式55
2.5.4多个量词之间的等价关系与蕴含关系56
2.6前束范式57
2.7谓词演算的推理理论58
2.8本章总结61
2.9本章习题63第二篇集合论
第3章集合/713.1集合的概念和表示法71
3.1.1集合的概念71
3.1.2集合的表示72
3.1.3特殊集合74
3.1.4集合之间的关系74
3.2集合的运算76
3.3序偶与笛卡儿积82
3.3.1序偶82
3.3.2笛卡儿积83
3.4包含排斥原理85
3.5集合的划分与覆盖87
3.6集合的应用89
3.7本章总结92
3.8本章习题95
第4章关系/100
4.1关系的概念与表示100
4.1.1关系的概念100
4.1.2关系的表示102
4.2关系的性质105
4.2.1关系的几种性质105
4.2.2性质的判别109
4.3复合关系和逆关系111
4.3.1复合关系111
4.3.2逆关系115
4.4关系的闭包运算117
4.4.1关系的闭包定义118
4.4.2关系闭包运算的相关定理118
4.5等价关系与等价类123
4.5.1等价关系124
4.5.2等价类125
4.5.3商集126
4.6相容关系128
4.6.1相容关系及其表示128
4.6.2相容类129
4.6.3最大相容类130
4.6.4完全覆盖131
4.7序关系132
4.7.1偏序关系及其表示132
4.7.2盖住关系132
4.7.3全序关系134
4.7.4特殊元素135
4.7.5良序集合137
4.8关系的应用138
4.9本章总结142
4.10本章习题143
第5章函数/151
5.1函数的概念151
5.2几种特殊的函数152
5.3函数的运算（复合、逆函数）154
5.3.1复合函数154
5.3.2逆函数155
5.4函数的应用157
5.5本章总结161
5.6本章习题162
第三篇代 数 系 统
第6章代数结构/1676.1代数系统引论167
6.2基本运算及其性质168
6.3半群与独异点174
6.4群与子群176
6.5阿贝尔群与循环群180
6.5.1阿贝尔群（交换群）180
6.5.2循环群180
6.6置换群183
6.7陪集与拉格朗日定理184
6.7.1陪集184
6.7.2拉格朗日定理186
6.8同构与同态188
6.8.1同构188
6.8.2同态190
6.9环与域193
6.9.1环193
6.9.2域196
6.10代数结构的应用198
6.10.1计数问题198
6.10.2群码与纠错码201
6.11本章总结215
6.12本章习题217
第7章格与布尔代数/221
7.1格的定义221
7.2分配格226
7.3有补格228
7.4布尔代数230
7.4.1布尔代数的一般概念230
7.4.2子代数231
7.4.3布尔同态与布尔同构232
7.5布尔代数表达式235
7.6格与布尔代数的应用242
7.6.1布尔函数的表示法243
7.6.2逻辑电路设计方法246
7.6.3时序逻辑电路的设计250
7.7本章总结254
7.8本章习题256
第四篇图论
第8章图/2618.1图的基本概念261
8.2路、回路与连通性267
8.2.1路与回路267
8.2.2无向图的连通性268
8.2.3有向图的连通性271
8.3图的矩阵表示273
8.3.1邻接矩阵273
8.3.2可达矩阵276
8.3.3关联矩阵277
8.4图的应用279
8.4.1无向图的应用279
8.4.2有向图的应用280
8.4.3混合图的应用280
8.4.4一些特殊简单图及其应用280
8.5本章总结282
8.6本章习题284
第9章特殊图/287
9.1欧拉图287
9.2哈密尔顿图292
9.3平面图296
9.4对偶图299
9.5树与根树302
9.5.1树的概念302
9.5.2生成树304
9.5.3根树305
9.6树与根树的应用307
9.6.1最小生成树307
9.6.2最优树308
9.7本章总结309
9.8本章习题312
参考文献/315