目录CONTENTS

第1部分数 理 逻 辑

第0章逻辑绪论40.1逻辑4

0.2形式逻辑5

0.3推理分类5

第1章命题8

1.1命题8

1.2命题的表示10

第2章联结词11

2.1否定11

2.2合取11

2.3析取12

2.4条件14

2.5双条件16

2.6小结16

2.7联结词的应用17

2.8布尔代数17

第3章命题合式公式及符号化20

3.1命题合式公式20

3.2命题符号化的方法20

习题22

第4章等价公式25

4.1真值表25

4.2等价公式27

4.2.1等价27

4.2.2从真值表到等价式27

4.2.3等价公式27

4.3等价公式的应用28

4.3.1证明28

4.3.2化简29

4.3.3综合应用29

4.4公式类型30

4.5逻辑三大定律30

习题32

第5章范式34

5.1范式35

5.1.1基本概念35

5.1.2范式35

5.1.3性质36

5.1.4求范式的基本步骤36

5.1.5范式的应用37

5.2主范式38

5.2.1主析取范式38

5.2.2主析取范式的求法39

5.2.3主合取范式40

5.2.4主合取范式的求法42

5.3主析取范式与主合取范式的关系43

习题45

第6章主范式的应用46

6.1赋值46

6.2判断公式的类型47

6.3判断公式是否等价47

6.4实际应用48

习题51

第7章蕴含54

7.1重言式54

7.2蕴含式55

7.2.1蕴含55

7.2.2蕴含式的证明55

7.2.3常见的蕴含式56

7.3应用56

习题57

第8章命题逻辑推理58

8.1推理及分类58

8.2直接推理58

8.3条件论证60

8.4反证法61

8.5应用63

习题64

第9章谓词68

9.1谓词68

9.2谓词的表示68

9.3命题函数69

9.4量词70

习题70

第10章谓词公式及符号化72

10.1谓词合式公式72

10.2特性谓词73

10.3谓词符号化75

习题77

第11章谓词等价式与蕴含式78

11.1公式的分类78

11.2公式的等价79

11.3等价式和蕴含式79

11.4谓词公式赋值84

习题85

第12章前束范式87

12.1量词辖域87

12.2约束变元的改名89

12.3自由变元的代入89

12.4前束范式90

12.5前束析(合)取范式91

习题92

第13章谓词推理93

13.1推理规则94

13.2直接推理95

13.3条件论证96

13.4反证法97

13.5三段论98

13.5.1基本概念98

13.5.2三段论规则98

习题101

第14章综合应用——动物识别103

第2部分集合论

第15章集合10915.1基本概念109

15.2集合的性质110

15.3集合的运算110

习题111

第16章序偶与笛卡儿积113

16.1序偶113

16.2笛卡儿积114

16.2.1笛卡儿积的定义114

16.2.2笛卡儿积的性质116

16.2.3笛卡儿积的应用117

习题118

第17章二元关系及其表示119

17.1关系的表示120

17.2特殊关系121

习题122

第18章关系的性质123

18.1自反性124

18.2反自反性124

18.3对称性125

18.4反对称性125

18.5传递性126

习题128

第19章关系的运算131

19.1基本概念131

19.2复合运算132

19.2.1计算方法133

19.2.2性质134

19.3逆运算135

19.4幂运算136

习题136

第20章关系闭包138

20.1定义139

20.2自反闭包139

20.3对称闭包139

20.4传递闭包139

20.5传递闭包的求法140

20.5.1定义法140

20.5.2有向图法140

20.5.3Warshall算法141

习题146

第21章等价关系148

21.1等价关系148

21.2等价类149

21.3商集150

习题150

第22章相容关系153

22.1相容关系153

22.2简化图和简化矩阵154

22.3相容类及最大相容类155

22.4覆盖与划分155

22.5完全覆盖156

习题156

第23章偏序关系157

23.1偏序157

23.2哈斯图158

23.3重要元素160

23.3.1极小元与极大元160

23.3.2最小元与最大元161

23.3.3上界与下界161

23.3.4上确界与下确界162

习题162

第24章综合应用——家族族谱管理系统165

第25章函数168

25.1基本概念169

25.2函数的映射171

25.3复合函数173

25.4逆函数174

25.5函数运算的应用176

习题177

第26章康托尔定理179

26.1基数179

26.1.1集合的势180

26.1.2有限集与无限集182

26.1.3集合的基数183

26.2可数集与不可数集185

26.3康托尔定理186

26.4ZFC公理188

26.4.1康托尔悖论188

26.4.2罗素悖论188

26.4.3ZFC公理体系189

26.4.4三次数学危机190

习题190

第3部分代 数 系 统

第27章代数系统19527.1基本概念195

27.2运算符与运算表196

27.3特殊运算197

27.3.1模k加法197

27.3.2模k乘法197

习题198

第28章运算及性质202

28.1运算性质203

28.2特殊元素204

习题207

第29章群209

29.1群的定义210

29.2子群212

29.3阿贝尔群与循环群213

29.4拉格朗日定理215

29.4.1陪集215

29.4.2拉格朗日定理216

29.5置换群218

29.6群与对称性220

29.6.1对称221

29.6.2对称的数学表示223

习题225

第30章同态与同构228

习题230

第31章环与域232

31.1基本概念232

31.2环在密码学中的应用234

习题234

第32章格238

32.1格的概念238

32.2格的对偶原理240

32.3格的性质240

32.4格的同态与同构243

32.5子格245

第33章分配格247

33.1分配格247

33.2模格249

第34章有补格251

34.1有界格251

34.2有补格252

第35章布尔代数253

35.1布尔代数253

35.2布尔表达式254

35.3布尔表达式的范式256

习题258

第4部分图论

第36章基本概念26636.1图的基本概念266

36.2通路与回路271

36.3图的连通性272

习题274

第37章图的矩阵存储275

37.1关联矩阵275

37.2邻接矩阵276

37.3可达矩阵277

习题278

第38章欧拉图280

38.1无向欧拉图281

38.2一笔画284

38.3有向欧拉图286

习题287

第39章哈密顿图289

39.1基本概念290

39.2判断方法290

39.3旅行商问题292

习题293

第40章二分图294

40.1基本概念294

40.2匈牙利算法295

40.3推荐系统297

40.3.1基于用户的协同过滤算法298

40.3.2基于项目的协同过滤算法300

习题305

第41章平面图及着色306

41.1平面图306

41.2对偶图310

41.3图的着色311

习题313

第42章最小生成树314

42.1基本概念314

42.2Kruskal算法315

42.3Prim算法319

习题322

第43章最短路径323

43.1基本概念323

43.2Dijkstra算法324

43.3FloydWarshall算法330

43.3.1传递闭包Warshall算法331

43.3.2FloydWarshall算法331

43.4FloydWarshall算法与Dijkstra算法比较332

习题333

参考文献334