zzh/handsomezhuzhu.github.io

Fork 0

mirror of https://github.com/handsomezhuzhu/handsomezhuzhu.github.io.git synced 2026-02-20 11:50:14 +00:00

Files

handsomezhuzhu ce2419a33e 离散

2026-01-07 00:27:21 +08:00

11 KiB

Raw Permalink Blame History

第二章：集合论与二元关系

2.1 集合论

2.1.1 基础运算

并 (\displaystyle A \cup B)、交 (\displaystyle A \cap B)、补 (\displaystyle \bar{A})、差 (\displaystyle A - B)。
对称差 (\displaystyle A \oplus B)：$\displaystyle A \oplus B = (A - B) \cup (B - A)$。
- 属于 A 或属于 B，但不同时属于两者。
- 特性：\displaystyle A \oplus A = \emptyset, \displaystyle A \oplus \emptyset = A, $\displaystyle A \oplus B = B \oplus A$。

2.1.2 集合恒等式证明技巧

子集互证法：证明 \displaystyle A=B 即证 \displaystyle A \subseteq B 且 $\displaystyle B \subseteq A$。
- 任取 $\displaystyle x \in A$，逻辑推导 $\displaystyle x \in B$。
集合演算法：利用集合恒等式（类似逻辑等值式）进行变形。
- \displaystyle A - B = A \cap \bar{B} (最常用的变形)
- 德摩根律：\displaystyle \overline{A \cup B} = \bar{A} \cap \bar{B}
成员表法/特征函数法：
- 列出元素属于各集合的所有 \displaystyle 0/1 组合，验证结果是否一致。

2.1.3 幂集与笛卡尔积

幂集 $\displaystyle P(A)$：\displaystyle A 的所有子集构成的集合。
- 若 $\displaystyle |A|=n$，则 $\displaystyle |P(A)| = 2^n$。
- 易错：\displaystyle \emptyset \in P(A), $\displaystyle A \in P(A)$。
笛卡尔积 $\displaystyle A \times B$：有序对的集合。
- $\displaystyle |A \times B| = |A| \cdot |B|$。
- 不满足交换律：\displaystyle A \times B \neq B \times A (除非 \displaystyle A=B 或为空)。

2.2 二元关系

2.2.1 关系的表示与基本性质

关系 \displaystyle R 是 \displaystyle A \times A 的子集。

表示法：集合表达式、关系矩阵 $\displaystyle M_R$、关系图 $\displaystyle G_R$。

五大基本性质 (必须熟练判断)

性质	定义	矩阵特征	图特征
自反性	`\displaystyle \forall x, (x,x) \in R`	主对角线全 1	每个节点都有自环
反自反性	`\displaystyle \forall x, (x,x) \notin R`	主对角线全 0	无自环
对称性	`\displaystyle (x,y) \in R \to (y,x) \in R`	对称矩阵 (`\displaystyle M=M^T`)	所有边双向
反对称性	`\displaystyle (x,y) \in R \land (y,x) \in R \to x=y`	`\displaystyle m_{ij}=1 \land i \ne j \Rightarrow m_{ji}=0`	无双向边
传递性	`\displaystyle (x,y) \in R \land (y,z) \in R \to (x,z) \in R`	`\displaystyle M^2 \le M` (布尔乘)	有路必达（形成捷径）

2.2.2 关系矩阵详解

定义：设 $\displaystyle A = {a_1, a_2, \dots, a_n}$，关系矩阵 \displaystyle M_R 是一个 \displaystyle n \times n 的 0-1 矩阵。

若 $\displaystyle (a_i, a_j) \in R$，则 $\displaystyle m_{ij} = 1$；否则 $\displaystyle m_{ij} = 0$。

关系运算的矩阵表示

逆关系：\displaystyle M_{R^{-1}} = (M_R)^T (转置矩阵)。
并集/交集：\displaystyle M_{R \cup S} = M_R \lor M_S, \displaystyle M_{R \cap S} = M_R \land M_S (对应位置逻辑运算)。
复合关系：\displaystyle M_{S \circ R} = M_R \cdot M_S (布尔矩阵乘法)。
- 注意顺序：\displaystyle S \circ R 表示先 \displaystyle R 后 $\displaystyle S$，矩阵乘法也是 \displaystyle M_R 在前。
- 布尔乘法规则：$\displaystyle c_{ij} = \bigvee_{k=1}^n (a_{ik} \land b_{kj})$。
幂运算：\displaystyle M_{R^n} = (M_R)^n (布尔乘幂)。

2.2.3 关系性质的运算封闭性 (表 6.2)

运算	自反性	反自反性	对称性	反对称性	传递性
逆关系 `\displaystyle R^{-1}`	是	是	是	是	是
交 `\displaystyle R \cap S`	是	是	是	是	是
并 `\displaystyle R \cup S`	是	是	是	否	否
差 `\displaystyle R - S`	否	是	是	是	否
复合 `\displaystyle R \circ S`	是	否	否	否	否

注：表中“是”表示该性质在运算下一定保持，“否”表示不一定保持。

2.2.4 关系的闭包

自反闭包 \displaystyle r(R) = R \cup I_A (矩阵：主对角线置1)
对称闭包 \displaystyle s(R) = R \cup R^{-1} (矩阵：\displaystyle M \lor M^T)
传递闭包 \displaystyle t(R) = R \cup R^2 \cup \dots \cup R^n (连通性)

Warshall 算法 (计算传递闭包的核心)

用于在计算机中高效计算 $\displaystyle t(R)$。

输入：\displaystyle n \times n 关系矩阵 $\displaystyle M$。
逻辑：
```
for k from 1 to n:
    for i from 1 to n:
        for j from 1 to n:
            M[i,j] = M[i,j] or (M[i,k] and M[k,j])
```
直观理解：第 \displaystyle k 轮循环尝试以节点 \displaystyle k 为中转站，如果 \displaystyle i \to k 且 $\displaystyle k \to j$，则建立 \displaystyle i \to j 的直达路径。

2.2.5 等价关系与划分

定义：满足 自反、对称、传递 的关系。
等价类 $\displaystyle [x]_R$：所有与 \displaystyle x 有关系 \displaystyle R 的元素集合。
划分：
- 集合 \displaystyle A 被划分为若干个不相交的子集，其并集为 $\displaystyle A$。
- 定理：等价关系与划分一一对应。等价类就是划分出的子集。
- 例：整数集上的模 3 同余关系，划分为 \displaystyle \{3k\}, \{3k+1\}, \{3k+2\} 三类。

2.2.6 偏序关系详解

定义：满足 自反、反对称、传递 的关系。符号 $\displaystyle \preceq$。
相关符号：
- $\displaystyle x \preceq y$：\displaystyle x 小于等于 \displaystyle y (或 \displaystyle x 排在 \displaystyle y 前)。
- $\displaystyle x \prec y$：$\displaystyle x \preceq y \land x \ne y$。
- 可比：若 \displaystyle x \preceq y 或 $\displaystyle y \preceq x$，则称 \displaystyle x, y 可比。
- 不可比：若既不 \displaystyle x \preceq y 也不 $\displaystyle y \preceq x$，则称 \displaystyle x, y 不可比。
覆盖关系：
- 若 \displaystyle x \prec y 且不存在 \displaystyle z 使得 $\displaystyle x \prec z \prec y$，则称 \displaystyle y 覆盖 $\displaystyle x$。
- 哈斯图即是基于覆盖关系绘制的简化图。

哈斯图画法步骤

画出覆盖关系（即去掉所有自环和传递边）。
若 \displaystyle y 覆盖 $\displaystyle x$，则将 \displaystyle y 画在 \displaystyle x 上方并连线。
方向默认向上，省略箭头。

特殊元素 (重要考点)

设 \displaystyle (A, \preceq) 为偏序集，$\displaystyle B \subseteq A$。

极小元：\displaystyle B 中没有比它更小的元素。$\displaystyle \neg \exists x \in B, x \prec a$。
极大元：\displaystyle B 中没有比它更大的元素。$\displaystyle \neg \exists x \in B, a \prec x$。
最小元：\displaystyle B 中所有元素都比它大。\displaystyle \forall x \in B, a \preceq x (若存在则唯一)。
最大元：\displaystyle B 中所有元素都比它小。\displaystyle \forall x \in B, x \preceq a (若存在则唯一)。
下界：\displaystyle A 中小于等于 \displaystyle B 中所有元素的元素。$\displaystyle \forall x \in B, l \preceq x$。
上界：\displaystyle A 中大于等于 \displaystyle B 中所有元素的元素。$\displaystyle \forall x \in B, x \preceq u$。
下确界 (GLB/Infimum)：最大下界。符号 \displaystyle \inf B 或 $\displaystyle \wedge B$。
上确界 (LUB/Supremum)：最小上界。符号 \displaystyle \sup B 或 $\displaystyle \lor B$。

示例：整除关系

设 $\displaystyle A = {1, 2, 3, 4, 6, 12}$，关系为整除 (\displaystyle |)。

哈斯图层级：\displaystyle 12 在顶；\displaystyle 4, 6 在中；\displaystyle 2, 3 在下；\displaystyle 1 在底。
\displaystyle 2 和 \displaystyle 3 不可比。
子集 \displaystyle \{2, 3\} 的上界是 $\displaystyle 6, 12$，上确界是 $\displaystyle 6$。
子集 \displaystyle \{2, 3\} 的下界是 $\displaystyle 1$，下确界是 $\displaystyle 1$。

格

定义：偏序集 \displaystyle (L, \preceq) 中任意两个元素 \displaystyle x, y 都有确定的上确界 (\displaystyle x \lor y) 和下确界 (\displaystyle x \land y)。
性质：格可以看作代数系统，满足交换律、结合律、吸收律。

2.3 函数

2.3.1 函数的性质

单射：
- 定义：$\displaystyle f(a) = f(b) \Rightarrow a = b$。
- 判别：陪域中每个元素最多被 1 个箭头指到。
满射：
- 定义：$\displaystyle \forall y \in B, \exists x \in A, f(x)=y$。
- 判别：陪域中每个元素至少被 1 个箭头指到 (值域=陪域)。
双射：既单且满。
- 只有双射存在逆函数 $\displaystyle f^{-1}$。

2.3.2 复合函数

$\displaystyle (g \circ f)(x) = g(f(x))$。
性质：
- 若 \displaystyle f, g 都是单射，则 \displaystyle g \circ f 是单射。
- 若 \displaystyle f, g 都是满射，则 \displaystyle g \circ f 是满射。
- 若 \displaystyle g \circ f 是单射 \Rightarrow f 必为单射。
- 若 \displaystyle g \circ f 是满射 \Rightarrow g 必为满射。

2.3.3 特殊函数与算法复杂度

取整函数：
- 向下取整 (Floor) $\lfloor x \rfloor$：小于等于 x 的最大整数。
- 向上取整 (Ceiling) $\lceil x \rceil$：大于等于 x 的最小整数。
算法复杂度 (Big-O Notation)：
- 定义：设 f, g 是从整数集或实数集到实数集的函数。若存在常数 C 和 $k$，使得当 x > k 时，$\lvert f(x) \rvert \le C \lvert g(x) \rvert$，则称 f(x) 是 $O(g(x))$。
- 常见阶：$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$。
- 判定技巧：
  - 忽略系数：7n^3 是 $O(n^3)$。
  - 只看最高次项：n^2 + n + 1 是 $O(n^2)$。

2.3.4 典型考题：等价关系的证明

题目：设 R 是集合 A 上的等价关系，证明 R \circ R 也是 A 上的等价关系。 证明思路：

自反性：
- \because R 自反 $\therefore \forall a \in A, (a,a) \in R$。
- 故 $(a,a) \in R \circ R$（通过中间点 $a$），即 R \circ R 自反。
对称性：
- 任取 $(x,y) \in R \circ R$，则 \exists t \in A 使得 $(x,t) \in R \land (t,y) \in R$。
- \because R 对称 $\therefore (t,x) \in R \land (y,t) \in R$。
- 交换顺序得 $(y,t) \in R \land (t,x) \in R \Rightarrow (y,x) \in R \circ R$。
传递性：
- \because R 传递，且 R 是等价关系 $\therefore R \circ R = R$（等价关系的幂运算封闭性）。
- R 自身具备传递性，故 R \circ R 传递。
- (注：若题目要求严格分布证明，需设 (x,y) \in R^2, (y,z) \in R^2 推导 (x,z) \in R^2)。

11 KiB Raw Permalink Blame History Unescape Escape