内容简介

本书面向“新工科”建设背景下普通高等学校的计算机类和软件工程专业类的本科生，以培养学生离散建模基础能力为目标，论述逻辑、证明、集合、函数、关系、算法、整数与同余、组合计数、图论以及代数系统相关基础知识，覆盖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