离散数学及应用PDF|Epub|txt|kindle电子书版本网盘下载

离散数学及应用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