本节对应原书 PDF 第 101–105 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

关系是离散数学中刻画元素之间相互联系的一个重要的概念，在计算机科学与技术领域中有着广泛的应用，关系数据库模型就是以关系及其运算作为理论基础的。

最基本的关系是二元关系，即发生在两个个体之间的关系。比如竞赛中间的胜负关系，如果每一场比赛都是在两个对手之间进行，不考虑平局，那么比赛结果 x 胜 y 就可以表示成 \langle x,y\rangle，关系 \{\langle a,b\rangle,\langle c,b\rangle,\langle c,a\rangle\} 记录了 3 场比赛的结果。由这个结果不难看出，c 是第一名，a 是第二名，而 b 是最后一名。这就是 \{a,b,c\} 集合上的一个二元关系的例子。

本章主要讨论二元关系。先给出二元关系的定义和表示方法，然后讨论关系的运算、关系的性质，最后研究两类重要的二元关系——等价关系与偏序关系。

4.1.1 有序对与笛卡儿积

定义 4.1　由两个元素,比如 x 和 y,按照一定次序构成的二元组称为一个有序对,记作 \langle x,y\rangle. 其中,x 是它的第一元素,y 是它的第二元素.

直角坐标系中点的坐标如 (1,-2),(0,5) 就是有序对.

在一个有序对中,如果两个元素不相等,那么它们是不能交换次序的. 例如 \langle 0,1\rangle 与 \langle 1,0\rangle 代表不同的有序对.

两个有序对 \langle x,y\rangle 与 \langle u,v\rangle 相等的充分必要条件是 x=u 且 y=v.

例 4.1　设有序对 \langle x+y,3\rangle=\langle 3y-2,x+5\rangle,那么根据有序对相等的充分必要条件有 x+y=3y-2 和 3=x+5,因此得到 x=-2,y=0.

利用有序对的概念可以定义集合的笛卡儿积.

定义 4.2　设 A,B 为集合,那么以 A 中元素作为第一元素,B 中元素作为第二元素做有序对,所有这样的有序对构成的集合称为 A 与 B 的笛卡儿积,记作 A\times B. 符号化表示为

A\times B=\{\langle x,y\rangle\mid x\in A\wedge y\in B\}

例 4.2　设 A=\{0,1\}, B=\{a,b,c\},那么

A\times B=\{\langle 0,a\rangle,\langle 0,b\rangle,\langle 0,c\rangle,\langle 1,a\rangle,\langle 1,b\rangle,\langle 1,c\rangle\}
B\times A=\{\langle a,0\rangle,\langle a,1\rangle,\langle b,0\rangle,\langle b,1\rangle,\langle c,0\rangle,\langle c,1\rangle\}

有穷集合的笛卡儿积的元素数可以通过下面公式计算: 如果 |A|=m,|B|=n,那么 |A\times B|=mn.

不难证明，笛卡儿积运算满足下述性质：

(1) 当 A 或者 B 为空集时,A\times B 也是空集.

(2) 笛卡儿积运算不适合交换律,即 A\times B\neq B\times A,除非 A=B,A=\varnothing 或者 B=\varnothing.

(3) 笛卡儿积运算不适合结合律,即 (A\times B)\times C\neq A\times(B\times C),除非 A=\varnothing, B=\varnothing 或者 C=\varnothing.

(4) 笛卡儿积运算对并和交运算适合分配律,即

A\times(B\cup C)=(A\times B)\cup(A\times C)
(B\cup C)\times A=(B\times A)\cup(C\times A)
A\times(B\cap C)=(A\times B)\cap(A\times C)
(B\cap C)\times A=(B\times A)\cap(C\times A)

上面定义的 2 阶笛卡儿积可以推广到 n 阶.

定义 4.3　(1) 由 n 个元素 x_1,x_2,\cdots,x_n 按照一定的顺序排列构成有序 n 元组,记作 \langle x_1,x_2,\cdots,x_n\rangle.

(2) 设 A_1,A_2,\cdots,A_n 为集合,称

A_1\times A_2\times\cdots\times A_n=\{\langle x_1,x_2,\cdots,x_n\rangle\mid x_i\in A_i,\ i=1,2,\cdots,n\}

为 n 阶笛卡儿积.

空间直角坐标系中全体点的集合就是 3 阶笛卡儿积 \mathbf{R}\times\mathbf{R}\times\mathbf{R}.

解读：笛卡儿积不满足交换律与结合律，但分配律成立；\langle 0,1\rangle 与 \langle 1,0\rangle 是不同的元素，这正是它与无序对（集合 \{0,1\}）的本质区别。

4.1.2 二元关系的定义

下面定义二元关系.

定义 4.4　如果一个集合中的元素都是有序对或者这个集合是空集,则称这个集合是一个二元关系,简称关系. 关系的名字一般使用大写的英文字母,通常记作 R.

如果有序对 \langle x,y\rangle\in R,可以简单记作 xRy,否则记为 x\not Ry. 例如,R=\{\langle a,b\rangle,\langle c,b\rangle,\langle c,a\rangle\} 就可以记作 aRb,cRb,cRa.

例 4.3　一些关系的实例.

(1) R=\{\langle x,y\rangle\mid x,y\in\mathbf{N},\ x+y<3\} 是自然数集 \mathbf{N} 上的关系,不难看出

R=\{\langle 0,0\rangle,\langle 0,1\rangle,\langle 0,2\rangle,\langle 1,0\rangle,\langle 1,1\rangle,\langle 2,0\rangle\}

(2) C=\{\langle x,y\rangle\mid x,y\in\mathbf{R},\ x^2+y^2=1\},其中 \mathbf{R} 是实数集,C 是直角坐标平面上点的横坐标与纵坐标之间的关系,满足关系 C 的所有的点恰好构成坐标平面上的单位圆.

(3) 设 A 是计算机专业 03 级学生的学号构成的集合,这些学号从 0305001 到 0305150. B 是课程号的集合,那么关系

R=\{\langle x,y\rangle\mid x\in A,\ y\in B,\ x\ \text{选修了课号为}\ y\ \text{的课程}\}

记录了计算机专业 03 级学生选课的情况.

二元关系也可以推广到 n 元关系，n 元关系中的元素是有序 n 元组。下面就是一些 n 元关系的例子。

例 4.4　(1) P=\{\langle x,y,z\rangle\mid x,y,z\in\mathbf{R},\ x+2y+z=3\},P 代表了空间直角坐标系中的一个平面.

(2) 表 4.1 是关系数据库中的一个实体模型,是有关员工的一张简表.

表　4.1

员工号姓名年龄性别工资
301张林50男1600
302王晓云43女1250
303李鹏宇47男1500
304赵辉21男900
\cdots\cdots\cdots\cdots\cdots

表 4.1 中包含了若干员工的记录，每个记录是一个 5 元组，由 5 个字段构成，称为属性。这些元组的集合构成了一个 5 元关系。

n 元关系及其运算构成了关系数据库的理论基础，在实际中有着重要的应用，后面将给出一个简单的例子，本章所涉及的关系均指二元关系。

二元关系中特别重要的是从 A 到 B 的关系与 A 上的关系.

定义 4.5　设 A, B 为集合,A\times B 的任何子集所定义的二元关系叫做从 A 到 B 的二元关系,当 A=B 时则叫做 A 上的二元关系.

例 4.5　A=\{a,b\}, B=\{1,2,3\},那么

R_1=\{\langle a,1\rangle\}, \quad R_2=A\times B, \quad R_3=\varnothing

都是从 A 到 B 的关系;

R_3, \quad R_4=\{\langle 2,1\rangle,\langle 2,3\rangle\}, \quad R_5=B\times B

都是 B 上的二元关系.

设 |A|=n, |B|=m,那么 |A\times B|=nm, A\times B 的不同的子集有 2^{nm} 个,因此存在 2^{nm} 个不同的从 A 到 B 的二元关系. 从这个结果可以推出 A 上存在有 2^{n^2} 个不同的二元关系. 例如 |A|=3,则 A 上有 2^{3^2}=512 个不同的二元关系.

下面是一些 A 上重要关系的实例.

\varnothing 是 A 上的关系,称为空关系. 其他的 A 上的关系定义如下.

定义 4.6　设 A 为任意集合,

E_A=\{\langle x,y\rangle\mid x\in A\wedge y\in A\}=A\times A
I_A=\{\langle x,x\rangle\mid x\in A\}

E_A, I_A 分别称为全域关系与恒等关系.

例如,A=\{1,2\},则

E_A=\{\langle 1,1\rangle,\langle 1,2\rangle,\langle 2,1\rangle,\langle 2,2\rangle\}
I_A=\{\langle 1,1\rangle,\langle 2,2\rangle\}

给定集合 A,A 上的小于等于关系 L_A、整除关系 D_A、包含关系 R_{\subseteq} 定义如下.

定义 4.7

L_A=\{\langle x,y\rangle\mid x,y\in A\wedge x\leqslant y\},\ \text{这里}\ A\subseteq \mathbf{R},\ \mathbf{R}\ \text{为实数集}.
D_A=\{\langle x,y\rangle\mid x,y\in A\wedge x\ \text{整除}\ y\},\ \text{这里}\ A\subseteq \mathbf{Z}^*,\ \mathbf{Z}^*\ \text{为非 0 整数集}.
R_{\subseteq}=\{\langle x,y\rangle\mid x,y\in A\wedge x\subseteq y\},\ \text{这里}\ A\ \text{是集合族}.

例如 A=\{1,2,3\},则

L_A=\{\langle 1,1\rangle,\langle 1,2\rangle,\langle 1,3\rangle,\langle 2,2\rangle,\langle 2,3\rangle,\langle 3,3\rangle\}
D_A=\{\langle 1,1\rangle,\langle 1,2\rangle,\langle 1,3\rangle,\langle 2,2\rangle,\langle 3,3\rangle\}

A=\{\varnothing,\{a\},\{b\},\{a,b\}\},则 A 上的包含关系是

\begin{aligned} R_{\subseteq}=\{&\langle \varnothing,\varnothing\rangle,\langle \varnothing,\{a\}\rangle,\langle \varnothing,\{b\}\rangle,\langle \varnothing,\{a,b\}\rangle,\langle \{a\},\{a\}\rangle,\langle \{a\},\{a,b\}\rangle,\\ &\langle \{b\},\{b\}\rangle,\langle \{b\},\{a,b\}\rangle,\langle \{a,b\},\{a,b\}\rangle\} \end{aligned}

类似地还可以定义 A 上的大于等于关系、小于关系、大于关系、真包含关系等.

例 4.6　设 A=\{1,2,\cdots,10\}, R=\{\langle x,y\rangle\mid x,y\in A,\ x+2y\leqslant 8\},列出 R 中的所有元素.

解　R=\{\langle 1,1\rangle,\langle 1,2\rangle,\langle 1,3\rangle,\langle 2,1\rangle,\langle 2,2\rangle,\langle 2,3\rangle,\langle 3,1\rangle,\langle 3,2\rangle,\langle 4,1\rangle,\langle 4,2\rangle,\langle 5,1\rangle,\langle 6,1\rangle\}

如果称横纵坐标均为整数的点为整点，那么 R 中的全体有序对恰好构成了平面直角坐标系坐标轴的正方向和直线 x+2y=8 所围成的区域（包括直线，但不含坐标轴）内的所有整点。

解读：A 上的关系就是 A\times A 的子集，所以 |A|=n 时一共有 2^{n^2} 个；空关系、全域关系 E_A、恒等关系 I_A 是其中三个"特殊位置"的关系。

4.1.3 二元关系的表示

可以使用集合表达式定义二元关系，上面的例子都通过这种方法来表示一个二元关系。除了集合表达式以外，还可以使用关系矩阵和关系图来表示二元关系。关系矩阵通常用于表示从 A 到 B 的关系或者 A 上的关系，这里的 A 和 B 都是有穷集合。关系图只能表示有穷集合 A 上的关系。

定义 4.8　设 A=\{x_1,x_2,\cdots,x_n\},B=\{y_1,y_2,\cdots,y_m\},R 是从 A 到 B 的关系,R 的关系矩阵是布尔矩阵 M_R=(r_{ij})_{n\times m},其中 r_{ij}=1\Leftrightarrow \langle x_i,y_j\rangle\in R, i=1,2,\cdots,n, j=1,2,\cdots,m.

当 R 为 A 上的关系时,R 的关系矩阵是 n 阶方阵.

定义 4.9　设 A=\{x_1,x_2,\cdots,x_n\},R 的关系图是 G_R=\langle A,R\rangle,其中 A 为 G 的结点集,R 为边集. \forall x_i,x_j\in A,如果 \langle x_i,x_j\rangle\in R,在图中就有一条从 x_i 到 x_j 的有向边.

例 4.7　(1) 设 A=\{a,b,c,d\}, R=\{\langle a,a\rangle,\langle a,b\rangle,\langle a,c\rangle,\langle b,a\rangle,\langle d,b\rangle\},R 的关系矩阵如下,关系图如图 4.1 所示.

\begin{bmatrix} 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \end{bmatrix}

原书图4.1 关系 R 的关系图

(2) 设 A=\{a,b,c,d\}, B=\{1,2,3\},R=\{\langle a,1\rangle,\langle a,2\rangle,\langle b,1\rangle,\langle b,3\rangle,\langle c,1\rangle,\langle c,2\rangle,\langle c,3\rangle\},R 的关系矩阵是

\begin{bmatrix} 1 & 1 & 0\\ 1 & 0 & 1\\ 1 & 1 & 1\\ 0 & 0 & 0 \end{bmatrix}

不难看出，R 的关系图 G_R 显然是唯一的。如果用列元素的方法给出了 A 与 B 的全体元素，那么从 A 到 B 的关系或者 A 上的关系 R 的矩阵 M_R 也是唯一的。

解读：集合表达式、关系矩阵、关系图是同一关系的三种写法，可以互相翻译；矩阵第 i 行第 j 列为 1 就对应图中一条 x_i\to x_j 的有向边。