"本书阐述了离散数学中基本而重要的理论，让读者方便、快捷、系统地掌握“离散数学”课程的核心、精髓及程序代码背后的算法原理；同时，本书采用问题驱动或案例式的编写方式，利用C或C++程序设计语言，编写出详细的程序代码，将“离散数学”中的抽象知识具体化、实战化、趣味化。
本书主要包括四大部分: ①数理逻辑； ②集合、二元关系与函数； ③代数系统与数论； ④图论。每一部分又分理论和程序实践两章，共8章。本书将理论知识和编程实践相结合，帮助读者在透彻理解理论知识的同时提高运用离散数学知识解决实际问题的思维水平及编程能力。
本书可作为高等学校相关专业课程的教材或辅导用书，也可作为相关科技工作者的参考用书。
"

目录


第1章数理逻辑理论1
1.1命题逻辑的基本概念1
1.1.1命题及联结词1
1.1.2命题公式与解释5
1.2命题公式的等值演算及其范式7
1.2.1命题公式等值的概念及基本等值式7
1.2.2简单析取式与简单合取式8
1.2.3析取范式与合取范式8
1.2.4主析取范式和主合取范式9
1.3命题逻辑的推理理论13
1.3.1基于等值演算的命题逻辑推理14
1.3.2基于推理规则的命题逻辑推理14
1.4一阶逻辑的基本概念16
1.4.1个体词、量词和谓词16
1.4.2一阶逻辑公式及解释18
1.5一阶逻辑的等值演算20
1.5.1一阶逻辑的等值概念及基本等值式20
1.5.2一阶逻辑的前束范式22
1.6一阶逻辑的推理与应用23
1.6.1一阶逻辑的自然演绎推理24
1.6.2一阶逻辑的归结反演推理25
习题28
第2章数理逻辑程序实践30
实验1命题逻辑联结词30
实验2公式合法性判断33
实验3命题公式真值表生成41
实验4基于真值表的主析取（合取）范式获取48
实验5命题逻辑推理——电路开关表决51实验6命题逻辑推理——谁是作案者52
实验7命题逻辑推理——某件事是谁干的53
实验8命题逻辑推理——王教授是哪里人54
实验9命题逻辑推理——班委会选举55
实验10命题逻辑推理——谁在说谎57
实验11基于一阶逻辑的自然演绎推理57
实验12基于一阶逻辑的归结反演推理64
目录〖3〗第3章集合、二元关系与函数79
3.1集合的基本概念79
3.2并查集81
3.3关系的定义与表示82
3.3.1序偶、笛卡儿积的概念82
3.3.2二元关系的定义82
3.3.3二元关系的表示83
3.4关系的运算84
3.5关系的性质86
3.6关系的闭包87
3.7关系的应用91
3.8相容关系93
3.9等价关系93
3.9.1等价关系的定义93
3.9.2等价关系的应用95
3.10偏序关系95
3.10.1偏序关系的定义95
3.10.2偏序关系的哈斯图96
3.10.3偏序集中的特殊元素96
3.10.4偏序关系图在课程设置中的应用97
3.11格的概念98
3.12特殊的二元关系——函数99
3.12.1函数的概念与分类99
3.12.2函数应用——哈希函数100
3.13计数问题101
3.13.1包含排斥原理102
3.13.2鸽笼原理104
3.13.3排列与组合105
3.13.4二项式定理108
3.13.5母函数及其应用108
习题112
第4章集合、二元关系与函数程序实践115
实验1集合运算115
实验2元素归属合并——并查集算法118
实验3笛卡儿积及关系的复合119
实验4二元关系及其性质123
实验5二元关系的闭包运算124
实验6等价关系判定130
实验7偏序关系上的特异元素132
实验8求函数的定义域和值域134
实验9函数中单射、满射、双射判断137
实验10集合计数——容斥原理140
实验11组合计数142
实验12排列计数143
实验13母函数组合计数145
实验14指母函数排列计数146
第5章代数系统与数论148
5.1代数系统的概念148
5.2代数系统的运算及其性质150
5.3半群与含幺半群155
5.4群与子群157
5.5交换群与循环群160
5.6陪集与拉格朗日定理162
5.7数论基础知识164
5.7.1素数164
5.7.2辗转相除法165
5.7.3同余及同余方程166
5.7.4欧拉函数及欧拉定理168
5.7.5中国剩余定理169
5.8数论与密码学170
习题173
第6章代数系统与数论程序实践175
实验1判断二元运算是否满足结合律175
实验2判断代数系统是否为群176
实验3判断整数能否被给定数整除178
实验4利用埃氏筛选法筛选素数179
实验5求一个数的所有因子及因子数目181
实验6算术基本定理——正整数专享分解定理183
实验7利用辗转相除法求两个数的优选公约数和最小公倍数184
实验8线性同余方程求解185
实验9利用中国剩余定理求解线性同余方程组187
实验10利用中国剩余定理加快RSA加密解密190
第7章图论理论195
7.1图的基本概念195
7.2通路、回路、图的连通性200
7.3点割集、割点、边割集、桥202
7.4图的矩阵表示202
7.4.1关联矩阵202
7.4.2邻接矩阵203
7.4.3可达矩阵204
7.5最短路径和关键路径205
7.5.1迪杰斯特拉算法205
7.5.2弗洛伊德算法207
7.6最小生成树及其求法210
7.6.1最小生成树定义211
7.6.2普里姆算法212
7.6.3克鲁斯卡尔算法213
7.7二叉树及哈夫曼编码215
7.7.1二叉树的定义及性质215
7.7.2哈夫曼树的概念及构造216
7.7.3哈夫曼编码218
7.8欧拉图与哈密顿图219
7.8.1欧拉图219
7.8.2哈密顿图220
7.9着色及其应用222
7.10匹配及其应用225
习题228
第8章图论程序实践231
实验1图的度和可达矩阵计算以及连通性判断231
实验2求图的所有割点236
实验3求图的所有割边237
实验4可图化、可简单图化、连通图和欧拉图的判断239
实验5哈密顿图的判断245
实验6图中两个顶点间通路数计算250
实验7利用迪杰斯特拉算法求最短路径252
实验8利用弗洛伊德算法求最短路径254
实验9图是否为树的判断255
实验10利用普里姆算法构造最小生成树257
实验11利用克鲁斯卡尔算法构造最小生成树260
实验12哈夫曼编码与解码262
实验13图的颜色分配方案判断267
实验14图的点着色269
实验15二部图判断272
实验16二部图的优选匹配274
参考文献278