离散数学
陈瑜离散数学(
命题逻辑
命题与条件命题
- 命题:能够确切判断真假的陈述句。
- 条件命题 \(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 树的构造:
- 将 \(n\) 个权值视为 \(n\) 棵只有根的树。
- 反复选取根权最小的两棵树合并,新根权值为两子树权值之和。
- 重复直到仅剩一棵树。
- 有序树与二叉树的转换:可通过长子右兄弟表示法等方式实现。
平面图(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。