【离散数学及其应用】课程笔记
wishapig
·
2026-01-18 22:38:04
·
算法·理论
成绩 96/100 ，绩点 5.0
这是大一下的课，补一部分的笔记（由于这门课有较多知识点对 oier 来说是常识，因此笔记只有某几章内容）
第四章 数论和密码学
4.1 整除性和模运算（Divisibility and Modular Arithmetic）
4.1.2 Division
定义 1. 设 a,b\in \mathbb{Z},a\not=0 ，则称 a|b 当且仅当 \dfrac{b}{a} 为整数（a divides b ），称 a 为 b 的一个因子（divisor/factor），b 为 a 的一个倍数（multiple）
定理 1. 设 a,b,c\in \mathbb{Z},a\not=0 ，则：
a|b,a|c\Rightarrow a|(b+c)
a|b\Rightarrow a|(bc)
a|b,b|c\Rightarrow a|c
推论 1. 设 a,b,c\in \mathbb{Z},a\not= 0 ，则：a|b,a|c\Rightarrow a|(mb+nc)\ (m,n\in \mathbb{Z})
4.1.3 The Division Algorithm
定理 2. 设 a\in \mathbb{Z},d\in \mathbb{Z}^{+} ，则存在唯一的一对整数 q,r ，满足 a=dq+r ，其中 0\le r<d
定义 2. 在上一条中，称 d 为除数（divisor），a 为被除数（dividend），q 为商（quotient），r 为余数（remainder），写为：q=a\ \operatorname{div}\ b ，r=a\ \operatorname{mod}\ d
4.1.4 Modular Arithmetic
定义 3. 设 a,b\in \mathbb{Z},m\in \mathbb{Z}^+ ，则称 a,b 在模 m 下同余当且仅当 m|(a-b) ，a\equiv b\pmod m （a is congruent to b modulo m ）称 a\equiv b\pmod m 为同余式（congruence），其中 m 为模数（modulus/moduli(pl.)）
定理 3. 设 a,b\in \mathbb{Z},m\in \mathbb{Z}^+ ，则 a\equiv b\pmod m\Leftrightarrow a\ \operatorname{mod}\ m=b\ \operatorname{mod}\ m
定理 4. 设 a,b\in \mathbb{Z},m\in \mathbb{Z}^+ ，则 a\equiv b\pmod m\Leftrightarrow \exist k\in \mathbb{Z},a=b+km
定理 5. 设 m\in \mathbb{Z}^+ ，且 a\equiv b\pmod m,c\equiv d\pmod m ，则 a+c\equiv b+d\pmod m,ac\equiv bd\pmod m
推论 2. 设 a,b\in \mathbb{Z},m\in \mathbb{Z}^+ ，则 (a+b)\operatorname{mod}m=((a\operatorname{mod}m)+(b\operatorname{mod} m))\operatorname{mod}m ，(ab)\operatorname{mod}m=((a\operatorname{mod}m)\times (b\operatorname{mod} m))\operatorname{mod}m
4.1.5 Arithmetic Modulo m
在模 m 意义下，(\mathbb{Z},+_m) 构成交换群（commutative group），(\mathbb{Z},+_m,\times_m) 构成交换环（commutative ring）
其满足：封闭性（closure），结合律（associativity），交换律（commutativity），存在单位元（identity elements），存在加法逆元（addictive inverses），分配律（distributivity）
4.2 整数的表示及相关算法（Integer Representation and Algorithms）
4.2.2 Representations of Integers
定理 1. 设 b\in \mathbb{Z},b>1,n\in \mathbb{Z}^+ ，则存在唯一的表示：n=a_kb^k+a_{k-1}b^{k-1}+\cdots +a_1b+a_0 ，其中 k,a_i\in \mathbb{N},a_i<b,a_k\not=0 ，称为 n 的 b 进制表示（base b expansion of n ）
当 b=2 时为二进制表示（binary expansion）
当 b=8 时为八进制表示（octal expansion）
当 b=10 时为十进制表示（decimal expansion）
当 b=16 时为十六进制表示（hexadecimal expansion）
4.3 质数和最大公约数（Primes and Greatest Common Divisors）
4.3.2 Primes
定义 1. 设 p\in \mathbb{N},p>1 ，称 p 为质数（prime）当且仅当 p 的正因子只有 1 和 p ；设 p'\in \mathbb{N}^+ 且 p' 不是质数，则称 p' 为合数（composite）
定理 1. 算术基本定理（The Fundamental Theorem of Arithmetic） 任意大于 1 的整数都可以唯一写成若干个质数之积
4.3.3 Trial Division
定理 2. 若 n 为一个大于 1 的合数，则 n 存在一个 \le \sqrt{n} 的质因子
4.3.4 The Sieve of Eratosthenes
定理 3. 质数有无穷多个（证明略）
定理 4. 设 \pi(n) 为 \le n 的质数个数，则 \pi (n)\sim \dfrac{n}{\ln n}(n\rightarrow \infty)
4.3.6 Greatest Common Divisors and Least Common Multiple
定义 2. 设 a,b 为不同时为 0 的整数，设 d 为最大的能同时整除 a,b 的整数，则称 d 为 a,b 的最大公约数（greatest common divisor），记为 d=\gcd(a,b)
定义 3. 整数 a,b 互质，当且仅当 \gcd(a,b)=1
定义 4. n 个整数 a_1,a_2,\cdots ,a_n 两两互质，当且仅当 \gcd(a_i,a_j)=1(1\le i<j\le n)
定义 5. 设 a,b 为两个正整数，设 d 为最小的能同时被 a,b 整除的整数，则称 d 为 a,b 的最小公倍数（least common multiple），记为 d=\operatorname{lcm}(a,b)
定理 5. 设 a,b 为两个正整数，则 ab=\gcd(a,b)\times \operatorname{lcm}(a,b)
4.3.7 The Euclidean Algorithm
引理 1. 设 a=bq+r(a,b,q,r\in \mathbb{Z}) ，则 \gcd(a,b)=\gcd(b,r)
4.3.8 gcds as Linear Combinations
定理 6. 裴蜀定理（Bézout's Theorem） 若 a,b\in \mathbb{N}^+ ，则存在 s,t\in \mathbb{Z} ，满足 \gcd(a,b)=sa+tb ，其中 s,t 称为裴蜀系数（Bézout coefficients）
引理 2. 设 a,b,c\in \mathbb{N}^+ ，若 \gcd(a,b)=1,a|(bc) ，则 a|c
引理 3. 设 p 为质数，若 p|(a_1a_2\cdots a_n) ，则存在 i\in [1,n] ，满足 p|a_i
定理 7. 设 m\in \mathbb{N}^+,a,b,c\in \mathbb{Z} ，若 ac\equiv bc\pmod m 且 \gcd(c,m)=1 ，则 a\equiv b\pmod m （这条定理说明当 c,m 互质时存在乘法逆元 c^{-1} ，满足 cc^{-1}\equiv 1\pmod m ）
4.4 求解同余式（Solving Congruences）
4.4.2 Linear Congruences
定理 1. 若 a,m(m>1) 互质，则 a 在\bmod m 意义下的乘法逆元存在且唯一
4.4.3 The Chinese Remainder Theorem
定理 2. 中国剩余定理（The Chinese Remainder Theorem）
设 m_1,m_2,\cdots, m_n 是 n 个两两不同的质数，则同余方程组：
\begin{cases}
x\equiv a_1\pmod {m_1}\\
x\equiv a_2\pmod {m_2}\\
\ \ \ \ \ \vdots\\
x\equiv a_n\pmod {m_n}
\end{cases}
存在唯一解 x\equiv\sum a_iM_i(M_i^{-1}\pmod {m_i})\pmod M ，其中 M=\prod m_i ，M_i=\dfrac{M}{m_i}
4.4.5 Fermat's Little Theorem
定理 3. 费马小定理（Fermat's Little Theorem） 设 p 为质数，a 不为 p 的倍数，则 a^{p-1}\equiv 1\pmod p 或 a^p\equiv a\pmod p
4.4.6 Pseudoprimes
定义 1. 设 b\in \mathbb{N}^+ ，n 为一个正合数，若 b^{n-1}\equiv 1\pmod n ，则称 n 为以 b 为基下的伪素数
定义 2. 设 n 为一个正合数，若对所有 \gcd(n,b)=1 的 b 均有 b^{n-1}\equiv 1 \pmod n ，则称 n 为一个 Carmichael Number
4.4.7 Primitive Roots and Discrete Logarithms
定义 3. 对质数 p ，若 r^k(k=0,1,2,\cdots, p-1) 在\bmod p 下两两不同，则称 r 为一个\bmod p 意义下的原根（primitive root）
定义 4. 设 p 为质数，r 为一个\bmod p 意义下的原根，a\in [1,p-1] ，若 r^e\equiv a \pmod p(0\le e<p) ，则称 e 为 a 对 r 的离散对数（Discrete Logarithm），即为 e=\log_ra
第六章 计数
6.1 计数基础（The Basic of Counting）
6.1.2 Basic Counting Principles
6.1.4 The Subtraction Rule（Inclusion-Exclusion for Two Sets）
|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|
6.1.6 Tree Diagrams
用树形图来展示所有的可能性（类似 Trie 树）
6.2 鸽巢原理（The Pigeonhole Principle）
6.2.1 Introduction
定理 1. \ge k+1 个物品放入 k 个盒子中，则至少有一个盒子放了至少 2 个物品
推论 1. 由 \ge k+1 个元素的集合到 k 个元素的集合的所有函数都不是一对一的（one-to-one）
6.2.2 The Generalized Pigeonhole Principle
定理 2. n 个物品放入 k 个盒子中，则至少有一个盒子放了至少 \left\lceil\dfrac{n}{k}\right\rceil 个物品
6.2.3 Some Elegant Applications of the Pigeonhole Principle
定理 3. 任意一个长为 n^2+1 的序列（序列中元素两两不同），则存在一个长为 n+1 的严格单增或严格单减子序列
6.3 排列和组合（Permutations and Combinations）
6.3.2 Permutations
定理 1. 设 n,r 均为正整数且 1\le r\le n ，则存在 P(n,r)=n(n-1)(n-2)\cdots(n-r+1) 种不同的 n 个元素的长为 r 的排列
推论 1. P(n,r)=\dfrac{n!}{(n-r)!}
6.3.3 Combinations
定理 2. 设 n,r 均为正整数且 1\le r\le n ，则存在 C(n,r)=\dfrac{n!}{r!(n-r)!} 种不同的 n 个元素的长为 r 的组合
推论 2. C(n,r)=C(n,n-r)
定义 1. combinatorial proof：利用组合意义或通过建立双射完成证明的手段
6.4 二项式系数及恒等式（Binomial Coefficients and Identities）
6.4.1 The Binomial Theorem
定理 1. 二项式定理（The Binomial Theorem）
(x+y)^n=\sum_{i=0}^n\binom{n}{i}x^iy^{n-i}
推论 1. \sum_{i=0}^n\binom{n}{i}=(1+1)^n=2^n
推论 2. \sum_{i=0}^n\binom{n}{i}(-1)^n=(1-1)^n=[n=0]
推论 1. \sum_{i=0}^n\binom{n}{i}2^n=(2+1)^n=3^n
6.4.2 Pascal's Identity and Triangle
定理 2. 帕斯卡恒等式（Pascal's Identity） 设 n,k\ge 1,n\ge k 则
\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}
（讨论 n 个元素中的某个元素有没有选即可）
6.4.3 Other Identities Involving Binomial Coefficients
定理 3. 范德蒙德恒等式（Vandermonde‘s identity）
\binom{m+n}{r}=\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}
（从 m+n 个物品中选 k 个，则考虑分别从 m 个和 n 个物品中选了 k 个和 r-k 个）
（需要扩展组合数的定义到 n,m\le 0 或 n\le m 的情况，不过这些都是平凡的）
推论 4. \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}
定理 4. \binom{n+1}{m+1}=\sum_{k=m}^n\binom{k}{m} （列向前缀和有封闭形式，行向前缀和无封闭形式）
6.5 广义排列组合（Generalized Permutations and Combinations）
6.5.2 Permutations with Repetition
定理 1. 长为 r 的 n 个元素的排列，允许元素重复，则排列数为 n^r
6.5.3 Combinations with Repetition
定理 2. 长为 r 的 n 个元素的组合，允许元素重复，则组合数为 \binom{n+r-1}{n-1}
证明：对 r 进行查板，划分成 n 个可以为空的部分
6.5.4 Permutations with Indistinguishable Objects
定理 3. 多重组合数，有 n_1 个物品 1 ，n_2 个物品 2 ，\cdots ，n_m 个物品 m ，则它们的排列数为：
\binom{n}{n_1,n_2,\cdots,n_m}=\dfrac{n!}{\prod_{i=1}^m n_i!}\ \ \ \ \ \ \ \left(n=\sum_{i=1}^m n_i\right)
6.5.5 Distributing Objects into Boxes
盒子可区分，小球可区分
则设第 i 个盒子个小球，共有 n=\sum n_i 个小球，则方案数即为广义组合数 \binom{n}{n_1,\cdots}
盒子可区分，小球不可区分
则此时我们只关注每个盒子里放了多少个球，换言之，求 x_1+x_2+\cdots+x_m=n 的解个数
若 x_i\ge0 ，则方案数为 \binom{n+m-1}{m-1}
盒子不可区分，小球可区分
将 n 个可区分的小球放到 m 个不可区分的盒子中，每个盒子至少放一个
则方案数为第二类斯特林数 {n\brace m} ，有边界条件，递推关系，表达式如下，可以使用二项式反演或容斥原理推导（本质相同）
\begin{aligned}
&{0\brace 0}=1\\
&{n\brace 0}=0\ \ \ (n\ge 1)\\
&{n\brace m}={n-1\brace m-1}+m{n-1\brace m}\\
&{n\brace m}=\dfrac{1}{m!}\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n
\end{aligned}
若允许盒子有空，则方案数为斯特林数一行的前缀和
第八章 高级计数技巧
8.1 递推式的应用（Applications of Recurrence Relations）
汉诺塔问题：H_n=2H_n+1 ，H_1=1
卡特兰数问题（合法括号序列数）：Cat_n=\sum_{k=0}^{n-1}Cat_k\cdot Cat_{n-k-1} ，Cat_0=Cat_1=1
8.2 求解线性递推式（Solving Linear Recurrence Relations）
8.2.1 Introduction
定义 1. 常系数 k 阶齐次线性递推（linear homogeneous recurrence of degree k with constant coefficients）
a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}
其中 c_i 为常数，c_k\not=0 ，且需要提供初始条件 a_0\sim a_{k-1}
8.2.2 Solving Linear Homogeneous Recurrence Relations with constant coefficients
定理 1. 对递推式 a_n=c_1a_{n-1}+c_2a_{n-2} ，若 r_1,r_2 是方程 x^2-c_1x-c_2=0 的两个不同的根，则 a_n 可写为 a_n=\alpha_1r_1^n+\alpha_2r_2^n ，其中 \alpha_1,\alpha_2 均为常数
定理1. 补充说明 对递推式 a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k} ，称方程 x^k-c_1x^{k-1}-c_2x^{k-2}-\cdots-c_k=0 为其特征方程（characteristic equation），这个方程的根称为特征根（characteristic roots）
定理 2. 对递推式 a_n=c_1a_{n-1}+c_2a_{n-2}(c_2\not=0) ，若其特征方程有一个重根 r_0 ，则 a_n 可写为 a_n=\alpha_1r_0^n+\alpha_2nr_0^n ，其中 \alpha_1,\alpha_2 均为常数
定理 3. 对递推式 a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k} ，若其特征方程有 k 个不同的根 r_{1\cdots k} ，则 a_n 可写为 a_n=\sum_{i=1}^k\alpha_ir_i^n ，其中 \alpha_i 均为常数
定理 4. 对递推式 a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k} ，若其特征方程有 t 个不同的根 r_1,r_2,\cdots ,r_t ，各根重数分别为 m_1,m_2,\cdots m_{t} （自然得到 \sum m_i=k ），则 a_n 可写为
a_n=\sum_{i=1}^tr_i^n\sum_{j=0}^{m_i-1}\alpha_{i,j}n^j
其中 \alpha_{i,j} 均为常数（可以注意到内层 \sum 实际上是一个关于 n 的 m_i-1 次多项式）
8.2.3 Linear Nonhomogeneous Recurrence Relations with Constant Coefficients
定义 2. 常系数 k 阶非齐次线性递推（linear nonhomogeneous recurrence of degree k with constant coefficients）
a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}+F(n)
其中 c_i 为常数，c_k\not=0 ，F(n) 为只与 n 有关的非零值函数
定义 3. 对一个非齐次线性递推 a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}+F(n) 其对应的常系数 k 阶齐次线性递推为 a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}
定理 5. 对非齐次线性递推 a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}+F(n) ，设其一组特解为 \{a_n^{(p)}\} ，其对应的齐次线性递推的一组通解为 \{a_n^{(h)}\} ，则原非齐次线性递推的通解为 \{a_n^{(p)}+a_n^{(h)}\}
例：a_n=3a_{n-1}+2n
其中 a_n=3a_{n-1} 的通解为 a_n^{(h)}=\alpha \cdot 3^n
而 a_n=3a_{n-1}+2n 特解：设 a_n=pn+q ，解出 p=-1,q=-\dfrac{3}{2} ，则特解 a_n^{(p)}=-n-\dfrac{3}{2}
因此通解为 a_n=\alpha\cdot 3^n-n-\dfrac{3}{2}
定理 6. 若 F(n)=(b_tn^t+b_{t-1}n^{t-1}+\cdots+b_1n+b_0)\cdot s^n ，则：
若 s 为特征根，则特解为 a_n^{(p)}=n^m(p_tn^t+p_{t-1}n^{t-1}+\cdots+p_1n+p_0)\cdot s^n （m 为 s 的重数）
若 s 不为特征根，则特解为 a_n^{(p)}=(p_tn^t+p_{t-1}n^{t-1}+\cdots+p_1n+p_0)\cdot s^n
8.3 分治算法及其递推关系（Divide-and-Conquer Algorithms and Recurrence Relations）
8.3.2 Divide-and-Conquer Recurrence Relations
定理 1. 设函数 f 单增且满足 f(n)=af\left(\dfrac{n}{b}\right)+c ，其中默认 b|n,a\ge 1,c>0 均为常数，则有：
f(n)=\begin{cases}
O(n^{\log_ba})&\text{if}\ \ a>1\\
O(\log n)&\text{if}\ \ a=1
\end{cases}
定理 2. 主定理（Master Theorem） 设函数 f 单增且满足 f(n)=af\left(\dfrac{n}{b}\right)+cn^d ，其中 n=b^k(k\in \mathbb{N}^+),a\ge 1,c>0,d\ge 0 均为常数，则有：
f(n)=\begin{cases}
O(n^d)&\text{if}\ \ a<b^d\\
O(n^d\log n)&\text{if}\ \ a=b^d\\
O(n^{\log_ba})&\text{if}\ \ a>b^d
\end{cases}
8.4 生成函数（Generating Functions）
8.4.1 Introduction
定义 1. 实数序列 a_0,a_1,\cdots ,a_n,\cdots 的生成函数为一个无穷级数 G(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots=\sum_{k\ge0}a_kx^k
这种生成函数称为普通型生成函数（ordinary generating function, OGF），与之对应的还有指数型生成函数（EGF）和概率生成函数（PGF）
8.4.2 Useful Facts About Power Series
定理 1. 设 f(x)=\sum_{k\ge0} a_kx^k ，g(x)=\sum_{k\ge0} b_kx^k ，则：
\begin{aligned}
&f(x)\pm g(x)=\sum_{k\ge0}(a_k\pm b_k)x^k\\
&f(x)g(x)=\sum_{k\ge 0}\left(\sum_{i=1}^ka_ib_{k-i}\right)x^k
\end{aligned}
由此可得一个重要的生成函数：
\dfrac{1}{(1-x)^2}=\dfrac{1}{1-x}\cdot\dfrac{1}{1-x}=\sum_{k\ge 0}\left(\sum_{i=0}^k 1\right)x^k=\sum_{k\ge 0}(k+1)x^k
定义 2. 扩展二项式系数（extended binomial coefficients）
\binom{u}{k}=\dfrac{u^{\underline{k}}}{k!}
其中 k\in \mathbb{N},u\in \mathbb{R} ，u^{\underline{k}} 为 u 的 k 次下降幂 u(u-1)\cdots (u-k+1)
定理 2. 扩展二项式定理（The Extended Binomial Theorem）
(1+x)^u=\sum_{k\ge0}\binom{u}{k}x^k\ \ \ \ \ (u\in \mathbb{R},|x|< 1)
8.5 容斥（Inclusion-Exclusion）
8.5.2 The Principle of Inclusion-Exclusion
定理 1. 容斥原理 设 A_1,A_2,\cdots, A_n 为 n 个有限集，则：
|A_1\cup A_2\cup\cdots\cup A_n|=\sum_{S\subseteq\{1,2,\cdots,n\}}(-1)^{|S|+1}\left|\bigcap_{i\in S} A_i\right|
8.6 容斥的应用（Applications of Inclusion-Exclusion）
8.6.4 The Number of Onto Functions
定理 1. 设 n,m\in \mathbb{N}^+,m\ge n ，则从一个大小为 m 的集合到一个大小为 n 的集合的单射个数为：
\sum_{i=0}^n(-1)^i\binom{n}{i}(n-i)^m
（即容斥哪些元素没有被映射到）
定理 2. n 个元素的错排（dearrangement）的个数为：
D_n=n!\left[1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+(-1)^n\dfrac{1}{n!}\right]
（容斥哪些位置没有错开即可）
第九章 关系
9.1 关系及其性质（Relations and Their Properties）
9.1.1 Introduction
定义 1. 设 A,B 为集合，则 A,B 之间的一个二元关系（binary relation）为一个 A\times B 的子集
9.1.3 Relations on a Set
定义 2. 设 A 为集合，则 A 上的一个关系为一个 A\times A 的子集
9.1.4 Properties of Relations
定义 3. 自反性（reflexive） 称 A 上的关系 R 是自反的，当且仅当 \forall x\in A,(x,x)\in R
定义 4.1. 对称性（symmetric） 称 A 上的关系 R 是对称的，当且仅当 \forall a,b\in A,(a,b)\in R\Leftrightarrow (b,a)\in R
定义 4.2. 反对称性（antisymmetric） 称 A 上的关系 R 是反对称的，当且仅当 \forall a,b\in A,(a,b)\in R\and (b,a)\in R\Rightarrow a=b
定义 4.3. 非对称性（asymmetric） 称 A 上的关系 R 是非对称的，当且仅当 \forall a,b\in A,(a,b)\in R\Rightarrow (a,b)\not\in R
定义 5. 传递性（transitive） 称 A 上的关系 R 是传递的，当且仅当 \forall a,b,c\in A,(a,b)\in R\and (b,c)\in R\Rightarrow (a,c)\in R
9.1.5 Combining Relations
定义 6. 设 R 为 A 到 B 的关系，S 为 B 到 C 的关系，则定义 S\circ R=\{(a,c)|a\in A,c\in C, \exist b\in B,(a,b)\in R,(b,c)\in S\} ，书写时注意 S 在前
定义 7. 设 R 为 A 上的关系，则 R^{n+1}=R^n\circ R ，R^1=R （n\in \mathbb{N} ）
定理 1. A 上的关系 R 是传递的当且仅当 \forall n\in \mathbb{N^+},R^n\subseteq R
9.4 关系的闭包（Closures of Relations）
9.4.2 Different Types of Closures
定义 1. 设 R 是 A 上的一个关系，P 是某种性质（如自反性，对称性，传递性）则 R 关于性质 P 的闭包（closure）为 R 的最小的满足性质 P 的超集
如 R 的自反闭包为 R\cup \Delta （\Delta=\{(a,a)|a\in A\} ），R 的对称闭包为 R\cup R^{-1} （R^{-1} 为 R 的逆关系，R^{-1}=\{(b,a)|(a,b)\in R\} ）
9.4.3 Paths in Directed Graphs
定义 2. 对有向图 G=(V,E) ，从节点 a 至节点 b 的路径为节点序列 x_0,x_1,\cdots,x_n ，其中 x_0=a,x_n=b,(x_{i-1},x_i)\in E\ (1\le i\le n) ，且称这条路径的长度为 n （即路径中边的个数）
定理 1. 设 R 为 A 上的一个关系，则存在一条从 a 到 b ，长度为 n 的路径，当且仅当 (a,b)\in R^n
定义 3. 设 R 为 A 上的一个关系，定义 R^* 为 R 的连同关系，即 R^*=\{(a,b)|\text{b is reachable from a}\} ，自然得到：
R^*=\bigcup_{n=1}^{+\infty}R^n
定理 2. R 的传递闭包就是 R 的连通关系 R^*
引理 1. 设节点个数为 n ，则对节点 a ，若存在 a\rightarrow a 的回路（circuit/cycle），则存在长度 \le n 的回路，对节点 a,b\ (a\not=b) ，若存在 a\rightarrow b 的路径，则存在长度 \le n-1 的路径
定理 3. 由上述引理，得到：
\begin{aligned}
M_{R^*}&=M_R\cup M_{R^2}\cup\cdots\cup M_{R^n}\\
&=M_R\cup M_R^2\cup \cdots\cup M_R^n
\end{aligned}
于是可以通过将 M_R 的幂次叠加得到传递闭包
9.5 等价关系（Equivalence Relations）
9.5.2 Equivalence Relations
定义 1. 称 A 上的关系 R 是等价关系当且仅当 R 同时具有自反性，对称性，传递性
定义 2. 对 a,b\in A ，若 (a,b)\in R ，则称 a,b 等价（equivalent），记为 a\sim b
9.5.3 Equivalence Classes
定义 3. 设 R 是一个 A 上的等价关系，a\in A ，记 [a]_R=\{b|(a,b)\in R\} 为所有与 a 等价的元素形成的集合，则称 [a]_R 为 a 的等价类（equivalence class），其中任意的 b\in [a]_R 均可被视作这个等价类的代表元素（representative）
9.5.4 Equivalence Classes and Partitions
定理 1. 设 R 是一个 A 上的等价关系，a,b\in A ，则以下三个表述是等价的
aRb((a,b)\in R)
[a]_R=[b]_R
[a]_R\cap [b]_R=\empty
定理 2. 设 R 是一个 A 上的等价关系，则由 R 定义出的等价类形成对 A 的划分（partition），相反地，给出一个 A 的划分，也存在一个与之对应的等价关系
9.6 偏序（Partial Orderings）
9.6.1 Introduction
定义 1. 称集合 S 上的关系 R 是一个偏序关系当且仅当 R 同时具有自反性，反对称性，传递性；二元组 (S,R) 被称为一个偏序集（partial ordered set/poset）其中 S 中的元素被称为偏序集的元素
定义 2. 设偏序集 (S,\preccurlyeq) ，a,b 是它的两个元素，则称 a,b 是可比的（comparable）当且仅当 a\preccurlyeq b 或 b\preccurlyeq a ，若均不满足，则称 a,b 是不可比的（incomparable）
定义 3. 若偏序集中的任意两个元素都是可比的，则称 R 为一个全序关系（total ordering），相应偏序集也被称为全序集（如 (\mathbb{Z},\leqslant)
定义 4. 称偏序集 (S,\preccurlyeq) 是良序的（well-ordered）当且仅当 \preccurlyeq 是全序关系，且 S 的每个非空子集都有一个最小元素，如以字典序定义的 \preccurlyeq ，就有：
定理 1. 良序归纳原理（The Principle of Well-Ordered Induction） 设 S 是一个良序集，则 P(x) 对所有 x\in S 为真，当下列条件成立：
每个 y\in S ，若所有 x\prec y 的 x 均有 P(x) 为真，则 P(y) 也为真
（这一步称为归纳步，induction step）
注意：这种归纳方法不需要 basis step，因为对 S 的最小元素 y_0 ，不存在 x\in S,x\prec y_0 ，此时 P(y_0) 自动为真（感觉有点奇怪）
9.6.3 Hasse Diagrams
当所有偏序关系中的二元数对以有向边连接，入点在上，出点在下，再删除所有可以通过传递性导出的边和自环，就可以得到哈塞图（Hasse Diagram）
具体的图可以看教材
定义 5. 设 (S,\preccurlyeq) 为一个偏序集，x,y\in S ，则称 y 覆盖（cover）x 当且仅当 x\prec y 且不存在另一个 z\in S ，x\prec z\prec y ，这样所有的 (x,y) 形成的关系即为覆盖关系（covering relation）
容易发现哈塞图即由覆盖关系形成
9.6.4 Maximal and Minimal Elements
定义 6. 设偏序集 (S,\preccurlyeq) ，a\in S ，则给出以下几个定义：
a$ 为极大值（Maximal Element）当且仅当不存在 $b\in S$，$a\prec b
a$ 为最大值（Greatest Element）当且仅当任意 $b\in S$，$b\preccurlyeq a
a$ 为极小值（Minimal Element）当且仅当不存在 $b\in S$，$b\prec a
a$ 为最小值（Least Element）当且仅当任意 $b\in S$，$a\preccurlyeq b
最大值/最小值若存在，则只有唯一一个，极大值/极小值可以有多个
定义 7. 设偏序集 (S,\preccurlyeq) ，集合 A\subseteq S,u\in S ，则给出以下几个定义：
若 \forall a\in A 都有 a\preccurlyeq u ，则称 u 是集合 A 的一个上界（upper bound）
若 \forall a\in A 都有 u\preccurlyeq a ，则称 u 是集合 A 的一个下界（lower bound）
对集合 A ，这四个都可能不存在
9.6.5 Lattices
定义 8. 若偏序集 (S,\preccurlyeq) 满足其任意非空子集都存在最小上界和最大下界，则称该偏序集为一个栅格（lattice）
9.6.6 Topological Sorting
引理 1. 设 (S,\preccurlyeq) 是一个有限偏序集，则 S 存在极小值
拓扑排序通过不断删除极小值来得到一个新的全序关系 a_1\prec_t a_2\prec_t\cdots\prec_t a_n ，其中任意 x,y\in S ，若 x\prec y ，则有 x\prec_t y