计算机科学中的离散结构PDF电子书下载

第1章 集合代数 1

1.1 集合的概念与表示 1

1.1.1 集合及其元素 1

1.1.2 集合的表示 2

1.1.3 外延性公理与子集合 3

1.2 集合运算 4

1.2.1 并、交、差、补运算 4

1.2.2 幂集运算和广义并、交运算 7

1.2.3 集合的笛卡儿积 9

1.3.1 集合归纳定义的意义 11

1.3 集合的归纳定义 11

1.3.2 集合定义的自然数 13

1.4 练习 14

第2章 两个常用数学基本原理 17

2.1 归纳原理 17

2.1.1 结构归纳原理 17

2.1.2 数学归纳原理 18

2.2 鸽笼原理 21

2.2.1 鸽笼原理的基本形式 22

2.2.2 鸽笼原理的加强形式 24

2.3 练习 25

3.1.1 命题 27

3.1 命题与逻辑联结词 27

第3章 逻辑代数(上)——命题演算 27

3.1.2 逻辑联结词 29

3.1.3 命题公式 31

3.1.4 语句的形式化 32

3.2 逻辑等价式和逻辑蕴涵式 34

3.2.1 重言式 34

3.2.2 重要的逻辑等价式和逻辑蕴涵式 34

3.2.3 对偶原理 37

3.3 范式 38

3.3.1 析取范式和合取范式 39

3.3.2 主析取范式与主合取范式 40

3.3.3 联结词的扩充与归约 42

3.4 练习 44

第4章 逻辑代数(下)——谓词演算 48

4.1 谓词演算基本概念 48

4.1.1 个体与个体域 48

4.1.2 谓词与谓词填式 49

4.1.3 量词及其辖域 50

4.1.4 谓词公式及语句的形式化 51

4.2 谓词演算永真式 54

4.2.1 谓词公式的真值规定 54

4.2.2 重要的谓词演算永真式 55

4.2.3 关于永真式的几个基本原理 57

4.3 谓词公式的前束范式 59

4.4 练习 60

第5章 形式系统与推理技术 63

5.1 谓词演算形式系统FC 63

5.1.1 FC的基本构成 63

5.1.2 系统内的推理：证明与演绎 64

5.1.3 FC的重要性质 65

5.2 自然推理形式系统ND 69

5.2.1 ND的基本构成 70

5.2.2 ND的系统内推理及性质 72

5.3 练习 79

6.1.1 加法原理和乘法原理 82

6.1 计数基本原理 82

第6章 计数 82

6.1.2 包含排斥原理 83

6.2 排列与组合 85

6.2.1 排列的计数 85

6.2.2 组合的计数 86

6.3 重集的排列与组合 88

6.3.1 重集的排列 88

6.3.2 重集的组合 90

6.3.3 禁位排列的计数 92

6.4 练习 94

7.1 一个重要的递归关系 96

第7章 递归关系 96

7.2.1 递归关系的迭代求解 98

7.2 递归关系的求解 98

7.2.2 常系数线性齐次递归关系的求解 100

7.2.3 一些特殊递归关系的求解 103

7.3 练习 106

第8章 图 108

8.1 图的基础知识 109

8.1.1 图的基本概念 109

8.1.2 结点的度 110

8.1.3 子图、补图及图同构 111

8.2.1 路径与回路 112

8.2 路径、回路及连通性 112

8.2.2 连通性 114

8.2.3 连通度 116

8.3 欧拉图与哈密顿图 117

8.3.1 欧拉图及欧拉路径 117

8.3.2 哈密顿图及哈密顿通路 118

8.4 图的矩阵表示 122

8.4.1 邻接矩阵 122

8.4.2 路径矩阵与可达性矩阵 124

8.5 练习 125

9.1 二分图 130

9.1.1 二分图的基本概念 130

第9章 二分图、平面图和树 130

9.1.2 匹配 131

9.2 平面图 134

9.2.1 平面图的基本概念 134

9.2.2 欧拉公式和库拉托夫斯基定理 136

9.2.3 着色问题 140

9.3 树 142

9.3.1 树的基本概念 142

9.3.2 生成树 144

9.3.3 根树 147

9.4 练习 153

10.1.1 关系的基本概念 156

第10章 关系 156

10.1 二元关系 156

10.1.2 关系的基本运算 159

10.1.3 关系的基本特性 164

10.1.4 关系特性闭包 166

10.2 等价关系 169

10.2.1 等价关系与等价类 169

10.2.2 等价关系与划分 170

10.3 序关系 174

10.3.1 序关系和有序集 175

10.3.2 良基性与良序集，完备序集 178

10.3.3 全序集、良序集的构造 180

10.4 练习 181

第11章 函数 188

11.1 函数及函数的合成 188

11.1.1 函数的基本概念 188

11.1.2 函数概念的拓广 190

11.1.3 函数的合成 192

11.1.4 函数的递归定义 193

11.2 特殊函数类 195

11.2.1 单射的、满射的和双射的函数 195

11.2.2 规范映射、单调映射和连续映射 197

11.3 函数的逆 198

11.4 有限集和无限集 201

11.4.1 有限集、可数集与不可数集 202

11.4.2 无限集的特性 205

11.4.3 有限集和无限集的基数 206

11.4.4 基数比较 207

11.5 练习 209

第12章 递归函数集与可计算性 214

12.1 初等函数集 214

12.1.1 初等函数 214

12.1.2 初等谓词 217

12.2 原始递归函数集 220

12.2.1 初等函数集的不足 220

12.2.2 原始递归式 222

12.2.3 原始递归函数 223

12.3 递归函数集 225

12.3.1 阿克曼函数及其性质 225

12.3.2 μ-递归式 227

12.3.3 递归函数集(μ-递归函数集) 227

12.4 图灵机与可计算函数集 228

12.4.1 图灵机 228

12.4.2 图灵可计算函数 232

12.5 习题 235

13.1 代数结构 238

13.1.1 代数结构的意义 238

第13章 代数结构概论 238

13.1.2 代数结构的特殊元素 239

13.1.3 子代数结构 242

13.2 同态、同构及同余 243

13.2.1 同态与同构 243

13.2.2 同余关系 246

13.3 商代数 248

13.4 练习 250

第14章 群、环、域 254

14.1 半群 254

14.1.1 半群及独异点 254

14.1.2 自由独异点 255

14.1.3 高斯半群 256

14.2 群 258

14.2.1 群及其基本性质 258

14.2.2 子群、陪集和拉格朗日定理 261

14.2.3 正规子群、商群和同态基本定理 263

14.3 循环群和置换群 265

14.3.1 循环群 265

14.3.2 置换群 266

14.4 环 269

14.4.1 环和整环 269

14.4.2 子环和理想 271

14.5 域和有限域 273

14.6 练习 277

第15章 格与布尔代数 281

15.1 格 281

15.1.1 格——有序集 281

15.1.2 格代数 284

15.1.3 分配格和模格 287

15.2 布尔代数 290

15.2.1 有界格和有补格 290

15.2.2 布尔代数的意义 292

15.2.3 布尔代数表示定理 294

15.2.4 布尔表达式与布尔函数 297

15.3 练习 300

参考文献 302