内容简介

本书系统介绍了离散数学的基础定义、定理及性质等基础知识，着重引导学生认识离散数学与计算机专业课程之间的密切关系。例题选择在传统经典题型基础上尽可能靠近计算机专业所学内容。每章的算法思想描述尽可能让学生更直观地认识离散数学理论与计算机专业之间的联系，从而理解计算机思维。

全书共分为四部分: 第一部分（第1～3章）为集合论，着重介绍了集合、关系和映射；第二部分（第4、5章）为数理逻辑，着重介绍了命题逻辑和谓词逻辑;第三部分（第6～8章）为图论，着重介绍了图、欧拉图和哈密尔顿图、树、二部图和平面图等特殊图；第四部分（第9～11章）为代数系统，着重介绍了代数结构、环与域、格与布尔代数。每节后分级设计了课后习题，并附有题库平台，提供更多习题以及解答。

本书适合作为高等院校计算机相关专业本科生、大专生的教材或参考书，特别是作为离散数学教学改革探索者的教材或参考书。

编辑推荐

充分考虑应用型本科人才培养的需求，更加侧重于学生逻辑思维能力的培养，同时兼顾学生继续深造的需求，在重要知识的学习之后附加分级练习题：A类基础题、B类综合题和C类考研真题，为不同学习目的同学提供针对性训练。

在每个章节中的末尾用学科思维导图归纳总结章节内容，

并给出相关知识点的算法思想表示，

使学生在掌握离散数学基础概念的基础上，理解相关概念在计算机中的表示形式，所学有所用，更深刻理解离散数学在计算机相关专业课程中的重要作用。

目录

绪论离散数学与计算机

绪论离散数学与计算机1

第一部分集合论

第1章集合7

1.1集合的概念与表示7

1.1.1集合的概念7

1.1.2集合的元素8

1.1.3集合的表示方法8

1.1.4集合之间的关系10

习题1.111

1.2集合的运算12

1.2.1交运算12

1.2.2并运算12

1.2.3补运算13

1.2.4差运算14

1.2.5对称差运算14

习题1.215

1.3集合的划分与覆盖16

1.3.1集合的划分16

1.3.2集合的覆盖17

习题1.317

1.4容斥原理18

习题1.421

1.5集合的思维导图22

1.6集合的算法思想23

1.6.1求任意一个集合的幂集23

1.6.2求任意两个集合的交集、并集、差集23

1.7本章小结23

第2章关系24

2.1有序n元组24

习题2.125

2.2笛卡儿积25

2.2.1笛卡儿积的定义25

2.2.2笛卡儿积的性质27

习题2.229

2.3二元关系30

2.3.1二元关系的概念30

2.3.2二元关系的表示32

习题2.333

2.4关系的运算34

2.4.1关系的集合运算34

2.4.2关系的复合运算35

2.4.3关系的逆运算37

习题2.437

2.5关系的性质38

2.5.1自反性39

2.5.2反自反性40

2.5.3对称性42

2.5.4反对称性43

2.5.5传递性44

习题2.549

2.6关系的闭包50

2.6.1自反闭包r(R)50

2.6.2对称闭包s(R)51

2.6.3传递闭包t(R)52

2.6.4闭包之间的关系54

习题2.655

2.7等价关系和等价类56

2.7.1等价关系56

2.7.2等价类57

习题2.760

2.8相容关系和相容类61

2.8.1相容关系61

2.8.2相容类62

习题2.864

2.9偏序关系64

2.9.1偏序关系的定义64

2.9.2哈斯图及特殊元素65

2.9.3全序关系70

2.9.4良序关系71

2.9.5拟序关系71

习题2.971

2.10关系的思维导图73

2.11关系的算法思想74

2.11.1求任意个元素的全排列74

2.11.2求笛卡儿积74

2.11.3判断关系性质及类型算法74

2.11.4求等价类75

2.11.5求极大相容类75

2.11.6求关系的闭包75

2.12本章小结76

第3章映射77

3.1映射的基本概念77

习题3.179

3.2映射的性质80

3.2.1单射80

3.2.2满射80

3.2.3双射81

习题3.282

3.3映射的复合运算82

习题3.384

3.4映射的逆运算85

习题3.486

3.5映射的思维导图87

3.6映射的算法思想87

3.6.1映射的判定87

3.6.2求满射88

3.7本章小结88

第二部分数 理 逻 辑

第4章命题逻辑91

4.1命题91

习题4.193

4.2联结词94

4.2.1否定联结词94

4.2.2合取联结词∧（与）95

4.2.3析取联结词∨（或）95

4.2.4不可兼析取联结词∨（异或）96

4.2.5条件联结词→97

4.2.6双条件联结词98

4.2.7与非联结词↑98

4.2.8或非联结词↓98

4.2.9条件否定联结词n99

4.2.10联结词与集合运算之间的关系99

习题4.2101

4.3命题公式101

4.3.1命题公式的定义101

4.3.2命题公式的符号化102

4.3.3命题公式的解释104

4.3.4命题公式的真值表105

4.3.5命题公式的类型106

习题4.3106

4.4命题公式的逻辑等值107

4.4.1命题公式逻辑等值的定义107

4.4.2命题公式基本的逻辑等值式108

4.4.3命题公式的等值演算110

4.4.4命题公式的对偶定理113

习题4.4113

4.5范式114

4.5.1析取范式与合取范式114

4.5.2主析取范式与主合取范式116

4.5.3主范式的应用122

习题4.5124

4.6命题公式的逻辑蕴涵125

4.6.1逻辑蕴涵的定义125

4.6.2蕴涵式的证明方法126

4.6.3基本的逻辑蕴涵式128

习题4.6129

4.7全功能联结词与极小联结词组129

习题4.7130

4.8命题逻辑推理131

4.8.1命题逻辑推理理论131

4.8.2推理规则131

4.8.3判断有效结论的常用方法133

习题4.8137

4.9命题逻辑的思维导图138

4.10命题逻辑的算法思想——求任意一个命题公式的真值表139

4.11本章小结140

第5章谓词逻辑141

5.1谓词逻辑的相关概念141

5.1.1个体词与谓词141

5.1.2量词143

习题5.1144

5.2谓词公式145

5.2.1谓词公式的定义145

5.2.2谓词公式的符号化146

5.2.3谓词的约束与替换148

5.2.4谓词公式的解释151

5.2.5谓词公式的类型152

习题5.2153

5.3谓词公式的逻辑等值154

5.3.1谓词公式逻辑等值的定义154

5.3.2谓词公式基本的逻辑等值式155

习题5.3158

5.4谓词公式的前束范式158

5.4.1谓词公式前束范式的定义158

5.4.2谓词公式前束范式的计算159

习题5.4160

5.5谓词公式的逻辑蕴涵160

习题5.5163

5.6谓词逻辑的推理164

5.6.1谓词逻辑中的逻辑蕴涵式164

5.6.2谓词逻辑的推理规则164

5.6.3谓词逻辑的自然推理系统165

习题5.6168

5.7谓词逻辑的思维导图169

5.8本章小结170

第三部分图论

第6章图173

6.1图的基本概念173

6.1.1图174

6.1.2子图176

6.1.3通路与回路177

6.1.4图的同构179

习题6.1180

6.2结点的度181

6.2.1结点的度的概念181

6.2.2握手定理及其推论181

习题6.2182

6.3图的连通性183

6.3.1无向图的连通性183

6.3.2有向图的连通性186

习题6.3188

6.4图的矩阵表示189

6.4.1邻接矩阵189

6.4.2可达矩阵190

6.4.3关联矩阵193

习题6.4195

6.5图的应用196

6.5.1加权图的最短通路196

6.5.2加权图的关键路径200

习题6.5202

6.6图的思维导图203

6.7图的算法思想204

6.7.1图的可达矩阵算法204

6.7.2有向图的所有强分支算法204

6.7.3有向图的所有单向分支算法204

6.7.4图的所有割点算法205

6.7.5图的所有割边算法205

6.7.6发点到其他各点的所有最短通路算法206

6.7.7求两点间最短通路的WarshallFloyd算法207

6.7.8图的所有关键路径算法207

6.8本章小结208

……