离散数学笔记

离散数学课堂笔记 / Discrete Mathematics Class Notes#

本笔记按专题整理，而不是按课次整理。课件用于确认本地课程已讲到的顺序，Rosen《Discrete Mathematics and Its Applications》第 8 版及其中文版、MIT 6.042J/6.1200J Mathematics for Computer Science 用于补全全课程专题。

These notes are organized by topics, not by lecture number. Local slides indicate the current lecture order, while Rosen and MIT MCS materials are used as the full-course backbone.

0. 使用说明 / How to Use This Note#

0.1 笔记结构 / Structure#

• Statement / 定理或公式: 需要记住的标准结论。
• Proof / 证明: 课堂考试中可复现的证明思路。
• Use / 用法: 做题时什么时候用、怎样套。
• EN: English statement or keyword, useful for matching the English textbook and MIT notes.
• CN: 中文解释，便于复习和答题组织。

0.2 资料范围 / Source Scope#

• Rosen 英文版: Chapters 1-13, especially logic, proof, sets, functions, algorithms, number theory, induction, counting, probability, recurrence, relations, graphs, trees, Boolean algebra, computation models.
• Rosen 中文版: 中文术语对照和课堂表述参考。
• MIT 6.042J textbook and MIT 6.1200J notes: proof methods, state machines, asymptotics, recurrences, graph theory, matching, probability, expectation, deviation bounds.
• Local slides: currently emphasize Rosen Sections 1.1-8.4, but the course is not limited to those sections.

0.3 核心学习策略 / Core Study Strategy#

CN: 离散数学题目通常不是“套一个大公式”，而是先判断对象类型: 命题、集合、函数、整数、序列、图、关系、概率空间。对象判断正确后，再选对应工具。

EN: Most discrete math problems begin by identifying the object: proposition, set, function, integer, sequence, graph, relation, or probability space. Once the object is identified, the correct theorem usually becomes visible.

1. 逻辑与证明 / Logic and Proofs#

1.1 命题与联结词 / Propositions and Connectives#

Definition / 定义.
CN: 命题是能判断真假的陈述句。常用联结词:

EN: An implication $p \to q$ does not claim causal relation. It only specifies a truth table.

Use / 用法.
CN: 证明条件命题 $p \to q$ 时，不要试图证明 $p$ 为真，而是假设 $p$ 为真并推出 $q$。判断等价命题时可用真值表或等价变形。

1.2 常用逻辑等价式 / Common Logical Equivalences#

For all propositions $p, q, r$:

Proof / 证明.
CN: 每个等价式都可用真值表逐行验证。比如 $p \to q \equiv \neg p \lor q$: 当 $p=T,q=F$ 时两边都假；其余三种情形两边都真。德摩根律可用真值表，也可理解为“不是同时发生”等于“至少一个不发生”。

EN: Each equivalence follows by truth-table verification. In proofs, equivalence replacement is valid because equivalent formulas have the same truth value under every assignment.

Use / 用法.
CN: 化简命题、证明永真式、把程序条件取反时使用。尤其注意 $\neg (p \to q) \equiv p \land \neg q$，这常用于反证和找反例。

1.3 谓词与量词 / Predicates and Quantifiers#

Definition / 定义.
CN: 谓词 $P(x)$ 是含变量的陈述，给定变量值后成为命题。量词:

• Universal quantifier / 全称量词: $\forall x P(x)$, 对所有 $x$ 成立。
• Existential quantifier / 存在量词: $\exists x P(x)$, 存在至少一个 $x$ 成立。
• Unique existence / 唯一存在: $\exists!x P(x)$, 存在唯一一个 $x$ 成立。

Quantifier negation / 量词否定.

Proof / 证明.
CN: $\neg \forall xP(x)$ 表示“并非每个对象都满足”，即至少有一个对象不满足，所以等价于 $\exists x\neg P(x)$。第二式同理。嵌套量词取反时，每经过一个量词就翻转一次。

Use / 用法.
CN: 写反例时常用。要否定“每个学生都有一本书”，正确形式是“存在一个学生没有任何书”，而不是“每个学生都没有书”。

1.4 推理规则 / Rules of Inference#

Proof / 证明.
CN: 命题逻辑规则可由真值表验证有效性。量词规则依赖“任意性”和“见证元”: 全称推广中的 $c$ 必须是任意对象，存在实例化中的 $c$ 不能偷带额外性质。

Use / 用法.
CN: 写形式化证明时用。若题目给出“所有 A 都是 B”和“x 是 A”，用全称实例化加肯定前件推出“x 是 B”。

1.5 证明方法 / Proof Methods#

Direct Proof / 直接证明#

Statement / 形式. To prove $p \to q$, assume $p$ and derive $q$.

Proof template / 证明模板.
CN: 假设 $p$ 成立。利用定义、已知定理和代数变形，推出 $q$。因此 $p \to q$ 成立。

Use / 用法.
CN: 适合定义直接展开的题，如整除、奇偶性、集合包含。

Contrapositive Proof / 逆否证明#

Statement / 形式. Prove $\neg q \to \neg p$, because $p \to q \equiv \neg q \to \neg p$.

Proof / 证明.
CN: 由逆否等价，证明逆否命题就等于证明原命题。

Use / 用法.
CN: 当结论是否定形式或前件难用时常用。例如证明“若 $n^2$ 为偶数，则 $n$ 为偶数”，证明“若 $n$ 为奇数，则 $n^2$ 为奇数”更容易。

Proof by Contradiction / 反证法#

Statement / 形式. To prove $p$, assume $\neg p$, derive contradiction $F$.

Proof / 证明.
CN: 若 $\neg p$ 会推出矛盾，则 $\neg p$ 不可能真，因此 $p$ 真。这依赖排中律 $p \lor \neg p$。

Use / 用法.
CN: 常用于无理数、无限性、唯一性、不可达性问题。

Proof by Cases / 分类讨论#

Statement / 形式. If $p_1 \lor p_2 \lor ... \lor pk$ covers all cases, and each $pi \to q$, then $q$.

Proof / 证明.
CN: 全部可能情形被穷尽，每一种情形都推出同一结论，所以结论成立。

Use / 用法.
CN: 奇偶、模余数、图中顶点度数、算法分支等题。

Existence and Uniqueness / 存在性与唯一性#

Statement / 形式. To prove $\exists!xP(x)$, prove:

1. Existence / 存在: $\exists xP(x)$.
2. Uniqueness / 唯一: if $P(a)$ and $P(b)$, then $a=b$.

Use / 用法.
CN: 除法算法、逆元、最小元素、图中某些构造的唯一性常用。

2. 集合、函数、序列、求和、矩阵 / Sets, Functions, Sequences, Sums, Matrices#

2.1 集合基本概念 / Sets#

Definitions / 定义.

• $x \in A$: $x$ is an element of $A$ / $x$ 属于 $A$。
• $A \subseteq B$: every element of $A$ is in $B$ / 子集。
• $A = B$: $A \subseteq B$ and $B \subseteq A$ / 集合相等。
• $P(A)$: power set, the set of all subsets of $A$ / 幂集。
• $|A|$: cardinality / 基数。
• Cartesian product / 笛卡尔积: $A \times B = {(a,b): a\in A, b\in B}$。

Power set formula / 幂集公式.

Proof / 证明.
CN: 对 $A$ 中每个元素，构造子集时有“选入/不选入”两种选择，独立相乘得 $2^n$。

Use / 用法.
CN: 数子集数量、二进制串与子集一一对应时使用。

2.2 集合运算 / Set Operations#

Set identities / 集合恒等式.
For all subsets of universe $U$:

Proof / 证明.
CN: 用元素追踪法。证明 $A \cup (B\cap C) = (A\cup B)\cap (A\cup C)$: 任取 $x$，左边成立当且仅当 $x\in A$ 或者 $x\in B$ 且 $x\in C$，按命题分配律等价于 $(x\in A 或 x\in B)$ 且 $(x\in A 或 x\in C)$，即右边。

Use / 用法.
CN: 集合证明一般用“两边互相包含”或“元素追踪法”。遇到补集先想德摩根律。

2.3 容斥与集合大小 / Cardinality and Inclusion-Exclusion#

Two-set formula / 二集合公式.

Three-set formula / 三集合公式.

General PIE / 一般容斥原理.

Proof / 证明.
CN: 固定一个元素 $x$。若 $x$ 属于恰好 $r$ 个集合，则右边对它的贡献为
$C(r,1)-C(r,2)+...+(-1)^{r+1}C(r,r)=1$，因为 $(1-1)^r=0$。不属于任何集合的元素贡献为 $0$。所以总贡献等于并集大小。

Use / 用法.
CN: “至少满足一个条件”“不能被某些数整除”“排除重复计数”时使用。

2.4 函数 / Functions#

Definitions / 定义.

• Function / 函数: $f: A \to B$ assigns each $a\in A$ exactly one $f(a)\in B$.
• Domain / 定义域: $A$; codomain / 陪域: $B$; range / 值域: $f(A)$.
• Injection / 单射: $f(a_1)=f(a_2) \to a_1=a_2$.
• Surjection / 满射: for every $b\in B$, there exists $a\in A$ with $f(a)=b$.
• Bijection / 双射: both injection and surjection.
• Inverse / 反函数: if $f$ bijective, $f^{-1}: B \to A$.
• Composition / 复合: $(g∘f)(x)=g(f(x))$.

Theorem / 定理: finite injection and surjection.
EN: If $A$ and $B$ are finite and $|A|=|B|$, then for $f:A \to B$, injection, surjection, and bijection are equivalent in pairs.

CN: 有限集合且大小相等时，单射必满射，满射必单射，因此等价于双射。

Proof / 证明.
CN: 若单射，则 $A$ 中不同元素落到 $B$ 中不同值，值域大小为 $|A|=|B|$，所以值域就是 $B$，即满射。满射反向同理: 若不是单射，则两个元素合并到同一值，最多只能覆盖 $|A|-1=|B|-1$ 个值，矛盾。

Use / 用法.
CN: 证明有限集合等势、计数、构造反函数时用。要证明两个有限集合大小相等，最常用办法是找双射。

2.5 可数与不可数 / Countability#

Definitions / 定义.

• Countably infinite / 可数无限: a set has a bijection with $N$.
• Countable / 可数: finite or countably infinite.
• Uncountable / 不可数: not countable.

Theorem / 定理: $Z$ is countable.
CN: 整数集可数。

Proof / 证明.
CN: 排列为 $0,1,-1,2,-2,3,-3,...$，这给出从 $N$ 到 $Z$ 的枚举。

Use / 用法.
CN: 只要能把元素排成一个无遗漏序列，就证明了可数。

Theorem / 定理: positive rational numbers are countable.
CN: 正有理数可数。

Proof / 证明.
CN: 把 $p/q$ 放在二维表中，按 $p+q=2,3,4,...$ 的对角线枚举，并跳过已出现的等值分数。每个正有理数最终出现在某条对角线上。

Use / 用法.
CN: 证明二维自然数对、整数对、有理数等可数时用“对角线枚举”。

Theorem / 定理: real numbers in $(0,1)$ are uncountable.
CN: $(0,1)$ 中实数不可数。

Proof / 证明.
CN: 假设可列为 $r_1,r_2,...$，写十进制展开。构造新数 $x$，第 $i$ 位小数与 $ri$ 的第 $i$ 位不同，并避免使用 9 造成二义性。则 $x$ 与列表中每个 $ri$ 至少一位不同，矛盾。

Use / 用法.
CN: 这是 Cantor 对角线法。用于证明所有无限集合并不一样大。

Theorem / 定理: algebraic numbers are countable.
EN: The set of real numbers that are roots of nonzero polynomial equations with integer coefficients is countable.

CN: 所有整系数非零多项式的实根组成的集合可数。

Proof / 证明.
CN: 固定次数 $d$ 和系数绝对值总和上界 $H$，满足条件的整系数多项式只有有限个，每个多项式最多有 $d$ 个实根。所有代数数可按 $d+H=1,2,3,...$ 分层枚举为可数个有限集合的并，因此可数。

Use / 用法.
CN: Quiz 中常出现“整系数二次/三次方程的实根集合是否可数”。固定次数时也可数，因为多项式集合可数且每个根有限。

2.6 序列与求和 / Sequences and Summations#

Definitions / 定义.

• Sequence / 序列: function from integers, usually $N$ or positive integers, to a set.
• Arithmetic progression / 等差数列: $a_n = a_0 + nd$.
• Geometric progression / 等比数列: $a_n = ar^n$.
• Recurrence relation / 递推关系: defines $a_n$ from previous terms.

Standard sums / 常用求和公式.

Proof / 证明.
CN: 等差和可把 $1+...+n$ 与 $n+...+1$ 相加，得到 $n$ 个 $n+1$。等比和令 $S=1+r+...+r^n$，计算 $(r-1)S=r^{n+1}-1$。平方和、立方和可用归纳法。

Use / 用法.
CN: 算法循环次数、计数题、递推展开常用。几何级数尤其常见于二分、树层数、概率无限过程。

2.7 矩阵 / Matrices#

Definitions / 定义.

• Matrix / 矩阵: rectangular array $A=[a_{ij}]$.
• Matrix product / 矩阵乘法: $(AB)_ij = \sum_k a_{ik} b_{kj}$.
• Identity matrix / 单位矩阵: $I$.
• Boolean matrix product / 布尔矩阵乘法: replace $+$ by $\lor$, multiplication by $\land$.

Theorem / 定理: relation matrix and composition.
EN: If relations are represented by Boolean matrices, composition corresponds to Boolean matrix multiplication.

CN: 若关系用 0-1 矩阵表示，则关系复合对应布尔矩阵乘法。

Proof / 证明.
CN: $(A∘B)$ 中 $i$ 与 $j$ 有关系，当且仅当存在中间点 $k$ 使 $iBk$ 且 $kAj$。矩阵上正是对所有 $k$ 做 “或-且” 运算。

Use / 用法.
CN: 求关系复合、传递闭包、图的可达性。

3. 算法与增长阶 / Algorithms and Growth#

3.1 算法 / Algorithms#

Definition / 定义.
CN: 算法是有限、明确、可执行的步骤序列，输入给定后产生输出并终止。

EN: An algorithm is a finite, precise procedure that takes input, performs steps, terminates, and returns output.

Use / 用法.
CN: 证明算法时通常要证明两件事: 正确性和终止性。分析算法时通常计算时间复杂度和空间复杂度。

3.2 渐近符号 / Asymptotic Notation#

Definitions / 定义.

Limit tests / 极限判别.

Proof / 证明.
CN: 由极限定义。若比值趋于有限 $L$，则充分大的 $n$ 后比值小于某个常数 $C$，这正是 Big-O。其他结论类似。

Use / 用法.
CN: 比较算法增长速度。考试中常用极限法，也可直接找常数。

3.3 常见增长阶 / Common Growth Orders#

Stirling formula / Stirling 公式.

Use / 用法.
CN: 比较阶乘、指数、组合数时使用。比如 $\log(n!) = \Theta(n \log n)$。

3.4 算法复杂度 / Complexity of Algorithms#

Typical complexity / 常见复杂度.

• Linear search / 线性搜索: $O(n)$.
• Binary search / 二分搜索: $O(\log n)$.
• Bubble/insertion selection sort / 基础排序: $O(n^2)$.
• Merge sort / 归并排序: $O(n \log n)$.
• Matrix multiplication classical / 普通矩阵乘法: $O(n^3)$.

Use / 用法.
CN: 写复杂度时说明输入规模 $n$ 是什么。循环嵌套通常相乘，顺序执行取最大阶。

4. 数论与密码 / Number Theory and Cryptography#

4.1 整除 / Divisibility#

Definition / 定义.

CN: 读作 $a$ divides $b$，即 $a$ 整除 $b$。

Basic properties / 基本性质.

Proof / 证明.
CN: 直接展开定义。若 $b=ar,c=as$，则 $mb+nc=a(mr+ns)$。

Use / 用法.
CN: 证明整除题先写出 $b=ak$，再做代数变形。

4.2 除法算法 / Division Algorithm#

Theorem / 定理.
EN: For integers $a$ and positive integer $d$, there exist unique integers $q,r$ such that

CN: 对任意整数 $a$ 和正整数 $d$，存在唯一商 $q$ 和余数 $r$。

Proof / 证明.
CN: 考虑集合 ${a-dk : k\in Z, a-dk\ge 0}$，由良序性有最小元 $r$。若 $r\ge d$，则 $r-d$ 更小且非负，矛盾，所以 $0\le r<d$。唯一性: 若 $a=dq+r=dq'+r'$，则 $d(q-q')=r'-r$。右边绝对值小于 $d$，只有可能为 $0$，故 $r=r'$ 且 $q=q'$。

Use / 用法.
CN: 一切模运算、欧几里得算法、进制表示的基础。

4.3 同余 / Modular Arithmetic#

Definition / 定义.

Equivalent condition / 等价条件.

Congruence arithmetic / 同余运算规则.

If $a\equiv b \pmod{m}$ and $c\equiv d \pmod{m}$, then

Proof / 证明.
CN: 由 $m|(a-b)$ 和 $m|(c-d)$，线性组合得到加减法；乘法用 $ac-bd=a(c-d)+d(a-b)$。

Use / 用法.
CN: 化简大数余数、证明整除、计算循环节、密码学。

4.4 最大公约数与欧几里得算法 / GCD and Euclidean Algorithm#

Definition / 定义.

Lemma / 引理.

Proof / 证明.
CN: 由除法算法 $a=bq+r$。任何同时整除 $a,b$ 的数也整除 $r=a-bq$；任何同时整除 $b,r$ 的数也整除 $a=bq+r$。公共因子集合相同，所以最大公约数相同。

Use / 用法.
CN: 用连续取余快速求 $gcd$。

Euclidean algorithm / 欧几里得算法.

1. Start with integers $a,b$.
2. While $b\ne 0$, replace $(a,b)$ by $(b, a \bmod b)$.
3. Return $|a|$.

Bezout identity / 贝祖等式.

Proof / 证明.
CN: 用扩展欧几里得算法把每一步余数倒推成 $a,b$ 的整数线性组合。最后一个非零余数就是 $\gcd(a,b)$。

Use / 用法.
CN: 求模逆元、解线性同余、证明互素性质。

4.5 素数与唯一分解 / Primes and Fundamental Theorem of Arithmetic#

Definition / 定义.
CN: 大于 1 的整数 $p$ 若正因子只有 $1$ 和 $p$，则为素数。

Euclid theorem / 欧几里得素数无穷定理.

Proof / 证明.
CN: 假设素数只有 $p_1,...,pn$。令 $N=p1p2...pn+1$。任意 $pi$ 都不整除 $N$，但 $N>1$ 必有素因子，矛盾。

Use / 用法.
CN: 典型反证法。也说明构造 $product+1$ 是找新素因子的常见技巧。

Fundamental theorem of arithmetic / 算术基本定理.

Proof / 证明.
CN: 存在性用强归纳: 若 $n$ 非素数，则 $n=ab$ 且 $1<a,b<n$，由归纳假设分解。唯一性用欧几里得引理: 若素数 $p|ab$，则 $p|a$ 或 $p|b$。逐个消去两种分解中的素因子。

Use / 用法.
CN: 计算 $gcd/lcm$，证明整除关系，处理指数型数论题。

Formula / 公式. If

then

4.6 模逆元与线性同余 / Modular Inverses and Linear Congruences#

Theorem / 定理: inverse criterion.

Proof / 证明.
CN: 若 $ax\equiv 1 \pmod{m}$，则 $ax+my=1$，所以任何公因子只能整除 1，$\gcd(a,m)=1$。反过来若 $\gcd(a,m)=1$，贝祖等式给出 $sa+tm=1$，故 $sa\equiv 1 \pmod{m}$，$s$ 是逆元。

Use / 用法.
CN: 解 $ax\equiv b \pmod{m}$ 之前先看 $\gcd(a,m)$。

Linear congruence theorem / 线性同余定理.

Proof / 证明.
CN: $ax\equiv b \pmod{m}$ 等价于 $ax-my=b$。整数线性组合 $ax+my$ 能取到的数正是 $\gcd(a,m)$ 的倍数。若可解，除以 $d$ 得到互素情形，然后用逆元。

Use / 用法.
CN: 先求 $d=\gcd(a,m)$。若 $d\nmid b$ 无解；若整除，化为 $(a/d)x\equiv b/d \pmod{m/d}$，再乘逆元。

4.7 中国剩余定理 / Chinese Remainder Theorem#

Theorem / 定理.

EN: If $m_1,...,mk$ are pairwise coprime positive integers, then the system

has a unique solution modulo $M=m1m2...mk$.

CN: 两两互素模数下，同余方程组模 $M$ 有唯一解。

Constructive formula / 构造公式.

Proof / 证明.
CN: 对第 $i$ 个模数，$M_j$ 若 $j\ne i$ 含有因子 $m_i$，所以对应项为 0；只有 $a_i M_i y_i\equiv a_i$。唯一性: 两个解之差被每个 $m_i$ 整除，因模数两两互素，所以被 $M$ 整除。

Use / 用法.
CN: 解多个模条件、RSA、把大模计算拆成小模计算。

4.8 费马小定理、欧拉定理 / Fermat and Euler#

Fermat's little theorem / 费马小定理.

Proof / 证明.
CN: 集合 ${1,2,...,p-1}$ 乘以 $a$ 后模 $p$ 仍是非零剩余的一个排列。故
$a\cdot 2a\cdot ...\cdot (p-1)a \equiv 1\cdot 2\cdot ...\cdot (p-1) \pmod{p}$，消去 $(p-1)!$ 得 $a^{p-1}\equiv 1$。

Use / 用法.
CN: 快速化简素数模下的大指数、证明 RSA 正确性、构造伪素数测试。

Euler phi function / 欧拉函数.

Euler theorem / 欧拉定理.

Proof / 证明.
CN: 将模 $n$ 的所有既约剩余乘以 $a$，仍得到同一集合的排列。两边连乘并消去所有可逆元素，得到结论。

Use / 用法.
CN: 非素数模下化简指数。注意必须互素。

4.9 进制表示与快速幂 / Representations and Fast Exponentiation#

Base-b representation / b 进制表示.

Proof / 证明.
CN: 反复用除法算法除以 $b$，余数给出低位数字，商继续除。

Use / 用法.
CN: 二进制、十六进制转换，算法复杂度分析。

Fast modular exponentiation / 快速模幂.

CN: 用二进制展开指数，反复平方取模。

Use / 用法.
CN: 计算 RSA、费马/欧拉题中的大指数。

4.10 RSA#

Algorithm / 算法.

1. Choose distinct primes $p,q$; let $n=pq$.
2. Let $\varphi(n)=(p-1)(q-1)$.
3. Choose $e$ with $\gcd(e,\varphi(n))=1$.
4. Find $d$ with $ed\equiv 1 \pmod{\varphi(n)}$.
5. Encrypt $C\equiv M^e \pmod{n}$.
6. Decrypt $M\equiv C^d \pmod{n}$.

Correctness / 正确性证明.
CN: 因 $ed=1+k\varphi(n)$。若 $\gcd(M,n)=1$，欧拉定理给出 $M^{ed}=M(M^{\varphi(n)})^k\equiv M \pmod{n}$。若 $M$ 与 $n$ 不互素，可分别在模 $p$ 和模 $q$ 下验证，再用 CRT 合并。

Use / 用法.
CN: 题目常要求生成密钥、加密解密、证明正确性。关键是求逆元 $d$。

4.11 伪素数、原根、离散对数 / Pseudoprimes, Primitive Roots, Discrete Logs#

Pseudoprime / 伪素数.
CN: 若合数 $n$ 对某个底 $a$ 满足

则称 $n$ 是以 $a$ 为底的 Fermat 伪素数。

Use / 用法.
CN: Fermat 小定理的逆命题不成立。若 $a^{n-1} \not\equiv 1 \pmod{n}$，可判定 $n$ 合数；若成立，只能说明 $n$ 可能为素数。

Carmichael number / Carmichael 数.
CN: 合数 $n$ 若对所有与 $n$ 互素的 $a$ 都满足 $a^{n-1}\equiv 1 \pmod{n}$，则为 Carmichael 数。

Primitive root / 原根.
CN: 若 $g$ 的幂模 $p$ 生成所有非零剩余

则 $g$ 是模素数 $p$ 的原根。

Discrete logarithm / 离散对数.

Use / 用法.
CN: 离散对数难题是 Diffie-Hellman 密钥交换等密码协议的基础。计算正向幂容易，反求指数通常困难。

4.12 同余的应用 / Applications of Congruences#

Hashing / 哈希.

CN: 把键映射到 $0,...,m-1$ 的槽位。$m$ 常取素数以减少模式性冲突。

Pseudorandom numbers / 伪随机数.

CN: 线性同余生成器。周期长度依赖 $a,c,m$ 的数论性质。

Check digits / 校验码.

CN: ISBN、UPC 等用加权和模某个数检测输入错误。基本思想是让合法编码满足一个同余条件。

Affine cipher / 仿射密码.

CN: 必须有 $\gcd(a,26)=1$ 才能解密，因为需要 $a$ 的模逆元。

5. 归纳与递归 / Induction and Recursion#

5.1 良序原理 / Well-Ordering Principle#

Theorem / 定理.

CN: 非负整数的任意非空子集都有最小元。

Proof / 证明.
CN: 在本课程中通常作为公理或与数学归纳法等价的原则使用。

Use / 用法.
CN: 证明存在“最小反例”时使用，是反证法和归纳法的基础。

5.2 数学归纳法 / Mathematical Induction#

Theorem / 定理.

If

then $P(n)$ is true for all $n\ge 0$.

Proof / 证明.
CN: 若存在反例，则反例集合非空，由良序性取最小反例 $m$。$m\ne 0$，所以 $m-1$ 不是反例，即 $P(m-1)$ 真。由归纳步推出 $P(m)$ 真，矛盾。

Use / 用法.
CN: 证明所有自然数命题，尤其是求和公式、整除、递推、图和树性质。

Template / 模板.

1. Base case / 基础步: prove $P(0)$ or $P(1)$.
2. Inductive hypothesis / 归纳假设: assume $P(k)$.
3. Inductive step / 归纳步: prove $P(k+1)$.
4. Conclusion / 结论: by induction, $P(n)$ for all $n$.

5.3 强归纳法 / Strong Induction#

Theorem / 定理.

If

then $P(n)$ holds for all $n\ge 0$.

Proof / 证明.
CN: 对命题 $Q(n): P(0)\land ...\land P(n)$ 做普通归纳即可。

Use / 用法.
CN: 当证明 $P(k+1)$ 需要不止 $P(k)$，而需要所有更小情形时使用。典型例子: 素因子分解、递归算法、组合拆分。

5.4 递归定义 / Recursive Definitions#

Definition / 定义.
CN: 递归定义包括基础步和递归步。

Example / 例:

Use / 用法.
CN: 遇到递归定义，计算前几项，猜闭式，再用归纳证明。

5.5 结构归纳 / Structural Induction#

Theorem / 定理.
EN: To prove a property for all objects in a recursively defined set, prove it for basis objects and prove that recursive constructors preserve it.

CN: 对递归定义的结构，若基础对象满足性质，且构造新对象时性质保持，则所有对象都满足性质。

Proof / 证明.
CN: 递归生成对象有构造层数，对层数做数学归纳。

Use / 用法.
CN: 字符串、树、表达式、公式、递归集合。

5.6 递归算法正确性 / Recursive Algorithm Correctness#

Principle / 原理.
CN: 递归算法正确性通常用归纳证明: 假设所有更小输入能正确求解，证明当前输入通过递归调用和合并步骤得到正确输出。

Example / 例: factorial.

Proof / 证明.
CN: 基础情形 $0! = 1$。若递归调用能返回 $(n-1)!$，算法返回 $n(n-1)!=n!$。

Use / 用法.
CN: 归并排序、二分查找、汉诺塔、递归求幂。

5.7 程序正确性与不变量 / Program Correctness and Invariants#

Loop invariant / 循环不变量.
CN: 循环每次迭代前后都保持为真的性质。

Proof steps / 证明步骤.

1. Initialization / 初始化: 循环前不变量成立。
2. Maintenance / 保持: 若一次迭代前成立，则迭代后仍成立。
3. Termination / 终止: 循环结束时，不变量加终止条件推出结果。

Use / 用法.
CN: 证明循环算法，如查找、排序、欧几里得算法。

6. 计数 / Counting#

6.1 基本计数原则 / Basic Counting Principles#

Sum rule / 加法原则.

Product rule / 乘法原则.

Division rule / 除法原则.

Bijection rule / 双射原则.

Proof / 证明.
CN: 加法原则来自不相交并集。乘法原则可对阶段数归纳。除法原则把计数结果按每个真实对象的 $d$ 个表示分组。

Use / 用法.
CN: 先判断选择过程是“或者”还是“然后”。如果有重复表示，用除法原则。

6.2 排列与组合 / Permutations and Combinations#

Permutation / 排列.

CN: 从 $n$ 个不同对象中有序选 $r$ 个。

Combination / 组合.

CN: 从 $n$ 个不同对象中无序选 $r$ 个。

Proof / 证明.
CN: 排列由乘法原则。组合先有序选 $r$ 个得 $P(n,r)$，但每个无序集合被 $r!$ 种顺序重复计数，故除以 $r!$。

Use / 用法.
CN: 有顺序用排列，无顺序用组合。关键词: arrangement/order 通常排列，subset/committee 通常组合。

6.3 二项式系数恒等式 / Binomial Coefficient Identities#

Proof / 证明.
CN: 对称性来自选 $r$ 个等价于排除 $n-r$ 个。Pascal 恒等式按某个固定元素是否被选分类。求和为 $2^n$ 是数所有子集。平方和可从两个 $n$ 元集合中共选 $n$ 个来解释。

Use / 用法.
CN: 化简组合式、证明组合恒等式、二项分布期望。

6.4 二项式定理与多项式定理 / Binomial and Multinomial Theorems#

Binomial theorem / 二项式定理.

Proof / 证明.
CN: 展开 $n$ 个因子 $(x+y)$。要得到 $x^{n-k}y^k$，需从 $n$ 个因子中选择 $k$ 个提供 $y$，共有 $\binom{n}{k}$ 种。

Use / 用法.
CN: 展开式系数、组合恒等式、概率分布。

Multinomial theorem / 多项式定理.

Use / 用法.
CN: 多类别分配、字符串字母频数、多项分布。

6.5 鸽巢原理 / Pigeonhole Principle#

Basic theorem / 基本鸽巢原理.

Generalized theorem / 广义鸽巢原理.

Proof / 证明.
CN: 若每个盒子最多 $ceil(N/k)-1$ 个，则总数至多 $k(ceil(N/k)-1)<N$，矛盾。

Use / 用法.
CN: 证明“必有两个相同/至少多少个”的存在性。先设计盒子，物体是被分类的对象。

6.6 可重复组合与星棒法 / Stars and Bars#

Theorem / 定理.

Number of nonnegative integer solutions to

is

Number of positive integer solutions is

Proof / 证明.
CN: 把 $n$ 个星号排成一行，用 $k-1$ 个隔板分成 $k$ 组。总共有 $n+k-1$ 个位置，选隔板位置。正整数情形先给每组 1 个，剩余 $n-k$ 个非负分配。

Use / 用法.
CN: 分糖果、方程非负整数解、多重集合选择。

6.7 有重复元素的排列 / Permutations with Repetition#

Formula / 公式.

Proof / 证明.
CN: 若先把所有对象标号区分，有 $n!$ 种。每类内部 $n_i!$ 种标号交换不改变结果，除去重复。

Use / 用法.
CN: 含重复字母单词重排。

6.8 错排 / Derangements#

Formula / 公式.

Proof / 证明.
CN: 令 $A_i$ 为第 $i$ 个元素固定。错排数为总排列数减去至少一个固定点的排列数。由容斥:
$D_n = n! - C(n,1)(n-1)! + C(n,2)(n-2)! - ... = n!\sum (-1)^k/k!$。

Use / 用法.
CN: “没有人拿到自己的东西”“没有位置保持原样”的题。

7. 离散概率 / Discrete Probability#

7.1 概率空间 / Probability Spaces#

Definition / 定义.

• Sample space / 样本空间: $S$, all outcomes.
• Event / 事件: subset $A\subseteq S$.
• Probability / 概率: function $Pr$ with $\Pr(S)=1$, $\Pr(A)\ge 0$, and additivity for disjoint events.

Laplace model / 古典概型.

Use / 用法.
CN: 概率题先定义样本空间，确保等可能后才能用 $|A|/|S|$。

7.2 概率规则 / Probability Rules#

General inclusion-exclusion / 概率容斥.

Proof / 证明.
CN: 概率规则是集合计数公式的加权版本，由互斥可加性推出。

Use / 用法.
CN: 至少发生一个事件、生日问题、并界估计。

7.3 条件概率与贝叶斯 / Conditional Probability and Bayes#

Definition / 定义.

Product rule / 乘法公式.

Total probability / 全概率公式.

If $B_1,...,B_n$ partition $S$, then

Bayes theorem / 贝叶斯公式.

Proof / 证明.
CN: 条件概率定义给出乘法公式。全概率公式把 $A$ 分解成互不相交的 $A\cap B_i$。贝叶斯公式由 $\Pr(B_j|A)=\Pr(A\cap B_j)/\Pr(A)$ 并代入乘法公式。

Use / 用法.
CN: 已知“原因到结果”的概率，求“看到结果后原因”的概率。医学检测、垃圾邮件、Monty Hall 类题常用。

7.4 独立性 / Independence#

Definition / 定义.

Equivalent if probabilities positive:

Mutual independence / 相互独立.

Events $A_1,...,A_n$ are mutually independent iff for every nonempty subset $I$,

Proof / 证明.
CN: 两事件等价式由条件概率定义。相互独立需要检查所有子集，不仅是两两独立。

Use / 用法.
CN: 连续抛硬币、独立试验乘法。注意“互斥”和“独立”不同: 非零概率互斥事件通常不独立。

7.5 随机变量、期望、方差 / Random Variables, Expectation, Variance#

Definition / 定义.
CN: 随机变量 $X$ 是从样本空间到实数的函数。

Expectation / 期望.

Indicator variable / 指示随机变量.

Linearity of expectation / 期望线性性.

Proof / 证明.
CN: 对有限样本空间，$\mathbb{E}[X+Y]=\sum_\omega (X(\omega)+Y(\omega))\Pr(\omega)=\sum X(\omega)\Pr(\omega)+\sum Y(\omega)\Pr(\omega)$。不需要独立。

Use / 用法.
CN: 计数随机对象时非常强。把总数拆成指示变量之和，再求每个事件概率。

Variance / 方差.

If $X,Y$ independent:

Proof / 证明.
CN: 展开平方得到 $\mathbb{E}[X^2]-2E[X]\mathbb{E}[X]+\mathbb{E}[X]^2$。独立时 $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$，协方差为 0。

Use / 用法.
CN: 衡量偏离均值大小，配合 Chebyshev 不等式。

7.6 常见分布 / Common Distributions#

Use / 用法.
CN: 独立重复试验数成功次数通常是二项分布；第一次成功等待时间是几何分布。

7.7 偏差界 / Deviation Bounds#

Markov inequality / 马尔可夫不等式.

Proof / 证明.
CN: $\mathbb{E}[X]$ 至少包含事件 $X\ge a$ 上的贡献，而该贡献不少于 $a \Pr(X\ge a)$。

Use / 用法.
CN: 只知道期望且变量非负时估计尾概率。

Chebyshev inequality / 切比雪夫不等式.

Proof / 证明.
CN: 对非负变量 $(X-\mathbb{E}[X])^2$ 用 Markov:
$\Pr((X-\mathbb{E}[X])^2\ge a^2) \le \mathbb{E}[(X-\mathbb{E}[X])^2]/a^2$。

Use / 用法.
CN: 知道均值和方差时估计偏离概率。

Chernoff bound / Chernoff 界.

For independent Bernoulli variables with $X=\sum X_i$, $\mu =\mathbb{E}[X]$:

Proof / 证明.
CN: 对 $e^{tX}$ 用 Markov，再利用独立性分解矩母函数，最后优化 $t$。

Use / 用法.
CN: 独立 0-1 随机变量和的强尾界，比 Chebyshev 通常指数级更强。

8. 高级计数、递推与生成函数 / Advanced Counting, Recurrences, Generating Functions#

8.1 递推关系 / Recurrence Relations#

Definition / 定义.
CN: 递推关系用前面若干项定义后一项。

Examples / 例.

Use / 用法.
CN: 先写清初值，再求闭式或渐近阶。

8.2 一阶线性递推 / First-Order Linear Recurrences#

Formula / 公式.

For

repeated substitution gives

Proof / 证明.
CN: 展开:
$a_n=ca_{n-1}+f(n)=c(ca_{n-2}+f(n-1))+f(n)=...$。

Use / 用法.
CN: 求汉诺塔、复利、简单算法递推。

Tower of Hanoi / 汉诺塔.

Proof / 证明.
CN: 猜测 $2^n-1$ 后归纳验证。移动 $n$ 个盘: 先移 $n-1$ 个，移最大盘，再移 $n-1$ 个。

8.3 常系数齐次线性递推 / Linear Homogeneous Recurrences#

Theorem / 定理.

For

try $a_n=r^n$. Characteristic equation:

If roots $r_1,...,r_k$ are distinct, then

If root $r$ has multiplicity $m$, terms are

Proof / 证明.
CN: 将 $r^n$ 代入递推得到特征方程。线性组合仍满足递推。初值构成线性方程组确定系数。重根情形由线性递推理论或差分算子推出。

Use / 用法.
CN: Fibonacci、二阶递推、组合计数闭式。

Fibonacci closed form / 斐波那契闭式.

Zeckendorf existence / Zeckendorf 表示的存在性.

CN: 更强的 Zeckendorf 定理说每个正整数可唯一表示成若干个不相邻 Fibonacci 数之和。Quiz 常只要求证明“不同 Fibonacci 数之和”的存在性。

Proof / 证明.
CN: 对 $n$ 强归纳。取不超过 $n$ 的最大 Fibonacci 数 $F_k$。若 $n=F_k$，完成。否则 $0<n-F_k<F_k$，由归纳假设，$n-F_k$ 可写成若干不同 Fibonacci 数之和。因为这些 Fibonacci 数都不超过 $F_{k-1}$，不会与 $F_k$ 重复，故 $n$ 也可表示成不同 Fibonacci 数之和。

Use / 用法.
CN: 看到“每个正整数都能表示成某类数之和”时，常用强归纳加“取不超过它的最大特殊数”。

8.4 非齐次递推 / Nonhomogeneous Recurrences#

Method / 方法.

For RHS of form polynomial, exponential, or their product, guess a similar form. If it overlaps with homogeneous solution, multiply by enough powers of $n$.

Use / 用法.
CN: $a_n=2a_{n-1}+3$, $a_n=a_{n-1}+n$, $a_n=3a_{n-1}+2^n$ 等题。

8.5 分治递推与主定理 / Divide-and-Conquer and Master Theorem#

Master theorem / 主定理.

For

Let $n^{\log_b a}$ be the critical term.

1. If $f(n)=O(n^{\log_b a - \varepsilon})$, then $T(n)=\Theta(n^{\log_b a})$.
2. If $f(n)=\Theta(n^{\log_b a} \log^k n)$, then $T(n)=\Theta(n^{\log_b a} \log^{k+1} n)$.
3. If $f(n)=\Omega(n^{\log_b a + \varepsilon})$ and regularity holds, then $T(n)=\Theta(f(n))$.

Proof / 证明.
CN: 递归树第 $i$ 层有 $a^i$ 个子问题，规模 $n/b^i$，该层代价 $a^i f(n/b^i)$。与叶子总量 $n^{\log_b a}$ 比较，三种情形分别是叶子主导、各层同阶、根部主导。

Use / 用法.
CN: 二分、归并、Karatsuba 等分治算法。先找 $a,b,f(n)$，再比较 $f(n)$ 与 $n^{\log_b a}$。

8.6 生成函数 / Generating Functions#

Definition / 定义.

For sequence ${a_n}$, ordinary generating function is

Standard generating functions / 常用生成函数.

Operations / 运算.

• Addition / 加法: coefficients add.
• Multiplication / 乘法: coefficient of $x^n$ in $A(x)B(x)$ is $\sum_{k=0}^n a_k b_{n-k}$.
• Derivative / 求导: if $A(x)=\sum a_n x^n$, then $A'(x)=\sum n a_n x^{n-1}$.

Proof / 证明.
CN: 乘法公式来自收集所有指数和为 $n$ 的项。

Use / 用法.
CN: 解递推、计数受限制组合、把卷积变成乘法。

Example / 例.
CN: 非负整数解 $x_1+...+x_k=n$ 的生成函数为 $(1+x+x^2+...)^k=1/(1-x)^k$，$x^n$ 系数为 $\binom{n+k-1}{k-1}$。

8.7 双重求和与乘积 / Double Sums and Products#

Double sum switch / 双重求和换序.

Triangular region / 三角区域换序.

Product notation / 连乘.

Use / 用法.
CN: 算法嵌套循环、期望线性性、组合计数中经常需要换序。先画出指标区域再换上下限。

9. 关系、等价关系、偏序 / Relations, Equivalence Relations, Partial Orders#

9.1 关系及性质 / Relations and Properties#

Definition / 定义.
CN: 从 $A$ 到 $B$ 的关系是 $A\times B$ 的子集。$A$ 上的二元关系是 $A\times A$ 的子集。

Properties / 性质.

Use / 用法.
CN: 判断关系类型时逐条回到定义。反对称不是“不对称”，它允许 $aRa$。

9.2 关系表示与闭包 / Representing Relations and Closures#

Matrix representation / 矩阵表示.
CN: 关系 $R$ 的矩阵 $M_R$ 中，$m_{ij}=1$ 当且仅当 $a_i R a_j$。

Graph representation / 图表示.
CN: 有向边 $a_i \to a_j$ 表示 $a_i R a_j$。

Closures / 闭包.

• Reflexive closure / 自反闭包: add all $(a,a)$.
• Symmetric closure / 对称闭包: add $(b,a)$ whenever $(a,b)$ exists.
• Transitive closure / 传递闭包: add all pairs connected by directed paths.

Warshall algorithm / Warshall 算法.

CN: 对每个中间点 $k$，更新可达性:

Proof / 证明.
CN: 第 $k$ 轮后，$W[i,j]$ 表示是否存在只使用前 $k$ 个顶点作为中间点的路径。对 $k$ 归纳。

Use / 用法.
CN: 求传递闭包、可达矩阵、先修关系推导。

9.3 等价关系与划分 / Equivalence Relations and Partitions#

Definition / 定义.

Equivalence class / 等价类.

Theorem / 定理.

EN: An equivalence relation on $A$ partitions $A$ into equivalence classes, and every partition of $A$ defines an equivalence relation.

CN: 等价关系与集合划分一一对应。

Proof / 证明.
CN: 自反性保证每个元素在自己的等价类中。若两个等价类相交，设 $x\in [a]\cap [b]$，则 $aRx$ 且 $xRb$，由对称和传递得 $aRb$，进而 $[a]=[b]$。因此等价类两两不交且覆盖 $A$。反向: 同一块中的元素定义为等价，显然自反、对称、传递。

Use / 用法.
CN: 模同余类、图连通分量、分类问题。

9.4 偏序 / Partial Orders#

Definition / 定义.

CN: 偏序集写作 $(P,\le )$。

Important terms / 术语.

• Comparable / 可比: $a\le b$ or $b\le a$.
• Chain / 链: every pair comparable.
• Antichain / 反链: no two distinct elements comparable.
• Maximal / 极大元: no strictly larger element above it.
• Maximum / 最大元: greater than or equal to every element.
• Minimal / 极小元, minimum / 最小元。
• Upper bound / 上界, least upper bound / 最小上界 or join.
• Lower bound / 下界, greatest lower bound / 最大下界 or meet.
• Lattice / 格: every pair has join and meet.

Use / 用法.
CN: 先区分 maximum 和 maximal。最大元若存在唯一；极大元可以多个。

9.5 Hasse 图与拓扑排序 / Hasse Diagrams and Topological Sorting#

Hasse diagram / Hasse 图.
CN: 对有限偏序，去掉自环和传递边，只画覆盖关系，较大元素放上方。

Theorem / 定理: finite DAG has topological order.

EN: Every finite directed acyclic graph has a topological ordering.

CN: 每个有限有向无环图都有拓扑序。

Proof / 证明.
CN: 有限 DAG 至少有一个入度为 0 的点。否则从任一点不断沿入边往前走，由有限性必重复，形成环。删除该点后递归排序。

Use / 用法.
CN: 任务调度、先修课程、偏序线性扩展。

9.6 Dilworth 型结论 / Dilworth-Type Statements#

Dilworth theorem / Dilworth 定理.
CN: 在有限偏序集中，最少需要多少条链覆盖全部元素，等于最大反链的大小。

Dual intuition / 对偶直觉.
CN: 链表示完全可比较的一组任务，反链表示两两不可比较、可并行的一组任务。

Use / 用法.
CN: MIT 资料中常作为偏序和 DAG 调度的补充。若考试不要求完整证明，重点会是会识别 chain、antichain、critical path，并用它们描述调度瓶颈。

10. 图论 / Graph Theory#

10.1 图的基本概念 / Basic Graph Concepts#

Definitions / 定义.

• Simple graph / 简单图: $G=(V,E)$ with undirected edges and no loops or multiple edges.
• Multigraph / 多重图: allows multiple edges.
• Directed graph / 有向图: edges have directions.
• Degree / 度: $\deg(v)$ number of incident edges; loop counts twice.
• In-degree/out-degree / 入度/出度: for digraphs.
• Complete graph / 完全图: $K_n$.
• Cycle graph / 圈图: $C_n$.
• Path graph / 路图: $P_n$.
• Bipartite graph / 二分图: vertices split into two parts, edges only cross parts.

10.2 握手定理 / Handshake Lemma#

Theorem / 定理.

CN: 所有顶点度数之和等于边数两倍。

Proof / 证明.
CN: 每条边贡献给两个端点各 1 次，总贡献 2。

Use / 用法.
CN: 求边数、证明奇度顶点个数为偶数。

Corollary / 推论.

Proof / 证明.
CN: 度数和为偶数，偶度顶点贡献偶数，所以奇度顶点个数必须为偶数。

10.3 图同构 / Graph Isomorphism#

Definition / 定义.
CN: 图 $G,H$ 同构若存在顶点双射 $f:V(G) \to V(H)$，使得 ${u,v}$ 是边当且仅当 ${f(u),f(v)}$ 是边。

Use / 用法.
CN: 证明不同构可比较顶点数、边数、度数序列、连通性、环数量。证明同构则给出明确双射。

10.4 连通性 / Connectivity#

Definitions / 定义.

• Walk / 通道: consecutive vertices connected by edges, may repeat.
• Trail / 迹: no repeated edge.
• Path / 路径: no repeated vertex.
• Connected / 连通: every pair has a path.
• Component / 连通分量: maximal connected subgraph.

Theorem / 定理.

Proof / 证明.
CN: 若通道重复某个顶点，删除两次出现之间的闭合部分，仍连接 $u$ 到 $v$。反复删除直到无重复顶点。

Use / 用法.
CN: 可达性证明中可把 walk 简化成 path。

10.5 欧拉路与欧拉回路 / Euler Paths and Circuits#

Definitions / 定义.

• Euler circuit/tour / 欧拉回路: uses every edge exactly once and returns to start.
• Euler path/trail / 欧拉路: uses every edge exactly once, start and end may differ.

Theorem / 定理: undirected Euler criterion.

For a connected graph with at least one edge:

Proof / 证明.
CN: 必要性: 欧拉回路每次进入一个顶点也必须离开，边成对贡献，所以度为偶数。欧拉路中只有起点和终点的进出不配对，所以它们为奇度。充分性可用逐步走未用边形成闭回路，再把剩余边所在闭回路拼接进来。

Use / 用法.
CN: 一笔画问题。先看连通，再数奇度顶点。

Directed Euler criterion / 有向欧拉回路.

For directed Euler path from $s$ to $t$: $outdeg(s)=indeg(s)+1$, $indeg(t)=outdeg(t)+1$, all others equal, plus connectivity condition.

10.6 哈密顿路与哈密顿圈 / Hamilton Paths and Cycles#

Definitions / 定义.

• Hamilton path / 哈密顿路: visits every vertex exactly once.
• Hamilton cycle / 哈密顿圈: visits every vertex exactly once and returns to start.

Dirac theorem / Dirac 定理.

Ore theorem / Ore 定理.

Proof / 证明.
CN: 这些定理的完整证明较长。考试通常要求会用条件判断存在性，而不是重证。证明思想是取最长路径或最长圈，若不能覆盖全部顶点，则用度数条件构造更长圈，矛盾。

Use / 用法.
CN: 欧拉看边，哈密顿看点。哈密顿问题通常难得多。

10.7 最短路 / Shortest Paths#

Dijkstra algorithm / Dijkstra 算法.
CN: 对非负权图，从源点开始反复确定当前距离最小的未确定顶点，并松弛其邻边。

Correctness / 正确性.
CN: 每次选出的未确定顶点 $u$ 的暂定距离已是最短。若存在更短路，它必须先经过某个未确定顶点，但非负边权使该路径长度不可能小于当前最小暂定距离。

Use / 用法.
CN: 非负权最短路。若有负权边，不能直接用 Dijkstra。

10.8 平面图 / Planar Graphs#

Definition / 定义.
CN: 图可画在平面上且边只在端点相交，则为平面图。

Euler formula / 欧拉公式.

For connected planar graph:

Proof / 证明.
CN: 对边数归纳。若图有环，删除环上一条边，面数和边数各减 1，$v-e+f$ 不变。不断删到树。树有 $e=v-1$ 且 $f=1$，所以 $v-e+f=2$。

Use / 用法.
CN: 判断非平面、求面数、证明边数上界。

Edge bounds / 边数上界.

For simple connected planar graph with $v\ge 3$:

If no triangles, especially bipartite planar:

Proof / 证明.
CN: 每个面边界至少 3 条边，且每条边被两个面计数，故 $3f\le 2e$。代入欧拉公式得 $e\le 3v-6$。无三角时每个面至少 4 条边，得 $4f\le 2e$，从而 $e\le 2v-4$。

Use / 用法.
CN: $K_5$ 有 $e=10>35-6=9$，非平面。$K_{3,3}$ 二分且 $e=9>26-4=8$，非平面。

10.9 图着色 / Graph Coloring#

Definitions / 定义.

• Proper coloring / 正常着色: adjacent vertices have different colors.
• Chromatic number / 色数: $\chi(G)$, minimum number of colors.

Basic facts / 基本事实.

Proof / 证明.
CN: 偶圈和树可按层或交替 2 色染色。奇圈不能 2 色，因为绕一圈回来会迫使起点同时用两色。二分图无奇圈的证明用 BFS 层奇偶分类。

Use / 用法.
CN: 排课、寄存器分配、地图染色、冲突图。

Greedy coloring bound / 贪心着色上界.

Proof / 证明.
CN: 任意顺序给顶点染色。给某个顶点染色时，它至多有 $\Delta$ 个已染邻居，因此在 $\Delta+1$ 种颜色中至少有一种没被邻居使用。

Use / 用法.
CN: 快速给出色数上界。若能找到大小为 $k$ 的完全子图，则 $\chi(G)\ge k$，上下界相等时得到准确色数。

Ramsey example / Ramsey 例: $R(3,3)=6$.

Proof / 证明.
CN: 固定一人 $v$。其余 5 人中，至少有 3 人与 $v$ 的关系同类，设为都认识 $v$。若这 3 人中有两人相识，则加上 $v$ 得 3 个两两相识；若这 3 人两两不相识，则得到 3 个两两陌生。另一类同理。

Use / 用法.
CN: 证明“足够大时必然出现有序结构”。这是分类讨论加鸽巢原理的经典题。

10.10 匹配与稳定婚姻 / Matching and Stable Marriage#

Definitions / 定义.

• Matching / 匹配: no two edges share a vertex.
• Maximum matching / 最大匹配: largest size.
• Perfect matching / 完美匹配: covers every vertex.
• Stable matching / 稳定匹配: no rogue/blocking pair prefers each other to current partners.

Hall theorem / Hall 定理.

For bipartite graph with left part $L$ and right part $R$, a matching covering all vertices of $L$ exists iff for every $S\subseteq L$,

Proof / 证明.
CN: 必要性显然: 若 $S$ 中每个点都匹配到不同邻居，则邻居数至少 $|S|$。充分性可用增广路或极小反例证明。

Use / 用法.
CN: 任务分配、婚配、系统代表元。

Gale-Shapley theorem / Gale-Shapley 定理.

Proof / 证明.
CN: 每个申请者最多向每个评价者申请一次，所以有限终止。若存在阻挡对 $(a,e)$，则 $a$ 一定曾向 $e$ 申请过；$e$ 拒绝或后来替换 $a$ 只会因为持有更喜欢的对象，且评价者手中对象随时间不变差，所以终局不会更喜欢 $a$，矛盾。

Use / 用法.
CN: 稳定匹配构造题。申请方得到申请方最优稳定匹配，另一方得到相对最差稳定匹配。

10.11 通信网络指标 / Communication Network Metrics#

Network graph model / 网络图模型.
CN: 顶点表示处理器或交换机，边表示通信链路。

Metrics / 指标.

• Diameter / 直径: maximum shortest-path distance between two vertices.
• Degree/switch count / 度数或交换机数: hardware cost proxy.
• Bisection width / 对分宽度: minimum number of edges crossing a balanced cut.
• Congestion / 拥塞: maximum load on a link under a routing scheme.
• Latency / 延迟: time for a message to traverse a route.

Common networks / 常见网络.

• Complete binary tree / 完全二叉树: 节点少、结构简单，但根附近容易拥塞。
• 2-D array / 二维网格: 布线自然，直径约为行列规模之和。
• Butterfly network / 蝶形网络: 常用于并行路由，层数约为 $\log n$。
• Benes network / Benes 网络: 可重排网络，能实现任意置换路由。

Use / 用法.
CN: MIT MCS 中这部分把图论指标用于计算机网络。做题时先明确要优化的是直径、边数、拥塞还是可重排性。

11. 树 / Trees#

11.1 树的等价刻画 / Equivalent Characterizations of Trees#

Definition / 定义.
CN: 树是连通且无环的无向图。

Theorem / 定理. For a graph $G$ with $n$ vertices, the following are equivalent:

1. $G$ is a tree.
2. $G$ is connected and has $n-1$ edges.
3. $G$ is acyclic and has $n-1$ edges.
4. Between every pair of vertices there is a unique simple path.
5. $G$ is minimally connected: removing any edge disconnects it.
6. $G$ is maximally acyclic: adding any new edge creates a cycle.

Proof / 证明.
CN: 树中任意两点存在路径；若有两条不同简单路径，合起来形成环，所以路径唯一。对树删叶子归纳可得边数 $n-1$。连通且 $n-1$ 边若有环，删环上一边仍连通，边数会少于连通图最少边数，矛盾。其他等价由“唯一路径”直接推出。

Use / 用法.
CN: 树题常在这些刻画之间切换。给边数和连通性可立刻判断树。

11.2 叶子与度数公式 / Leaves and Degree Formula#

Theorem / 定理.

Proof / 证明.
CN: 取树中最长简单路径。路径两端若度数大于 1，就能继续延长，矛盾。因此两端都是叶子。

Use / 用法.
CN: 树的归纳证明通常删叶子。

Degree sum / 度数公式.

CN: 来自握手定理和树边数 $n-1$。

11.3 根树与 m 叉树 / Rooted and m-ary Trees#

Definitions / 定义.

• Root / 根, parent / 父, child / 子, sibling / 兄弟。
• Internal vertex / 内部点, leaf / 叶。
• Height / 高度, level / 层。
• Full m-ary tree / 满 m 叉树: every internal vertex has exactly $m$ children.

Formula / 公式: full m-ary tree.

If a full m-ary tree has $i$ internal vertices and $l$ leaves, then

Proof / 证明.
CN: 每个内部点发出 $m$ 条父子边，共 $mi$ 条边。树有 $n-1$ 条边，所以 $n-1=mi$。又 $n=i+l$，代入得叶子公式。

Use / 用法.
CN: 决策树、编码树、表达式树。

11.4 遍历 / Tree Traversal#

Orders / 顺序.

• Preorder / 前序: root, left, right.
• Inorder / 中序: left, root, right.
• Postorder / 后序: left, right, root.
• Level order / 层序: BFS by levels.

Use / 用法.
CN: 表达式树、二叉搜索树、语法树。

11.5 生成树与最小生成树 / Spanning Trees and MST#

Theorem / 定理.

Proof / 证明.
CN: 若连通图有环，删除环上一条边仍连通。反复删除直到无环，得到连通无环的生成子图，即生成树。

Use / 用法.
CN: 网络连接、图连通性、MST 算法。

Kruskal correctness / Kruskal 正确性.

CN: 每次选择连接不同连通分量的最小边。割性质保证安全: 对任意割，跨越该割的最轻边属于某棵 MST。

Prim correctness / Prim 正确性.

CN: 从一个连通块开始，每次加入跨出当前块的最轻边。由同一割性质，该边安全。

Use / 用法.
CN: 求最小成本连接所有顶点。

11.6 Huffman 编码 / Huffman Coding#

Theorem / 定理.
CN: Huffman 算法构造最优前缀码。

Proof / 证明.
CN: 最优前缀码可表示为二叉树。最低频率的两个符号可安排为最深层兄弟叶子；合并它们为一个频率和的伪符号后，子问题仍最优。递归得到 Huffman 算法。

Use / 用法.
CN: 数据压缩、最优前缀码、加权外部路径长度最小。

12. 布尔代数 / Boolean Algebra#

12.1 布尔函数 / Boolean Functions#

Definition / 定义.
CN: 布尔函数 $F:{0,1}^n\to{0,1}$。变量取 0/1，运算包括 complement, join, meet。

Boolean identities / 布尔恒等式.

Proof / 证明.
CN: 与命题逻辑等价式一致，可用真值表证明。

Use / 用法.
CN: 化简逻辑电路、证明布尔表达式等价。

12.2 表示布尔函数 / Representing Boolean Functions#

Sum-of-products / 析取范式 DNF.
CN: 对真值表中每一行为 1 的输入，写一个 minterm，使变量或补变量匹配该行；把所有 minterm 用 OR 相连。

Product-of-sums / 合取范式 CNF.
CN: 对真值表中每一行为 0 的输入，写一个 maxterm；把所有 maxterm 用 AND 相连。

Theorem / 定理.

Proof / 证明.
CN: 用 DNF 构造。函数为 1 的每一行对应一个只在该行取 1 的 minterm。所有 minterm 析取后正好表示函数。

Use / 用法.
CN: 从真值表写表达式，从电路写公式。

12.3 逻辑门与完备性 / Logic Gates and Functional Completeness#

Important facts / 重要事实.

Proof / 证明.
CN: 任意布尔函数可用 AND/OR/NOT 表示。NAND 可构造 $NOT x = x NAND x$，$x AND y = (x NAND y) NAND (x NAND y)$，再由德摩根构造 OR。NOR 类似。

Use / 用法.
CN: 用单一门实现电路。

12.4 Karnaugh 图 / Karnaugh Maps#

Principle / 原理.
CN: 相邻格只差一个变量。把 1 组成大小为 $1,2,4,8,...$ 的矩形块，可消去变化的变量，得到更简单的 SOP 表达式。

Use / 用法.
CN: 小变量数布尔函数化简。注意可环绕相邻。

13. 计算模型 / Modeling Computation#

13.1 语言与文法 / Languages and Grammars#

Definitions / 定义.

• Alphabet / 字母表: finite set of symbols.
• String / 字符串: finite sequence over alphabet.
• Language / 语言: set of strings.
• Grammar / 文法: production rules generating strings.

Chomsky hierarchy / 乔姆斯基层级.

CN: 正则语言、上下文无关语言、上下文有关语言、递归可枚举语言，表达能力逐级增强。

Use / 用法.
CN: 描述程序语言语法、字符串模式、形式语言。

13.2 有限状态机 / Finite-State Machines#

Definitions / 定义.

• FSM with output / 带输出有限状态机: state, input, transition, output.
• DFA / deterministic finite automaton: $(Q,\sum ,\delta ,q_0,F)$.
• Accepted language / 接受语言: all strings ending in accepting states.

Use / 用法.
CN: 识别正则语言、设计控制器、模式匹配。

13.3 正则表达式与自动机 / Regular Expressions and Automata#

Theorem / 定理: Kleene theorem.

Proof / 证明.
CN: 正则表达式到自动机用结构归纳构造；自动机到正则表达式可逐步消除状态，保留路径标签表达式。

Use / 用法.
CN: 正则表达式和有限自动机可以互相转换。

13.4 图灵机与可计算性 / Turing Machines and Computability#

Definition / 定义.
CN: 图灵机包含有限控制、无限纸带、读写头和转移函数，可形式化“算法”。

Church-Turing thesis / Church-Turing 论题.

EN: Effectively computable functions are exactly those computable by a Turing machine.

CN: 一切有效可计算函数都可由图灵机计算。这不是数学定理，而是计算模型一致性的原则。

Halting problem / 停机问题.

Proof / 证明.
CN: 假设存在判定器 $H(P,x)$。构造程序 $D(P)$: 若 $H(P,P)$ 说会停机，则 $D$ 死循环；若说不会停机，则 $D$ 停机。问 $D(D)$，会得到自相矛盾。因此 $H$ 不存在。

Use / 用法.
CN: 证明不可判定性，理解计算能力边界。

14. MIT 6.1200J 补充专题 / MIT 6.1200J Additions#

14.1 状态机与不变量 / State Machines and Invariants#

Invariant principle / 不变量原则.

Proof / 证明.
CN: 对从初始状态到当前状态的转移步数做归纳。

Use / 用法.
CN: 证明某状态不可达。找一个所有可达状态都满足但目标状态不满足的性质。

Termination via derived variable / 用派生变量证明终止.

Proof / 证明.
CN: 非负整数不存在无限严格下降链，由良序性。

14.2 积分估计求和 / Integral Bounds for Sums#

Theorem / 定理.

If $f$ is nonnegative increasing on $[1,n]$,

If $f$ is nonnegative decreasing,

Proof / 证明.
CN: 用矩形面积夹逼曲线面积。递增函数右端点矩形高估，左端点矩形低估；递减函数反过来。

Use / 用法.
CN: 估计调和数、幂和、算法求和。

14.3 生日原理 / Birthday Principle#

Formula / 公式.

For $n$ people and $d$ equally likely birthdays:

Approximation:

Proof / 证明.
CN: 无碰撞时第 $i$ 个人有 $d-i+1$ 个可用生日。近似用 $\ln(1-x)\approx -x$。

Use / 用法.
CN: 哈希碰撞、随机抽样重复概率。

14.4 随机游走 / Random Walks#

Idea / 思想.
CN: 随机游走是状态按概率转移的过程。常用工具包括期望递推、马尔可夫链、吸收状态分析。

Use / 用法.
CN: 赌博破产、图上随机游走、算法随机化。若课程后续涉及，可把状态期望写成方程组求解。

15. 高频证明模板 / High-Frequency Proof Templates#

15.1 证明集合相等 / Proving Set Equality#

CN: 证明 $A=B$:

1. Take arbitrary $x\in A$, prove $x\in B$.
2. Take arbitrary $x\in B$, prove $x\in A$.

EN: Prove both inclusions.

15.2 证明函数单射、满射 / Injection and Surjection#

• Injection / 单射: assume $f(x_1)=f(x_2)$, prove $x_1=x_2$.
• Surjection / 满射: take arbitrary $y$ in codomain, find $x$ with $f(x)=y$.
• Bijection / 双射: prove both or construct inverse.

15.3 证明整除 / Divisibility Proof#

15.4 证明同余 / Congruence Proof#

CN: 先把同余转成整除，再用代数。

15.5 组合证明 / Combinatorial Proof#

CN: 要证明等式 $LHS=RHS$，找一个集合，左边和右边用两种方法计数。
EN: Count the same set in two ways.

15.6 概率四步法 / Probability Four-Step Method#

1. Define the sample space.
2. Check whether outcomes are equally likely.
3. Define the event.
4. Count or compute probability.

15.7 图论题流程 / Graph Problem Checklist#

1. Is the graph directed or undirected?
2. Simple graph or multigraph?
3. Are you counting edges, vertices, paths, or colors?
4. For Euler: check degrees and connectivity.
5. For planar: use Euler formula and edge bounds.
6. For trees: use connected plus acyclic or $e=n-1$.
7. For bipartite: check odd cycles or 2-coloring.

16. 公式索引 / Formula Index#

16.1 Logic#

• $p \to q \equiv \neg p \lor q$
• $p \leftrightarrow q \equiv (p \to q) \land (q \to p)$
• $\neg\forall x\,P(x) \equiv \exists x\,\neg P(x)$
• $\neg\exists x\,P(x) \equiv \forall x\,\neg P(x)$

16.2 Sets#

• $|\mathcal{P}(A)|=2^{|A|}$
• $|A\cup B|=|A|+|B|-|A\cap B|$
• $\left|\bigcup_{i=1}^n A_i\right|=\sum_i |A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots$

16.3 Sums#

• $\sum_{i=1}^n i=\dfrac{n(n+1)}{2}$
• $\sum_{i=1}^n i^2=\dfrac{n(n+1)(2n+1)}{6}$
• $\sum_{i=1}^n i^3=\left[\dfrac{n(n+1)}{2}\right]^2$
• $\sum_{i=0}^n r^i=\dfrac{r^{n+1}-1}{r-1}$, $r\ne 1$
• $\sum_{i=0}^{\infty} r^i=\dfrac{1}{1-r}$, $|r|<1$
• Double sums $\sum_i\sum_j a_{ij}$ can be switched by rewriting the index region.

16.4 Asymptotics#

• $f=O(g)$ iff $|f(n)|\le C|g(n)|$ eventually.
• $f=\Theta(g)$ iff $f=O(g)$ and $f=\Omega(g)$.
• $n!\sim \sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n$.

16.5 Number Theory#

• $a\mid b$ iff $b=ak$ for some $k\in\mathbb{Z}$.
• $a\equiv b\pmod{m}$ iff $m\mid(a-b)$.
• $a=dq+r$, $0\le r<d$.
• $\gcd(a,b)=\gcd(b,a\bmod b)$.
• $\gcd(a,b)=sa+tb$ for some $s,t\in\mathbb{Z}$.
• $a$ has an inverse modulo $m$ iff $\gcd(a,m)=1$.
• $ax\equiv b\pmod{m}$ is solvable iff $\gcd(a,m)\mid b$.
• Fermat: $a^{p-1}\equiv 1\pmod{p}$ if $p$ is prime and $p\nmid a$.
• Euler: $a^{\varphi(n)}\equiv 1\pmod{n}$ if $\gcd(a,n)=1$.
• CRT: $x\equiv\sum_i a_iM_iy_i\pmod{M}$.
• Pseudoprime base $a$: composite $n$ with $a^{n-1}\equiv1\pmod{n}$.
• Affine cipher: $E(x)\equiv ax+b\pmod{26}$, where $\gcd(a,26)=1$.

16.6 Counting#

• $P(n,r)=\dfrac{n!}{(n-r)!}$
• $\binom{n}{r}=\dfrac{n!}{r!(n-r)!}$
• $\binom{n}{r}=\binom{n}{n-r}$
• $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$
• $\sum_{r=0}^n\binom{n}{r}=2^n$
• $(x+y)^n=\sum_{k=0}^n\binom{n}{k}x^{n-k}y^k$
• Stars and bars: the number of nonnegative solutions to $x_1+\cdots+x_k=n$ is $\binom{n+k-1}{k-1}$.
• Derangements: $D_n=n!\sum_{k=0}^n\dfrac{(-1)^k}{k!}$.

16.7 Probability#

• $\Pr(A^c)=1-\Pr(A)$
• $\Pr(A\cup B)=\Pr(A)+\Pr(B)-\Pr(A\cap B)$
• $\Pr(A\mid B)=\dfrac{\Pr(A\cap B)}{\Pr(B)}$
• Bayes: $\Pr(B_j\mid A)=\dfrac{\Pr(A\mid B_j)\Pr(B_j)}{\sum_i\Pr(A\mid B_i)\Pr(B_i)}$
• $\mathbb{E}[X]=\sum_x x\Pr(X=x)$
• $\mathbb{E}\left[\sum_iX_i\right]=\sum_i\mathbb{E}[X_i]$
• $\operatorname{Var}(X)=\mathbb{E}[X^2]-\mathbb{E}[X]^2$
• Markov: $\Pr(X\ge a)\le\dfrac{\mathbb{E}[X]}{a}$
• Chebyshev: $\Pr(|X-\mathbb{E}[X]|\ge a)\le\dfrac{\operatorname{Var}(X)}{a^2}$

16.8 Recurrences#

• For $T(n)=aT(n/b)+f(n)$, compare $f(n)$ with $n^{\log_b a}$.
• $G(x)=\sum_{n\ge0}a_nx^n$
• $\dfrac{1}{1-x}=\sum_{n\ge0}x^n$
• $\dfrac{1}{(1-x)^2}=\sum_{n\ge0}(n+1)x^n$

16.9 Relations#

• Equivalence relation $=$ reflexive $+$ symmetric $+$ transitive.
• Partial order $=$ reflexive $+$ antisymmetric $+$ transitive.

16.10 Graphs and Trees#

• $\sum_{v\in V}\deg(v)=2|E|$
• Tree: $e=n-1$
• Connected planar graph: $v-e+f=2$
• Simple planar graph: $e\le3v-6$
• Bipartite planar graph: $e\le2v-4$
• $\chi(K_n)=n$
• $\chi(C_n)=2$ if $n$ is even; $\chi(C_n)=3$ if $n$ is odd.
• $\chi(G)\le\Delta+1$
• $R(3,3)=6$
• Hall condition: $|N(S)|\ge|S|$ for every $S\subseteq L$.
• Full $m$-ary tree: $n=mi+1$, $l=(m-1)i+1$.

16.11 Boolean Algebra#

• $(x+y)'=x'y'$
• $(xy)'=x'+y'$
• DNF and CNF represent every Boolean function.
• NAND alone and NOR alone are functionally complete.

17. Quiz 高频题型 / Frequent Quiz Patterns#

CN: 本目录中的 Quiz 1 主要考早期基础，但题目经常把基础概念揉在一起。下面是对应的复习入口。

17.1 取石子游戏 / Stone Games#

Single pile, remove 1 to 3 / 单堆每次取 1 到 3 个.

Proof / 证明.
CN: 若剩 $4k$ 个，无论取 $1,2,3$，对方都可取到下一个 $4(k-1)$。若剩数不是 4 的倍数，当前玩家可取 $r$ 个使剩数变成 4 的倍数。

Two-pile Nim idea / 双堆 Nim 思想.

CN: 若题目只允许每次从一堆取 $1,2,3$，可把每堆大小按模 4 化成 Grundy 值；两堆的异或非 0 时先手有必胜策略。

Use / 用法.
CN: Quiz 中出现“两堆石子每次从一堆取 1,2,3 个，取最后者胜”时，先看每堆模 4。$115\equiv 3 \pmod{4}$, $125\equiv 1 \pmod{4}$，$3 xor 1 \ne 0$，所以先手能赢。

18. 中英术语表 / Bilingual Glossary#