离散数学（第3版）

经典教材改版，内容易懂、易学，提供课件、教学大纲、习题答案

 

主要内容包括离散数学中的集合论、数理逻辑与图论相关的基础内容，它是学习后续专业课程不可缺少的数学基础。该教材结合计算机学科的特点，主要研究离散量结构及相互关系，是一本将理论与应用相结合的教材。本教材适合普通高等院校的计算机专业以及与计算机相关的专业作为专业基础课的教材。

谢美萍，博士，副教授，研究生导师，2001年7月毕业于哈尔滨工程大学控制理论与控制工程专业，获博士学位，2001年8月进入上海财经大学信息管理与工程学院任教，任教以来主讲过《离散数学》、《计算机应用》、《数据挖掘》等课程，主持财经院校中的《离散数学》课程建设（上海财经大学重点课程建设项目）教学研究课题。主编了由清华大学出版社出版的《离散数学》与《离散数学》习题集。

第1章  集合

1.1  集合的基本概念

1.1.1  集合的概念

1.1.2  集合的特性

1.1.3  集合的表示方法

1.2  集合间的关系

1.2.1  包含关系

1.2.2  相等关系

1.2.3  特殊集合

1.3  集合的运算

1.3.1  集合的基本运算

1.3.2  有限集合的计数

1.4  幂集和编码

1.4.1  幂集

1.4.2  幂集元素与编码

1.5  集合恒等式证明

1.5.1  基本定义法

1.5.2  公式法

1.5.3  集合成员表法

习题

 

第2章  关系

2.1  关系的基本概念

2.2  关系的表示方法

2.3  关系的运算

2.4  关系的性质

2.4.1  关系的五种性质

2.4.2  关系性质的证明

2.5  关系的闭包

2.6  等价关系与划分

2.6.1  等价关系

2.6.2  集合的划分

2.6.3  划分与等价关系

2.7  偏序关系

2.7.1  偏序的定义及表示

2.7.2  偏序集中的特殊元素

2.7.3  全序集与良序集

习题

 

第3章  函数

3.1  函数的基本概念

3.2  特殊函数

3.3  复合函数与逆函数

3.3.1  复合函数

3.3.2  逆函数

习题

 

第4章  命题逻辑

4.1  命题与命题连接词

4.1.1  命题与真值

4.1.2  命题连接词

4.2  命题公式与真值表

4.3  命题公式的等价关系和蕴涵关系

4.3.1  命题公式的等价关系

4.3.2  命题公式的蕴涵关系

4.4  命题公式的范式表示

4.4.1  析取范式与合取范式

4.4.2  主范式

4.4.3  主范式的应用

4.5  命题演算的推理理论

4.5.1  推理形式

4.5.2  推理规则

习题

 

第5章  一阶谓词逻辑

5.1  一阶谓词逻辑的基本概念

5.1.1  谓词、个体词和个体域

5.1.2  量词

5.1.3  换名规则与代入规则

5.2  谓词公式及其解释

5.2.1  谓词公式的定义

5.2.2  谓词公式的解释

5.2.3  谓词公式的分类

5.3  谓词公式之间的关系与范式表示

5.3.1  谓词公式之间的关系

5.3.2  范式

5.3.3  斯柯林范式

5.4  谓词演算的推理理论

5.4.1  推理规则

5.4.2  推理规则实例

习题

 

第6章  图

6.1  图的基本概念

6.1.1  图的定义

6.1.2  顶点的度数

6.1.3  子图

6.1.4  并图、交图、差图

6.1.5  完全图、补图、正则图、带权图

6.1.6  图的同构

6.2  通路、回路和连通图

6.2.1  通路与回路

6.2.2  连通图

6.3  图的连通性

6.4  图的矩阵表示

6.4.1  邻接矩阵

6.4.2  关联矩阵

6.4.3  可达矩阵

习题

 

第7章  特殊图

7.1  欧拉图及其应用

7.1.1  欧拉图

7.1.2  欧拉图的应用

7.2  哈密顿图及其应用

7.2.1  哈密顿图

7.2.2  闭图

7.3  二分图

7.4  平面图与对偶图

7.4.1  平面图

7.4.2  对偶图

7.5  平面图的着色

7.5.1  图的顶点着色

7.5.2  图的边着色

7.5.3  平面图的应用

7.6  树与生成树

7.6.1  无向树

7.6.2  生成树

7.6.3  小生成树

7.6.4  有向树

习题

 

参考文献

 

离散数学是计算机专业的一门重要的基础课程，它是研究离散的数量关系与离散的数学结构模型的数学学科，也是现代数学的一个重要分支。 离散数学在许多学科领域有着广泛的应用，尤其是计算机领域。离散数学可以看成是构筑在数学和计算机科学之间的桥梁，因为离散数学既离不开集合论、图论等数学知识，又和计算机科学中的数据库理论、数据结构等相关，它可以引导人们进入计算机科学的思维领域，促进计算机科学的发展。

离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中； 同时，该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于培养学生严谨、完整、规范的科学态度，为将来参与创新性的研究和研发工作打下坚实的理论基础。

本教材是在2008年第1版与2014年第2版的基础上，对主要内容进行了详细的阐述，并适当地增加了一些例题以加深理解，这样比较适合于学时少以及非计算机专业的学生使用，在这之前的教材以及习题集都可以继续使用。
本教材具有以下主要特色。
（1） 从集合理论出发，将离散数学的主要内容有机地集合在一起。前后呼应，各部分又可以独立使用。
（2） 强化基本概念和基本性质的论述，在内容阐述时力求深入浅出，注重基本理论的证明，并在每章结束后配备适当数量的习题供读者练习，目的在于启发和培养读者的抽象思维能力和逻辑推理能力，也使得本教材具备一定的理论深度。
（3） 配备了完整的教学课件，供教师上课时使用。

本书第1、2、3章由谢美萍编写，第4、5章由陈媛编写，第6、7章由南通理工学院基础教学学院徐希编写。在本书的编写过程中参阅了大量的离散数学教材与相关资料，在此向作者们表示衷心的感谢。
在编写过程中，会有一些不足与疏漏之处，恳请同行专家与广大读者批评指正。

编著者
2020年7月