离散数学

图书标准信息

• 作者 吴昊；梁艳春；李雄飞；郭夕敬；冯广慧；林刚；马蕊；王舒
• 出版社 清华大学出版社
• 出版时间 2022-09
• 版次 1
• ISBN 9787302612469
• 定价 69.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸

【内容简介】

本书系统介绍了离散数学的基础定义、定理及性质等基础知识，着重引导学生认识离散数学与计算机专业课程之间的密切关系。例题选择在传统经典题型基础上尽可能靠近计算机专业所学内容。每章的算法思想描述尽可能让学生更直观地认识离散数学理论与计算机专业之间的联系，从而理解计算机思维。 全书共分为四部分: 第一部分（第1～3章）为集合论，着重介绍了集合、关系和映射；第二部分（第4、5章）为数理逻辑，着重介绍了命题逻辑和谓词逻辑;第三部分（第6～8章）为图论，着重介绍了图、欧拉图和哈密尔顿图、树、二部图和平面图等特殊图；第四部分（第9～11章）为代数系统，着重介绍了代数结构、环与域、格与布尔代数。每节后分级设计了课后习题，并附有题库平台，提供更多习题以及解答。 本书适合作为高等院校计算机相关专业本科生、大专生的教材或参考书，特别是作为离散数学教学改革探索者的教材或参考书。

【目录】

绪论离散数学与计算机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〖1〗〖2〗离散数学目录〖2〗〖2〗第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

第7章 欧拉图与哈密尔顿图209

7.1欧拉图209

7.1.1欧拉图的定义209

7.1.2欧拉图的判定210

7.1.3欧拉图的应用212

习题7.1215

7.2哈密尔顿图216

7.2.1哈密尔顿图的定义216

7.2.2哈密尔顿图的判定217

7.2.3哈密尔顿图的应用220

习题7.2221

7.3欧拉图和哈密尔顿图的思维导图223

7.4欧拉图和哈密尔顿图的算法思想224

7.4.1求欧拉回路的算法224

7.4.2判断一个图是否为哈密尔顿图224

7.5本章 小结225

第8章 特殊图226

8.1树226

8.1.1无向树226

8.1.2生成树与最小生成树228

8.1.3有向树与根树232

8.1.4k叉树与有序树233

习题8.1238

8.2二部图239

8.2.1二部图的概念239

8.2.2二部图的匹配241

习题8.2243

8.3平面图244

8.3.1平面图的概念244

8.3.2欧拉公式245

8.3.3平面图的判定247

8.3.4平面图的着色248

习题8.3253

8.4特殊图的思维导图254

8.5特殊图的算法思想255

8.5.1求Huffman树255

8.5.2求无（有）向图的生成树的算法256

8.5.3求最小生成树的两种算法: Kruskal算法、Prim算法256

8.5.4广度优先搜索算法257

8.5.5深度优先搜索算法257

8.5.6二叉树的遍历258

8.5.7二部图的所有完备匹配算法259

8.5.8图的着色算法259

8.6本章 小结259

第四部分 代 数 系 统

第9章 代数结构263

9.1代数系统的定义263

9.1.1代数运算263

9.1.2代数系统266

习题9.1267

9.2代数系统的性质267

9.2.1交换律267

9.2.2结合律268

9.2.3分配律268

9.2.4吸收律268

9.2.5幂等律269

9.2.6单位元（幺元）269

9.2.7零元270

9.2.8逆元270

9.2.9消去律272

习题9.2274

9.3代数系统的同态与同构275

习题9.3278

9.4半群与独异点279

9.4.1半群279

9.4.2独异点280

习题9.4282

9.5群283

9.5.1群的定义283

9.5.2群的性质285

习题9.5286

9.6子群287

9.6.1子群的定义287

9.6.2子群的判定287

习题9.6289

9.7特殊的群289

9.7.1阿贝尔群289

9.7.2循环群291

9.7.3置换群293

习题9.7296

9.8群的同态与同构297

习题9.8299

9.9代数系统的思维导图300

9.10代数系统的算法思想301

9.11本章 小结301

第10章 环与域302

10.1环302

10.1.1环的概念302

10.1.2子环与理想305

10.1.3环的同态与同构306

习题10.1307

10.2域307

10.2.1域的概念307

10.2.2有限域309

10.2.3域的同态与同构309

习题10.2310

10.3环与域的思维导图311

10.4本章 小结312

第11章 格与布尔代数313

11.1格的定义和性质313

11.1.1格的定义313

11.1.2格的对偶原理314

11.1.3格的性质315

习题11.1316

11.2子格与格同态317

11.2.1子格317

11.2.2格同态与格同构317

习题11.2318

11.3几种特殊的格319

11.3.1分配格319

11.3.2模格321

11.3.3有界格321

11.3.4有补格322

习题11.3323

11.4布尔代数324

11.4.1布尔代数的定义324

11.4.2布尔代数的性质325

11.4.3布尔代数的同态与同构326

习题11.4328

11.5格与布尔代数的思维导图329

11.6本章 小结330

附录1符号索引331

附录2相关数学概念333