离散数学

第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〖1〗离 散 数 学 〖1〗目录 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.4Prolog简介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.3n元关系及其运算125

7.3.1n元关系125

7.3.2n元关系的运算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.3n元运算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