离散数学大全

摘要: 《离散数学及其应用》

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本书系统地介绍了组合数学的议题，主要包括：逻辑和证明，集合、函数、序列、求和与矩阵，算法，数论和密码学，归纳与递归，计数，离散概率，关系，图，树，布尔代数，计算模型。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的例题、图表、应用实例和练习。

但注意本书不包括代数系统的内容，这部分可以参考 《离散数学》。

• 《离散数学及其应用》 (vwhr)

---

基础：逻辑和证明

命题逻辑

• 命题
• 条件语句
• 复合命题的真值表
• 逻辑运算符的优先级
• 逻辑运算和比特运算

命题逻辑的应用

• 语句翻译
• 系统规范说明
• 布尔搜索
• 逻辑谜题
• 逻辑电路

命题等价式

• 逻辑等价式
• 德·摩根律的运用
• 构造新的逻辑等价式
• 可满足性
• 可满足性的应用
• 可满足性问题求解

谓词和量词

• 谓词
• 量词
• 有限域上的量词
• 受限域的量词
• 量词的优先级
• 变量绑定
• 涉及量词的逻辑等价式
• 量化表达式的否定
• 语句到逻辑表达式的翻译
• 系统规范说明中量词的使用
• 选自路易斯·卡罗尔的例子
• 逻辑程序设计

嵌套量词

• 理解涉及嵌套量词的语句
• 量词的顺序
• 数学语句到嵌套量词语句的翻译
• 嵌套量词到自然语言的翻译
• 汉语语句到逻辑表达式的翻译
• 嵌套量词的否定

推理规则

• 命题逻辑的有效论证
• 命题逻辑的推理规则
• 使用推理规则建立论证
• 消解律
• 谬误
• 量化命题的推理规则
• 命题和量化命题推理规则的组合使用

证明导论

• 一些专用术语
• 理解定理是如何陈述的
• 证明定理的方法
• 直接证明法
• 反证法
• 归谬证明法
• 证明中的错误
• 良好的开端

证明的方法和策略

• 穷举证明法和分情形证明法
• 存在性证明
• 唯一性证明
• 证明策略
• 寻找反例
• 证明策略实践
• 拼接
• 开放问题的作用
• 其他证明方法

---

基本结构：集合、函数、序列、求和与矩阵

集合

• 文氏图
• 子集
• 集合的大小
• 幂集
• 笛卡儿积
• 使用带量词的集合符号
• 真值集和量词

集合运算

• 集合恒等式
• 扩展的并集和交集
• 集合的计算机表示
• 多重集

函数

• 一对一函数和映上函数
• 反函数和函数合成
• 函数的图
• 一些重要的函数
• 部分函数

序列与求和

• 序列
• 递推关系
• 特殊的整数序列
• 求和

集合的基数

• 可数集合
• 不可数集合

矩阵

• 矩阵算术
• 矩阵的转置和幂
• 0-1矩阵

---

算法

算法

• 搜索算法
• 排序
• 字符串匹配
• 贪婪算法
• 停机问题

函数的增长

• 大O记号
• 一些重要函数的大O估算
• 函数组合的增长
• 大Ω与大Θ记号

算法的复杂度

• 时间复杂度
• 矩阵乘法的复杂度
• 算法范型
• 理解算法的复杂度

---

数论和密码学

整除性和模算术

• 除法
• 除法算法
• 模算术
• 模m算术

整数表示和算法

• 整数表示
• 整数运算算法
• 模指数运算

素数和最大公约数

• 素数
• 试除法
• 埃拉托斯特尼筛法
• 关于素数的猜想和开放问题
• 最大公约数和最小公倍数
• 欧几里得算法
• gcd的线性组合表示

求解同余方程

• 线性同余方程
• 中国剩余定理
• 大整数的计算机算术
• 费马小定理
• 伪素数
• 原根和离散对数

同余的应用

• 散列函数
• 伪随机数
• 校验码

密码学

• 古典密码学
• 公钥密码学
• RSA密码系统
• RSA加密
• RSA解密
• 用RSA作为公钥系统
• 密码协议
• 同态加密

---

归纳与递归

数学归纳法

• 数学归纳法
• 为什么数学归纳法是有
• 选择正确的基础步骤
• 运用数学归纳法进行证明的原则
• 数学归纳法的优点与缺点
• 利用数学归纳法证明的例子
• 使用数学归纳法时犯的错误

强归纳法与良序性

• 强归纳法
• 利用强归纳法证明的例子
• 计算几何学中使用强归纳法
• 利用良序性证明

递归定义与结构归纳法

• 递归地定义函数
• 递归地定义集合与结构
• 结构归纳法
• 广义归纳法

递归算法

• 证明递归算法的正确性
• 递归与迭代
• 归并排序

程序正确性

• 程序验证 329
• 推理规则 330
• 条件语句 330
• 循环不变量 332

---

计数

计数的基础

• 基本的计数原则
• 比较复杂的计数问题
• 减法法则（两个集合的容斥原理）
• 除法法则
• 树图

鸽巢原理

• 广义鸽巢原理
• 鸽巢原理的几个简单应用

排列与组合

• 排列
• 组合

二项式系数和恒等式

• 二项式定理
• 帕斯卡恒等式和三角形
• 其他的二项式系数
• 恒等式

排列与组合的推广

• 有重复的排列
• 有重复的组合
• 具有不可区别物体的集合的排列
• 把物体放入盒子

生成排列和组合

• 生成排列
• 生成组合

---

离散概率

离散概率引论

• 有限概率
• 事件组合的概率
• 概率的推理

概率论

• 概率指派
• 事件的组合
• 条件概率
• 独立性
• 伯努利试验与二项分布
• 随机变量
• 生日问题
• 蒙特卡罗算法
• 概率方法

贝叶斯定理

• 贝叶斯定理
• 贝叶斯垃圾邮件过滤器

期望值和方差

• 期望值
• 期望的线性性质
• 平均情形下的计算复杂度
• 几何分布
• 独立随机变量
• 方差
• 切比雪夫不等式

---

高级计数技术

递推关系的应用

• 用递推关系构造模型
• 算法与递推关系

求解线性递推关系

• 求解常系数线性齐次递推关系
• 求解常系数线性非齐次递推关系

分治算法和递推关系

• 分治递推关系

生成函数

• 关于幂级数的有用事实
• 计数问题与生成函数
• 使用生成函数求解递推关系
• 使用生成函数证明恒等式

容斥

• 容斥原理

容斥原理的应用

• 容斥原理的另一种形式
• 埃拉托色尼筛
• 映上函数的个数
• 错位排列

---

关系

关系及其性质

• 函数作为关系
• 集合的关系
• 关系的性质
• 关系的组合

n元关系及其应用

• n元关系
• 数据库和关系
• n元关系的运算
• SQL
• 数据挖掘中的关联规则

关系的表示

• 用矩阵表示关系
• 用图表示关系

关系的闭包

• 不同类型的闭包
• 有向图中的路径
• 传递闭包
• 沃舍尔算法

等价关系

• 等价关系
• 等价类
• 等价类与划分

偏序

• 字典顺序
• 哈塞图
• 极大元与极小元
• 格
• 拓扑排序

---

图

• 图和图模型
• 图模型

图的术语和几种特殊的图

• 基本术语 573
• 一些特殊的简单图 575
• 二分图 576
• 二分图和匹配 577
• 特殊类型图的一些应用 580
• 从旧图构造新图 582

图的表示和图的同构

• 图的表示
• 邻接矩阵
• 关联矩阵
• 图的同构
• 判定两个简单图是否同构

连通性

• 通路 598
• 无向图的连通性 600
• 图是如何连通的 601
• 有向图的连通性 603
• 通路与同构 604
• 计算顶点之间的通路数 605

欧拉通路与哈密顿通路

• 欧拉通路与欧拉回路
• 哈密顿通路与哈密顿回路
• 哈密顿回路的应用

最短通路问题

• 最短通路算法
• 旅行商问题

平面图

• 欧拉公式
• 库拉图斯基定理

图着色

• 图着色的应用

---

树

树的概述

• 有根树
• 树作为模型
• 树的性质

树的应用

• 二叉搜索树
• 决策树
• 前缀码
• 博弈树

树的遍历

• 通用地址系统
• 遍历算法
• 中缀、前缀和后缀记法

生成树

• 深度优先搜索
• 宽度优先搜索
• 回溯的应用
• 有向图中的深度优先搜索

最小生成树

• 最小生成树算法

---

布尔代数

布尔函数

• 布尔表达式和布尔函数
• 布尔代数恒等式
• 对偶性
• 布尔代数的抽象定义

布尔函数的表示

• 积之和展开式
• 函数完备性

逻辑门电路

• 门的组合
• 电路的例子
• 加法器

电路的极小化

• 卡诺图
• 无须在意的条件
• 奎因-莫可拉斯基方法

---

计算模型

语言和文法

• 短语结构文法
• 短语结构文法的类型
• 派生树
• 巴克斯-诺尔范式

带输出的有限状态机

• 带输出的有限状态机

不带输出的有限状态机

• 串的集合
• 有限状态自动机
• 有限状态机的语言识别
• 非确定性的有限状态自动机

语言的识别

• 克莱因定理
• 正则集合和正则文法
• 一个不能由有限状态自动机识别的集合
• 一些更强大的机器

图灵机

• 图灵机的定义
• 用图灵机识别集合
• 用图灵机计算函数
• 不同类型的图灵机
• 丘奇-图灵论题
• 计算复杂度、可计算性和可判定性

---