离散数学及其应用（第2版） / 高等学校计算机专业系列教材
￥59.00定价
作者： 陈琼，马千里，周育人，陈伟能
出版时间：2024-12-04
出版社：机械工业出版社
- 机械工业出版社
- 9787111764274
- 2-1
- 530244
- 平装
- 2024-12-04
- 416
内容简介
本书根据计算机科学与技术专业对离散数学的教学要求，参考国内外众多优秀的离散数学教材，并结合教学组老师多年的教学实践编写而成。本书对离散数学的核心知识单元进行了系统的理论阐述，对离散数学的分析证明方法进行了严谨的介绍，并通过丰富的应用实例介绍了离散系统建模，旨在帮助读者在掌握理论基础的同时，理解如何利用这些理论知识来分析和解决问题。作为《离散数学及其应用》的第!版，本书将函数的相关内容列为独立章节，进行了更详尽的阐述；图论部分增加了握手定理、独立集、覆盖和支配集，以及网络与网络流、基本割集和基本回路的相关内容。此外，本书根据用书学校的反馈对其他章节进行了更新和完善，使其更符合教学要求。本书每部分均配有大量典型例题和难易程度不同的习题，紧密结合实际应用，使学生能够将对离散数学课程的认识由抽象、枯燥转变为易学、有趣。
目录
第一部分 数理逻辑
第1章 命题逻辑2
1.1 命题与联结词2
1.1.1 命题的概念2
1.1.2 联结词3
1.2 命题公式及其分类8
1.3 命题演算的关系式10
1.3.1 等价关系式10
1.3.2 全功能联结词集13
1.3.3 对偶式14
1.4 范式15
1.4.1 析取范式和合取范式15
1.4.2 主析取范式和主合取范式16
1.5 命题逻辑的推理21
1.5.1 推理理论21
1.5.2 推理证明方法22
习题26
第2章 谓词逻辑30
2.1 谓词逻辑的基本概念30
2.1.1 个体词和谓词30
2.1.2 量词32
2.2 谓词合式公式36
2.3 谓词公式的解释和分类37
2.3.1 谓词公式的解释37
2.3.2 谓词公式的分类38
2.4 谓词演算的关系式39
2.5 前束范式43
2.6 谓词逻辑的推理44
2.6.1 推理理论44
2.6.2 推理问题的证明45
2.7 谓词逻辑的应用48
习题50
第二部分 集合、关系和函数
第3章 集合56
3.1 集合及其表示56
3.2 集合间的关系57
3.3 集合的运算60
3.4 自然数65
3.5 集合的特征函数66
习题67
第4章 关系70
4.1 关系概述70
4.1.1 有序对和有序n元组70
4.1.2 笛卡儿积70
4.1.3 关系的概念72
4.2 关系的表示法74
4.2.1 用集合表示关系74
4.2.2 用关系图表示关系75
4.2.3 用矩阵表示关系76
4.3 关系的运算76
4.3.1 关系的逆运算77
4.3.2 关系的复合运算78
4.4 关系的性质82
4.5 关系的闭包88
4.6 等价关系和等价类94
4.6.1 等价关系94
4.6.2 等价类95
4.7 偏序关系100
习题105
第5章 函数109
5.1 函数的定义109
5.2 特殊函数110
5.3 复合函数111
5.4 反函数113
5.5 集合的基数114
习题118
第三部分 组合数学
第6章 计数122
6.1 基本计数规则122
6.1.1 加法法则122
6.1.2 乘法法则122
6.2 排列与组合124
6.2.1 排列125
6.2.2 组合125
6.2.3 多重集的排列与组合127
6.2.4 二项式定理129
6.3 容斥原理131
6.4 鸽巢原理136
习题137
第7章 高级计数技术139
7.1 递推方程139
7.1.1 求解递推方程141
7.1.2 常系数线性齐次递推方程的
求解141
7.1.3 常系数线性非齐次递推方程
的求解144
7.2 生成函数147
7.2.1 牛顿二项式系数与牛顿
二项式定理147
7.2.2 生成函数的定义及其
性质149
7.2.3 生成函数的应用150
7.2.4 指数型生成函数153
习题155
第四部分 图论
第8章 图158
8.1 图的基本概念158
8.1.1 无向图和有向图159
8.1.2 度的概念160
8.1.3 握手定理160
8.1.4 图的分类162
8.1.5 子图与补图165
8.1.6 图的同构168
8.2 通路与回路、连通的概念169
8.2.1 通路与回路169
8.2.2 连通的概念172
8.3 图的表示175
8.3.1 邻接表175
8.3.2 邻接矩阵176
8.3.3 可达矩阵180
8.3.4 关联矩阵181
8.4 独立集、覆盖和支配集183
习题186
第9章 特殊图189
9.1 欧拉图与哈密顿图189
9.1.1 欧拉图189
9.1.2 哈密顿图192
9.2 带权图196
9.2.1 旅行商问题196
9.2.2 最短路径问题196
9.2.3 中国邮路问题198
9.2.4 关键路径200
9.2.5 网络与网络流202
9.3 匹配和二分图208
9.3.1 匹配208
9.3.2 二分图209
9.3.3 网络流的应用213
9.4 平面图214
9.4.1 平面图的定义214
9.4.2 平面图的欧拉公式216
9.4.3 对偶图与图着色218
习题222
第10章 树227
10.1 树的定义和特性227
10.2 生成树229
10.2.1 生成树的定义229
10.2.2 基本割集和基本回路231
10.2.3 最小生成树及其应用232
10.3 根树233
10.3.1 有向根树和有序根树233
10.3.2 有序根树的遍历236
10.4 根树的应用238
10.4.1 前缀码238
10.4.2 最优二元树和Huffman
编码239
10.4.3 决策树241
习题242
第五部分 代数结构
第11章 代数系统246
11.1 代数系统的概念和性质246
11.1.1 二元运算及其性质246
11.1.2 代数系统和子代数249
11.1.3 代数系统的性质250
11.1.4 代数系统的分类252
11.2 代数系统的同态和同构253
11.3 半群255
11.4 群257
11.4.1 群及其基本性质257
11.4.2 子群260
11.5 循环群和置换群261
11.5.1 循环群261
11.5.2 置换群263
11.6 环和域264
习题266
第12章 格与布尔代数269
12.1 格269
12.1.1 格的基本概念269
12.1.2 分配格272
12.1.3 有界格和有补格274
12.2 布尔代数275
12.2.1 布尔代数的基本概念275
12.2.2 布尔表达式与布尔
函数277
12.2.3 布尔代数和数字电路279
习题280
参考文献283
第1章 命题逻辑2
1.1 命题与联结词2
1.1.1 命题的概念2
1.1.2 联结词3
1.2 命题公式及其分类8
1.3 命题演算的关系式10
1.3.1 等价关系式10
1.3.2 全功能联结词集13
1.3.3 对偶式14
1.4 范式15
1.4.1 析取范式和合取范式15
1.4.2 主析取范式和主合取范式16
1.5 命题逻辑的推理21
1.5.1 推理理论21
1.5.2 推理证明方法22
习题26
第2章 谓词逻辑30
2.1 谓词逻辑的基本概念30
2.1.1 个体词和谓词30
2.1.2 量词32
2.2 谓词合式公式36
2.3 谓词公式的解释和分类37
2.3.1 谓词公式的解释37
2.3.2 谓词公式的分类38
2.4 谓词演算的关系式39
2.5 前束范式43
2.6 谓词逻辑的推理44
2.6.1 推理理论44
2.6.2 推理问题的证明45
2.7 谓词逻辑的应用48
习题50
第二部分 集合、关系和函数
第3章 集合56
3.1 集合及其表示56
3.2 集合间的关系57
3.3 集合的运算60
3.4 自然数65
3.5 集合的特征函数66
习题67
第4章 关系70
4.1 关系概述70
4.1.1 有序对和有序n元组70
4.1.2 笛卡儿积70
4.1.3 关系的概念72
4.2 关系的表示法74
4.2.1 用集合表示关系74
4.2.2 用关系图表示关系75
4.2.3 用矩阵表示关系76
4.3 关系的运算76
4.3.1 关系的逆运算77
4.3.2 关系的复合运算78
4.4 关系的性质82
4.5 关系的闭包88
4.6 等价关系和等价类94
4.6.1 等价关系94
4.6.2 等价类95
4.7 偏序关系100
习题105
第5章 函数109
5.1 函数的定义109
5.2 特殊函数110
5.3 复合函数111
5.4 反函数113
5.5 集合的基数114
习题118
第三部分 组合数学
第6章 计数122
6.1 基本计数规则122
6.1.1 加法法则122
6.1.2 乘法法则122
6.2 排列与组合124
6.2.1 排列125
6.2.2 组合125
6.2.3 多重集的排列与组合127
6.2.4 二项式定理129
6.3 容斥原理131
6.4 鸽巢原理136
习题137
第7章 高级计数技术139
7.1 递推方程139
7.1.1 求解递推方程141
7.1.2 常系数线性齐次递推方程的
求解141
7.1.3 常系数线性非齐次递推方程
的求解144
7.2 生成函数147
7.2.1 牛顿二项式系数与牛顿
二项式定理147
7.2.2 生成函数的定义及其
性质149
7.2.3 生成函数的应用150
7.2.4 指数型生成函数153
习题155
第四部分 图论
第8章 图158
8.1 图的基本概念158
8.1.1 无向图和有向图159
8.1.2 度的概念160
8.1.3 握手定理160
8.1.4 图的分类162
8.1.5 子图与补图165
8.1.6 图的同构168
8.2 通路与回路、连通的概念169
8.2.1 通路与回路169
8.2.2 连通的概念172
8.3 图的表示175
8.3.1 邻接表175
8.3.2 邻接矩阵176
8.3.3 可达矩阵180
8.3.4 关联矩阵181
8.4 独立集、覆盖和支配集183
习题186
第9章 特殊图189
9.1 欧拉图与哈密顿图189
9.1.1 欧拉图189
9.1.2 哈密顿图192
9.2 带权图196
9.2.1 旅行商问题196
9.2.2 最短路径问题196
9.2.3 中国邮路问题198
9.2.4 关键路径200
9.2.5 网络与网络流202
9.3 匹配和二分图208
9.3.1 匹配208
9.3.2 二分图209
9.3.3 网络流的应用213
9.4 平面图214
9.4.1 平面图的定义214
9.4.2 平面图的欧拉公式216
9.4.3 对偶图与图着色218
习题222
第10章 树227
10.1 树的定义和特性227
10.2 生成树229
10.2.1 生成树的定义229
10.2.2 基本割集和基本回路231
10.2.3 最小生成树及其应用232
10.3 根树233
10.3.1 有向根树和有序根树233
10.3.2 有序根树的遍历236
10.4 根树的应用238
10.4.1 前缀码238
10.4.2 最优二元树和Huffman
编码239
10.4.3 决策树241
习题242
第五部分 代数结构
第11章 代数系统246
11.1 代数系统的概念和性质246
11.1.1 二元运算及其性质246
11.1.2 代数系统和子代数249
11.1.3 代数系统的性质250
11.1.4 代数系统的分类252
11.2 代数系统的同态和同构253
11.3 半群255
11.4 群257
11.4.1 群及其基本性质257
11.4.2 子群260
11.5 循环群和置换群261
11.5.1 循环群261
11.5.2 置换群263
11.6 环和域264
习题266
第12章 格与布尔代数269
12.1 格269
12.1.1 格的基本概念269
12.1.2 分配格272
12.1.3 有界格和有补格274
12.2 布尔代数275
12.2.1 布尔代数的基本概念275
12.2.2 布尔表达式与布尔
函数277
12.2.3 布尔代数和数字电路279
习题280
参考文献283
