离散数学概论

本书通过对目前主流离散数学教材的分析研究，并结合计算机专业的后续学习需求，由浅入深地介绍了数理逻辑、集合论、图论和代数系统四个部分，每一部分均配有大量难易程度不同的例题，且重、难点知识点均配有视频讲解。本书内容翔实，深入浅出，是一本适宜学生预习和复习，且可读性强的教材。

本书分为四部分，共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习题43
第二部分集合论
第3章集合和矩阵49
3.1集合49
3.1.1集合概念49
3.1.2集合间关系50
3.1.3集合运算52
3.1.4集合证明54
3.1.5集合的计算机表示方法57
3.2矩阵58
3.2.1矩阵概念58
3.2.2矩阵基本运算59
3.2.3布尔矩阵运算61
3.3习题62
第4章关系和函数65
4.1关系65
4.1.1关系概念65
4.1.2关系表示方法69
4.1.3关系运算71
4.1.4关系性质76
4.1.5关系闭包81
4.1.6等价关系83
4.1.7偏序关系87
4.2函数91
4.2.1函数定义91
4.2.2函数性质93
4.2.3函数运算94
4.3习题96
第三部分图论
第5章图的基本概念和矩阵表示100
5.1图的基本概念100
5.2顶点的度数与度序列102
5.3握手定理103
5.4接近图104
5.5图的同构与子图105
5.6图的操作107
5.7通路回路109
5.8连通性110
5.8.1无向图的连通性110
5.8.2有向图的连通性112
5.9矩阵表示113
5.9.1邻接矩阵113
5.9.2可达矩阵115
5.9.3关联矩阵116
5.9.4连通性与矩阵关系117
5.10路径117
5.10.1最短路径117
5.10.2Dijkstra算法118
5.10.3Bellman-Ford算法120
5.10.4SPFA算法122
5.10.5Floyd算法124
5.10.6拓扑排序和关键路径127
5.11图的着色问题131
5.11.1对偶图131
5.11.2地图着色与四色猜想132
5.11.3平面图着色与五色定理133
5.11.4平面图点着色134
5.12匹配136
5.12.1匹配与优选匹配136
5.12.2霍尔定理138
5.13习题139
第6章特殊的图142
6.1欧拉图142
6.1.1基本概念142
6.1.2判定143
6.2哈密顿图144
6.3二部图148
6.4平面图149
6.4.1基本概念149
6.4.2欧拉公式150
6.4.3平面图判定151
6.5习题154
第7章树156
7.1概念介绍156
7.2生成树与最小生成树157
7.2.1Kruskal算法159
7.2.2管梅谷算法160
7.2.3逐步短接法161
7.3根树162
7.3.1根树概念162
7.3.2二叉树遍历164
7.3.3很优二叉树和哈夫曼编码166
7.3.4一般树遍历167
7.4习题169
第四部分代数系统
第8章代数系统基础171
8.1代数系统概念171
8.2半群与独异点179
8.3群的基本定义与性质181
8.4子群与陪集186
8.5循环群和置换群192
8.6环和域197
8.7习题200
第9章格与布尔代数203
9.1格203
9.2布尔代数210
9.3习题212
参考文献214