离散数学PDF电子书下载

第一部分 数理逻辑 2

第1章 命题逻辑 2

本章学习目标 2

1.1 命题和命题联结词 2

1.1.1 命题 2

1.1.2 命题联结词 4

1.2 命题公式与解释 8

1.2.1 命题公式 8

1.2.2 命题公式的解释 10

1.3 真值表与等价公式 11

1.3.1 真值表 11

1.3.2 命题公式的分类 13

1.3.3 等价公式 15

1.3.4 代入规则和替换规则 18

1.4 对偶定理 23

1.5 范式 25

1.5.1 合取范式和析取范式 25

1.5.2 主析取范式和主合取范式 27

1.6 公式的蕴涵 33

1.6.1 蕴涵的概念 33

1.6.2 蕴涵式的证明方法 34

1.6.3 基本蕴涵式 35

1.7 其他联结词与最小联结词组 36

1.7.1 其他联结词 36

1.7.2 最小联结词组 39

1.8 命题逻辑推理理论 40

1.8.1 命题逻辑推理理论 40

1.8.2 推理规则 42

1.8.3 判断有效结论的常用方法 44

本章小结 48

习题1 48

第2章 谓词逻辑 52

本章学习目标 52

2.1 谓词逻辑命题的符号化 52

2.1.1 个体词与谓词 53

2.1.2 量词 54

2.1.3 谓词逻辑中命题的符号化 55

2.2 谓词逻辑公式与解释 57

2.2.1 谓词逻辑的合式公式 57

2.2.2 谓词的约束和替换 59

2.2.3 谓词逻辑公式的解释 61

2.3 谓词逻辑公式的等价与蕴涵 63

2.3.1 谓词逻辑的等价公式 63

2.3.2 谓词逻辑的蕴涵公式 67

2.3.3 多个量词的使用 68

2.4 前束范式 69

2.5 谓词逻辑的推理理论 71

本章小结 76

习题2 76

第二部分 集合论 81

第3章 集合 81

本章学习目标 81

3.1 集合的概念与表示 81

3.1.1 集合的基本概念 81

3.1.2 集合的表示 82

3.1.3 集合之间的关系 83

3.2 集合的运算 86

3.2.1 集合的交运算 86

3.2.2 集合的并运算 87

3.2.3 集合的补 88

3.2.4 集合的对称差 90

3.3 包含排斥原理 91

本章小结 94

习题3 94

第4章 关系 98

本章学习目标 98

4.1 序偶与笛卡尔积 98

4.1.1 有序n元组 98

4.1.2 笛卡尔积的概念 99

4.1.3 笛卡尔积的性质 100

4.2 二元关系及其表示 102

4.2.1 二元关系的概念 102

4.2.2 二元关系的表示 103

4.3 关系的运算 105

4.3.1 关系的交、并、差、补运算 105

4.3.2 关系的复合运算 106

4.3.3 关系的逆运算 110

4.4 关系的性质 112

4.4.1 自反性和反自反性 112

4.4.2 对称性和反对称性 112

4.4.3 传递性 113

4.4.4 关系性质的判定 113

4.5 关系的闭包 120

4.6 等价关系与集合的划分 125

4.6.1 等价关系 125

4.6.2 等价类 126

4.6.3 集合的划分 127

4.7 相容关系 130

4.7.1 相容关系 130

4.7.2 覆盖 132

4.8 偏序关系 134

4.8.1 偏序关系 134

4.8.2 哈斯图 135

4.8.3 全序关系 137

4.8.4 良序关系 139

本章小结 140

习题4 140

第5章 函数 144

本章学习目标 144

5.1 函数的概念 144

5.2 函数的性质 146

5.3 复合函数和逆函数 149

5.3.1 复合函数 149

5.3.2 逆函数 151

5.4 置换 152

本章小结 154

习题5 154

第6章 集合的基数 156

本章学习目标 156

6.1 基数的概念 156

6.2 可数集和不可数集 158

6.2.1 可数集 158

6.2.2 不可数集 160

6.3 基数的比较 161

本章小结 163

习题6 164

第三部分 图论 166

第7章 图 166

本章学习目标 166

7.1 图的基本概念 166

7.1.1 图论的发展 166

7.1.2 图的基本概念 167

7.2 通路与回路 175

7.3 图的连通性 176

7.3.1 无向图的连通性 176

7.3.2 有向图的连通性 179

7.4 图的矩阵表示 183

7.4.1 图的邻接矩阵 183

7.4.2 图的关联矩阵 185

7.4.3 有向图的可达矩阵 188

7.5 图的应用 190

7.5.1 带权图的最短通路 190

7.5.2 带权图的关键路径 193

本章小结 196

习题7 196

第8章 欧拉图与哈密尔顿图 200

本章学习目标 200

8.1 欧拉图 200

8.1.1 欧拉图的定义 200

8.1.2 欧拉图的判定 201

8.1.3 求欧拉回路的算法 203

8.1.4 欧拉图的应用 204

8.2 哈密尔顿图 205

8.2.1 哈密尔顿图 205

8.2.2 哈密尔顿图的判定 206

本章小结 207

习题8 208

第9章 特殊图 210

本章学习目标 210

9.1 树 210

9.1.1 无向树 210

9.1.2 生成树与最小生成树 213

9.1.3 有向树与根树 214

9.1.4 最优二叉树及其应用 219

9.2 二部图 222

9.3 平面图 225

9.3.1 平面图的定义 225

9.3.2 欧拉公式 226

9.3.3 库拉托夫斯基定理 229

9.3.4 平面图的对偶图 230

本章小结 232

习题9 232

第四部分 代数系统 236

第10章 代数结构 236

本章学习目标 236

10.1 二元运算及其性质 236

10.1.1 二元运算 236

10.1.2 二元运算的性质 238

10.2 代数系统 242

10.3 群的定义 243

10.3.1 半群 243

10.3.2 群 245

10.3.3 群的性质 247

10.4 子群 248

10.4.1 子群 248

10.4.2 子群的判定 249

10.5 阿贝尔群和循环群 251

10.5.1 阿贝尔群 251

10.5.2 循环群 252

10.6 置换群与伯恩赛德定理 254

10.6.1 置换群 254

10.6.2 伯恩赛德定理（Burnside） 257

10.7 陪集与拉格朗日定理 260

10.7.1 陪集 260

10.7.2 正规子群和商群 261

10.7.3 拉格朗日定理 263

10.8 群的同态与同构 264

本章小结 267

习题10 267

第11章 格与布尔代数 271

本章学习目标 271

11.1 格的定义和性质 271

11.1.1 格的定义 271

11.1.2 格的对偶原理 272

11.1.3 格的性质 273

11.1.4 子格和格的同态 276

11.2 分配格和有补格 278

11.2.1 模格 278

11.2.2 分配格 279

11.2.3 有界格 281

11.2.4 有补格 281

11.3 布尔代数 282

11.3.1 布尔代数的定义及性质 282

11.3.2 布尔代数的同构与同态 284

11.3.3 布尔代数的表示理论 287

本章小结 289

习题11 289

习题参考答案 292

参考文献 355