集合与关系

1. 集合运算

1.1 基本概念

集合是具有某种特定性质的事物的总体。用大写字母 $A,B,C,\dots$ 表示集合，小写字母 $a,b,c,\dots$ 表示元素。

$a\in A$：$a$ 属于 $A$；$a\notin A$：$a$ 不属于 $A$。

1.2 集合的表示

• 列举法：$A=\{1,2,3\}$
• 描述法：$B=\{x\mid x>0\}$

1.3 集合间的关系

• $A\subseteq B$（$A$ 是 $B$ 的子集）：$\forall x(x\in A\to x\in B)$
• $A=B$：$A\subseteq B\wedge B\subseteq A$
• $A\subset B$（$A$ 是 $B$ 的真子集）：$A\subseteq B\wedge A\ne B$

1.4 集合运算

并：$A\cup B=\{x\mid x\in A\vee x\in B\}$

交：$A\cap B=\{x\mid x\in A\wedge x\in B\}$

差：$A-B=\{x\mid x\in A\wedge x\notin B\}$

补：$\bar{A}=U-A$（$U$ 为全集）

对称差：$A\oplus B=(A-B)\cup (B-A)=(A\cup B)-(A\cap B)$

1.5 运算律

交换律：$A\cup B=B\cup A$，$A\cap B=B\cap A$

结合律：$(A\cup B)\cup C=A\cup (B\cup C)$

分配律：$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

德摩根律：$\overline{A\cup B}=\bar{A}\cap \bar{B}$，$\overline{A\cap B}=\bar{A}\cup \bar{B}$

吸收律：$A\cup (A\cap B)=A$，$A\cap (A\cup B)=A$

补律：$A\cup \bar{A}=U$，$A\cap \bar{A}=\varnothing$

2. 幂集与笛卡尔积

2.1 幂集

集合 $A$ 的幂集是 $A$ 的所有子集的集合：

$\mathcal{P}(A)=\{X\mid X\subseteq A\}$

若 $|A|=n$，则 $|\mathcal{P}(A)|=2^n$。

例：$A=\{1,2\}$，$\mathcal{P}(A)=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$，$|\mathcal{P}(A)|=4$。

2.2 笛卡尔积

$A\times B=\{(a,b)\mid a\in A,b\in B\}$

性质：

• $|A\times B|=|A|\cdot |B|$
• 笛卡尔积不满足交换律：$A\times B\ne B\times A$（一般情况）
• $A\times (B\cup C)=(A\times B)\cup (A\times C)$
• $A\times (B\cap C)=(A\times B)\cap (A\times C)$

3. 二元关系

3.1 定义

$A\times B$ 的任意子集 $R$ 称为从 $A$ 到 $B$ 的二元关系。当 $A=B$ 时，$R$ 称为 $A$ 上的二元关系。

若 $(a,b)\in R$，记作 $aRb$。

特殊关系：

• 空关系：$\varnothing$
• 全关系：$A\times A$
• 恒等关系：$I_A=\{(a,a)\mid a\in A\}$

3.2 关系的表示

• 集合表示：$R=\{(1,2),(2,3),(1,3)\}$
• 关系矩阵：$M_R=(m_{ij})$，$m_{ij}=1$ 若 $(a_i,b_j)\in R$，否则为 $0$
• 关系图：用有向图表示

3.3 关系的性质

设 $R$ 是 $A$ 上的关系：

例：$A=\{1,2,3\}$，$R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$。

自反：是（每点有环） 对称：是（$(1,2)$ 和 $(2,1)$ 都在） 传递：是（检查所有路径） 反对称：否（$1R2$ 且 $2R1$ 但 $1\ne 2$）

3.4 关系的运算

逆关系：$R^{-1}=\{(b,a)\mid (a,b)\in R\}$

复合关系：$R\circ S=\{(a,c)\mid \exists b,(a,b)\in S\wedge (b,c)\in R\}$

注意：$R\circ S$ 中 $S$ 先作用，$R$ 后作用。

矩阵运算：$M_{R\circ S}=M_S\cdot M_R$（布尔矩阵乘法）

幂运算：$R^n=R^{n-1}\circ R$，$R^0=I_A$

4. 等价关系与划分

4.1 等价关系

若 $R$ 满足自反性、对称性和传递性，则 $R$ 为等价关系。

等价类：$[a{]}_R=\{x\in A\mid xRa\}$

性质：

• $aRb⟺[a]=[b]$
• $[a]\cap [b]=\varnothing$ 或 $[a]=[b]$
• ${\bigcup }_{a\in A}[a]=A$

4.2 划分

集合 $A$ 的划分是 $A$ 的非空子集族 $\pi =\{A_1,A_2,\dots ,A_k\}$，满足：

1. $A_i\ne \varnothing$
2. $A_i\cap A_j=\varnothing$（$i\ne j$）
3. $\bigcup A_i=A$

定理：$A$ 上的等价关系与 $A$ 的划分一一对应。

例：$A=\{1,2,3,4,5\}$，$R=\{(a,b)\mid a\equiv b(\mathrm{mod}2)\}$。

等价类：$[1]=\{1,3,5\}$，$[2]=\{2,4\}$ 划分：$\{\{1,3,5\},\{2,4\}\}$

4.3 商集

$A$ 关于等价关系 $R$ 的商集：$A/R=\{[a{]}_R\mid a\in A\}$

5. 偏序关系与 Hasse 图

5.1 偏序关系

若 $R$ 满足自反性、反对称性和传递性，则 $R$ 为偏序关系，记作 $\le$。$(A,\le )$ 称为偏序集。

全序（线序）：偏序集中任意两个元素都可比较。

5.2 特殊元素

设 $(A,\le )$ 为偏序集，$S\subseteq A$：

• 极大元：$a\in S$，不存在 $b\in S$ 使 $a<b$
• 极小元：$a\in S$，不存在 $b\in S$ 使 $b<a$
• 最大元：$a\in S$，$\forall b\in S,b\le a$（若存在则唯一）
• 最小元：$a\in S$，$\forall b\in S,a\le b$（若存在则唯一）
• 上界：$u\in A$，$\forall b\in S,b\le u$
• 下界：$l\in A$，$\forall b\in S,l\le b$
• 最小上界（上确界）：$\sup S$，上界中的最小元
• 最大下界（下确界）：$\inf S$，下界中的最大元

5.3 Hasse 图

绘制规则：

1. 省去自环（自反性）
2. 省去由传递性可推出的边
3. 若 $a<b$，则 $b$ 画在 $a$ 上方

例：$A=\{1,2,3,6\}$，偏序关系为整除关系 $|$。

Hasse 图：

    6
   / \
  2   3
   \ /
    1

极大元：6（也是最大元） 极小元：1（也是最小元）

5.4 格

若偏序集中任意两个元素都有上确界和下确界，则称为格。

• $a\vee b=\sup \{a,b\}$（并运算）
• $a\wedge b=\inf \{a,b\}$（交运算）

6. 闭包运算

6.1 定义

关系 $R$ 的闭包是包含 $R$ 且具有某种性质的最小关系。

• 自反闭包：$r(R)=R\cup I_A$
• 对称闭包：$s(R)=R\cup R^{-1}$
• 传递闭包：$t(R)={\bigcup }_{i=1}^{\infty }{R}^i=R\cup R^2\cup R^3\cup \cdots$

6.2 传递闭包的计算

有限集上：若 $|A|=n$，则 $t(R)={\bigcup }_{i=1}^n{R}^i$

Warshall 算法（求传递闭包的关系矩阵）：

W = M_R（关系矩阵的副本）
for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:
            W[i][j] = W[i][j] OR (W[i][k] AND W[k][j])

时间复杂度 $O(n^3)$。

例：$A=\{1,2,3\}$，$R=\{(1,2),(2,3)\}$，求 $t(R)$。

$R^2=\{(1,3)\}$，$R^3=\varnothing$ $t(R)=R\cup R^2\cup R^3=\{(1,2),(2,3),(1,3)\}$

6.3 闭包的性质

$rs(R)=sr(R)$

$rt(R)=tr(R)$

$st(R)\subseteq ts(R)$

其中 $rs(R)$ 表示先求自反闭包再求对称闭包。