离散数学基础

图书标准信息

• 作者 周晓聪；乔海燕
• 出版社 清华大学出版社
• 出版时间 2021-05
• 版次 1
• ISBN 9787302576679
• 定价 79.80元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸

【内容简介】

本书面向“新工科”建设背景下普通高等学校的计算机类和软件工程专业类的本科生，以培养学生离散建模基础能力为目标，论述逻辑、证明、集合、函数、关系、算法、整数与同余、组合计数、图论以及代数系统相关基础知识，覆盖Computer Science Curricula 2013离散结构知识体的所有知识单元。与传统离散数学教材相比，

【作者简介】

周晓聪，中山大学数据科学与计算机学院副教授、硕士生导师。长期从事离散数学、程序设计等本科生课程教学，获得广东省教学成果奖2项，与人合作编著和翻译教材、辅助教材5部，发表教学论文多篇。

【目录】

第1 章  基础知识  1

1.1  逻辑语言 1

1.2  集合语言 5

1.3  图论语言 9

1.4  代数语言 13

1.5  算法语言 14

1.6  本章小结 20

1.7  习题  21

第2 章  命题逻辑 24

2.1  命题逻辑的基本概念  24

2.1.1  命题与真值 24

2.1.2  原子命题与复合命题 25

2.2  命题逻辑公式的语法  25

2.2.1  命题逻辑公式的定义 26

2.2.2  命题逻辑公式的语法性质 28

2.2.3  命题逻辑公式的简写 31

2.3  命题逻辑公式的语义  32

2.3.1  命题逻辑公式的真值定义 32

2.3.2  命题逻辑公式的真值表 35

2.3.3  命题逻辑公式的分类 37

2.4  命题逻辑的等值演算  40

2.4.1  命题逻辑公式的逻辑等值 40

2.4.2  基本逻辑等值式 41

2.4.3  命题逻辑公式的范式 44

2.5  命题逻辑的推理理论  48

2.5.1  推理的有效性 49

2.5.2  命题逻辑的自然推理系统 50

2.5.3  构造验证推理有效性的论证  54

2.6  命题逻辑的应用 60

2.6.1  自然语言命题的符号化 60

2.6.2  普通逻辑问题的符号化分析  67

2.6.3  算法性质的逻辑分析 73

2.7  本章小结  75

2.8  习题 75

第3 章  一阶逻辑  81

3.1  一阶逻辑的基本概念 81

3.2  一阶逻辑公式的语法 83

3.2.1  一阶逻辑公式的符号 83

3.2.2  一阶逻辑公式的定义 84

3.2.3  自由变量和约束变量 86

3.3  一阶逻辑公式的语义 89

3.3.1  一阶逻辑公式的解释 89

3.3.2  一阶逻辑公式的真值 91

3.3.3  一阶逻辑公式的分类 97

3.4  一阶逻辑的等值演算 100

3.4.1  一阶逻辑公式的逻辑等值 100

3.4.2  量词公式的基本等值式 103

3.4.3  一阶逻辑的前束范式 106

3.5  一阶逻辑的推理理论 110

3.5.1  一阶逻辑推理的有效性 110

3.5.2  量词公式的推理规则 112

3.5.3  一阶逻辑的自然推理举例 116

3.6  一阶逻辑的应用  121

3.6.1  自然语言命题的符号化 122

3.6.2  自然语言推理有效性的验证 128

3.6.3  算法性质的逻辑分析 130

3.7  本章小结 133

3.8  习题 134

第4 章  证明方法 139

4.1  数学证明导引 139

4.2  基本证明方法与策略 141

4.2.1  直接证明与间接证明 142

4.2.2  分情况证明  146

4.2.3  存在性证明  149

4.2.4  基本证明策略  152

4.3  归纳定义与归纳证明 154

4.3.1  数学归纳法与良序原理 154

4.3.2  归纳定义与结构归纳法 161

4.3.3  递归算法与归纳证明 168

4.4  本章小结 172

4.5  习题 173

第5 章  集合 179

5.1  集合的基本概念  179

5.1.1  集合的基本术语  179

5.1.2  定义集合的基本方法 181

5.1.3  文氏图与成员关系表 184

5.2  集合运算 186

5.2.1  集合交  187

5.2.2  集合并  190

5.2.3  集合差与补  192

5.2.4  集合的幂集  194

5.2.5  集合运算的算法  195

5.3  集合等式 197

5.3.1  基于定义证明集合等式 197

5.3.2  集合等式演算  200

5.3.3  子集关系与集合等式 202

5.4  本章小结 206

5.5  习题 206

第6 章  关系 210

6.1  关系的基本概念  210

6.1.1  集合的笛卡儿积  210

6.1.2  关系的定义  212

6.1.3  关系的表示  214

6.1.4  关系的运算  216

6.2  关系的性质 222

6.2.1  关系的自反性与反自反性 223

6.2.2  关系的对称性与反对称性 225

6.2.3  关系的传递性  228

6.2.4  关系性质与关系运算 230

6.3  关系的闭包 233

6.3.1  关系闭包的定义  233

6.3.2  关系闭包的计算  235

6.3.3  Warshall 算法 240

6.4  特殊关系举例 242

6.4.1  等价关系 242

6.4.2  偏序关系 247

6.5  本章小结 252

6.6  习题 253

第7 章  函数 259

7.1  函数的基础知识  259

7.1.1  函数的基本概念  259

7.1.2  函数的性质  263

7.1.3  函数运算与函数的性质 266

7.2  集合基数的基础知识 270

7.2.1  集合等势  270

7.2.2  有穷集与无穷集  272

7.2.3  可数集与不可数集  276

7.3  函数的增长与算法效率分析 280

7.3.1  函数的增长  281

7.3.2  算法效率分析基础  287

7.3.3  算法复杂度基础知识 293

7.4  本章小结 295

7.5  习题 296

第8 章  计数与组合 301

8.1  组合计数的基本原理 301

8.1.1  加法原理和乘法原理 301

8.1.2  容斥原理  307

8.1.3  鸽笼原理  312

8.2  排列与组合 316

8.2.1  排列与组合的基本定义 316

8.2.2  二项式定理与组合等式 323

8.2.3  允许重复的排列与组合 328

8.2.4  再论容斥原理及其应用 333

8.2.5  排列与组合的生成算法 338

8.3  递推关系式 342

8.3.1  计数问题的递推关系式建模 342

8.3.2  线性递推关系式求解 347

8.3.3  分治算法与递推关系式 352

8.4  本章小结 355

8.5  习题 356

第9 章  图与树 362

9.1  图的基础知识 362

9.1.1  图的基本概念  362

9.1.2  图的连通性  368

9.1.3  图的表示与存储  373

9.1.4  无向图的遍历  377

9.2  树的基础知识 382

9.2.1  无向树的定义  382

9.2.2  根树的定义  384

9.2.3  树的遍历  386

9.3  带权图及其应用  390

9.3.1  带权图的最短距离  390

9.3.2  带权图的最小生成树 395

9.3.3  哈夫曼树  398

9.4  一些特殊的图 402

9.4.1  平面图  403

9.4.2  欧拉图  406

9.4.3  哈密顿图  407

9.5  本章小结 409

9.6  习题 410

第10章  代数系统 419

10.1  运算及其性质 419

10.1.1  运算的定义 419

10.1.2  运算的性质 422

10.1.3  运算性质的判定 427

10.2  代数及同态 430

10.2.1  代数与子代数 430

10.2.2  同余关系与商代数 432

10.2.3  代数同态与同构 436

10.3  群的基础知识 441

10.3.1  群的定义  442

10.3.2  群元素的阶  445

10.3.3  子群与陪集  446

10.3.4  正规子群与商群  452

10.3.5  群同态  453

10.4  格与布尔代数 455

10.4.1  格的偏序定义与代数定义 455

10.4.2  分配格与有界格 458

10.4.3  布尔代数  460

10.5  本章小结  462

10.6  习题 463

第11章  结束语  468

参考文献 471