“离散数学”是计算机和信息类专业重要的核心学科基础课程之一。本书内容主要包括集合论（集合、二元关系与函数）、组合数学初步、图论、数理逻辑（命题逻辑、谓词逻辑）、代数系统简介五部分。在涵盖离散数学各方面内容的同时，本书有层次地精选了丰富的例题和多种解题思路与方法，各章配有适量的习题，帮助读者巩固和掌握所学知识，提高解题能力及技巧。本书结构清晰，概念准确，叙述严谨，力图做到“宜教易学”。本版新增了微课，扫描书中二维码即可观看；本书提供电子课件和习题答案，登录华信教育资源网可免费下载。本书可作为高等学校计算机和信息类等专业的教材，也适合作为考研复习的辅助资料。

张婷 ，北京工业大学计算机学院副教授，主要研究方向：计算机科学、模式识别与信息处理；在研课题：数字几何处理的理论和应用问题的研究、网络传输自相似性研究；科研成果：四元数射影空间上的一类等参超曲面，关于谓词逻辑教学中的一些探索等。

目 录
第1章 集合1
1.1 集合的基本概念1
1.1.1 集合的表示方法1
1.1.2 子集2
1.1.3 全集和补集3
1.1.4 幂集3
1.2 集合的基本运算4
1.2.1 并和交4
1.2.2 差和对称差7
习题19
第2章 二元关系与函数12
2.1 二元关系的基本概念12
2.1.1 引言12
2.1.2 笛卡儿乘积和二元关系的定义12
2.1.3 二元关系的三种表示方法13
2.1.4 二元关系的基本类型16
2.2 等价关系和偏序关系19
2.2.1 等价关系与划分19
2.2.2 偏序关系25
2.3 关系的特殊运算28
2.3.1 复合关系28
2.3.2 逆关系32
2.3.3 闭包运算33
2.4 函数36
2.4.1 函数的基本概念36
2.4.2 特殊函数38
2.4.3 复合函数和逆函数40
习题243
第3章 组合数学初步47
3.1 计数的基本原则与鸽巢原理47
3.1.1 乘积法则与求和法则47
3.1.2 减法法则（容斥原理）48
3.1.3 除法法则49
3.1.4 树形图50
3.1.5 鸽巢原理50
3.1.6 鸽巢原理的应用52
3.2 排列与组合及其推广53
3.2.1 基本计数原理53
3.2.2 排列：顺序重要、不放回54
3.2.3 组合：顺序不重要、不放回54
3.2.4 允许重复的排列（有放回）55
3.2.5 多重集的排列（元素不可区分）55
3.2.6 允许重复的组合（多重集的组合）56
3.2.7 分配模型与等价转换57
3.3 二项式与经典恒等式57
3.3.1 二项式定理58
3.3.2 组合恒等式的推导59
3.3.3 帕斯卡恒等式60
3.3.4 范德蒙德卷积61
3.3.5 上指标求和与其他恒等式62
3.3.6 应用举例62
3.4 生成排列与组合63
3.4.1 生成排列63
3.4.2 生成组合65
3.5 递推模型与分治思想67
3.5.1 递推关系及应用67
3.5.2 动态规划与递推关系68
3.5.3 分治算法与递推关系69
3.5.4 分治递推关系估计算法复杂度71
3.6 线性递推关系的求解73
3.6.1 线性齐次递推关系求解73
3.6.2 常系数线性齐次递推关系求解73
3.6.3 常系数线性非齐次递推关系求解75
3.7 生成函数76
3.7.1 生成函数的定义和定理76
3.7.2 生成函数的应用77
习题378
第4章 图论81
4.1 图的基本概念81
4.1.1 几个问题81
4.1.2 图的基本术语82
4.1.3 图的矩阵表示85
4.1.4 子图与图的同构87
4.1.5 完全图与补图89
4.2 通路与赋权图的最短通路91
4.2.1 通路与回路91
4.2.2 图的连通性92
4.2.3 赋权图的最短通路96
4.3 树102
4.3.1 无向树102
4.3.2 有向树106
4.3.3 前缀码与最优树108
4.4 欧拉图和哈密顿图114
4.4.1 欧拉图114
4.4.2 哈密顿图118
4.5 二部图和平面图122
4.5.1 二部图123
4.5.2 平面图127
习题4135
第5章 命题逻辑140
5.1　命题逻辑的基本概念140
5.1.1　命题140
5.1.2 命题联结词141
5.1.3 命题公式143
5.1.4 命题公式的真值表145
5.1.5 永真式、永假式和可满足式145
5.2　逻辑等价147
5.2.1　逻辑等价147
5.2.2 代换规则148
5.2.3 对偶原理150
5.2.4 联结词的完备集150
5.2.5 奎因法151
5.3 范式和主范式152
5.3.1 析取范式和合取范式152
5.3.2 主析取范式和主合取范式153
5.4 逻辑蕴涵160
5.4.1 逻辑蕴涵的定义160
5.4.2 逻辑蕴涵的性质161
5.5 推理理论164
5.5.1 前提和有效结论164
5.5.2 直接证明法165
5.5.3 间接证明法166
习题5170
第6章 谓词逻辑174
6.1 谓词逻辑的基本概念174
6.1.1 个体词、谓词和命题函数174
6.1.2 量词176
6.1.3 谓词公式181
6.1.4 约束变元和自由变元182
6.1.5 解释184
6.2 逻辑等价与逻辑蕴含186
6.2.1 永真式、永假式和可满足式186
6.2.2 逻辑等价式和逻辑蕴含式186
6.2.3 前束范式191
6.3 谓词演算的推理理论192
习题6196
第7章 代数系统简介198
7.1 代数系统的基本概念198
7.1.1 代数系统的定义198
7.1.2 特殊运算与特殊元素201
7.1.3 同构206
7.2 半群和独异点207
7.2.1 半群和子半群207
7.2.2 独异点和子独异点211
7.3 群212
7.3.1 群的定义和性质212
7.3.2 子群218
7.3.3 循环群223
7.3.4 陪集和拉格朗日定理225
7.3.5 群码229
7.4 环和域232
7.4.1 环232
7.4.2 域235
7.5 格237
7.5.1 格的定义237
7.5.2 格和偏序集239
7.5.3 特殊格241
习题7246
参考文献251