离散数学教程（第4版）
定价：￥59.00
作者： 张婷
出版时间：2026-01
出版社：电子工业出版社
- 电子工业出版社
- 9787121519475
- 1-1
- 16开
- 2026-01
- 416
- 工学
- 计算机类
- 计算机科学与技术
- 本科 研究生及以上
内容简介
“离散数学”是计算机和信息类专业重要的核心学科基础课程之一。本书内容主要包括集合论（集合、二元关系与函数）、组合计数初步、图论、数理逻辑（命题逻辑、谓词逻辑）、代数系统简介等5部分。在涵盖离散数学各方面内容的同时，本书有层次地精选了丰富的例题和多种解题思路与方法，各章配有适量的习题，帮助读者巩固和掌握所学知识，提高解题能力及技巧。本书结构清晰，概念准确，叙述严谨，力图做到“宜教易学”。本版新增了微课，扫描书中二维码即可观看；本书提供电子课件和习题答案，登录华信教育资源网可免费下载。
目录
目 录
第1章 集合 1
1.1 集合的基本概念 1
1.1.1 集合的表示方法 1
1.1.2 子集 2
1.1.3 全集和补集 3
1.1.4 幂集 3
1.2 集合的基本运算 4
1.2.1 并和交 4
1.2.2 差和对称差 7
习题1 9
第2章 二元关系与函数 12
2.1 二元关系的基本概念 12
2.1.1 引言 12
2.1.2 笛卡儿乘积和二元关系的定义 12
2.1.3 二元关系的三种表示方法 13
2.1.4 二元关系的基本类型 16
2.2 等价关系和偏序关系 19
2.2.1 等价关系与划分 19
2.2.2 偏序关系 25
2.3 关系的特殊运算 28
2.3.1 复合关系 28
2.3.2 逆关系 32
2.3.3 闭包运算 33
2.4 函数 36
2.4.1 函数的基本概念 36
2.4.2 特殊函数 38
2.4.3 复合函数和逆函数 40
习题2 43
第3章 组合数学初步 47
3.1 计数的基本原则与鸽巢原理 47
3.1.1 乘积法则与求和法则 47
3.1.2 减法法则（容斥原理） 48
3.1.3 除法法则 49
3.1.4 树形图 50
3.1.5 鸽巢原理 50
3.1.6 鸽巢原理的应用 52
3.2 排列与组合及其推广 53
3.2.1 基本计数原理 53
3.2.2 排列：顺序重要、不放回 54
3.2.3 组合：顺序不重要、不放回 54
3.2.4 允许重复的排列（有放回） 55
3.2.5 多重集的排列（元素不可区分） 55
3.2.6 允许重复的组合（多重集的组合） 56
3.2.7 分配模型与等价转换 57
3.3 二项式与经典恒等式 57
3.3.1 二项式定理 58
3.3.2 组合恒等式的推导 59
3.3.3 帕斯卡恒等式 60
3.3.4 范德蒙德卷积 61
3.3.5 上指标求和与其他恒等式 62
3.3.6 应用举例 62
3.4 生成排列与组合 63
3.4.1 生成排列 63
3.4.2 生成组合 65
3.5 递推模型与分治思想 67
3.5.1 递推关系及应用 67
3.5.2 动态规划与递推关系 68
3.5.3 分治算法与递推关系 69
3.5.4 分治递推关系估计算法复杂度 71
3.6 线性递推关系的求解 73
3.6.1 线性齐次递推关系求解 73
3.6.2 常系数线性齐次递推关系求解 73
3.6.3 常系数线性非齐次递推关系求解 75
3.7 生成函数 76
3.7.1 生成函数的定义和定理 76
3.7.2 生成函数的应用 77
习题3 78
第4章 图论 81
4.1 图的基本概念 81
4.1.1 几个问题 81
4.1.2 图的基本术语 82
4.1.3 图的矩阵表示 85
4.1.4 子图与图的同构 87
4.1.5 完全图与补图 89
4.2 通路与赋权图的最短通路 91
4.2.1 通路与回路 91
4.2.2 图的连通性 92
4.2.3 赋权图的最短通路 96
4.3 树 102
4.3.1 无向树 102
4.3.2 有向树 106
4.3.3 前缀码与最优树 108
4.4 欧拉图和哈密顿图 114
4.4.1 欧拉图 114
4.4.2 哈密顿图 118
4.5 二部图和平面图 122
4.5.1 二部图 123
4.5.2 平面图 127
习题4 135
第5章 命题逻辑 140
5.1 命题逻辑的基本概念 140
5.1.1 命题 140
5.1.2 命题联结词 141
5.1.3 命题公式 143
5.1.4 命题公式的真值表 145
5.1.5 永真式、永假式和可满足式 145
5.2 逻辑等价 147
5.2.1 逻辑等价 147
5.2.2 代换规则 148
5.2.3 对偶原理 150
5.2.4 联结词的完备集 150
5.2.5 奎因法 151
5.3 范式和主范式 152
5.3.1 析取范式和合取范式 152
5.3.2 主析取范式和主合取范式 153
5.4 逻辑蕴涵 160
5.4.1 逻辑蕴涵的定义 160
5.4.2 逻辑蕴涵的性质 161
5.5 推理理论 164
5.5.1 前提和有效结论 164
5.5.2 直接证明法 165
5.5.3 间接证明法 166
习题5 170
第6章 谓词逻辑 174
6.1 谓词逻辑的基本概念 174
6.1.1 个体词、谓词和命题函数 174
6.1.2 量词 176
6.1.3 谓词公式 181
6.1.4 约束变元和自由变元 182
6.1.5 解释 184
6.2 逻辑等价与逻辑蕴含 186
6.2.1 永真式、永假式和可满足式 186
6.2.2 逻辑等价式和逻辑蕴含式 186
6.2.3 前束范式 191
6.3 谓词演算的推理理论 192
习题6 196
第7章 代数系统简介 198
7.1 代数系统的基本概念 198
7.1.1 代数系统的定义 198
7.1.2 特殊运算与特殊元素 201
7.1.3 同构 206
7.2 半群和独异点 207
7.2.1 半群和子半群 207
7.2.2 独异点和子独异点 211
7.3 群 212
7.3.1 群的定义和性质 212
7.3.2 子群 218
7.3.3 循环群 223
7.3.4 陪集和拉格朗日定理 225
7.3.5 群码 229
7.4 环和域 232
7.4.1 环 232
7.4.2 域 235
7.5 格 237
7.5.1 格的定义 237
7.5.2 格和偏序集 239
7.5.3 特殊格 241
习题7 246
参考文献 251
第1章 集合 1
1.1 集合的基本概念 1
1.1.1 集合的表示方法 1
1.1.2 子集 2
1.1.3 全集和补集 3
1.1.4 幂集 3
1.2 集合的基本运算 4
1.2.1 并和交 4
1.2.2 差和对称差 7
习题1 9
第2章 二元关系与函数 12
2.1 二元关系的基本概念 12
2.1.1 引言 12
2.1.2 笛卡儿乘积和二元关系的定义 12
2.1.3 二元关系的三种表示方法 13
2.1.4 二元关系的基本类型 16
2.2 等价关系和偏序关系 19
2.2.1 等价关系与划分 19
2.2.2 偏序关系 25
2.3 关系的特殊运算 28
2.3.1 复合关系 28
2.3.2 逆关系 32
2.3.3 闭包运算 33
2.4 函数 36
2.4.1 函数的基本概念 36
2.4.2 特殊函数 38
2.4.3 复合函数和逆函数 40
习题2 43
第3章 组合数学初步 47
3.1 计数的基本原则与鸽巢原理 47
3.1.1 乘积法则与求和法则 47
3.1.2 减法法则（容斥原理） 48
3.1.3 除法法则 49
3.1.4 树形图 50
3.1.5 鸽巢原理 50
3.1.6 鸽巢原理的应用 52
3.2 排列与组合及其推广 53
3.2.1 基本计数原理 53
3.2.2 排列：顺序重要、不放回 54
3.2.3 组合：顺序不重要、不放回 54
3.2.4 允许重复的排列（有放回） 55
3.2.5 多重集的排列（元素不可区分） 55
3.2.6 允许重复的组合（多重集的组合） 56
3.2.7 分配模型与等价转换 57
3.3 二项式与经典恒等式 57
3.3.1 二项式定理 58
3.3.2 组合恒等式的推导 59
3.3.3 帕斯卡恒等式 60
3.3.4 范德蒙德卷积 61
3.3.5 上指标求和与其他恒等式 62
3.3.6 应用举例 62
3.4 生成排列与组合 63
3.4.1 生成排列 63
3.4.2 生成组合 65
3.5 递推模型与分治思想 67
3.5.1 递推关系及应用 67
3.5.2 动态规划与递推关系 68
3.5.3 分治算法与递推关系 69
3.5.4 分治递推关系估计算法复杂度 71
3.6 线性递推关系的求解 73
3.6.1 线性齐次递推关系求解 73
3.6.2 常系数线性齐次递推关系求解 73
3.6.3 常系数线性非齐次递推关系求解 75
3.7 生成函数 76
3.7.1 生成函数的定义和定理 76
3.7.2 生成函数的应用 77
习题3 78
第4章 图论 81
4.1 图的基本概念 81
4.1.1 几个问题 81
4.1.2 图的基本术语 82
4.1.3 图的矩阵表示 85
4.1.4 子图与图的同构 87
4.1.5 完全图与补图 89
4.2 通路与赋权图的最短通路 91
4.2.1 通路与回路 91
4.2.2 图的连通性 92
4.2.3 赋权图的最短通路 96
4.3 树 102
4.3.1 无向树 102
4.3.2 有向树 106
4.3.3 前缀码与最优树 108
4.4 欧拉图和哈密顿图 114
4.4.1 欧拉图 114
4.4.2 哈密顿图 118
4.5 二部图和平面图 122
4.5.1 二部图 123
4.5.2 平面图 127
习题4 135
第5章 命题逻辑 140
5.1 命题逻辑的基本概念 140
5.1.1 命题 140
5.1.2 命题联结词 141
5.1.3 命题公式 143
5.1.4 命题公式的真值表 145
5.1.5 永真式、永假式和可满足式 145
5.2 逻辑等价 147
5.2.1 逻辑等价 147
5.2.2 代换规则 148
5.2.3 对偶原理 150
5.2.4 联结词的完备集 150
5.2.5 奎因法 151
5.3 范式和主范式 152
5.3.1 析取范式和合取范式 152
5.3.2 主析取范式和主合取范式 153
5.4 逻辑蕴涵 160
5.4.1 逻辑蕴涵的定义 160
5.4.2 逻辑蕴涵的性质 161
5.5 推理理论 164
5.5.1 前提和有效结论 164
5.5.2 直接证明法 165
5.5.3 间接证明法 166
习题5 170
第6章 谓词逻辑 174
6.1 谓词逻辑的基本概念 174
6.1.1 个体词、谓词和命题函数 174
6.1.2 量词 176
6.1.3 谓词公式 181
6.1.4 约束变元和自由变元 182
6.1.5 解释 184
6.2 逻辑等价与逻辑蕴含 186
6.2.1 永真式、永假式和可满足式 186
6.2.2 逻辑等价式和逻辑蕴含式 186
6.2.3 前束范式 191
6.3 谓词演算的推理理论 192
习题6 196
第7章 代数系统简介 198
7.1 代数系统的基本概念 198
7.1.1 代数系统的定义 198
7.1.2 特殊运算与特殊元素 201
7.1.3 同构 206
7.2 半群和独异点 207
7.2.1 半群和子半群 207
7.2.2 独异点和子独异点 211
7.3 群 212
7.3.1 群的定义和性质 212
7.3.2 子群 218
7.3.3 循环群 223
7.3.4 陪集和拉格朗日定理 225
7.3.5 群码 229
7.4 环和域 232
7.4.1 环 232
7.4.2 域 235
7.5 格 237
7.5.1 格的定义 237
7.5.2 格和偏序集 239
7.5.3 特殊格 241
习题7 246
参考文献 251
