4.2 二元关系及其性质

第 4.1 节把函数看作一种特殊的有序对集合。现在我们去掉“每个输入恰好一个输出”的限制，研究任意连接。

社交网络中的一个人可以连接许多人；一个数可以整除多个数；网页可以链接自身、另一个网页，也可以没有链接。这些情况都可以用二元关系建模。

二元关系记录什么

给定集合 $A$ 与 $B$ ，从 $A$ 到 $B$ 的二元关系是一个子集

R\subseteq A\times B.

若 $(a,b)\in R$ ，我们写成

aRb,

读作“ $a$ 与 $b$ 具有关系 $R$ ”。符号 $R$ 本身没有固定含义；关系的具体定义决定这条连接代表什么。

例如，令

A=\{1,2,3\},

并用“小于”定义关系 $R$ 。那么

R=\{(1,2),(1,3),(2,3)\}.

因为 $1<3$ ，所以 $(1,3)$ 属于 $R$ ；而 $(3,1)$ 不属于 $R$ 。

集合 $A$ 上的关系，是从 $A$ 到自身的关系：

R\subseteq A\times A.

本节的自反、对称、反对称和传递性质，通常都是针对同一个集合上的关系来讨论。

表示同一个有限关系的四种方法

令 $A=\{1,2,3\}$ ，并设

R=\{(1,1),(1,2),(2,1),(2,2),(3,3)\}.

同一份关系信息可以用多种形式呈现：

1. 列举法：像上面一样列出所有有序对；

2. 箭头图：每当 $(a,b)\in R$ ，就画一支从 $a$ 指向 $b$ 的箭头；

3. 有向图：每个元素画成顶点，按同一规则加入有向边；

4. 零一矩阵：若 $(a,b)\in R$ ，就在第 $a$ 行、第 $b$ 列写 $1$ ，否则写 $0$ 。

按照 $1,2,3$ 的顺序排列行和列，矩阵是

M_R= \begin{pmatrix} 1&1&0\\ 1&1&0\\ 0&0&1 \end{pmatrix}.

这里暂时不需要矩阵运算。矩阵只是把成员关系压缩成网格，每个格子回答一个问题：“这个有序对是否属于 $R$ ？”

自反：每个元素都与自身相关

集合 $A$ 上的关系 $R$ 称为自反的，如果

\forall a\in A,\quad aRa.

用列举法看，每个 $(a,a)$ 都必须出现；在有向图中，每个顶点都有自环；在矩阵中，主对角线上的元素全部为 $1$ 。

整数上的 $\le$ 关系是自反的，因为每个整数都满足 $a\le a$ 。关系 $<$ 不是自反的，因为 $a<a$ 永远为假。

要否定自反性，只需要找到一个缺少的自环：

\exists a\in A\text{ 使得 }(a,a)\notin R.

对称：每支箭头都有反向箭头

关系称为对称的，如果

\forall a,b\in A,\quad aRb\Rightarrow bRa.

在矩阵中，对称意味着元素关于主对角线镜像相等：

M_R(a,b)=M_R(b,a).

“生日在同一个月”是对称关系：如果小艾与小博的生日月份相同，那么小博与小艾的生日月份也相同。

“是……的父母”不是对称关系。只要找到 $aRb$ 成立而 $bRa$ 不成立的一对，就得到反例。

反对称不是“不对称”

关系称为反对称的，如果

\forall a,b\in A,\quad (aRb\land bRa)\Rightarrow a=b.

它表示两个不同元素之间不能同时存在两个方向的箭头。自环不受禁止。

例如，整数上的 $\le$ 是反对称的：若 $a\le b$ 且 $b\le a$ ，则 $a=b$ 。正整数上的整除关系也是反对称的：若 $a\mid b$ 且 $b\mid a$ ，则 $a=b$ 。

“对称”和“反对称”不是逻辑反义词。相等关系

R=\{(a,a)\mid a\in A\}

既对称又反对称。只要不同元素之间没有双向连接，一个关系就可能同时满足二者。

传递：两步路径强制产生捷径

关系称为传递的，如果

\forall a,b,c\in A,\quad (aRb\land bRc)\Rightarrow aRc.

在有向图中，每条两步路径

a\to b\to c

都要求直接捷径 $a\to c$ 存在。

关系 $\le$ 是传递的： $a\le b$ 且 $b\le c$ 会推出 $a\le c$ 。“是……的父母”不传递：父母的父母通常是祖父母，而不是父母。

一个边很少的关系也可能是传递的。如果根本没有两条边能组成前提 $aRb\land bRc$ ，那么没有任何违反条件的链条，蕴含仍然为真。这正是第 2 章学过的蕴含逻辑。

对一个关系进行性质审计

对于

R=\{(1,1),(1,2),(2,1),(2,2),(3,3)\},

可以得到：

性质	结果	原因
自反	是	$(1,1),(2,2),(3,3)$ 全都存在
对称	是	$(1,2)$ 与 $(2,1)$ 成对出现
反对称	否	$1R2$ 且 $2R1$ ，但 $1\ne2$
传递	是	每条两步路径都留在 $\{1,2\}$ 内或停在 $3$ ，相应捷径都存在

正在加载交互实验...

在关系矩阵中涂亮格子，同时观察对应的有向网络。四个检测器会找出缺失自环、未配对箭头、不同元素间被禁止的双向连接，以及缺失的传递捷径；每个失败都会给出具体见证。

正在加载概念检查...

正在加载本节练习...

用闭包修复关系

有时原关系不具有某种性质，而我们希望加入最少的有序对，使它获得该性质。闭包会保留所有原始有序对，再补上必须的有序对；它不会删除原始数据。

令

A=\{1,2,3\},\qquad R=\{(1,2),(2,3)\}.

自反闭包

补齐所有缺失的自环：

R_{\mathrm{ref}} =R\cup\{(1,1),(2,2),(3,3)\}.

对称闭包

为每个有序对加入反向有序对：

R_{\mathrm{sym}} =R\cup\{(2,1),(3,2)\}.

定义逆关系

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

就可以把上式简写成

R_{\mathrm{sym}}=R\cup R^{-1}.

这里的 $R^{-1}$ 表示反转有序对。它与第 4.1 节的逆函数有关，但范围更广：每个关系都有逆关系，只有双射函数才有逆函数。

传递闭包

因为

1R2\quad\text{且}\quad2R3,

传递性要求 $1R3$ 。因此

R_{\mathrm{trans}}=\{(1,2),(2,3),(1,3)\}.

在更长的网络中，新加入的一条捷径可能形成新的两步路径，于是还需要另一条捷径。这个过程要一直继续，直到从任意起点可到达的终点，都与起点存在直接关系。

一个有用的理解是：

(a,b)\text{ 属于传递闭包} \quad\Longleftrightarrow\quad \text{存在一条从 }a\text{ 到 }b\text{ 的正长度有向路径}.

闭包在集合包含意义下是最小的：它包含原关系，满足目标性质，并且没有加入不必要的有序对。

正在加载交互实验...

运营一张把直接轨道看成关系有序对的地铁网。乘客路线会暴露传递性要求的捷径。你需要提出快速轨道、运行动画传播，并在不加入无关连接的前提下修复网络。

正在加载概念检查...

正在加载本节练习...

注意

对称检查每支箭头是否被反向复制；反对称只禁止不同元素之间的双向箭头；传递检查每条两步路径是否有直接捷径。请把这三幅图像分别记清楚。

本节衔接

现在我们能够识别任意关系中的结构模式。下一节会把其中三种性质——自反、对称、传递——组合起来，精确表达不同对象“属于同一类”。这种关系会把一个集合切分成互不重叠的整齐分组。

4.2 二元关系及其性质

第 4.1 节把函数看作一种特殊的有序对集合。现在我们去掉“每个输入恰好一个输出”的限制，研究任意连接。

二元关系记录什么

给定集合 $A$ 与 $B$ ，从 $A$ 到 $B$ 的二元关系是一个子集

R\subseteq A\times B.

若 $(a,b)\in R$ ，我们写成

aRb,

读作“ $a$ 与 $b$ 具有关系 $R$ ”。符号 $R$ 本身没有固定含义；关系的具体定义决定这条连接代表什么。

例如，令

A=\{1,2,3\},

并用“小于”定义关系 $R$ 。那么

R=\{(1,2),(1,3),(2,3)\}.

因为 $1<3$ ，所以 $(1,3)$ 属于 $R$ ；而 $(3,1)$ 不属于 $R$ 。

集合 $A$ 上的关系，是从 $A$ 到自身的关系：

R\subseteq A\times A.

本节的自反、对称、反对称和传递性质，通常都是针对同一个集合上的关系来讨论。

表示同一个有限关系的四种方法

令 $A=\{1,2,3\}$ ，并设

R=\{(1,1),(1,2),(2,1),(2,2),(3,3)\}.

同一份关系信息可以用多种形式呈现：

1. 列举法：像上面一样列出所有有序对；

2. 箭头图：每当 $(a,b)\in R$ ，就画一支从 $a$ 指向 $b$ 的箭头；

3. 有向图：每个元素画成顶点，按同一规则加入有向边；

4. 零一矩阵：若 $(a,b)\in R$ ，就在第 $a$ 行、第 $b$ 列写 $1$ ，否则写 $0$ 。

按照 $1,2,3$ 的顺序排列行和列，矩阵是

M_R= \begin{pmatrix} 1&1&0\\ 1&1&0\\ 0&0&1 \end{pmatrix}.

这里暂时不需要矩阵运算。矩阵只是把成员关系压缩成网格，每个格子回答一个问题：“这个有序对是否属于 $R$ ？”

自反：每个元素都与自身相关

集合 $A$ 上的关系 $R$ 称为自反的，如果

\forall a\in A,\quad aRa.

用列举法看，每个 $(a,a)$ 都必须出现；在有向图中，每个顶点都有自环；在矩阵中，主对角线上的元素全部为 $1$ 。

整数上的 $\le$ 关系是自反的，因为每个整数都满足 $a\le a$ 。关系 $<$ 不是自反的，因为 $a<a$ 永远为假。

要否定自反性，只需要找到一个缺少的自环：

\exists a\in A\text{ 使得 }(a,a)\notin R.

对称：每支箭头都有反向箭头

关系称为对称的，如果

\forall a,b\in A,\quad aRb\Rightarrow bRa.

在矩阵中，对称意味着元素关于主对角线镜像相等：

M_R(a,b)=M_R(b,a).

“生日在同一个月”是对称关系：如果小艾与小博的生日月份相同，那么小博与小艾的生日月份也相同。

“是……的父母”不是对称关系。只要找到 $aRb$ 成立而 $bRa$ 不成立的一对，就得到反例。

反对称不是“不对称”

关系称为反对称的，如果

\forall a,b\in A,\quad (aRb\land bRa)\Rightarrow a=b.

它表示两个不同元素之间不能同时存在两个方向的箭头。自环不受禁止。

例如，整数上的 $\le$ 是反对称的：若 $a\le b$ 且 $b\le a$ ，则 $a=b$ 。正整数上的整除关系也是反对称的：若 $a\mid b$ 且 $b\mid a$ ，则 $a=b$ 。

“对称”和“反对称”不是逻辑反义词。相等关系

R=\{(a,a)\mid a\in A\}

既对称又反对称。只要不同元素之间没有双向连接，一个关系就可能同时满足二者。

传递：两步路径强制产生捷径

关系称为传递的，如果

\forall a,b,c\in A,\quad (aRb\land bRc)\Rightarrow aRc.

在有向图中，每条两步路径

a\to b\to c

都要求直接捷径 $a\to c$ 存在。

关系 $\le$ 是传递的： $a\le b$ 且 $b\le c$ 会推出 $a\le c$ 。“是……的父母”不传递：父母的父母通常是祖父母，而不是父母。

对一个关系进行性质审计

对于

R=\{(1,1),(1,2),(2,1),(2,2),(3,3)\},

可以得到：

性质	结果	原因
自反	是	$(1,1),(2,2),(3,3)$ 全都存在
对称	是	$(1,2)$ 与 $(2,1)$ 成对出现
反对称	否	$1R2$ 且 $2R1$ ，但 $1\ne2$
传递	是	每条两步路径都留在 $\{1,2\}$ 内或停在 $3$ ，相应捷径都存在

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

用闭包修复关系

令

A=\{1,2,3\},\qquad R=\{(1,2),(2,3)\}.

自反闭包

补齐所有缺失的自环：

R_{\mathrm{ref}} =R\cup\{(1,1),(2,2),(3,3)\}.

对称闭包

为每个有序对加入反向有序对：

R_{\mathrm{sym}} =R\cup\{(2,1),(3,2)\}.

定义逆关系

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

就可以把上式简写成

R_{\mathrm{sym}}=R\cup R^{-1}.

这里的 $R^{-1}$ 表示反转有序对。它与第 4.1 节的逆函数有关，但范围更广：每个关系都有逆关系，只有双射函数才有逆函数。

传递闭包

因为

1R2\quad\text{且}\quad2R3,

传递性要求 $1R3$ 。因此

R_{\mathrm{trans}}=\{(1,2),(2,3),(1,3)\}.

一个有用的理解是：

(a,b)\text{ 属于传递闭包} \quad\Longleftrightarrow\quad \text{存在一条从 }a\text{ 到 }b\text{ 的正长度有向路径}.

闭包在集合包含意义下是最小的：它包含原关系，满足目标性质，并且没有加入不必要的有序对。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

注意

对称检查每支箭头是否被反向复制；反对称只禁止不同元素之间的双向箭头；传递检查每条两步路径是否有直接捷径。请把这三幅图像分别记清楚。