离散数学 第2版PDF电子书下载

第1章 命题演算基础 1

1.1命题和联结词 1

1.1.1命题 1

1.1.2联结词 2

1.1.3合式公式 5

1.2真假性 6

1.2.1解释 6

1.2.2等价公式 6

1.2.3联结词的完备集 8

1.2.4对偶式和内否式 9

1.3范式及其应用 10

1.3.1范式 10

1.3.2主范式 12

1.3.3范式的应用 14

1.4典型例题及解答 15

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

2.1命题演算的公理系统 18

2.1.1公理系统的组成部分 19

2.1.2公理系统的推理过程 20

2.2若干重要的导出规则 21

2.2.1关于分离规则的讨论 21

2.2.2关于公理和定理的导出规则 22

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

2.3.1假设推理系统的组成 23

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

2.3.3额外假设推理法 25

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

2.4.1归结证明过程 27

2.4.2归结证明举例 28

2.5典型例题及解答 29

第3章 谓词演算基础 33

3.1个体和谓词 33

3.1.1个体 33

3.1.2谓词 34

3.2函数项和量词 36

3.2.1函数项 36

3.2.2量词 36

3.3自由变元和约束变元 38

3.3.1自由出现和约束出现 38

3.3.2改名和代入 38

3.4永真性和可满足性 40

3.4.1真假性 40

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

3.4.3范式 45

3.5唯一性量词和摹状词 46

3.5.1唯一性量词 46

3.5.2摹状词 47

3.6典型例题及解答 47

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

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

4.1.1公理系统的组成部分 51

4.1.2公理系统的推理过程 53

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

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

4.2.2定理的推导过程 55

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

4.3.1置换 57

4.3.2归结反演系统 57

4.3.3霍恩子句逻辑程序 60

4.4典型例题及解答 62

第5章 递归函数论 66

5.1数论函数和数论谓词 66

5.1.1数论函数 66

5.1.2数论谓词和特征函数 67

5.2函数的构造 69

5.2.1迭置法 69

5.2.2算子法 70

5.2.3原始递归函数 71

第6章 集合 74

6.1集合的基本概念 74

6.1.1集合的定义 74

6.1.2集合的表示 75

6.1.3集合的包含关系 76

6.1.4集合的特点 76

6.2集合的基本运算 77

6.2.1集合的并、交、差 77

6.2.2集合的对称差 79

6.2.3文氏图 79

6.2.4集合的幂集合 81

6.2.5多个集合的并与交 81

6.3全集和集合的补 82

6.3.1全集和集合的补 82

6.3.2基本运算定理 83

6.4自然数与自然数集 84

6.4.1后继 84

6.4.2自然数、自然数集 84

6.4.3皮亚诺公理假设 85

6.4.4自然数集的性质 86

6.4.5集合的归纳定义 87

6.5包含与排斥原理 87

6.6典型例题及解答 90

第7章 关系 94

7.1集合的笛卡儿积集 94

7.1.1有序二元组 94

7.1.2笛卡尔积集 94

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

7.2二元关系的基本概念 96

7.2.1二元关系 96

7.2.2二元关系的表示 96

7.2.3二元关系的交、并、差、对称差 97

7.2.4二元关系的逆与复合 97

7.3二元关系的性质 99

7.3.1自反性、反自反性、对称性、反对称性、传递性 99

7.3.2关于二元关系性质的判定定理 100

7.4二元关系的闭包运算 102

7.4.1自反闭包、对称闭包、传递闭包 102

7.4.2闭包的判定定理 103

7.5等价关系和集合的划分 106

7.5.1等价关系与等价类 106

7.5.2商集合 107

7.5.3集合的划分 108

7.6偏序关系和格 109

7.7典型例题及解答 112

第8章 函数与集合的势 118

8.1函数的基本概念 118

8.2函数的复合和可逆函数 120

8.3无限集 124

8.4集合势大小的比较 127

8.5鸽巢原理 128

8.6典型例题及解答 129

第9章 图 135

9.1图的基本概念 135

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

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

9.4欧拉图 143

9.5哈密尔顿图 146

9.6二部图 149

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

9.8典型例题及解答 154

第10章 树与有序树 160

10.1树的基本概念 160

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

10.3有序树 164

10.4前缀码和最优二分树 166

10.5典型例题及解答 169

第11章 群和环 172

11.1代数运算的基本概念 172

11.1.1代数运算 172

11.1.2交换律、结合律 173

11.1.3n元运算 175

11.2代数系统和半群 175

11.3群的基本概念 178

11.4群的几个等价定义 184

11.5变换群和置换群 186

11.6循环群 190

11.7子群，子集生成的子群 191

11.8子群的陪集 194

11.9正规子群、商群 198

11.10环和域 202

11.11典型例题及解答 204

第12章 格与布尔代数 210

12.1格定义的代数系统 210

12.2格的代数定义 212

12.3一些特殊的格 215

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

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

12.6典型例题及解答 224