二元关系¶

二元关系是离散数学中的一个重要概念，它描述了两个集合之间的元素之间的关系。

二元关系是函数与图论的基础理论。

有序对与笛卡尔积¶

有序对¶

由两个元素 \(x\) 和 \(y\)（允许 \(x=y\)）按一定顺序排列成的二元组叫做一个有序对（ordered pair）或序偶，记作 \(\langle x,y \rangle\)，其中 \(x\) 是它的第一元素，\(y\) 是它的第二元素。

有序对的基本性质¶

• \(x \neq y\)时，\(\langle x, y \rangle \neq \langle y, x \rangle\)

  Tip

  • 有序对中的元素是有序的

  • 集合中的元素是无序的

• \(<x, y> = <u,v> \iff (x = u) \land (y = v)\)

笛卡尔积¶

设 \(A\)，\(B\) 为集合,用 \(A\) 中元素为第一元素，\(B\) 中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做 \(A\) 和 \(B\) 的笛卡儿积（Cartesian product），记作 \(A \times B\)。

笛卡儿积的符号化表示为：

笛卡尔积的运算性质¶

1. 对任意集合A，根据定义有

   \[ A \times \varnothing = \varnothing, \varnothing \times A = \varnothing \]

2. 一般的说，笛卡儿积运算不满足交换律，即

   \[ A \times B \neq B \times A \quad (当 A \neq \varnothing \land B \neq \varnothing \land A \neq B 时) \]

3. 笛卡儿积运算不满足结合律，即

   \[ (A \times B) \times C \neq A \times (B \times C) \quad (当 A \neq \varnothing \land B \neq \varnothing \land C \neq \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) \]

5. \(A \subseteq C \land B \subseteq D \Rightarrow A \times B \subseteq C \times D\)

n阶笛卡尔积¶

设 \(A_1, A_2, ..., A_n\) 为 \(n\) 个集合（\(n \geq 2\)），则 \(A_1 \times A_2 \times ... \times A_n\) 叫做 \(A_1, A_2, ..., A_n\) 的 \(n\) 阶笛卡尔积，记作 \(A_1 \times A_2 \times ... \times A_n\)。其中：

当 \(A_1 = A_2 = ... = A_n = A\) 时，它们的 \(n\) 阶笛卡尔积可简记作 \(A^n\)。

二元关系的定义和表示¶

如果一个集合满足以下条件之一：

1. 集合非空，且它的元素都是有序对

2. 集合是空集

则称该集合为一个二元关系，记作 \(R\)。二元关系也可简称为关系。

对于二元关系 \(R\)，如果 \(\langle x,y \rangle \in R\)，可记作 \(xRy\)；如果 \(\langle x,y \rangle \notin R\)，则记作 \(x\not{R}y\)。

集合到集合的二元关系¶

设 \(A\)，\(B\) 为集合，\(A \times B\) 的任何子集所定义的二元关系叫做从 \(A\) 到 \(B\) 的二元关系；特别当 \(A = B\) 时，则叫做 \(A\) 上的二元关系。

常用的关系¶

对任意集合A，定义：

• 全域关系：\(E_A = \{\langle x,y \rangle \mid x \in A \land y \in A\} = A \times A\)

• 恒等关系：\(I_A = \{\langle x,x \rangle \mid x \in A\}\)

• 空关系：\(\varnothing\)

• 小于或等于关系：\(L_A = \{\langle x,y \rangle \mid x,y \in A \land x \leq y\}，其中 A \subseteq R\)。

• 整除关系：\(D_B = \{\langle x,y \rangle \mid x,y \in B \land x | y\}，其中 B \subseteq Z^*\)，\(Z^*\) 是非零整数集

• 包含关系：\(R \subseteq = \{\langle x,y \rangle \mid x,y \in A \land x \subseteq y\}\)，其中 A 是集合族。

关系的表示方法¶

关系一般有三种表示方法：

• 集合表达式

• 关系矩阵

• 关系图

关系矩阵和关系图可以表示有穷集合上的关系。

关系矩阵和关系图的实例

其实对数据结构的相关内容（邻接矩阵）有了解的话，会发现这二者的思想其实是高度重合的，包括下面的关系图也是如此。

关系矩阵¶

设 \(A = \{x_1, x_2, \cdots, x_n\}\)，\(R\) 是 \(A\) 上的二元关系，令

则 \(R\) 的关系矩阵为：

关系图¶

设 \(A = \{x_1, x_2, \cdots, x_n\}\)，\(R\) 是 \(A\) 上的关系。令图 \(G = \langle V,E \rangle\)，其中顶点集合 \(V = A\)，边集为 \(E\)。对于 \(\forall x_i, x_j \in V\)，满足

称图G为R的关系图，记作 \(G_R\)。

关系的运算¶

关系的定义域、值域和域¶

设 \(R\) 是二元关系，则：

1. \(R\) 中所有有序对的第一元素构成的集合称为 \(R\) 的定义域(domain)，记为 \(dom R\)。形式化表示为：

   \[ dom R ＝ \{x \mid \exists y (\langle x,y \rangle \in R)\} \]

2. \(R\) 中所有有序对的第二元素构成的集合称为 \(R\) 的值域(range) ，记作 \(ran R\)。形式化表示为：

   \[ ran R＝\{y \mid \exists x (\langle x,y \rangle \in R)\} \]

3. \(R\) 的定义域和值域的并集称为 \(R\) 的域(field)，记作 \(fld R\)。形式化表示为：

   \[ fld R＝dom R \cup ran R \]

图解法表示二元关系

首先用两个封闭的曲线表示 \(R\) 的定义域（或集合 \(A\)）和值域（或集合 \(B\)），如果 \(xRy\)，则从 \(x\) 出发，沿着有向边（箭头）到达 \(y\)。

关系的逆、合成、限制和像¶

1. 设 \(F\) 为二元关系，\(F\) 的逆关系，简称 \(F\) 的逆(inverse)，记作 \(F^{-1}\)，其中

   \[ F^{-1} = \{\langle x,y \rangle \mid yFx\} \]

2. 设 \(F\)，\(G\) 为二元关系，\(F\) 与 \(G\) 的合成(composite)记作 \(F \circ G\) (左复合)，其中

   \[ F \circ G = \{\langle x,y \rangle \mid \exists z (xGz \land zFy)\} \]

3. \(F\) 在 \(A\) 上的限制(restriction)记作 \(F\upharpoonright A\)，其中

   \[ F\upharpoonright A = \{\langle x,y \rangle \mid xFy \land x \in A\} \]

4. \(A\) 在 \(F\) 下的像(image)记作 \(F\lbrack A\rbrack\)，其中

   \[ F\lbrack A\rbrack = ran(F\upharpoonright A) \]

关系与集合¶

关系是集合，集合运算对于关系也是适用的。

规定：

• 关系运算中逆运算优先于其它运算

• 所有的关系运算都优先于集合运算

• 优先权的运算以括号决定运算顺序

关系运算的部分定理¶

1. 设 \(F\)，\(G\)，\(H\) 是任意的关系，则有

   \[ (F^{-1})^{-1} = F \]
   \[ dom F^{-1} = ran F, \quad ran F^{-1} = dom F \]
   \[ (F \circ G) \circ H = F \circ (G \circ H) \]
   \[ (F \circ G)^{-1} = G^{-1} \circ F^{-1} \]

2. 设 \(F\)，\(G\)，\(H\) 是任意的关系，则有

   \[ (F \circ G)^{-1} = G^{-1} \circ F^{-1} \]
   \[ F \circ (G \cup H) = F \circ G \cup F \circ H \]
   \[ (G \cup H) \circ F = G \circ F \cup H \circ F \]
   \[ F \circ (G \cap H) \subseteq F \circ G \cap F \circ H \]

   • 推论：

     基于数学归纳法不难证明定理2的结论对于有限多个关系的并和交也是成立的，即有

     \[ R \circ (R_1 \cup R_2 \cup \cdots \cup R_n) = R \circ R_1 \cup R \circ R_2 \cup \cdots \cup R \circ R_n \]
     \[ (R_1 \cup R_2 \cup \cdots \cup R_n) \circ R = R_1 \circ R \cup R_2 \circ R \cup \cdots \cup R_n \circ R \]
     \[ R \circ (R_1 \cap R_2 \cap \cdots \cap R_n) \subseteq R \circ R_1 \cap R \circ R_2 \cap \cdots \cap R \circ R_n \]
     \[ (R_1 \cap R_2 \cap \cdots \cap R_n) \circ R \subseteq R_1 \circ R \cap R_2 \circ R \cap \cdots \cap R_n \circ R \]

关系的幂运算¶

设 \(R\) 为 \(A\) 上的关系，\(n\) 为自然数，则 \(R\) 的 \(n\) 次幂定义为：

Example

幂运算的性质¶

• 设 \(A\) 为 \(n\) 元集，\(R\) 是 \(A\) 上的关系，则存在自然数 \(s\) 和 \(t\)，使得 \(R^s = R^t\)。

  Note

  该定理说明有穷集上只有有穷多个不同的二元关系。当 \(t\) 足够大时，\(R^t\) 必与某个 \(R^s\)(\(s<t\)) 相等（如上面例子中的 \(R^4 = R^2\)）。

• 设 \(R\) 是 \(A\) 上的关系，\(m,n \in \mathbb{N}\)，则

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

  2. \((R^m)^n = R^{mn}\)

关系的性质¶

关系的自反性和反自反性¶

设 \(R\) 为 \(A\) 上的关系，

• 若 \(\forall x (x \in A \rightarrow \langle x,x \rangle \in R)\)，则称 \(R\) 在 \(A\) 上是自反（reflexivity）的。

• 若 \(\forall x (x \in A \rightarrow \langle x,x \rangle \notin R)\)，则称 \(R\) 在 \(A\) 上是反自反（irreflexivity）的。

关系的对称性和反对称性¶

设 \(R\) 为 \(A\) 上的关系，

• 若 \(\forall x \forall y (x,y \in A \land \langle x,y \rangle \in R \rightarrow \langle y,x \rangle \in R)\)，则称 \(R\) 为 \(A\) 上对称（symmetry）的关系。

• 若 \(\forall x \forall y (x,y \in A \land \langle x,y \rangle \in R \land \langle y,x \rangle \in R \rightarrow x = y)\)，则称 \(R\) 为 \(A\) 上的反对称（antisymmetry）关系。

关系的传递性¶

设 \(R\) 为 \(A\) 上的关系，若

则称 \(R\) 是 \(A\) 上的传递（transitivity）关系。

关系性质的特点¶

Example

关系的闭包¶

闭包的定义¶

设 \(R\) 是非空集合 \(A\) 上的关系，\(R\) 的自反（对称或传递）闭包是 \(A\) 上的关系 \(R'\)，使得 \(R'\) 满足以下条件：

• \(R'\) 是自反的（对称的或传递的）

• \(R \subseteq R'\)

• 对 \(A\) 上任何包含 \(R\) 的自反（对称或传递）关系 \(R''\) 有 \(R' \subseteq R''\)。

一般将 \(R\) 的自反闭包记作 \(r(R)\)，对称闭包记作 \(s(R)\)，传递闭包记作 \(t(R)\)。

Example

闭包的构造方法¶

设 \(R\) 为非空集合 \(A\) 上的关系，则有：

1. \(r(R) = R \cup R^0\)

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

3. \(t(R) = R \cup R^2 \cup R^3 \cup \cdots\)

<!--

-->

通过关系图求闭包¶

设关系 \(R\)，\(r(R)\)，\(s(R)\)，\(t(R)\) 的关系图分别记为 \(G\)，\(G_r\)，\(G_s\)，\(G_t\)，则 \(G_r\)，\(G_s\)，\(G_t\) 的顶点集与 \(G\) 的顶点集相等。

除了 \(G\) 的边以外，以下述方法添加新的边：

1. 考察 \(G\) 的每个顶点，如果没有环就加上一个环。最终得到 \(G_r\)。

2. 考察 \(G\) 的每一条边，如果有一条 \(x_i\) 到 \(x_j\) 的单向边，\(i \neq j\)，则在 \(G\) 中加一条边 \(x_j\) 到 \(x_i\) 的反方向边。最终得到 \(G_s\)。

3. 考察 \(G\) 的每个顶点 \(x_i\)，找出从 \(x_i\) 出发的所有2步，3步，…，\(n\) 步长的路径（\(n\) 为 \(G\) 中的顶点数）。

   设路径的终点为 \(x_{j_1}, x_{j_2}, \ldots, x_{j_k}\)。如果没有从 \(x_i\) 到 \(x_{j_k}\) 的边，就加上这条边。当检查完所有的顶点后就得到图 \(G_t\)。

Example

通过关系矩阵求闭包¶

设关系 \(R\)，\(r(R)\)，\(s(R)\)，\(t(R)\) 的关系矩阵分别为 \(M\)，\(M_r\)，\(M_s\) 和 \(M_t\)，则：

• 对角线上的值都改为 \(1\)：\(M_r = M + E\)

• 若 \(a_{ij} = 1\)，则令 \(a_{ji} = 1\)：\(M_s = M + M'\)

• 沃舍尔算法：\(M_t = M + M^2 + M^3 + \cdots\)（沃舍尔算法是一种求传递闭包的算法）

  Warshall算法

  输入：\(M\)（\(R\) 的关系矩阵）

  输出：\(M_t\)（\(t(R)\) 的关系矩阵）

  M_T ← M
  for k ← 1 to n do
      for i ← 1 to n do
          for j ← 1 to n do
              M_T[i,j]←M_T[i,j]+M_T[i,k]*M_T[k,j]
  

  注意：算法中矩阵加法和乘法中的元素相加都使用逻辑加。

其中 \(E\) 是和 \(M\) 同阶的单位矩阵，\(M'\) 是 \(M\) 的转置矩阵。

注意在上述等式中矩阵的元素相加时使用逻辑加。

等价关系和偏序关系¶

等价关系¶

设 \(R\) 为非空集合 \(A\) 上的关系。如果 \(R\) 是自反的、对称的和传递的，则称 \(R\) 为 \(A\) 上的等价关系（equivalent relation）。设 \(R\) 是一个等价关系，若 \(\langle x,y \rangle \in R\)，称 \(x\) 等价于 \(y\)，记做 \(x \sim y\)。

Example

等价类¶

设 \(R\) 为非空集合 \(A\) 上的等价关系，\(\forall x \in A\)，令

称 \(\left[x\right]_R\) 为 \(x\) 关于 \(R\) 的等价类，简称为 \(x\) 的等价类，简记为 \(\left[x\right]\)。

x 的等价类是 A 中所有与 x 等价的元素构成的集合。

等价类的性质¶

设 \(R\) 是非空集合 \(A\) 上的等价关系，则

1. \(\forall x \in A\)，\(\left[x\right]\) 是 A 的非空子集。

2. \(\forall x,y \in A\)，如果 \(xRy\)，则 \(\left[x\right] = \left[y\right]\)。

3. \(\forall x,y \in A\)，如果 \(\langle x,y \rangle \notin R\)，则 \(\left[x\right]\) 与 \(\left[y\right]\) 不交。

4. \(\bigcup_{x \in A} \left[x\right] = A\)。

商集¶

设 \(R\) 是非空集合 \(A\) 上的等价关系，以 \(R\) 的所有等价类作为元素的集合称为 \(A\) 关于 \(R\) 的商集（quotient set），记作 \(A/R\)。

Example

划分¶

设 \(R\) 是非空集合 \(A\) 上的等价关系，\(A\) 的子集族 \(\mathcal{P}\) 满足：

1. \(\forall X \in \mathcal{P}\)，\(X \neq \varnothing\)。

2. \(\forall X,Y \in \mathcal{P}\)，如果 \(X \neq Y\)，则 \(X \cap Y = \varnothing\)。

3. \(\bigcup_{X \in \mathcal{P}} X = A\)。

则称 \(\mathcal{P}\) 为 \(A\) 的一个划分（partition）。

Example

偏序关系¶

设 \(R\) 为非空集合 \(A\) 上的关系。如果 \(R\) 是自反的、反对称的和传递的，则称 \(R\) 为 \(A\) 上的偏序关系（partial order relation）。设 \(R\) 是一个偏序关系，若 \(\langle x,y \rangle \in R\)，称 \(x\) 小于或等于 \(y\)，记做 \(x \leq y\)。

其他常用关系

• 小于或等于关系：\(L_A = \{\langle x,y \rangle \mid x,y \in A \land x \leq y\}\)，其中 \(A \subseteq R\)。

• 整除关系：\(D_B = \{\langle x,y \rangle \mid x,y \in B \land x | y\}\)，其中 \(B \subseteq Z^*\)，\(Z^*\) 是非零整数集。

• 包含关系：\(R \subseteq = \{\langle x,y \rangle \mid x,y \in A \land x \subseteq y\}\)，其中 \(A\) 是集合族。

Example

偏序集¶

设 \(R\) 是非空集合 \(A\) 上的偏序关系，则称集合 \(A\) 以 \(R\) 为偏序关系构成的偏序集，记作 \(\langle A,R \rangle\)。

偏序集的特殊元素¶

设 \(\langle A, \leq \rangle\) 是偏序集，\(B \subseteq A\)，\(y \in B\)，如果

• \(\forall x(x\in B \rightarrow x \leq y)\)，则称 \(y\) 为 \(B\) 的最大元（maximum）。

• \(\forall x(x\in B \rightarrow y \leq x)\)，则称 \(y\) 为 \(B\) 的最小元（minimum）。

• \(\exists x(x\in B \wedge x < y)\)，则称 \(y\) 为 \(B\) 的极小元（minimal）。

• \(\exists x(x\in B \wedge y < x)\)，则称 \(y\) 为 \(B\) 的极大元（maximal）。

Example

特殊元素的性质¶

• 最小元是 \(B\) 中最小的元素，它与 \(B\) 中其它元素都可比。

• 极小元不一定与 \(B\) 中元素可比，只要没有比它小的元素，它就是极小元。

• 对于有穷集 \(B\)，极小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的。

• 极小元可能有多个，但不同的极小元之间是不可比的（无关系）。

• 如果 \(B\) 中只有一个极小元，则它一定是 \(B\) 的最小元。

• 哈斯图中，集合 \(B\) 的极小元是 \(B\) 中各元素中的最底层。

可比¶

设 \(R\) 为非空集合 \(A\) 上的偏序关系，定义

在具有偏序关系的集合 \(A\) 中任取两个元素 \(x\) 和 \(y\)，可能有下述几种情况发生：

• \(x < y\)（或 \(y < x\)），\(x = y\)，\(x\) 与 \(y\) 不是可比的。

  其中 \(x < y\) 读作 \(x\)“小于”\(y\)。这里所说的“小于”是指在偏序中 \(x\) 排在 \(y\) 的前边。

覆盖¶

设 \(\langle A, \leq \rangle\) 是偏序集，\(x, y \in A\)，如果 \(x \leq y\) 且不存在 \(z \in A\) 使得 \(x < z < y\)，则称 \(y\) 覆盖 \(x\)。

全序关系¶

设 \(R\) 为非空集合 \(A\) 上的偏序关系，如果 \(\forall x, y \in A\)，\(x\) 和 \(y\) 都是可比的，则称 \(R\) 为 \(A\) 上的全序关系（total order relation）或线序关系。

哈斯图¶

利用偏序关系的自反性、反对称性和传递性所得到的偏序集合图，称为哈斯图（Hasse diagram）。

画偏序集 \(\langle A, \leq \rangle\) 的哈斯图的方法：

1. 用小圆圈代表元素。

2. \(\forall x,y \in A\)，若 \(x < y\)，则将 \(x\) 画在 \(y\) 的下方。

3. 对于 \(A\) 中的两个不同元素 \(x\) 和 \(y\)，如果 \(y\) 覆盖 \(x\)，就用一条线段连接 \(x\) 和 \(y\)。

上下界¶

设 \(\langle A, \leq \rangle\) 是偏序集，\(B \subseteq A\)，\(y \in A\)：

• 若 \(\forall x(x\in B \rightarrow x \leq y)\)，则称 \(y\) 为 \(B\) 的上界（upper bound）。

• 若 \(\forall x(x\in B \rightarrow y \leq x)\)，则称 \(y\) 为 \(B\) 的下界（lower bound）。

• 令 \(C = \{y \mid y \text{ 为 } B \text{ 的上界}\}\)，则称 \(C\) 的最小元为 \(B\) 的最小上界或上确界。

• 令 \(D = \{y \mid y \text{ 为 } B \text{ 的下界}\}\)，则称 \(D\) 的最大元为 \(B\) 的最大下界或下确界。

Example

上下界的性质¶

• \(B\) 的最小元一定是 \(B\) 的下界，同时也是 \(B\) 的最大下界。

• \(B\) 的最大元一定是 \(B\) 的上界，同时也是 \(B\) 的最小上界。

• \(B\) 的下界不一定是 \(B\) 的最小元，因为它可能不是 \(B\) 中的元素。

• \(B\) 的上界也不一定是 \(B\) 的最大元。

• \(B\) 的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界与最大下界是唯一的。