离散数学PDF电子书下载

第一篇 数理逻辑 1

第一章 命题演算及其形式系统 1

1．1 命题与联结词 1

1．1．1 命题 1

1．1．2 联结词 3

1．1．3 命题公式及其真值表 7

1．1．4 语句的形式化 9

1．2 重言式 12

1．2．1 重言式概念 12

1．2．2 逻辑等价式和逻辑蕴涵式 13

1．2．3 对偶原理 17

1．3 范式 20

1．3．1 析取范式和合取范式 20

1．3．2 主析取范式与主合取范式 22

1．3．3 联结词的扩充与归约 25

1．4 命题演算形式系统 29

1．4．1 证明、演绎和推理 30

1．4．2 命题演算形式系统PC 34

1．4．3 自然推理系统ND 40

第二章 谓词演算及其形式系统 48

2．1 个体、谓词和量词 49

2．1．1 个体 49

2．1．2 谓词 49

2．1．3 量词 51

2．1．4 谓词公式及语句的形式化 53

2．2 谓词演算永真式 59

2．2．1 谓词公式的真值规定 59

2．2．2 谓词演算永真式 61

2．2．3 关于永真式的几个基本原理 63

2．3 谓词公式的前束范式 66

2．4 一阶谓词演算形式系统 68

2．4．1 一阶谓词演算形式系统FPC 68

2．4．2 一阶谓词演算的自然推理系统FND 73

2．4．3 含等词的一阶谓词演算自然推理系统 80

第三章 消解原理 85

3．1 斯柯伦标准形 85

3．1．1 斯柯伦标准形 85

3．1．2 子句集及其可满足性 88

3．2 命题演算消解原理 90

3．3．1 代换及一致化 93

3．3 谓词演算消解原理 93

3．3．2 谓词演算消解原理 95

3．3．3 换位原理 99

第二篇 集合论 103

第四章 集合及其运算 103

4．1 集合的基本概念 104

4．1．1 集合及其元素 104

4．1．2 外延公理、概括公理和正规公理 106

4．1．3 子集合 108

4．2．1 并、交、差、补运算 111

4．2 集合运算 111

4．2．2 幂集运算和广义并、交运算 114

4．2．3 环和、环积运算 117

4．3 集合的归纳定义及归纳法证明 121

4．3．1 集合的归纳定义 121

4．3．2 自然数的集合论定义 123

4．3．3 归纳法证明 126

第五章 关系 135

5．1 有序组与集合的笛卡儿积 135

5．2．1 关系的基本概念 139

5．2 关系 139

5．2．2 关系的基本运算 143

5．2．3 关系的基本特性 150

5．2．4 关系特性闭包 154

5．2．5 特殊关系运算 160

5．3 等价关系 165

5．3．1 等价关系 165

5．3．2 划分与等价关系 167

5．4．1 序关系和有序集 175

5．4 序关系 175

5．4．2 良基性与良序集，完备序集 181

5．4．3 全序集、良序集的构造 184

第六章 函数 190

6．1 函数及函数的合成 190

6．1．1 函数的基本概念 190

6．1．2 函数概念的拓广 194

6．1．3 函数的合成 196

6．1．4 函数的递归定义 198

6．2 特殊函数类 203

6．2．1 单射的、满射的和双射的函数 203

6．2．2 规范映射、单调映射和连续映射 206

6．3 函数的逆 211

6．4 函数、谓词、集合 216

第七章 基数 221

7．1 有限集和无限集 221

7．1．1 有限集、可数集与不可数集 221

7．1．2 无限集的特性 227

7．2 基数 229

7．2．1 有限集、可数无限集和连续统的基数 229

7．2．2 基数比较 231

7．2．3 基数算术 236

第三篇 图论 245

第八章 图 245

8．1 图的基本知识 245

8．1．1 图的定义及有关术语 245

8．1．2 结点的度 249

8．1．3 图运算及图同构 251

8．2 路径、回路及连通性 258

8．2．2 连通性 260

8．2．3 连通度 264

8．2．1 路径与回路 268

8．3 欧拉图与哈密顿图 270

8．3．1 欧拉图与欧拉路径 270

8．3．2 哈密顿图及哈密顿通路 272

8．4 图的矩阵表示 279

8．4．1 关联矩阵 279

8．4．2 邻接矩阵 281

8．4．3 路径矩阵与可达性矩阵 284

9．1 二分图 288

9．1．1 二分图的基本概念 288

第九章 特殊图 288

9．1．2 匹配 290

9．2 平面图 297

9．2．1 平面图的基本概念 297

9．2．2 欧拉公式和库拉托夫斯基定理 299

9．2．3 着色问题 304

9．3 树 308

9．3．1 树的基本概念 308

9．3．2 生成树 311

9．3．3 根树 316

10．1．1 代数结构的意义 329

10．1 代数结构 329

第四篇 抽象代数 329

第十章 代数结构通论 329

10．1．2 代数结构的特殊元素 331

10．1．3 子代数结构 336

10．2 同态、同构及同余 339

10．2．1 同态与同构 339

10．2．2 同余关系 344

10．3 商代数与积代数 349

10．3．1 商代数 349

10．3．2 积代数 353

11．1．1 半群及独异点 356

第十一章 群、环、域 356

11．1 半群 356

11．1．2 自由独异点 357

11．1．3 商半群及高斯半群 359

11．2 群 364

11．2．1 群及其基本性质 364

11．2．2 子群、陪集和拉格朗日定理 368

11．2．3 正规子群、商群和同态基本定理 371

11．3．1 循环群 376

11．3 循环群和置换群 376

11．3．2 置换群 378

11．4 环 384

11．4．1 环和整环 384

11．4．2 子环和理想 387

11．4．3 多项式环 390

11．5 域 399

11．5．1 域和子域 399

11．5．2 有限域 403

12．1．1 格——有序集 412

第十二章 格与布尔代数 412

12．1 格 412

12．1．2 格代数 416

12．1．3 分配格和模格 421

12．2 布尔代数 427

12．2．1 有界格和有补格 427

12．2．2 布尔代数 429

12．2．3 布尔代数的表示定理 433

12．2．4 布尔表达式与布尔函数 438