包邮普通高等教育计算机类重量特色专业系列教材离散数学(第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
习题1 38
第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
习题2 62
第二篇 集合论
第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
习题3 83
第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
习题4 121
第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
习题5 138
第三篇 图论
第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
习题6 203
第四篇 代数系统
第7章 代数结构 210
7.1 代数系统的基本概念 210
7.1.1 n元运算及代数系统 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
习题7 248
第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
习题8 267
第五篇 组合与计数
第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
习题9 286
参考文献 288