离散数学概论 第2版

**部分　数理逻辑
第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