跳转至

离散数学

参考资料

数理逻辑

命题逻辑

  • 命题
  • 命题连结词 / 复合命题
  • 真值表 / 命题化简
  • 等价式
  • 范式 / 主范式 / 析取范式 / 合取范式
    • \(\bigvee_{i=1}^{n} \left( \bigwedge_{j=1}^{m} l_{ij} \right)\)
  • 可满足性

推理

  • 根据已知命题的真值推出新的命题
  • 直接证明
  • 间接证明
    • 反证法 假设待证明的命题为假, 推出矛盾的命题
    • 等价证明法 证明待证明命题的逆否命题
  • 非推理的证明
    • 构造证明 证明存在
    • 数学归纳法

谓词逻辑

  • 个体词 / 谓词 / 量词
  • 自由变元即未被量词绑定的变元, 约束变元反之
  • 前束范式 所有的量词都在最左边且辖域覆盖全式
    • \(Q_1x_1 Q_2x_2 \cdots Q_nx_n \ \varphi\)
    • 其中 \(Q_i \in { \forall, \exists }\), \(\varphi\) 为不含量词的公式
  • 解释 使全式为真的一组真值
  • 推理规则
  • 分情形证明法 (分类讨论) / 穷举法
  • 全称证明 / 存在证明 (构造 / 非构造) / 唯一证明

组合数学

基础计数原理

基本法则

  • 加法原理: 若 \(A \cap B = \emptyset\), 则 \(|A \cup B| = |A| + |B|\)
  • 乘法原理: \(|A \times B| = |A| \cdot |B|\)
  • 容斥原理: \(|A \cup B| = |A| + |B| - |A \cap B|\)
  • 除法法则 类似计数时重复计算, 最终结果需要除以重复次
  • 鸽巢原理: 将 \(n\) 个物体放入 \(k\) 个盒子, 至少存在一个盒子包含 \(\lceil n/k \rceil\) 个物体

排列组合

类型 公式 示例
排列 \(P(n, k) = \frac{n!}{(n-k)!}\) 5 人选 3 人排队: \(P (5, 3)=60\)
组合 \(C(n, k) = \frac{n!}{k!(n-k)!}\) 5 人选 3 人: \(C (5, 3)=10\)
重复组合 \(C(n+k-1, k)\) 3 种水果买 5 个: \(C (7, 5)=21\)

允许重复的排列组合

  • 排列与组合

    • 排列(有序, 可重复): \(n^r\)
    • 组合(无序, 可重复): \(\binom{n+r-1}{r}\)

  • 多重集排列

    • 若集合中有重复元素, 排列数为 \(\frac{n!}{\prod_{i} (k_i!)}\), 其中 \(k_i\) 为第 \(i\) 类元素的重复次数
    • 将 \(n\) 个相同元素分为 \(k\) 组, 每组大小为 \(R_i\), 则分组方式为 \(\frac{n!}{\prod_{i=1}^{k} (R_i!)}\)
  • 字典序生成排列
  • 比特串生成组合

高级计数技术

递推关系

常系数齐次线性递推关系

对于递推关系: $$ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} $$

  • 特征方程法
    • 特征方程为: \(r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0\)
    • 若特征根 \(r_1, r_2, \ldots, r_k\) 互异, 通解为 $$ a_n = A_1 r_1^n + A_2 r_2^n + \cdots + A_k r_k^n $$
    • 若存在重根(如二重根 \(r\)), 对应解为 \((A + Bn) r^n\)
常系数非齐次线性递推关系
\[ a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} + F(n) \]
  • 求解步骤
    • 先求齐次方程的通解 \(a_n^{(h)}\)
    • 再找一个特解 \(a_n^{(p)}\)(形式与 \(F(n)\) 相关)
    • 通解为 \(a_n = a_n^{(h)} + a_n^{(p)}\)

生成函数

  • 生成函数是以一个数列的变形作为不同幂次项的系数的多项式和式
  • 普通生成函数指数列项直接为系数 \(G(x) = \sum_{k=0}^\infty a_kx^k\)
  • 它显然是数学工具

广义二项式

  • 将 \(C(n, k)\) 中 \(n\) 推广为实数
  • 广义二项式定理 \((1+x)^n = \sum_{k=0}^\infty \binom{n}{k} x^k \quad (|x|<1)\)

斐波那契数列

  • \(F (n) = F (n-1) + F (n-2)\)
  • 卢卡斯数列 \(L(n)\) 是以 2, 1 开始的斐波那契数列 \(F(n)\)
  • 注意到 \(L(n)^2 - 5F(n)^2 = -4\)
  • 以斐波那契数列相邻两项作为输入会使欧几里德算法达到最坏复杂度
  • \(2L(m+n) = 5F(m)F(n) - L(m)L(n)\)
  • \(2F(m+n) = F(m)L(n) + L(m)F(n)\)

特殊计数序列

卡特兰数

\[C_n = \frac{1}{n+1} \binom{2n}{n}\]

应用场景:

  1. 合法括号序列数
  2. 二叉树形态数
  3. 凸多边形三角剖分数

斯特林数

类型 定义 递推关系
第一类 \([n \atop k]\): \(n\) 元 \(k\) 轮换 \(s(n, k) = s(n-1, k-1) + (n-1)s(n-1, k)\)
第二类 \(\left\{ \begin{matrix} n \\ k \end{matrix} \right\}\): \(n\) 元 \(k\) 子集 \(S(n, k) = S(n-1, k-1) + kS(n-1, k)\)
  • 第二种斯特林数 \(S(n, k)\) 表示将 n 个不同的元素分成 k 个非空集合的方案数
  • 第一种斯特林数 \(S(n, k)\) 表示将 n 个不同的元素分成 k 个非空轮换的方案数
  • 一组元素 (n 个) 的轮换是指将这组元素的排列顺序循环右移一位得到的 n 个排列

组合恒等式

  • 二项式系数求和

    • \(\sum_{r=0}^{n} \binom{n}{r} = 2^n\)
    • 奇数项和等于偶数项和: \(\sum_{r \text{ odd}} \binom{n}{r} = \sum_{r \text{ even}} \binom{n}{r} = 2^{n-1}\)
    • 加权求和: \(\sum_{r=0}^{n} 2^r \binom{n}{r} = 3^n\)

  • 帕斯卡恒等式

    • \(\binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1}\)
    • 杨辉三角性质: \(\binom{n+1}{r+1} = \sum_{j=r}^{n} \binom{j}{r} \quad (r \leq n)\)
名称 公式
范德蒙德 \(\sum_{k=0}^r C(m, k)C(n, r-k) = C(m+n, r)\)
多项式定理 \((\sum x_i)^n = \sum \frac{n!}{\prod k_i!}\prod x_i^{k_i}\)

经典问题

错位排列

  • \(D_n = (n-1)(D_{n-1} + D_{n-2}) \quad (D_1=0, D_2=1)\)
  • 封闭形式: \(D_n = n!\sum_{k=0}^n \frac {(-1)^k}{k!}\)

夫妻围坐

  • \(n\) 对夫妻围坐一圈, 每对夫妻之间有一个人, 问有多少种方案:
  • \(\frac {(2n)!}{2n} - \sum_{k=1}^n (-1)^{k+1} C (n, k) 2^k (2n-1-k)!\)

集合论

概念

  • 高中集合
  • 集合: 组合 / 关系 / 图 / 有限状态机 / 基数
  • 函数 / 笛卡尔积 (两个集合所有元素之间的关系)
  • A 可数等价于: \(|A| = |\mathbb{N}| \Rightarrow \aleph_0\)
  • 连续统假设: \(\not\exists\ \kappa\ \ \aleph_0 < \kappa < 2^{\aleph_0} = \aleph_1 = |\mathbb{R}|\)
  • 矩阵
  • 笛卡尔积: \(A \times B = {(a, b) \mid a \in A, b \in B}\)
  • 幂集: \(\mathcal{P}(A) = { S \mid S \subseteq A }\)

关系

  • \(R \subseteq A \times B\)
  • 显然, 函数是关系的一种特殊情况
  • 常用 0-1 矩阵与图表示关系

到自身的关系性质

  • \(\forall a \in A, \ (a, a) \in R\) 自反
  • \((a, b) \in R \Rightarrow (b, a) \in R\) 对称
  • \((a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R\) 传递
  • 以上全满足为等价关系, 其中元素的集合为等价类
  • 还有反对称与反自反
  • 对于关系 R, 能使 R 满足自反, 对称, 传递的最小超集为 R 的自反, 对称, 传递闭包
  • \([a] = { x \in S \mid x \sim a }\) a 的等价类 (在某个等价关系下相等的元素的集合)

关系性质

  • \(S \circ R = {(a, c) \mid \exists b, (a, b) \in R \land (b, c) \in S}\) 复合运算
  • \(R^{n+1} = R^n \circ R\) 幂运算

序

  • 若 R 是自反的, 反对称的, 传递的, 则称 R 为偏序, \((S, R)\) 为一个偏序集
  • 若 S 中所有元素可比, 则称 R 是全序, S 为一个全序集, 亦称链
  • 链 S 的非空子集都有最小元素, 则称 S 是良序集
  • 偏序可以用哈塞图表示, 节省许多边
  • 若偏序集每对元素都有最小上界与最大下界, 则该偏序集为格

图论

基本

  • 边 / 弧, 顶点 / 弧头弧尾
  • 以有向 / 无向, 是否多重边, 是否允许自环来区分图类型
  • 度 / 出度入度
  • 根据这些定义可以显然推得一些数量关系
  • 带权 (指边 / 弧) 图亦称网

特殊的简单图

  • 完全图, 每对顶点都有边 (表示为 \(K_n\))
  • 圈图, 字面意思
  • 轮图, 加一个与其它所有顶点有边的顶点的圈图
  • n 立方体图, 字面意思

二分图

  • 分俩集合, 仅与对方集合顶点存在边
  • 完全二分图, 字面, 表示为 \(K_{n, m}\)
  • 特别的, 若二分图的边集合的一个子集中没有两边关联同一顶点, 称之为匹配
    • 最多边的匹配为最大匹配, 反之同理
  • 霍尔婚配定律, 若二分图一个点集的任意非空子集的基都小于等于其邻接点集的基, 则有完全匹配
    • \(\forall S \subseteq \mathcal{X}, \ |N(S)| \geq |S| \Rightarrow \exists \mathcal{X}-\text{完全匹配}\)

子图

  • 将两个邻接顶点变为一个顶点 (并删除相应的边), 称为收缩

图的表示

  • 邻接表 / 邻接矩阵, 按图的疏密选择
  • 关联矩阵, 描述边点是否关联

同构

  • ~~结构一样~~

连通性

无向图连通性

  • 路径 / 环
  • 无向图两顶点有路径为连通, 无向图任意两点连通为连通图
  • 若能删除一个点, 使连通图不连通, 称为割点
  • 有 k 个割点的图称为 k 联通图
  • 极大 (最多顶点) 连通子图 (包含依附的边) 称为图的连通分量

有向图连通性

  • 有向图强连通要求双向存在路径, 否则为弱联通
  • 强连通分量

欧拉通路与哈密顿通路 (都是简单路径!!!)

  • 欧拉通路 / 回路, 要求包含每一条边
    • \(\forall v \in V, \ \deg(v) \equiv 0 \pmod{2} \Rightarrow \text{欧拉回路}\)
    • \(\exists!\, u, v \in V, \ \deg(u) \equiv \deg(v) \equiv 1 \pmod{2} \Rightarrow \text{欧拉通路且不为回路}\)
  • 哈密顿通路 / 回路, 要求包含每一个点
    • \(n \geq 3 \ \land\ \forall v \in V, \ \deg(v) \geq \lceil n/2 \rceil \Rightarrow \text{哈密顿回路存在}\)
    • \(n \geq 3 \ \land\ \forall u \nsim v, \ \deg(u)+\deg(v) \geq n \Rightarrow \text{哈密顿回路存在}\)
    • 没找到可高效计算的哈密顿充要

平面图

  • 画出来没交点
  • 平面图分割的 \(面数 r = 边数 e - 点数 v + 2\)
  • 可以推出, 联通平面简单图
    • \(v \geq 3 \Rightarrow e \leq (3*v - 6)\)
    • $\exists v \in V, \ \deg(v) \leq 5 $
    • \(v \geq 3 \ \land \ \text{无长度为 3 的回路} \Rightarrow e \leq 2v - 4\)
    • 可以检验平面图
  • 若一个图可以通过初等细分 (~~把一条边掰断~~) 转换为另一个图, 则称同胚
  • 平面图 \(\Leftrightarrow\) 不存在子图同胚于 \(K_5 / K_{3, 3}\)
  • 四色定理

树

  • 没有简单回路的连通无向图
  • 森林指不相交的树的集合 (不连通)
  • \(树的边数 e = 节点数 v - 1\)

有根性

  • 定义根, 使边具有远离根的方向
  • 节点的子树数是节点的度, 度为 0 的节点是叶节点 / 终端节点, 反之是非终端节点 / 分支节点, 非根的分支节点也叫内部节点
  • 具有 \(i\) 个内点的树有 \(m*i+1\) 个节点
  • 树的度是树内各节点度的最大值

深度

  • 树最大节点层次是树的深度
  • 树最多有 \(h^m\) (深度\(h\), 叉数\(m\)) 个叶子

二叉树

  • \(\mathcal{B} = {\emptyset} \cup { (v, L, R) \mid v \in V, \ L, R \in \mathcal{B} }\)
    • 空树或由根节点, 左子树, 右子树递归构成
  • 只有左 / 右的二叉树即斜树 (链表就是)
  • 满二叉树: 所有叶节点都在同一层的二叉树 (\(2^n-1\) 个节点)
  • 若设二叉树的深度为 \(h\), 除第 \(h\) 层外, 各层 \((1 \sim h-1)\) 的结点数都达到最大个数, 第 \(h\) 层所有的结点都连续集中在最左边

树的遍历

  • 略

生成树

  • 连通图的极小 (包含所有点与此情况的最少边 (\(n-1\))) 连通子图称为生成树
  • 有向图中有一顶点入度为 0, 其余为 1 称有向树
  • 有向图去掉一些弧至其仅由有向树构成称其为图的有向森林

网路流

  • 见算法