离散数学及应用PDF电子书下载

第1篇 集合论 1

第1章 集合 1

1.1 集合的基本概念及性质 1

1.1.1 集合的基本概念 1

1.1.2 集合的表示形式 2

1.1.3 集合的基本性质 4

1.1.4 集合之间的关系 4

1.2 集合的运算 6

1.2.1 集合的交运算 6

1.2.2 集合的并运算 6

1.2.3 集合的补运算 7

1.2.4 集合的对称差运算 8

1.2.5 集合的广义交和广义并运算 8

1.3 有限集合的计数 9

1.3.1 鸽巢原理 9

1.3.2 包容排斥原理 9

1.4 集合的运算定律 11

思考与练习题 11

第2章 关系 14

2.1 笛卡尔积概念 14

2.1.1 序偶 14

2.1.2 笛卡尔积 15

2.2 二元关系及其表示方法 17

2.2.1 二元关系的定义 17

2.2.2 二元关系的表示方法 18

2.3 二元关系的运算 19

2.3.1 关系的基本运算 19

2.3.2 关系的复合运算 20

2.3.3 关系的幂运算 25

2.3.4 关系的逆运算 26

2.3.5 关系的限制和像 28

2.4 二元关系的性质 29

2.4.1 自反性与反自反性 29

2.4.2 对称性、反对称性、非对称性 31

2.4.3 传递性 33

2.4.4 关系性质的保持性 35

2.5 二元关系的闭包 37

2.5.1 关系闭包定义 38

2.5.2 关系闭包涉及的定理 39

2.5.3 关系闭包的求解方法总结 42

2.6 等价关系 44

2.6.1 等价关系定义 44

2.6.2 等价类与商集 45

2.6.3 等价类与划分 47

2.7 相容关系与覆盖 49

2.7.1 相容关系与覆盖的定义 49

2.7.2 最大相容类 50

2.8 序关系 52

2.8.1 偏序关系 53

2.8.2 全序关系与良序关系 59

2.8.3 拟序关系 60

思考与练习题 60

第3章 函数 65

3.1 函数的基本概念 65

3.1.1 函数的引入 65

3.1.2 函数的定义及特点 65

3.2 特殊函数 67

3.2.1 单射、满射与双射 67

3.2.2 常用函数 69

3.3 函数的运算 69

3.3.1 函数的复合运算 70

3.3.2 函数的逆运算 72

3.4 集合的基数 74

3.4.1 基数的定义 74

3.4.2 可数集的定义及性质 75

3.4.3 集合基数的比较 76

思考与练习题 77

第2篇 图论 80

第4章 图的基本概念 80

4.1 图的基本概念 80

4.1.1 图的基本概念 81

4.1.2 图中结点的度数 83

4.1.3 可图化的 85

4.1.4 图的同构 86

4.1.5 完全图与正则图 88

4.1.6 子图与补图 89

4.1.7 图的操作与运算 90

4.2 图的通路与图的连通性 91

4.2.1 通略 91

4.2.2 图的连通性 94

4.3 图的矩阵表示 98

4.3.1 图的关联矩阵 98

4.3.2 有向图的邻接矩阵 100

4.3.3 图的可达矩阵 102

思考与练习题 104

第5章 特殊图 107

5.1 欧拉图 107

5.1.1 欧拉图定义 107

5.1.2 欧拉图判定定理 108

5.2 汉密尔顿图 111

5.2.1 汉密尔顿图定义 111

5.2.2 汉密尔顿图判定定理 111

5.3 二部图与匹配 116

5.3.1 二部图 116

5.3.2 匹配 118

5.4 平面图与着色 119

5.4.1 平面图的定义 119

5.4.2 平面图的欧拉公式 122

5.4.3 平面图的判定定理 124

5.4.4 平面图的对偶图 125

5.4.5 平面图的着色 128

思考与练习题 131

第6章 无向树 134

6.1 无向树概念 134

6.1.1 无向树定义 134

6.1.2 无向树性质 135

6.2 生成树与最小生成树 136

6.2.1 生成树 136

6.2.2 最小生成树 138

思考与练习题 144

第7章 有向树 146

7.1 有向树概念 146

7.2 完全有向树与正则有向树 147

7.3 最优二叉树 148

7.3.1 最优二叉树定义 148

7.3.2 最优二叉树求解 149

7.3.3 哈夫曼编码 150

7.4 二叉树的遍历 151

思考与练习题 152

第3篇 数理逻辑 154

第8章 命题逻辑 154

8.1 命题与联结词 154

8.1.1 命题的基本概念 155

8.1.2 联结词 156

8.2 命题公式 159

8.2.1 命题公式定义 159

8.2.2 命题公式的赋值 160

8.2.3 命题公式的类型 161

8.2.4 命题的等价关系 162

8.2.5 命题的蕴涵关系 165

8.3 范式 167

8.3.1 命题的一般范式 167

8.3.2 命题的主范式 169

8.3.3 范式的应用 172

8.4 联结词完备集 175

8.5 命题逻辑的推理理论 179

8.5.1 命题逻辑推理规则 179

8.5.2 命题逻辑推理方法 182

思考与练习题 184

第9章 谓词逻辑 188

9.1 谓词逻辑的基本概念 188

9.1.1 谓词与个体 189

9.1.2 量词 190

9.2 谓词公式 191

9.2.1 谓词公式定义 191

9.2.2 谓词公式的约束变元与自由变元 194

9.2.3 谓词公式的解释 195

9.2.4 谓词公式的类型 196

9.2.5 谓词的等价关系 197

9.2.6 谓词的蕴涵关系 199

9.3 谓词逻辑的范式 200

9.3.1 前束范式 200

9.3.2 Skolem范式 202

9.4 谓词逻辑的推理理论 202

9.4.1 谓词逻辑的推理规则 202

9.4.2 谓词逻辑的推理方法 204

思考与练习题 207

第4篇 代数结构 210

第10章 群 210

10.1 群的定义 210

10.1.1 二元运算 210

10.1.2 代数系统 211

10.1.3 半群和群 211

10.2 交换群、置换群和循环群 213

10.2.1 交换群 213

10.2.2 置换群和循环群 214

10.3 子群、正规子群与商群 214

10.3.1 子群 214

10.3.2 正规子群 215

10.3.3 商群 215

10.4 群的同态与同构 216

思考与练习题 218

第11章 环与理想 219

11.1 基本概念 219

11.2 子环与环的同态 220

11.3 多项式环与欧几里德环 221

11.3.1 多项式环 221

11.3.2 欧几里德环 222

11.4 理想与商环 222

11.4.1 理想 222

11.4.2 商环 223

思考与练习题 224

第12章 域 226

12.1 扩域 226

12.2 代数元与超越元 227

12.3 有限域 229

12.4 本原元与本原多项式 232

思考与练习题 236

第5篇 综合应用 238

第13章 数理逻辑的应用实例 238

13.1 命题逻辑的应用实例 238

13.2 谓词逻辑的应用实例 242

思考与练习题 250

第14章 关系的应用实例 251

14.1 关系及运算在关系数据库中的应用 251

14.1.1 关系数据库简介 251

14.1.2 关系在关系数据库中的应用 252

14.1.3 关系运算在关系数据库中的应用 252

14.2 关系闭包的应用 257

14.3 等价关系与划分的应用 257

14.4 序关系的应用 258

思考与练习题 259

第15章 图论的应用实例 261

15.1 平面图及着色的应用 261

15.1.1 地图的着色 261

15.1.2 交通信号灯问题 262

15.1.3 公共事业问题 262

15.1.4 冰箱分隔问题 263

15.1.5 排课表问题 263

15.2 通路的应用 264

15.2.1 边权为1的两点最短路径——Moore算法 264

15.2.2 单源最短路径——Dijkstra算法 265

15.2.3 所有点对间最短路径——Floyd算法 266

15.2.4 关键道路法 267

15.3 欧拉图的应用实例 272

15.3.1 计算机鼓轮设计问题 272

15.3.2 中国邮路问题 273

15.4 汉密尔顿图的应用实例 273

15.5 树的应用 275

15.5.1 数据压缩问题 275

15.5.2 最优二叉检索树问题 276

15.5.3 决策树与博弈树问题 278

15.6 网络流 283

15.6.1 运输网 283

15.6.2 扩展的运输网 291

15.6.3 匹配问题 291

思考与练习题 292

第16章 有限自动机与语言 294

16.1 单词与语言 294

16.2 正则式和正则语言 296

16.3 有限状态自动机 297

16.4 文法和语言 298

思考与练习题 303

参考文献 307