离散数学PDF电子书下载

第1章 命题演算基础 1

1.1 命题和联结词 1

1.1.1 命题 1

1.1.2 联结词 2

1.1.3 合式公式 6

1.1.4 命题逻辑的应用 6

1.2 真假性 9

1.2.1 解释 9

1.2.2 等价公式 10

1.2.3 联结词的完备集 12

1.2.4 对偶式和内否式 13

1.3 范式及其应用 15

1.3.1 范式 15

1.3.2 主范式 17

1.3.3 范式的应用 20

1.4 典型例题 21

习题 23

第2章 命题演算的推理理论 26

2.1 命题演算的公理系统 26

2.1.1 公理系统的组成部分 27

2.1.2 公理系统的推理过程 28

2.2 若干重要的导出规则 30

2.2.1 分离规则的讨论 30

2.2.2 公理和定理的导出规则 30

2.3 命题演算的假设推理系统 32

2.3.1 假设推理系统的组成 32

2.3.2 假设推理系统的推理过程 33

2.3.3 额外假设推理法 35

2.4 命题演算的归结推理法 37

2.4.1 归结证明过程 38

2.4.2 归结证明示例 39

2.5 典型例题 40

习题 43

第3章 谓词演算基础 45

3.1 谓词和个体 45

3.1.1 个体 45

3.1.2 谓词 45

3.2 函数项和量词 48

3.2.1 函数项 48

3.2.2 量词 49

3.3 自由变元和约束变元 51

3.3.1 自由出现和约束出现 51

3.3.2 改名和代入 51

3.4 永真性和可满足性 53

3.4.1 真假性 53

3.4.2 同真假性、永真性和可满足性 55

3.4.3 范式 58

3.5 唯一性量词和摹状词 59

3.5.1 唯一性量词 59

3.5.2 摹状词 60

3.6 典型例题 61

习题 62

第4章 谓词演算的推理理论 65

4.1 谓词演算的永真推理系统 65

4.1.1 公理系统的组成部分 65

4.1.2 公理系统的推理过程 67

4.2 谓词演算的假设推理系统 68

4.2.1 假设推理系统的组成及证明方法 68

4.2.2 定理的假设推导过程 69

4.3 谓词演算的归结推理系统 71

4.3.1 置换 72

4.3.2 归结反演系统 72

4.3.3 霍恩子句逻辑程序 75

4.4 Prolog简介 78

4.5 典型例题 80

习题 82

第5章 递归函数论 85

5.1 数论函数和数论谓词 85

5.1.1 数论函数 85

5.1.2 数论谓词和特征函数 86

5.2 函数的构造 88

5.2.1 迭置法 88

5.2.2 算子法 90

5.2.3 原始递归函数 91

5.3 典型例题 92

习题 92

第6章 集合 94

6.1 集合的基本概念 94

6.1.1 集合的定义 94

6.1.2 集合的表示 95

6.1.3 集合的包含关系 96

6.1.4 集合的特点 97

6.1.5 多重集 97

6.2 集合的基本运算 98

6.2.1 集合的并、交、差 98

6.2.2 集合的对称差 99

6.2.3 文氏图 100

6.2.4 集合的幂集合 101

6.2.5 多个集合的并与交 101

6.3 全集和补集 102

6.3.1 全集和补集的定义 102

6.3.2 基本运算定理 103

6.3.3 集合的计算机表示 104

6.4 自然数与自然数集 105

6.4.1 后继 105

6.4.2 自然数和自然数集 105

6.4.3 皮亚诺公理假设 106

6.4.4 自然数集的性质 107

6.4.5 集合的递归定义与递归子程序 108

6.5 包含与排斥原理 110

6.6 典型例题 112

习题 113

第7章 关系 118

7.1 集合的笛卡儿积集 118

7.1.1 有序二元组 118

7.1.2 笛卡儿积集 118

7.1.3 有序n元组、n个集合的笛卡儿积集 119

7.2 二元关系的基本概念 120

7.2.1 二元关系 120

7.2.2 二元关系的表示 120

7.2.3 二元关系与数据结构 122

7.2.4 二元关系的运算 122

7.3 n元关系及其运算 125

7.3.1 n元关系 125

7.3.2 n元关系的运算 125

7.4 二元关系的性质 128

7.4.1 自反性、反自反性、对称性、反对称性、传递性和反传递性 128

7.4.2 二元关系性质的判定定理 130

7.5 二元关系的闭包运算 132

7.5.1 自反闭包、对称闭包和传递闭包 132

7.5.2 闭包的判定定理 132

7.6 等价关系和集合的划分 137

7.6.1 等价关系和等价类 137

7.6.2 商集合 138

7.6.3 集合的划分 138

7.7 偏序关系和格 141

7.7.1 偏序关系和偏序集 141

7.7.2 哈斯图 142

7.7.3 链、反链、全序集 142

7.7.4 极大元、极小元、最大元和最小元 143

7.7.5 上界、下界、最小上界和最大下界 143

7.7.6 格 144

7.7.7 拓扑排序 145

7.8 粗糙集概论 147

7.8.1 知识与知识分类 147

7.8.2 集合近似与粗糙集概念 150

7.9 典型例题 151

习题 152

第8章 函数与集合的势 157

8.1 函数的基本概念 157

8.1.1 函数（映射）的定义 157

8.1.2 函数的性质 159

8.2 函数的复合和逆函数 160

8.2.1 函数的复合 160

8.2.2 左可逆函数、右可逆函数和逆函数 162

8.3 无限集 164

8.3.1 势 164

8.3.2 有限集和无限集 166

8.3.3 可数无限集和不可数无限集 166

8.4 集合势大小的比较 168

8.4.1 集合势的大小 168

8.4.2 伯恩斯坦定理 169

8.5 鸽巢原理 169

8.6 典型例题 171

习题 172

第9章 图论 175

9.1 图的基本概念 175

9.1.1 有向图和无向图 176

9.1.2 图的同构、子图和补图 177

9.1.3 顶点的度 178

9.2 图中的通路、图的连通性和图的矩阵表示 179

9.2.1 通路、回路和连通性 179

9.2.2 图的矩阵表示 181

9.3 带权图与带权图中的最短通路 184

9.4 欧拉图 187

9.5 哈密顿图 190

9.6 二部图 194

9.7 平面图与平面图的着色 197

9.7.1 平面图 197

9.7.2 平面图的着色 200

9.8 典型例题 203

习题 204

第10章 树和有序树 209

10.1 树的基本概念 209

10.2 连通图的生成树和带权连通图的最小生成树 211

10.3 有序树 214

10.3.1 根树 214

10.3.2 根树的应用 216

10.4 前缀码和最优2-分树 218

10.4.1 前缀码 218

10.4.2 最优2-分树 220

10.4.3 赫夫曼编码 222

10.5 典型例题 224

习题 226

第11章 群和环 229

11.1 代数运算的基本概念 229

11.1.1 代数运算 229

11.1.2 交换律、结合律 230

11.1.3 n元运算 231

11.2 代数系统和半群 232

11.2.1 代数系统 232

11.2.2 同态映射和同构映射 233

11.2.3 半群与含幺半群 235

11.3 群的基本概念 236

11.3.1 逆元 236

11.3.2 群的定义 237

11.3.3 群的同态、同构 240

11.3.4 无限群、有限群、交换群和元的阶 242

11.4 群的几个等价定义 244

11.5 变换群和置换群 245

11.5.1 变换群 246

11.5.2 置换群 247

11.6 循环群 250

11.7 子群 252

11.7.1 子群的定义 252

11.7.2 子群的判定定理 252

11.8 子群的陪集 254

11.8.1 按子群划分的剩余类 254

11.8.2 右陪集 254

11.8.3 左陪集 256

11.8.4 拉格朗日定理 257

11.9 正规子群和商群 259

11.9.1 正规子群 259

11.9.2 商群 260

11.10 环和域 262

11.10.1 环、子环与理想 263

11.10.2 交换环和整环 264

11.10.3 除环和域 264

11.11 典型例题 265

习题 268

第12章 格与布尔代数 271

12.1 格定义的代数系统 271

12.2 格的代数定义 273

12.2.1 格的代数定义 273

12.2.2 子格 275

12.2.3 格的同态和同构 275

12.3 一些特殊的格 276

12.3.1 分配格 276

12.3.2 布尔格和布尔代数 278

12.4 有限布尔代数的唯一性 279

12.4.1 原子 279

12.4.2 有限布尔代数非零元素的表达 279

12.4.3 布尔代数的同构 280

12.5 布尔表达式和布尔函数 282

12.5.1 布尔表达式 282

12.5.2 布尔函数 283

12.6 典型例题 285

习题 286

参考文献 288