离散数学(第2版) 黄亚群,蒋慕蓉,赵春娜 编 大中专 文轩网

第一篇数理逻辑
第1章命题逻辑1
1.1命题及命题联结词1
1.1.1命题的基本概念2
1.1.2命题联结词4
1.1.3命题符号化8
1.2命题公式及其类型9
1.2.1命题公式的概念9
1.2.2真值表10
1.2.3命题公式的类型11
1.3等价式与蕴涵式11
1.3.1命题公式的等价11
1.3.2蕴涵式15
1.3.3对偶式16
1.4命题公式标准型——范式17
1.4.1范式17
1.4.2主范式18
1.5推理与证明23
1.5.1有效推理的概念与形式24
1.5.2推理的构造证明法24
1.6命题逻辑的应用27
1.6.1逻辑代数27
1.6.2程序设计29
1.6.3判断推理30
1.7典型例题分析31
小结36
上机练习37
习题138
第2章谓词逻辑42
2.1谓词逻辑基本概念42
2.1.1个体和谓词42
2.1.2量词43
2.2谓词公式及命题符号化45
2.2.1谓词公式45
2.2.2量词的辖域与变元的约束45
2.2.3量词的消去规则46
2.2.4谓词公式命题符号化47
2.3谓词演算的等价式和蕴涵式48
2.3.1谓词公式的解释48
2.3.2谓词公式的类型49
2.3.3谓词公式的等价及蕴涵49
2.4谓词公式的范式52
2.4.1前束范式52
2.4.2前束合取、析取范式53
2.5谓词逻辑的推理理论53
2.5.1量词消去与引入规则53
2.5.2推理方法54
2.6典型例题分析57
小结61
习题262
第二篇集合论
第3章集合论基础65
3.1集合的基本概念65
3.1.1集合及元素65
3.1.2集合的表示66
3.1.3集合间的关系67
3.1.4特殊集合67
3.2集合的运算68
3.2.1交运算68
3.2.2并运算69
3.2.3差运算69
3.2.4对称差运算69
3.2.5集合运算的性质69
3.3集合的划分与覆盖71
3.4包含排斥原理72
3.5数学归纳法73
3.6集合的应用75
3.6.1集合的计算机表示75
3.6.2数学形态学75
3.7典型例题分析78
小结82
上机练习82
习题383
第4章二元关系86
4.1关系的概念86
4.1.1序偶及n元有序组86
4.1.2笛卡儿积87
4.1.3二元关系的基本概念87
4.1.4二元关系的表示88
4.2关系的性质90
4.2.1关系性质的概念90
4.2.2关系性质的判断91
4.3关系的运算92
4.3.1关系的集合运算92
4.3.2逆关系93
4.3.3复合关系93
4.3.4关系的幂95
4.3.5关系运算的性质96
4.3.6关系运算与关系性质96
4.3.7关系的和扩充97
4.4关系的闭包运算97
4.4.1闭包的定义97
4.4.2闭包的计算98
4.4.3闭包的性质101
4.4.4多重闭包102
4.5等价关系和等价类102
4.5.1等价关系的定义102
4.5.2等价类103
4.5.3等价关系与划分104
4.6相容关系和相容类106
4.6.1相容关系的定义106
4.6.2相容类107
4.6.3相容关系与覆盖107
4.7序关系和哈塞图108
4.7.1偏序关系的定义108
4.7.2偏序关系的哈塞图109
4.7.3偏序集中的特殊元素110
4.7.4链和全序关系111
4.8关系的应用——逾渗现象研究111
4.8.1问题描述111
4.8.2数学模型113
4.8.3等价类的求解方法113
4.9典型例题分析115
小结120
上机练习121
习题4121
第5章函数126
5.1函数的概念126
5.1.1函数的定义126
5.1.2函数的性质128
5.2函数的运算128
5.2.1逆函数129
5.2.2复合函数129
5.3集合的基数130
5.3.1等势130
5.3.2有限集与无限集131
5.3.3可数集与不可数集132
5.3.4基数的比较133
5.4特征函数134
5.5典型例题分析135
小结138
上机练习138
习题5138
第三篇图论
第6章图论基础141
6.1图的基本概念142
6.1.1图的定义142
6.1.2节点的度数143
6.1.3正则图和接近图144
6.1.4子图和补图145
6.1.5图的同构146
6.2路和图的连通性146
6.2.1通路和回路146
6.2.2无向图的连通性148
6.2.3有向图的连通性151
6.3图的矩阵表示152
6.3.1邻接矩阵153
6.3.2可达性矩阵155
6.3.3接近关联矩阵156
6.3.4图的连通性判断157
6.4欧拉图和哈密顿图158
6.4.1欧拉图158
6.4.2哈密顿图160
6.5平面图与图着色162
6.5.1平面图162
6.5.2平面图的对偶图166
6.5.3平面图的着色166
6.6二部图与匹配168
6.6.1二部图基本概念168
6.6.2匹配168
6.7树与生成树169
6.7.1树的基本概念169
6.7.2生成树171
6.7.3最小生成树172
6.8根树及其应用174
6.8.1根树的基本概念174
6.8.2二叉树176
6.8.3很优二叉树177
6.8.4根树的遍历177
6.9网络优化问题178
6.9.1最短路径问题179
6.9.2优选流问题182
6.9.3最小费用流及其求法186
6.10图论的应用188
6.10.1公交站点可达性查询188
6.10.2计算机鼓轮的设计——布鲁英序列193
6.10.3资源分配图194
6.10.4前缀码195
6.11典型例题分析197
小结202
上机练习203
习题6203
第四篇代数系统
第7章代数结构210
7.1代数系统的基本概念210
7.1.1n元运算及代数系统210
7.1.2二元运算的性质212
7.1.3代数系统的特异元213
7.2半群与独异点215
7.2.1半群215
7.2.2独异点217
7.3群与子群218
7.3.1群的定义218
7.3.2群的性质220
7.3.3子群221
7.3.4群中的幂运算223
7.4阿贝尔群与循环群223
7.4.1阿贝尔群223
7.4.2循环群224
7.5陪集与拉格朗日定理226
7.5.1陪集及其基本性质226
7.5.2拉格朗日定理227
7.5.3正规子群229
7.6同态与同构229
7.6.1同态与同构的定义230
7.6.2同态和同构的性质232
7.6.3同余关系233
7.7环与域234
7.7.1环及其性质235
7.7.2域及其性质237
7.8代数系统的应用——纠错码237
7.8.1纠错码的纠错能力238
7.8.2纠错码的选择239
7.8.3群码的校正241
7.9典型例题分析242
小结247
上机练习248
习题7248
第8章格与布尔代数251
8.1格251
8.1.1格和子格251
8.1.2格的对偶原理和性质252
8.1.3格的代数系统定义253
8.1.4格的同态和同构254
8.2特殊格255
8.2.1分配格255
8.2.2有界格256
8.2.3有补格256
8.3布尔代数257
8.3.1布尔代数的定义及性质257
8.3.2布尔代数的同构258
8.4布尔表达式259
8.4.1布尔表达式的基本概念259
8.4.2布尔表达式的范式260
8.5布尔表达式在数字逻辑设计中的应用263
8.6典型例题分析264
小结266
习题8267
第五篇组合与计数
第9章组合计数270
9.1基本计数法则270
9.1.1枚举270
9.1.2计数原理271
9.2排列与组合271
9.2.1线排列、圆排列、单组合271
9.2.2重排列、重组合273
9.2.3排列组合生成算法274
9.3鸽巢原理275
9.4递推关系276
9.4.1递推关系的概念276
9.4.2递推关系的求解277
9.5典型例题分析281
小结285
上机练习285
习题9286
参考文献288