离散数学概论 第2版

本书是一本通俗易懂的离散数学课程教材。由浅入深地介绍了数理逻辑、集合论、图论和代数系统四个部分，每一部分均配有大量难易程度不同的例题，且重、难点知识点均配有视频讲解。 本书内容翔实，深入浅出，是一本适宜学生预习和复习，且可读性强的教材。 本书注重先进性和实用性，同时概念清楚，系统性强，力求保持离散数学知识的完整性，有利于不同层次的读者从不同起点逐步理解和掌握离散数学知识。 课时安排：本书数理逻辑部分适宜12～16个课时，集合论部分适宜16～22个课时，图论部分适宜10～12个课时，代数系统部分适宜6～8个课时。

本书分为四部分，共9章。第一部分为数理逻辑，主要包括命题逻辑、一阶逻辑及数理逻辑中的推理证明等内容。第二部分为集合论，主要包括集合、矩阵、关系和函数等内容。第三部分为图论，主要包括图的基本概念和矩阵表示、特殊的图和树等内容。第四部分为代数系统，主要包括代数系统基础、格与布尔代数等内容。
本书内容丰富，层次分明，重点突出，并注重离散数学的实用性，可以为计算机专业学生提供重要的数学基础。本书可作为计算机专业本科生、大专生等的理论教学教材。

前言
第一部分 数理逻辑
第1章 命题逻辑2
1.1 命题及符号化2
1.1.1 命题2
1.1.2 联结词3
1.1.3 真值表5
1.1.4 复合命题符号化6
1.1.5 命题公式分类7
1.2 命题等值演算9
1.2.1 等值式9
1.2.2 等值演算9
1.3 范式12
1.3.1 析取范式和合取范式12
1.3.2 主析取范式和主合取范式14
1.4 逻辑电路20
1.5 习题22
第2章 一阶逻辑26
2.1 一阶逻辑基本概念26
2.1.1 个体词、谓词26
2.1.2 量词27
2.1.3 嵌套量词29
2.2 一阶逻辑公式分类及解释30
2.2.1 谓词公式解释30
2.2.2 谓词公式分类32
2.3 一阶逻辑等值式和前束范式33
2.3.1 一阶逻辑等值式33
2.3.2 前束范式35
2.4 逻辑推理36
2.4.1 命题逻辑推理37
2.4.2 一阶逻辑推理41
2.5 习题44
第二部分 集合论
第3章 集合和矩阵50
3.1 集合50
3.1.1 集合概念50
3.1.2 集合间关系51
3.1.3 集合运算53
3.1.4 集合证明55
3.1.5 集合的计算机表示方法58
3.2 矩阵59
3.2.1 矩阵概念59
3.2.2 矩阵基本运算60
3.2.3 布尔矩阵运算62
3.3 习题63
第4章 关系和函数66
4.1 关系66
4.1.1 关系概念66
4.1.2 关系表示方法70
4.1.3 关系运算72
4.1.4 关系性质77
4.1.5 关系闭包82
4.1.6 等价关系84
4.1.7 偏序关系88
4.2 函数92
4.2.1 函数定义92
4.2.2 函数性质94
4.2.3 函数运算95
4.3 习题97
第三部分 图论
第5章 图的基本概念和矩阵表示102
5.1 图的基本概念102
5.2 顶点的度数与度序列104
5.3 握手定理105
5.4 完全图106
5.5 图的同构与子图107
5.6 图的操作109
5.7 通路回路111
5.8 连通性112
5.8.1 无向图的连通性112
5.8.2 有向图的连通性114
5.9 矩阵表示115
5.9.1 邻接矩阵115
5.9.2 可达矩阵118
5.9.3 关联矩阵119
5.9.4 连通性与矩阵关系120
5.10 路径120
5.10.1 最短路径120
5.10.2 Dijkstra算法121
5.10.3 Bellman-Ford算法123
5.10.4 SPFA算法125
5.10.5 Floyd算法127
5.10.6 拓扑排序和关键路径130
5.11 习题134
第6章 特殊的图136
6.1 欧拉图136
6.1.1 基本概念136
6.1.2 判定137
6.2 哈密顿图138
6.3 二部图142
6.4 平面图146
6.4.1 基本概念146
6.4.2 欧拉公式147
6.4.3 平面图判定148
6.5 图的着色问题151
6.5.1 对偶图151
6.5.2 地图着色与四色猜想152
6.5.3 平面图着色与五色定理153
6.5.4 平面图点着色154
6.6 习题156
第7章 树159
7.1 概念介绍159
7.2 生成树与最小生成树160
7.2.1 Kruskal算法162
7.2.2 管梅谷算法163
7.2.3 逐步短接法164
7.3 根树165
7.3.1 根树概念165
7.3.2 二叉树遍历167
7.3.3 最优二叉树和哈夫曼编码169
7.3.4 一般树遍历170
7.4 习题172
第四部分 代数系统
第8章 代数系统基础174
8.1 代数系统概念174
8.2 半群与独异点182
8.3 群的基本定义与性质184
8.4 子群与陪集189
8.5 循环群和置换群195
8.6 环和域200
8.7 习题203
第9章 格与布尔代数206
9.1 格206
9.2 布尔代数213
9.3 习题215
参考文献217