离散数学

陈瑜离散数学(

命题逻辑

命题与条件命题

  • 命题:能够确切判断真假的陈述句。
  • 条件命题 \(p \rightarrow q\) 的常见表述:
    • if \(p\), then \(q\)
    • \(p\) implies \(q\)
    • \(p\) only if \(q\)
    • \(q\) if \(p\)

常用等价律

  • 吸收律
    • \(p \lor (p \land q) \equiv p\)
    • \(p \land (p \lor q) \equiv p\)
  • 分配律
    • \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
  • 逆否律
    • \(p \rightarrow q \equiv \neg q \rightarrow \neg p\)

范式与化简

  • 合取范式(CNF):形如 \(p \land q \land r\) 的命题式。
  • 析取范式(DNF):形如 \(p \lor q \lor r\) 的命题式。
  • 主析取范式(主DNF):将命题化为若干极小项的析取;极小项为永真式相合取。
  • 主合取范式(主CNF):将命题化为若干极大项的合取;极大项为永假式相析取。

量词与翻译

翻译带量词的语句时,全称量词通常使用蕴含表达,特称量词通常使用合取表达: \(\forall x\,(P(x) \to Q(x)) \\ \exists x\,(P(x) \land Q(x))\) 这样可以限制讨论的论域:

  • 蕴含式对 \(P(x)\) 之外的情况不敏感,有助于保证结论在当前论域内始终为真。
  • 特称量词强调存在性,使用合取可以只关注满足 \(P(x)\) 的对象。
  • 如果直接限制论域为满足 \(P(x)\) 的元素,亦可混用,但通常没有必要。

常见联结词

  • 与非:\(p \uparrow q \equiv \neg (p \land q)\)
  • 或非:\(p \downarrow q \equiv \neg (p \lor q)\)
  • 条件否定联结词:\(p \overset{c}{\rightarrow} q \equiv \neg p \lor q\)
  • 功能完备集:由一个或多个联结词构成的集合,可表达所有逻辑运算。
  • 最小功能完备集:在功能完备的前提下,联结词数量最少的集合。

逻辑演绎技巧

  • CP 规则:若要证明 \(p \rightarrow q\),可暂设 \(p\) 为附加前提,再证明 \(q\)。
  • 消解法:基于假言推理的反证技术。
    • 将结论的否定加入前提;
    • 将所有前提转换成合取范式;
    • 通过消解逐步推导出矛盾式。

关系与集合

集合运算

  • 笛卡尔积(Cartesian Product):\(A \times B = {(a,b) \mid a \in A, b \in B}\),构造两个集合之间所有可能的有序对。
  • 幂集(Power Set):\(2^{A} = {B \mid B \subseteq A}\),包含集合 \(A\) 的所有子集(含空集)。

关系的表示方式

  • 关系矩阵:二值矩阵表示关系是否成立。
  • 关系图:顶点表示元素,边表示对应关系。

关系的基本性质

  • 自反性(Reflexive):对角线元素全为 1。
  • 反自反性(Irreflexive):对角线元素全为 0,与“非自反”区分开来。
  • 对称性(Symmetric):若 \(aRb\) 成立,则 \(bRa\) 也成立。
  • 反对称性(Anti-symmetric):若 \(aRb\) 且 \(bRa\),则必有 \(a = b\)。
  • 传递性(Transitive):若 \(aRb\) 且 \(bRc\),则 \(aRc\)。

关系运算与性质

  • 关系复合:\(R \circ S = {(a,c) \mid \exists b, (a,b) \in S \land (b,c) \in R}\),与关系矩阵乘法一致。
  • 运算性质:
    • \(R \circ (S \circ T) = (R \circ S) \circ T\)
    • \((R \circ S)^{-1} = (S^{-1}) \circ (R^{-1})\)

关系的闭包(Closure)

指满足某一性质的最小关系。

  • 自反闭包:\(r(R) = R \cup I\)。
  • 对称闭包:\(s(R) = R \cup R^{-1}\)。
  • 传递闭包:\(t(R) = R \cup R^2 \cup R^3 \cup \cdots\),可通过 Warshall–Floyd 算法求解。

等价关系与划分

  • 等价关系:同时满足自反性、对称性与传递性。
  • 等价类:\([a] = {x \mid x \in A \land aRx}\)。
  • 不同等价类之间要么相等、要么不相交,因此等价类构成集合的划分,满足 \(\bigcup_{i=1}^{n} [a_i] = A\)。

偏序关系(Partial Order)

  • 满足自反性、反对称性与传递性的关系。
  • 集合层面
    • 最小元与最大元:分别不大于/不小于集合中任意元素。
    • 极小元与极大元:不存在比它更小/大的其他元素。
  • 子集层面
    • 上界与下界:分别不小于/不大于子集中所有元素。
    • 最小上界与最大下界:在原集合中比较得到的“最”值。
  • 若子集具有最小上界,则该元素在子集中称为上确界;具有最大下界时称为下确界。
  • 全序集(Linear Order):偏序集的一种,任意两元素都可比较。
  • 良序集(Well Order):全序集的一种,任意非空子集都存在最小元。

图论基础

基本概念

  • 子图:从原图删去部分点或边得到的图。
    • 删点子图、删边子图。
    • 点诱导子图、边诱导子图。
  • 完全图:任意两点之间均有边,边数满足 \(|E| = n(n-1)/2\)
  • 补图:以完全图为底,将原图不存在的边补上构成的图。
  • 图的同构:若存在双射 \(f: V(G) \to V(H)\),使得 \((u,v) \in E(G)\) 当且仅当 \((f(u), f(v)) \in E(H)\),则称 \(G\) 与 \(H\) 同构。同构关系是图集上的等价关系。
    • 必要条件:顶点数、边数、度数序列均相同。
  • 简单道路:不重复经过同一条边。
  • 基本道路:不重复经过同一顶点。

常用记号

  • \(\Delta_G\):图中最大顶点度。
  • \(\delta_G\):图中最小顶点度。
  • \(\omega(G)\):图的连通分支数。
  • \(\kappa(G)\):点连通度。
  • \(\lambda(G)\):边连通度。

基本定理

  • 握手定理:\(\sum_{v \in V} \deg(v) = 2|E|\)。
  • 二部图(二分图):顶点可分为两个独立集,所有边均连接不同集的顶点。
  • 点割集 / 边割集:删除后使图不再连通的顶点或边集合。
  • 点连通度 / 边连通度:最小点割集或边割集的大小。

树与编码

  • 常见类型:二叉树、完全二叉树、满二叉树、完美二叉树。
  • Huffman 树的构造:
    1. 将 \(n\) 个权值视为 \(n\) 棵只有根的树。
    2. 反复选取根权最小的两棵树合并,新根权值为两子树权值之和。
    3. 重复直到仅剩一棵树。
  • 有序树与二叉树的转换:可通过长子右兄弟表示法等方式实现。

平面图(Planar Graph)

  • 可以在平面上绘制且无边交叉的图称为平面图。
  • 面(Face):由边围成、不可再分的封闭区域。
  • 欧拉公式:若 \(G\) 是 \(n\) 个顶点、\(m\) 条边、\(f\) 个面的连通平面图,则 \(n - m + f = 2\)。这是平面图的必要条件。
  • 库拉图斯基定理:图是平面图的充要条件是其不包含与 \(K_5\) 或 \(K_{3,3}\) 的细分图同构的子图。
  • 对偶图:将原图每个面视作顶点,相邻面之间连边构成的图。

欧拉图与哈密顿图

  • 欧拉图:存在欧拉回路(遍历所有边恰好一次)的图。
    • 连通无向图是欧拉图当且仅当所有顶点度数为偶数。
  • 半欧拉图:存在欧拉道路(遍历所有边一次,起止点不同)。
    • 无向图中恰有两个奇度顶点时成立。
  • 有向图:若每个顶点入度等于出度则有欧拉回路;若仅有一个顶点入度比出度大 1,另有一个出度比入度大 1,则存在欧拉道路。
  • 欧拉回路构造(Fleury 算法):从任意顶点出发,优先选非桥边,走过后删除该边,直至无法继续。
  • 邮递员问题:在一般图中寻找最小代价的边遍历路径。若图为欧拉图,答案即欧拉回路;否则需添加边使其成为欧拉图。
  • 哈密顿图:存在哈密顿回路(恰好一次经过每个顶点)的图。
    • 充分条件示例:
      • 任意非相邻顶点 \(u,v\) 满足 \(\deg(u) + \deg(v) \ge n\)(Dirac 定理)。
      • 任意顶点的度数满足 \(\deg(v) \ge n/2\)。

代数结构

群的概念与性质

  • 常用术语:
    • 群的阶(order):群中元素个数。
    • 集合的势(cardinality):集合中元素个数。
  • 运算层级:
    • 仅封闭性:广群(groupoid)。
    • 加上结合律:半群(semigroup)。
    • 进一步存在幺元:含幺半群(monoid)。
    • 再满足每个元素存在逆元:群(group)。
    • 若运算满足交换律:阿贝尔群(abelian group)。
    • 若存在生成元:循环群(cyclic group)。逆元也可作为生成方式。
  • 剩余类加群构成群;剩余类乘群因 \(0\) 无乘法逆元而不是群。

陪集、正规子群与商群

  • 对于子群 \(H\)(必含幺元),在群 \(G\) 中定义:
    • 左陪集:\(aH = {ah \mid h \in H}\)。
    • 右陪集:\(Ha = {ha \mid h \in H}\)。
  • 性质:
    • 同一子群的所有陪集势相等。
    • 拉格朗日定理:\(|G| = (k+1)|H|\),其中 \(k\) 为不同陪集数减一。
    • 判定子集为子群的常用条件:封闭性与包含幺元、逆元。
  • 正规子群(normal subgroup):满足 \(aH = Ha\) 或 \(aHa^{-1} \subseteq H\)。
  • 商群(quotient group):\(G/H = {aH \mid a \in G}\),满足 \(|G/H| = |G|/|H|\),可视作由代表元构成的自然同构结构。

同态与同构

  • 单射(injective)满射(surjective)双射(bijective)分别对应函数的基本性质。
  • 群同态 \(f: G \to G’\) 满足 \(\forall a,b \in G, f(a b) = f(a) f(b)\),并有 \(f(e) = e’\)。
    • 单同态(monomorphism):\(f\) 为单射。
    • 满同态(epimorphism):\(f\) 为满射。
    • 同构(isomorphism):\(f\) 为双射。
  • 同态核:\(\ker(f) = {a \in G \mid f(a) = e’}\),是 \(G\) 的正规子群;\(f\) 单射当且仅当 \(\ker(f) = {e}\)。

环与域

  • 集合 \(R\) 配备二元运算 \(+\) 与 \(\cdot\):
    • \((R, +)\) 构成阿贝尔群;
    • \((R, \cdot)\) 构成半群;
    • 乘法对加法满足分配律。
    • 此时 \(R\) 称为环(ring),加法幺元记作 \(\theta\)。
  • 零因子:\(a \ne \theta\)、\(b \ne \theta\),且 \(a \cdot b = \theta\)。
  • 若乘法满足交换律,则为交换环;若存在乘法幺元,则为含幺环。
  • 同时满足交换、含幺且无零因子时称为整环(integral domain)。
  • 若含幺环中所有非零元素关于乘法构成阿贝尔群,则为域(field)。

格与布尔代数

  • 格(lattice):偏序集 \((L, \le)\) 中任意元素 \(a,b\) 均存在最小上界 \(a \vee b\) 与最大下界 \(a \wedge b\)。
    • 可定义偏序关系:\(a \le b \iff a \wedge b = a\) 或 \(a \vee b = b\)。
  • 分配格:满足 \(a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)\) 等分配律。
  • 补元(complement):元素 \(a’\) 满足 \(a \vee a’ = 1\) 且 \(a \wedge a’ = 0\)。
    • 元素可补称为 complemented。
    • 所有元素均有补元的格称为有补格。
  • 布尔代数(boolean algebra):既是分配格又是有补格的结构,常写为 \((B, \vee, \wedge, ‘, 0, 1)\)。
    • 原子(atom):非零且没有真子元素的元素,可视为覆盖最小元 0。