第1章集合、映射与运算1

1.1集合的有关概念1

1.1.1集合1

1.1.2子集3

1.1.3幂集4

1.1.4n元组4

1.1.5笛卡儿积5

习题1.15

1.2映射的有关概念6

1.2.1映射的定义6

1.2.2映射的性质8

1.2.3逆映射9

1.2.4复合映射10

习题1.212

1.3运算的定义及性质13

1.3.1运算的定义13

1.3.2运算的性质16

习题1.321

1.4集合的运算22

1.4.1并运算22

1.4.2交运算22

1.4.3补运算24

1.4.4差运算25

1.4.5对称差运算26

习题1.427

1.5集合的划分与覆盖28

1.5.1集合的划分29

1.5.2集合的覆盖30

习题1.531

1.6集合的对等31

1.6.1集合对等的定义31

1.6.2无限集合32

1.6.3集合的基数32

1.6.4可数集合33

1.6.5不可数集合33

1.6.6基数的比较34

习题1.634

本章小结35第2章关系37

2.1关系的概念37

2.1.1n元关系的定义37

2.1.22元关系38

2.1.3关系的定义域和值域41

2.1.4关系的表示42

2.1.5函数的关系定义43

习题2.144

2.2关系的运算46

2.2.1关系的集合运算46

2.2.2关系的逆运算46

2.2.3关系的复合运算47

2.2.4关系的其他运算50

习题2.251

2.3关系的性质51

2.3.1自反性51

2.3.2反自反性52

2.3.3对称性53

2.3.4反对称性54

2.3.5传递性55

习题2.357

2.4关系的闭包58

2.4.1自反闭包r(R)58

2.4.2对称闭包s(R)59

2.4.3传递闭包t(R)60

习题2.463

2.5等价关系64

2.5.1等价关系的定义64

2.5.2等价类65

习题2.567

2.6相容关系68

2.6.1相容关系的定义68

2.6.2相容类69

习题2.670

2.7偏序关系70

2.7.1偏序关系的定义70

2.7.2偏序集的哈斯图72

2.7.3偏序集中的特殊元素73

习题2.775

本章小结76第3章命题逻辑79

3.1命题的有关概念79

习题3.181

3.2逻辑联结词81

3.2.1否定联结词?瘙
綈p82

3.2.2合取联结词p∧q82

3.2.3析取联结词p∨q82

3.2.4异或联结词pq83

3.2.5条件联结词p→q83

3.2.6双条件联结词pq84

3.2.7与非联结词p↑q84

3.2.8或非联结词p↓q85

3.2.9条件否定联结词p→nq85

习题3.285

3.3命题公式及其真值表85

3.3.1命题公式的定义85

3.3.2命题的符号化86

3.3.3命题公式的真值表87

3.3.4命题公式的类型88

习题3.389

3.4逻辑等值的命题公式90

3.4.1逻辑等值的定义90

3.4.2基本等值式91

3.4.3等值演算法93

3.4.4对偶原理94

习题3.494

3.5命题公式的范式95

3.5.1命题公式的析取范式及合取范式96

3.5.2命题公式的主析取范式及主合取范式98

习题3.5104

3.6联结词集合的功能完备性105

3.6.1联结词的个数105

3.6.2功能完备联结词集106

习题3.6108

3.7命题逻辑中的推理108

3.7.1推理形式有效性的定义108

3.7.2基本推理规则110

3.7.3命题逻辑的自然推理系统111

习题3.7114

本章小结115第4章谓词逻辑118

4.1个体、谓词、量词和函词118

4.1.1个体118

4.1.2谓词119

4.1.3量词119

4.1.4函词121

习题4.1121

4.2谓词公式及命题的符号化122

4.2.1谓词公式122

4.2.2命题的符号化122

习题4.2124

4.3谓词公式的解释及类型126

4.3.1谓词公式的解释126

4.3.2谓词公式的类型127

习题4.3127

4.4逻辑等值的谓词公式129

4.4.1谓词公式等值的定义129

4.4.2基本等值式129

习题4.4131

4.5谓词公式的前束范式131

4.5.1谓词公式的前束范式的定义131

4.5.2谓词公式的前束范式的计算132

习题4.5132

4.6谓词逻辑中的推理133

4.6.1逻辑蕴涵式133

4.6.2基本推理规则133

4.6.3谓词逻辑的自然推理系统134

习题4.6136

本章小结137第5章代数结构140

5.1代数结构简介140

5.1.1代数结构的定义140

5.1.2两种最简单的代数结构: 半群及独异点141

5.1.3子代数142

5.1.4代数结构的同态与同构142

习题5.1144

5.2群的定义及性质145

5.2.1群的有关概念146

5.2.2子群148

5.2.3群的同态148

习题5.2149

5.3环和域150

5.3.1环的定义150

5.3.2几种特殊的环150

5.3.3域的定义152

5.3.4有限域152

习题5.3153

5.4格与布尔代数154

5.4.1格的定义和性质155

5.4.2分配格158

5.4.3有补格158

5.4.4布尔代数160

习题5.4162

本章小结163第6章图论165

6.1图的基本概念165

6.1.1图的定义165

6.1.2邻接167

6.1.3关联167

6.1.4简单图167

习题6.1168

6.2节点的度数169

习题6.2171

6.3子图、图的运算和图同构171

6.3.1子图171

6.3.2图的运算173

6.3.3图同构173

习题6.3174

6.4路与回路175

6.4.1路175

6.4.2回路176

习题6.4176

6.5图的连通性177

6.5.1无向图的连通性177

6.5.2无向连通图的点连通度与边连通度178

6.5.3有向图的连通性180

习题6.5181

6.6图的矩阵表示182

6.6.1图的邻接矩阵182

6.6.2图的可达矩阵183

6.6.3图的关联矩阵184

习题6.6185

6.7赋权图及最短路径186

6.7.1赋权图186

6.7.2最短路径186

习题6.7188

本章小结189第7章几类特殊的图191

7.1欧拉图191

7.1.1欧拉图的有关概念191

7.1.2欧拉定理191

7.1.3中国邮递员问题192

习题7.1193

7.2哈密尔顿图194

7.2.1哈密尔顿图的有关概念194

7.2.2哈密尔顿图的必要条件195

7.2.3哈密尔顿图的充分条件195

7.2.4旅行商问题197

习题7.2197

7.3无向树198

7.3.1无向树的定义198

7.3.2无向树的性质199

7.3.3生成树200

7.3.4最小生成树201

习题7.3202

7.4有向树202

7.4.1有向树的定义203

7.4.2根树203

7.4.3m叉树204

7.4.4有序树206

7.4.5定位二叉树207

习题7.4209

7.5平面图210

7.5.1平面图的有关概念211

7.5.2欧拉公式212

7.5.3库拉托夫斯基定理212

7.5.4平面图的对偶图213

习题7.5214

7.6平面图的面着色215

7.6.1平面图的面着色定义215

7.6.2图的节点着色216

7.6.3任意图的边着色217

习题7.6218

7.7二部图及其匹配218

7.7.1二部图218

7.7.2匹配219

习题7.7220

本章小结221第8章组合计数223

8.1计数原理、排列组合与二项式定理223

8.1.1计数原理223

8.1.2排列224

8.1.3组合225

8.1.4二项式定理226

习题8.1226

8.2生成函数227

8.2.1组合计数生成函数227

8.2.2排列计数生成函数229

习题8.2230

8.3递归关系231

8.3.1递归关系的概念231

8.3.2常用的递归关系求解方法232

习题8.3237

本章小结237附录A符号索引239附录B中英文名词索引242附录C习题答案及提示247参考文献270