handsomezhuzhu.github.io/otherdocs/离散/02_集合论与二元关系.md

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

## 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 集合恒等式证明技巧
1.  **子集互证法**：证明 $\displaystyle A=B$ 即证 $\displaystyle A \subseteq B$ 且 $\displaystyle B \subseteq A$。
    - 任取 $\displaystyle x \in A$，逻辑推导 $\displaystyle x \in B$。
2.  **集合演算法**：利用集合恒等式（类似逻辑等值式）进行变形。
    - $\displaystyle A - B = A \cap \bar{B}$ (最常用的变形)
    - 德摩根律：$\displaystyle \overline{A \cup B} = \bar{A} \cap \bar{B}$
3.  **成员表法/特征函数法**：
    - 列出元素属于各集合的所有 $\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$。

#### 关系运算的矩阵表示
1.  **逆关系**：$\displaystyle M_{R^{-1}} = (M_R)^T$ (转置矩阵)。
2.  **并集/交集**：$\displaystyle M_{R \cup S} = M_R \lor M_S$, $\displaystyle M_{R \cap S} = M_R \land M_S$ (对应位置逻辑运算)。
3.  **复合关系**：$\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})$。
4.  **幂运算**：$\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$。
- **逻辑**：
  ```text
  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$。
  - **哈斯图**即是基于覆盖关系绘制的简化图。

#### 哈斯图画法步骤
1.  画出覆盖关系（即去掉所有自环和传递边）。
2.  若 $\displaystyle y$ 覆盖 $\displaystyle x$，则将 $\displaystyle y$ 画在 $\displaystyle x$ 上方并连线。
3.  方向默认向上，省略箭头。

#### 特殊元素 (重要考点)
设 $\displaystyle (A, \preceq)$ 为偏序集，$\displaystyle B \subseteq A$。
1.  **极小元**：$\displaystyle B$ 中没有比它更小的元素。$\displaystyle \neg \exists x \in B, x \prec a$。
2.  **极大元**：$\displaystyle B$ 中没有比它更大的元素。$\displaystyle \neg \exists x \in B, a \prec x$。
3.  **最小元**：$\displaystyle B$ 中所有元素都比它大。$\displaystyle \forall x \in B, a \preceq x$ (若存在则唯一)。
4.  **最大元**：$\displaystyle B$ 中所有元素都比它小。$\displaystyle \forall x \in B, x \preceq a$ (若存在则唯一)。
5.  **下界**：$\displaystyle A$ 中小于等于 $\displaystyle B$ 中所有元素的元素。$\displaystyle \forall x \in B, l \preceq x$。
6.  **上界**：$\displaystyle A$ 中大于等于 $\displaystyle B$ 中所有元素的元素。$\displaystyle \forall x \in B, x \preceq u$。
7.  **下确界 (GLB/Infimum)**：最大下界。符号 $\displaystyle \inf B$ 或 $\displaystyle \wedge B$。
8.  **上确界 (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 特殊函数与算法复杂度
1.  **取整函数**：
    - **向下取整 (Floor)** $\lfloor x \rfloor$：小于等于 $x$ 的最大整数。
    - **向上取整 (Ceiling)** $\lceil x \rceil$：大于等于 $x$ 的最小整数。
2.  **算法复杂度 (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$ 上的等价关系。
**证明思路**：
1.  **自反性**：
    - $\because R$ 自反 $\therefore \forall a \in A, (a,a) \in R$。
    - 故 $(a,a) \in R \circ R$（通过中间点 $a$），即 $R \circ R$ 自反。
2.  **对称性**：
    - 任取 $(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$。
3.  **传递性**：
    - $\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$)*。