第 9 章关系¶

章节导引

本页从《离散数学讲义》拆分而来，保留原章节锚点，方便从旧总览页和旧链接跳转。

学习目标¶

把二元关系看作集合、矩阵和图之间可以互相转换的结构，并掌握闭包与等价类。

前置知识¶

第 2 章集合与矩阵，第 3 章算法思想，以及第 1 章的证明语言。

建议用时¶

建议 5–6 小时：关系性质 2 小时，表示与运算 1–2 小时，闭包与等价关系 2 小时。

练习建议¶

判断 5 个关系是否自反/对称/传递；画 2 个关系的有向图；求一个小关系的传递闭包。

参考资料与引用边界¶

整理者：Lumner。
课程来源：根据 DM/ 目录下的课件整理；本章对应课件：DM9.1-9.3(8).pdf, DM9.4(6).pdf, DM9.5(3).pdf。
原始讲义文件：note/离散数学讲义.md。
引用边界：这是公开学习笔记，不替代课程正式教材、教师课件或考试要求；外部引用时请注明来自本网站整理版。

9.0 核心目标¶

关系用于描述对象之间的连接。函数是特殊关系；数据库表、图的边、等价分类和偏序结构都可以用关系建模。

本章重点：

二元关系和 n 元关系。
关系的表示：有序对、表、矩阵、有向图。
自反、对称、反对称、传递等性质。
关系运算、复合和幂。
闭包，尤其是传递闭包和 Warshall 算法。
等价关系、等价类和划分。

9.1 关系及其性质¶

二元关系¶

从集合 \(A\) 到集合 \(B\) 的二元关系 \(R\) 是笛卡尔积 \(A\times B\) 的子集：

\(R\subseteq A\times B\)

若 \((a,b)\in R\)，也写作 \(aRb\)。

集合 \(A\) 上的关系是从 \(A\) 到 \(A\) 的关系，即：

\(R\subseteq A\times A\)

若 \(|A|=n\)，则 \(A\times A\) 有 \(n^2\) 个元素。因为每个有序对可选入或不选入关系，所以 \(A\) 上二元关系总数为：

\(2^{n^2}\)

n 元关系¶

设 \(A_1,A_2,\ldots,A_n\) 为集合。一个 n 元关系是：

\(A_1\times A_2\times\cdots\times A_n\)

的子集。

数据库中的表可视为 n 元关系：每一行是一个 n 元组。

函数作为关系¶

函数 \(f:A\to B\) 可看作关系：

\(\{(a,f(a))\mid a\in A\}\)

但它必须满足每个 \(a\in A\) 恰好出现一次作为第一分量。

一般关系允许一对多、多对一或没有对应。

关系的表示¶

有限关系可通过：

列出有序对。
用谓词描述。
用二维表。
用 0-1 矩阵。
用有向图。

连接矩阵¶

若 \(A=\{a_1,\ldots,a_m\}\)，\(B=\{b_1,\ldots,b_n\}\)，关系 \(R\) 从 \(A\) 到 \(B\)。其矩阵 \(M_R=[m_{ij}]\) 定义为：

\(m_{ij}=1\iff (a_i,b_j)\in R\)

否则 \(m_{ij}=0\)。

有向图表示¶

集合 \(A\) 上的关系可用有向图表示：

顶点为 \(A\) 的元素。
若 \((a,b)\in R\)，则画从 \(a\) 到 \(b\) 的有向边。
若 \((a,a)\in R\)，则是自环。

关系性质¶

设 \(R\) 是集合 \(A\) 上的关系。

自反：

\(\forall a\in A,\ (a,a)\in R\)

矩阵主对角线全为 1；有向图每个点都有自环。

反自反：

\(\forall a\in A,\ (a,a)\notin R\)

矩阵主对角线全为 0。

对称：

\(\forall a,b\in A,\ (a,b)\in R\to(b,a)\in R\)

矩阵关于主对角线对称；有向图每条边都有反向边。

反对称：

\(\forall a,b\in A,\ ((a,b)\in R\land(b,a)\in R)\to a=b\)

注意：对称和反对称不是互为否定。一个关系可以既对称又反对称，例如恒等关系。

传递：

\(\forall a,b,c\in A,\ ((a,b)\in R\land(b,c)\in R)\to(a,c)\in R\)

有向图中若存在长度 2 的路径 \(a\to b\to c\)，则必须有边 \(a\to c\)。

例：整除关系¶

在正整数集合上定义 \(aRb\) 当且仅当 \(a\mid b\)。

自反：\(a\mid a\)。
反对称：若 \(a\mid b\) 且 \(b\mid a\)，则 \(a=b\)。
传递：若 \(a\mid b\) 且 \(b\mid c\)，则 \(a\mid c\)。
不对称：例如 \(2\mid4\)，但 \(4\nmid2\)。

计数具有某性质的关系¶

若 \(|A|=n\)：

自反关系数：主对角线必须选入，其余 \(n^2-n\) 个有序对自由，所以：

\(2^{n^2-n}\)

反自反关系数：主对角线必须不选，其余自由，也是：

\(2^{n^2-n}\)

对称关系数：对角线 \(n\) 个位置自由；非对角线按 unordered pair 成对选择，共 \(\binom n2\) 对，所以：

\(2^{n+\binom n2}=2^{n(n+1)/2}\)

反对称关系数：每对不同元素 {a,b} 中，\((a,b)\)、\((b,a)\) 不能同时选，可选三种情况：只选前者、只选后者、都不选。对角线自由，所以：

\(2^n3^{\binom n2}\)

9.2 关系运算与复合¶

集合运算¶

关系是集合，因此可做并、交、差、补等运算。

若 \(R_1,R_2\subseteq A\times B\)，则：

\(R_1\cup R_2\)、\(R_1\cap R_2\)、\(R_1-R_2\) 仍为从 \(A\) 到 \(B\) 的关系。

逆关系¶

若 \(R\) 是从 \(A\) 到 \(B\) 的关系，其逆关系 \(R^{-1}\) 是从 \(B\) 到 \(A\) 的关系：

\(R^{-1}=\{(b,a)\mid(a,b)\in R\}\)

矩阵上对应转置：

\(M_{R^{-1}}=M_R^T\)

关系复合¶

若 \(R\) 是从 \(A\) 到 \(B\) 的关系，\(S\) 是从 \(B\) 到 \(C\) 的关系，则复合 \(S\circ R\) 是从 \(A\) 到 \(C\) 的关系：

\(S\circ R=\{(a,c)\mid \exists b\in B,\ (a,b)\in R\land(b,c)\in S\}\)

注意顺序：先走 \(R\)，再走 \(S\)。

关系的幂¶

若 \(R\) 是 \(A\) 上的关系，定义：

\(R^1=R\)

\(R^{n+1}=R^n\circ R\)

\((a,b)\in R^n\) 当且仅当在关系图中存在从 \(a\) 到 \(b\) 的长度为 \(n\) 的有向路径。

传递性与关系幂¶

关系 \(R\) 传递，当且仅当：

\(R^n\subseteq R,\quad n=1,2,3,\ldots\)

通常只需理解：如果所有长度 2 的路径都能被一条边“补上”，则更长路径也能不断压缩。

9.3 关系的表示¶

矩阵运算¶

关系矩阵使用布尔运算：

矩阵交：按位 AND。
矩阵并：按位 OR。
关系复合：布尔矩阵乘法。

若 \(M_R\) 是 \(R\) 的矩阵，\(M_S\) 是 \(S\) 的矩阵，则 \(S\circ R\) 的矩阵为布尔积：

\(M_R\odot M_S\)

其中加法用 OR，乘法用 AND。

有向图和路径¶

有向图表示使关系幂、传递闭包等概念更直观。

边表示一步可达。
\(R^2\) 表示两步可达。
\(R^n\) 表示 n 步可达。
传递闭包表示至少一步可达。

9.4 关系闭包¶

闭包定义¶

设 \(P\) 是关系的某种性质。包含 \(R\) 且具有性质 \(P\) 的最小关系，称为 \(R\) 关于性质 \(P\) 的闭包。

本节关注：

自反闭包。
对称闭包。
传递闭包。

自反闭包¶

设 \(\Delta_A=\{(a,a)\mid a\in A\}\) 是恒等关系。\(R\) 的自反闭包为：

\(r(R)=R\cup\Delta_A\)

即补上所有缺失的自环。

对称闭包¶

\(R\) 的对称闭包为：

\(s(R)=R\cup R^{-1}\)

即对每条边补上反向边。

传递闭包¶

\(R\) 的传递闭包 \(t(R)\) 是包含 \(R\) 的最小传递关系。

连通关系 \(R^*\) 定义为：

\(R^*=\{(a,b)\mid \text{存在从 }a\text{ 到 }b\text{ 的长度至少为 }1\text{ 的路径}\}\)

定理：

\(t(R)=R^*\)

也就是说，传递闭包包含所有“可达”的有序对。

有限集合上的路径长度¶

若 \(A\) 有 \(n\) 个元素，且从 \(a\) 到 \(b\) 存在长度至少 1 的路径，则存在长度不超过 \(n\) 的路径；当 \(a\ne b\) 时，可取长度不超过 \(n-1\) 的路径。

因此：

\(t(R)=R\cup R^2\cup\cdots\cup R^n\)

Warshall 算法¶

Warshall 算法用于计算传递闭包矩阵。

设初始矩阵 \(W_0=M_R\)。逐步允许编号不超过 \(k\) 的点作为中间点，得到 \(W_k\)。更新规则：

\(W_k[i,j]=W_{k-1}[i,j]\lor(W_{k-1}[i,k]\land W_{k-1}[k,j])\)

伪代码：

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])
return W

时间复杂度为 \(\Theta(n^3)\)。

多性质闭包¶

若要求同时满足自反和传递，可先加自反边，再求传递闭包。具体顺序应根据性质检查，但常见做法是对 \(R\cup\Delta_A\) 求传递闭包。

9.5 等价关系¶

定义¶

集合 \(A\) 上的关系 \(R\) 若同时满足：

自反。
对称。
传递。

则称为等价关系。

直观上，等价关系刻画“在某种标准下相同”。

等价类¶

若 \(R\) 是 \(A\) 上的等价关系，元素 \(a\) 的等价类为：

\([a]_R=\{x\in A\mid xRa\}\)

常简写为 \([a]\)。

模同余¶

在整数集上定义：

\(a\equiv b\pmod m\iff m\mid(a-b)\)

这是等价关系。

证明：

自反：\(m\mid(a-a)=0\)。
对称：若 \(m\mid(a-b)\)，则 \(m\mid(b-a)\)。
传递：若 \(m\mid(a-b)\) 且 \(m\mid(b-c)\)，则 \(m\mid(a-c)\)。

模 3 的等价类：

\([0]=\{\ldots,-6,-3,0,3,6,\ldots\}\)

\([1]=\{\ldots,-5,-2,1,4,7,\ldots\}\)

\([2]=\{\ldots,-4,-1,2,5,8,\ldots\}\)

由函数诱导的等价关系¶

设 \(f:A\to B\)。定义 \(xRy\) 当且仅当 \(f(x)=f(y)\)。

则 \(R\) 是等价关系。

它把定义域中具有相同函数值的元素分为一类。

字符串前缀等价¶

设 \(S\) 为字符串集合。定义 \(sR_nt\) 当且仅当 \(s=t\)，或 \(s,t\) 长度都至少为 \(n\) 且前 \(n\) 个字符相同。

这是等价关系，用于描述“按前 \(n\) 个字符无法区分”的字符串分类。

划分¶

集合 \(A\) 的划分是若干非空子集的集合，满足：

每个子集非空。
任意两个不同子集不相交。
所有子集的并为 \(A\)。

等价关系与划分¶

定理：

若 \(R\) 是 \(A\) 上的等价关系，则 \(R\) 的所有等价类构成 \(A\) 的一个划分。

反过来，若给定 \(A\) 的一个划分，定义 \(xRy\) 当且仅当 \(x,y\) 在同一个块中，则 \(R\) 是等价关系。

因此，等价关系和划分本质上是同一件事的两种描述。

等价类的基本性质¶

若 \(R\) 是等价关系，则对任意 \(a,b\in A\)：

以下命题等价：

\(aRb\)。
\([a]=[b]\)。
\([a]\cap[b]\ne\varnothing\)。

所以不同等价类要么完全相同，要么完全不相交。

等价关系的组合¶

若 \(R_1,R_2\) 是 \(A\) 上的等价关系，则：

\(R_1\cap R_2\)

也是等价关系。

但 \(R_1\cup R_2\) 一般不一定传递，因此不一定是等价关系。若要得到包含 \(R_1\cup R_2\) 的最小等价关系，需要进一步做传递闭包等操作。

本章小结与后续扩展¶

本章已覆盖关系定义、性质、表示、运算、闭包和等价关系。后续可补充：

偏序关系和 Hasse 图。
拓扑排序。
关系数据库中的 n 元关系操作。
Warshall 算法完整例题。

第 9 章 关系¶