本书依据编者多年的教学经验编写而成，着重介绍离散数学的基本概念、方法及应用。本书共5章，内容包括命题逻辑、谓词逻辑、集合论、图论以及离散数学的应用举例等。各章均配有典型例题，并对解题方法进行了系统分析与阐述。
本书侧重概念的具体应用，弱化了定理的抽象证明，简化了离散数学中部分理论性过强、过于抽象的内容，既可作为办学层次一般的普通高等院校计算机类专业的离散数学教材，也可供其他专业学生参考。
离散数学（discrete mathematics）是专门研究离散量的结构和相互间关系的数学学科，是现代数学的一个重要分支。离散数学在各学科领域，特别在计算机科学与技术领域有着广泛的应用。离散数学也是计算机类专业重要的专业基础课程，其基本概念、基本思想和方法与计算机科学中的高级语言程序设计、数据结构、操作系统、编译原理、人工智能、数据库原理与技术、算法设计与分析等课程联系紧密。通过对离散数学的学习，学生不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维能力和严谨的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。
随着普通高等教育的普及，在办学层次一般的普通高等院校，如一些独立学院、新兴的职业技术大学或含有计算机类专升本的院校里，离散数学扮演着重要的角色。
考虑这些学校学生的认知特点，我们依据多年的教学经验编写了本书，本书在内容编排上具有以下特点：
（1） 重点介绍离散数学最核心、最基础的内容，如命题逻辑、谓词逻辑、集合论、图论等，适合学生在一个学期内学习。
（2） 侧重概念的具体应用，弱化定理的抽象证明。
（3） 对于部分理论性过强、过于抽象的内容概括介绍。
（4） 各章均配有丰富的典型例题。
（5） 融入工程应用案例，有助于学生理解学与用之间的联系与差异。
本书的第1章、第2章、第4章和第5章由孙志海编写，第3章由张蒙编写。孙志海负责全书的审定。
在编写本书的过程中，我们参阅了大量的离散数学教材、专著和资料，在此向相关作者表示衷心的感谢。
由于编者水平有限，书中难免存在不妥之处，恳请读者批评指正，以便再版时修订。
联系邮箱：szh@hdu.edu.cn。
孙志海
2022年12月
第1章 命题逻辑 1
1.1 命题和逻辑联结词 2
1.1.1 命题 2
1.1.2 逻辑联结词与命题符号化 4
1.2 命题公式及其真值表 13
1.2.1 命题公式 13
1.2.2 真值表 14
1.3 命题公式的等价演算 20
1.4 命题公式的范式 29
1.4.1 析取范式和合取范式 29
1.4.2 标准析取范式和标准合取范式 32
1.4.3 利用真值表法求解标准范式 37
1.4.4 标准析取范式和标准合取范式的关系 40
1.5 联结词的完备集 48
1.6 命题公式的推理演算 54
1.6.1 命题公式推理演算的基本概念 55
1.6.2 命题逻辑的演绎推理方法 60
1.6.3 附加前提法 63
1.6.4 归谬法 66
本章小结 70
第2章 谓词逻辑 71
2.1 个体词、谓词与量词 71
2.1.1 个体词与谓词 71
2.1.2 量词 74
2.2 谓词公式及其解释 79
2.2.1 谓词公式 79
2.2.2 谓词公式的解释 82
2.3 谓词公式的等价演算 86
2.4 谓词公式前束范式 90
2.5 谓词公式的推理演算 94
2.5.1 谓词公式推理演算的基本概念 94
2.5.2 谓词逻辑的演绎推理方法 96
本章小结 101
第3章 集合论 102
3.1 集合及其运算 102
3.1.1 集合的基本概念 102
3.1.2 集合的运算 104
3.1.3 集合的计算机表示 110
3.2 二元关系及其运算 114
3.2.1 笛卡儿积 114
3.2.2 二元关系及其表示 117
3.2.3 二元关系的运算 119
3.3 二元关系的性质与闭包 127
3.3.1 二元关系的性质 127
3.3.2 二元关系的闭包 130
3.4 等价关系与划分 136
3.5 偏序关系与拓扑排序 141
3.5.1 偏序关系 141
3.5.2 偏序关系中的特殊元 143
3.5.3 拓扑排序 145
3.6 函数 148
3.6.1 函数的基本概念 148
3.6.2 复合函数 150
3.6.3 逆函数 152
3.7 集合的等势与基数 155
本章小结 156
第4章 图论 157
4.1 图的基本概念 158
4.2 通路与回路 167
4.3 图的连通性 170
4.4 图的矩阵表示 176
4.5 欧拉图和哈密尔顿图 181
4.5.1 欧拉图 181
4.5.2 哈密尔顿图 184
4.5.3 最短路问题、中国邮递员问题与货郎担问题 185
4.6 树 186
4.6.1 无向树及其性质 186
4.6.2 生成树 189
4.6.3 根树 190
本章小结 196
第5章 离散数学的应用举例 197
5.1 命题逻辑、 集合论和图论的应用举例 197
5.1.1 命题逻辑的应用举例 197
5.1.2 集合论的应用举例 200
5.1.3 图论的应用举例 203
5.2 函数在机器视觉测量中的应用举例 208
5.3 集合运算在机器视觉测量中的应用举例 213
本章小结 218
附录A 综合练习一 219
附录B 综合练习二 221
参考文献 223
书单推荐
