离散数学（第三版） / 普通高等院校计算机类专业规划教材·精品系列
￥58.00定价
作者： 刘任任，王婷，曹春红
出版时间：2023-12
出版社：中国铁道出版社
“十二五”普通高等教育本科国家级规划教材
- 中国铁道出版社
- 9787113306328
- 3版
- 521453
- 48256940-7
- 16开
- 2023-12
- 计算机及相关专业
- 本科 高职
作者简介
内容简介
本书是编者根据多年讲授“离散数学”课程的教学实践，为适应计算机科学与技术发展的需要，并参考国内外同类教材而编写，目的在于通过讲授离散数学中的基本概念、基本定理和运算及其在计算机科学与技术学科中的应用，培养学生的数学抽象能力、用数学语言描述问题的能力、逻辑思维能力以及数学论证能力。 本书力求概念阐述严谨，证明推演详尽，较难理解的概念用实例说明。 全书分四篇共 24 章，主要包括集合论与数理逻辑、图论与组合数学、代数结构与初等数论、线性规划与博弈论等内容。
本书适合作为普通高等院校计算机类专业的教材，也可供从事离散结构领域研究工作的人员参考。
本书适合作为普通高等院校计算机类专业的教材，也可供从事离散结构领域研究工作的人员参考。
目录
第 1 篇 集合论与数理逻辑
第 1 章 集合 2
§ 1. 1 集合的概念及其表示 2
§ 1. 2 集合的基本运算 4
§ 1. 3 笛卡尔积 5
习 题 6
第 2 章 关系 8
§ 2. 1 关系及其表示 8
§ 2. 2 关系的运算 9
§ 2. 3 等价关系 12
§ 2. 4 序关系 14
习 题 16
第 3 章 映射 19
§ 3. 1 基本概念 19
§ 3. 2 映射的运算 20
习 题 21
第 4 章 可数集与不可数集 22
§ 4. 1 等势 22
§ 4. 2 集合的基数 23
§ 4. 3 可数集与不可数集简介 24
习 题 26
第 5 章 命题逻辑 27
§ 5. 1 命题与逻辑联结词 27
§ 5. 2 命题公式与等值演算 30
§ 5. 3 对偶与范式 33
§ 5. 4 推理理论 38
§ 5. 5 命题演算的公理系统 43
习 题 46
第 6 章 一阶逻辑 49Ⅰ
§ 6. 1 谓词与量词 49
§ 6. 2 合式公式及解释 52
§ 6. 3 等值式与范式 54
§ 6. 4 一阶逻辑的推理理论 58
习 题 62
第 2 篇 图论与组合数学
第 7 章 图与子图 66
§ 7. 1 图的概念 66
§ 7. 2 图的同构 68
§ 7. 3 顶点的度 69
§ 7. 4 子图及图的运算 69
§ 7. 5 通路与连通图 71
§ 7. 6 图的矩阵表示 73
§ 7. 7 应用(最短通路问题) 74
习 题 77
第 8 章 树 80
§ 8. 1 树的定义 80
§ 8. 2 生成树 82
§ 8. 3 应用(最优树问题) 84
习 题 85
第 9 章 图的连通性 86
§ 9. 1 点连通度和边连通度 88
？§ 9. 2 块 88
§ 9. 3 应用(构造可靠的通信网络) 90
习 题 91
第 10 章 E 图与 H 图 93
§ 10. 1 七桥问题与 E 图 93
§ 10. 2 周游世界问题与 H 图 94
§ 10. 3 应用(旅行推销员问题) 98
习 题 99
第 11 章 匹配与点独立集 101
§ 11. 1 匹配 101
§ 11. 2 独立集和覆盖 105
§ 11. 3 Ramsey 数 107
§ 11. 4 应用(人员分配问题) 110
习 题 111
第 12 章 图的着色 113
§ 12. 1 顶点着色 113
§ 12. 2 边着色 115
§ 12. 3 色多项式 118
§ 12. 4 应用 121
习 题 122
第 13 章 平面图 123
§ 13. 1 平面图的概念 123
§ 13. 2 欧拉公式 125
§ 13. 3 可平面性判定 127
§ 13. 4 平面图的面着色 128
§ 13. 5 应用(印制电路板的设计) 130
习 题 130
第 14 章 有向图 132
§ 14. 1 有向图的概念 132
§ 14. 2 有向通路与有向回路 134
§ 14. 3 有向树简介 136
§ 14. 4 应用 137
习 题 139
第 15 章 网络最大流 140
§ 15. 1 网络的流与割 140
§ 15. 2 最大流最小割定理 142
§ 15. 3 应用(中国邮递员问题) 146
习 题 146
第 16 章 排列和组合的一般计数方法 148
§ 16. 1 两个基本的计数法则 148
§ 16. 2 基本排列组合的计数方法 149
§ 16. 3 可重复排列组合的计数方法 150
习 题 152
第 17 章 容斥原理 154
§ 17. 1 容斥原理概述 154
§ 17. 2 有禁止位的排列 156
习 题 158
第 18 章 递推关系与生成函数 159
§ 18. 1 递推关系及其解法 159
§ 18. 2 生成函数 161
习 题 163
第 3 篇 代数结构与初等数论
第 19 章 整数 166
§ 19. 1 整除性 166
§ 19. 2 素因数分解 170
§ 19. 3 同余 172
§ 19. 4 孙子定理与 Euler 函数 174
§ 19. 5 数论在计算机密码学中的应用 178
习 题 180
第 20 章 群 182
§ 20. 1 群的概念 182
§ 20. 2 子群 185
？§ 20. 3 置换群 189
§ 20. 4 陪集与 Lagrange 定理 194
§ 20. 5 同态与同构 196
§ 20. 6 群在计算机科学与技术中的应用 200
习 题 203
第 21 章 环与域 205
§ 21. 1 环与子环 205
§ 21. 2 环同态 208
§ 21. 3 域的特征和素域 212
？§ 21. 4 有限域 214
§ 21. 5 有限域的结构 218
§ 21. 6 纠错码 223
§ 21. 7 多项式编码方法及其实现 231
习 题 234
第 22 章 格与布尔代数 237
§ 22. 1 格的定义 237
§ 22. 2 格的性质 239
§ 22. 3 几种特殊的格 242
§ 22. 4 布尔代数 246
§ 22. 5 有限布尔代数的结构 252
§ 22. 6 格与布尔代数在计算机科学与技术中的应用 256
习 题 260
第 4 篇 线性规划与博弈论
第 23 章 线性规划 264
§ 23. 1 线性规划问题及其数学模型 264
§ 23. 2 图解法 267
§ 23. 3 单纯形法原理 269
§ 23. 4 单纯形法计算步骤 274
§ 23. 5 线性规划的对偶问题 278
习 题 279
第 24 章 博弈论 281
§ 24. 1 博弈问题 281
§ 24. 2 矩阵博弈的基本理论 283
§ 24. 3 矩阵博弈的解法 289
§ 24. 4 矩阵博弈均衡 293
习 题 296
参考文献 297
第 1 章 集合 2
§ 1. 1 集合的概念及其表示 2
§ 1. 2 集合的基本运算 4
§ 1. 3 笛卡尔积 5
习 题 6
第 2 章 关系 8
§ 2. 1 关系及其表示 8
§ 2. 2 关系的运算 9
§ 2. 3 等价关系 12
§ 2. 4 序关系 14
习 题 16
第 3 章 映射 19
§ 3. 1 基本概念 19
§ 3. 2 映射的运算 20
习 题 21
第 4 章 可数集与不可数集 22
§ 4. 1 等势 22
§ 4. 2 集合的基数 23
§ 4. 3 可数集与不可数集简介 24
习 题 26
第 5 章 命题逻辑 27
§ 5. 1 命题与逻辑联结词 27
§ 5. 2 命题公式与等值演算 30
§ 5. 3 对偶与范式 33
§ 5. 4 推理理论 38
§ 5. 5 命题演算的公理系统 43
习 题 46
第 6 章 一阶逻辑 49Ⅰ
§ 6. 1 谓词与量词 49
§ 6. 2 合式公式及解释 52
§ 6. 3 等值式与范式 54
§ 6. 4 一阶逻辑的推理理论 58
习 题 62
第 2 篇 图论与组合数学
第 7 章 图与子图 66
§ 7. 1 图的概念 66
§ 7. 2 图的同构 68
§ 7. 3 顶点的度 69
§ 7. 4 子图及图的运算 69
§ 7. 5 通路与连通图 71
§ 7. 6 图的矩阵表示 73
§ 7. 7 应用(最短通路问题) 74
习 题 77
第 8 章 树 80
§ 8. 1 树的定义 80
§ 8. 2 生成树 82
§ 8. 3 应用(最优树问题) 84
习 题 85
第 9 章 图的连通性 86
§ 9. 1 点连通度和边连通度 88
？§ 9. 2 块 88
§ 9. 3 应用(构造可靠的通信网络) 90
习 题 91
第 10 章 E 图与 H 图 93
§ 10. 1 七桥问题与 E 图 93
§ 10. 2 周游世界问题与 H 图 94
§ 10. 3 应用(旅行推销员问题) 98
习 题 99
第 11 章 匹配与点独立集 101
§ 11. 1 匹配 101
§ 11. 2 独立集和覆盖 105
§ 11. 3 Ramsey 数 107
§ 11. 4 应用(人员分配问题) 110
习 题 111
第 12 章 图的着色 113
§ 12. 1 顶点着色 113
§ 12. 2 边着色 115
§ 12. 3 色多项式 118
§ 12. 4 应用 121
习 题 122
第 13 章 平面图 123
§ 13. 1 平面图的概念 123
§ 13. 2 欧拉公式 125
§ 13. 3 可平面性判定 127
§ 13. 4 平面图的面着色 128
§ 13. 5 应用(印制电路板的设计) 130
习 题 130
第 14 章 有向图 132
§ 14. 1 有向图的概念 132
§ 14. 2 有向通路与有向回路 134
§ 14. 3 有向树简介 136
§ 14. 4 应用 137
习 题 139
第 15 章 网络最大流 140
§ 15. 1 网络的流与割 140
§ 15. 2 最大流最小割定理 142
§ 15. 3 应用(中国邮递员问题) 146
习 题 146
第 16 章 排列和组合的一般计数方法 148
§ 16. 1 两个基本的计数法则 148
§ 16. 2 基本排列组合的计数方法 149
§ 16. 3 可重复排列组合的计数方法 150
习 题 152
第 17 章 容斥原理 154
§ 17. 1 容斥原理概述 154
§ 17. 2 有禁止位的排列 156
习 题 158
第 18 章 递推关系与生成函数 159
§ 18. 1 递推关系及其解法 159
§ 18. 2 生成函数 161
习 题 163
第 3 篇 代数结构与初等数论
第 19 章 整数 166
§ 19. 1 整除性 166
§ 19. 2 素因数分解 170
§ 19. 3 同余 172
§ 19. 4 孙子定理与 Euler 函数 174
§ 19. 5 数论在计算机密码学中的应用 178
习 题 180
第 20 章 群 182
§ 20. 1 群的概念 182
§ 20. 2 子群 185
？§ 20. 3 置换群 189
§ 20. 4 陪集与 Lagrange 定理 194
§ 20. 5 同态与同构 196
§ 20. 6 群在计算机科学与技术中的应用 200
习 题 203
第 21 章 环与域 205
§ 21. 1 环与子环 205
§ 21. 2 环同态 208
§ 21. 3 域的特征和素域 212
？§ 21. 4 有限域 214
§ 21. 5 有限域的结构 218
§ 21. 6 纠错码 223
§ 21. 7 多项式编码方法及其实现 231
习 题 234
第 22 章 格与布尔代数 237
§ 22. 1 格的定义 237
§ 22. 2 格的性质 239
§ 22. 3 几种特殊的格 242
§ 22. 4 布尔代数 246
§ 22. 5 有限布尔代数的结构 252
§ 22. 6 格与布尔代数在计算机科学与技术中的应用 256
习 题 260
第 4 篇 线性规划与博弈论
第 23 章 线性规划 264
§ 23. 1 线性规划问题及其数学模型 264
§ 23. 2 图解法 267
§ 23. 3 单纯形法原理 269
§ 23. 4 单纯形法计算步骤 274
§ 23. 5 线性规划的对偶问题 278
习 题 279
第 24 章 博弈论 281
§ 24. 1 博弈问题 281
§ 24. 2 矩阵博弈的基本理论 283
§ 24. 3 矩阵博弈的解法 289
§ 24. 4 矩阵博弈均衡 293
习 题 296
参考文献 297
