离散数学PDF电子书下载

第一篇 集合论 3

第1章 经典集合论基础 3

1.1 集合的基本概念 3

1.1.1 集合的定义 3

1.1.2 集合的表示 3

1.1.3 集合与元素 4

1.1.4 集合的特点 4

1.2 集合间的关系 6

1.2.1 集合之间有哪些关系 6

1.2.2 维恩图 8

1.3 集合代数 8

1.3.1 基本集合运算的定义 8

1.3.2 主要的运算公式 10

1.3.3 集合运算的运用 12

1.4 幂集 15

1.5 有序组、笛卡儿乘积 15

1.6 集合与悖论 17

1.6.1 罗素悖论 17

1.6.2 集合悖论的意义 18

1.7 集合概念的应用 19

第2章 关系 21

2.1 关系的基本概念 21

2.1.1 什么是关系 21

2.1.2 关系的正式定义 23

2.1.3 如何表示关系 24

2.2 关系的基本运算 25

2.2.1 关系的集合运算 25

2.2.2 复合关系 26

2.2.3逆关系 28

2.2.4 关系运算的性质 29

2.2.5 关系运算的应用 30

2.3 关系的重要性质 30

2.3.1 关系的基本性质 31

2.3.2 关系的性质在图和矩阵上的特征 32

2.4 关系上的闭包运算 34

2.4.1 闭包运算的引入 34

2.4.2 闭包的概念 34

2.4.3 闭包的性质 35

2.4.4 闭包的计算 37

2.4.5 计算传递闭包的沃舍尔算法 39

2.4.6 闭包的应用 42

2.5 次序关系 43

2.5.1 什么是次序 43

2.5.2 次序关系的概念 45

2.5.3 哈斯图 46

2.5.4 次序关系中的特殊元素 47

2.5.5 次序关系的应用 49

2.5.6 如何研究一种关系 50

2.6 相容关系 51

2.6.1 什么是相容关系 51

2.6.2 相容关系的矩阵和图 53

2.6.3 极大相容性分块与覆盖 53

2.7 等价关系 54

2.7.1 研究等价关系的意义 55

2.7.2 等价关系的基本概念 55

2.7.3 等价类 55

2.7.4 等价关系与划分 56

2.7.5 等价关系的应用 59

第3章 函数 60

3.1 函数的基本概念 60

3.1.1 函数的定义 60

3.1.2 函数的性质 61

3.2 复合函数与反函数 62

3.2.1 复合函数 62

3.2.2 反函数 63

3.3 常用函数介绍 64

3.3.1 常函数和恒等函数 64

3.3.2 单调递增函数 64

3.3.3 特征函数 64

3.3.4 自然映射 65

第4章 无限集 66

4.1 概述 66

4.2 引言——个故事 67

4.3 热身运动——有限集与集合计数问题 67

4.4 无限集合研究的基本方法 69

4.5 可数无限集合 69

4.6 不可数无限集合 72

4.7 无穷集合基数的比较 73

第二篇 抽象代数 77

第5章 代数系统基础 77

5.1 代数系统的一般概念 77

5.1.1 运算的基本概念 77

5.1.2 什么是代数系统 79

5.1.3 同类型代数系统 80

5.1.4 子代数系统 80

5.2 代数系统的常见性质 80

5.2.1 结合律 81

5.2.2 交换律 81

5.2.3 分配律 81

5.2.4 单位元素 82

5.2.5 零元素 84

5.2.6 逆元素 85

5.2.7 通过运算表判别运算性质的方法 88

5.2.8 应用实例 89

5.3 同态与同构 89

5.3.1 同态／同构的基本思想 89

5.3.2同态 92

5.3.3 同构 95

第6章 群论基础 99

6.1 半群 99

6.1.1 基本概念 99

6.1.2 例题分析 102

6.2 群 104

6.2.1 群的基本概念 104

6.2.2 一些典型的群 105

6.2.3 群的基本性质 107

6.2.4 子群 110

6.2.5 群的同态与同构 112

6.2.6 循环群 113

6.2.7 置换群 114

第三篇 图论入门 119

第7章 图论基础 119

7.1 图的基本概念 119

7.1.1 什么是图 119

7.1.2 图的同构 124

7.1.3 图中结点的次数 126

7.1.4 初步利用图论思想解决问题 126

7.2 通路、回路和连通性 130

7.2.1 通路与回路 130

7.2.2 连通性 131

7.3 欧拉图 132

7.3.1 欧拉图的概念 133

7.3.2 欧拉图的判定 134

7.3.3 欧拉回路的生成 135

7.3.4 欧拉图的应用 137

7.4 哈密尔顿图 139

7.4.1 哈密尔顿图的起源 139

7.4.2 哈密尔顿图的概念 139

7.4.3 哈密尔顿图的判定 140

7.4.4 哈密尔顿图的应用 141

7.5 图的矩阵表示 142

7.5.1 问题的引入 142

7.5.2 有向图的邻接矩阵 143

7.5.3 可达性矩阵 146

7.5.4 矩阵与图的连通性 146

7.5.5 关联矩阵 147

第8章 树 149

8.1 树的概念及其基本性质 149

8.1.1 树的概念 149

8.1.2 树的基本性质 151

8.2 有向树 152

8.2.1 基本概念 153

8.2.2 外向树应用 154

8.3 二元树 155

8.3.1 基本概念 155

8.3.2 从外向树到二元树 156

8.3.3 二元树的应用 157

8.4 生成树 160

8.4.1 问题的引入 160

8.4.2 生成树的概念 161

8.4.3 生成树的构造 161

8.4.4 最小生成树 163

8.4.5 最小生成树的构造 163

第四篇 数理逻辑 167

第9章 命题逻辑 167

9.1 命题与命题联结词 167

9.1.1 命题 167

9.1.2 命题联结词 168

9.1.3 命题符号化 173

9.2 命题变元与命题公式 175

9.2.1 命题变元与命题公式的概念 175

9.2.2 真值指派 175

9.2.3 公式类型 176

9.3 命题逻辑的永真式 176

9.3.1 基本等式 177

9.3.2 基本蕴含重言式 179

9.3.3 逆命题、否命题和逆否命题 181

9.3.4 命题演算公式的应用 181

9.4 对偶定理 184

9.5 命题逻辑的推理规则及应用 185

9.5.1 推理的基本方法 185

9.5.2 推理规则 187

9.5.3 基本例题 191

9.5.4 推理规则的应用 193

9.6 范式 195

9.6.1 概述 195

9.6.2 析取范式 195

9.6.3 合取范式 197

9.6.4 命题公式的特异范式 199

9.6.5 范式的应用 202

第10章 谓词逻辑 205

10.1 概述 205

10.2 谓词与个体 206

10.2.1 个体、谓词的概念 206

10.2.2 个体变元 207

10.2.3 命题函数 207

10.3 量词 207

10.3.1 引言 207

10.3.2 量词的概念 208

10.3.3 全称量词 208

10.3.4 存在量词 208

10.3.5 量词与个体域 208

10.3.6 命题符号化 209

10.4 谓词逻辑公式 210

10.4.1 函数 210

10.4.2 谓词公式 210

10.5 自由变元与约束变元 211

10.5.1 自由变元与约束变元的概念 211

10.5.2 换名规则 212

10.5.3 代入规则 213

10.6 谓词演算的永真公式 213

10.6.1 公式的类型 213

10.6.2 公式的等价与蕴含 214

10.6.3 谓词演算的对偶定理 219

10.7 谓词逻辑的推理理论 219

10.7.1 推理规则 219

10.7.2 推理规则的应用 220

10.8 范式 222

10.8.1 前束范式 222

10.8.2 斯科林范式 223

10.9 谓词逻辑的应用 224

参考文献 226