离散数学II笔记(4)

关系的复合运算（合成）

定义：

设R是 X 到 Y 的关系， S 是Y到Z 的关
系，则 $R ◦ S ＝\{<x, z>|\exist y \in Y 使得\, x R y ∧ y S z \}$ 为 X 到 Z 的关系, 称为 R 和 S 的合成。
显然， $dom (R◦S) \subseteq dom(R)，ran(R◦S) \subseteq ran(S)．$

性质：

设A, B, C和D为任意四个集合，二元关系
$R_1 \subseteq A\times B,\, R_2, R_3 \subseteq B\times C，R_4 \subseteq C\times D：$

若 $R_2 \subseteq R_3$ ，则 $R_1◦R_2 \subseteq R_1 ◦ R_3$ 且 $R_2 ◦ R_4 \subseteq R_3 ◦R_4$ ；
$R_1 ◦ (R_2∪R_3) = (R_1◦R_2) ∪ (R_1◦R_3)$ ；
$(R_2∪R_3) ◦R_4 = (R_2◦R_4) ∪ (R_3◦R_4)$ ；
$R_1◦ (R_2∩R_3) \subseteq (R_1◦R_2) ∩ (R_1◦R_3)$ ；
$(R_2∩R_3) ◦R_4 \subseteq (R_2◦R_4) ∩ (R_3◦R_4)$ ；
$(R_1◦R_2)^{–1} = R_2^{–1} ◦ R_1^{–1}$ ；
$(R_1◦R_2) ◦R_4 = R_1◦ (R_2◦R_4)$ .

例子：

设 $R = \{(a, b), (b, c)\}$ $R = {(a, b), (b, c)}$ ，则：
- $R^{-1} = \{(b, a), (c, b)\}$ ，
- 如果再有一个关系 $S = \{(b, d)\}$ ，则：
  $R \circ S = \{(a, d)\}$

关系的幂次

定义：设 $R$ 是集合$ A$ 上的关系，$n $是自然数，$ R$ 的 $n $次幂 $R^n$ 定义如下：
(1) $R^0$ 是集合A上的恒等关系 $I_A$ ，即 $R^0 ＝ I_A$ ；
(2) $R^{n＋1} ＝ R^n ◦ R$ ．

若n, m ∈N 且 R 为集合A上的二元关系，则
(1) $(R^n)^{-1} = (R^{-1})^n$ ;
(2) $R^n◦R^m = R^{n+m}$ ;
(3) $(R^n)^m = R^{nm}$ .
设有限集$ A $恰有$ n $个元素．若$ R$ 为 $A $上的二元关系，则有,$ s, t ∈ N$, 使 $s < t ≤ 2^{n^𝟐}$ 且$ R^s = R^t$ ．
设 $R$ 和 $S $ 都是集合A上的二元关系,则
设 R 为 A 上的二元关系，
(1) R 为自反的当且仅当 $I_A \subseteq R$ ;
(2) R为反自反的当且仅当 $I_A\cap R = \varnothing$ ;
(3) R 为对称的当且仅当$R = R^{–1} $； (4) R 为反对称的当且仅当$ R \cap R^{–1} \subseteq I_A $; (5) R 为传递的当且仅当$ R ◦ R \subseteq R$

关系复合的矩阵表示

关系的闭包运算

闭包的定义

闭包运算用于通过添加一些元素，使原有关系具备某些特定的性质（如自反性、对称性或传递性）。常见的闭包运算包括自反闭包、对称闭包和传递闭包。

自反闭包：
- 定义：设 $R$ 是集合 $A$ 上的一个关系， $R$ 的自反闭包 $r(R)$ 是包含 $R$ 的最小自反关系。其形式为： $r(R) = R \cup I_A$
  
  其中， $I_A$ 是集合 $A$ 上的恒等关系，即 $I_A = \{(x, x) \mid x \in A\}$ 。
对称闭包：
- 定义：设 $R$ 是集合 $A$ 上的一个关系， $R$ 的对称闭包 $s(R)$ 是包含 $R$ 的最小对称关系。其形式为： $s(R) = R \cup R^{-1}$ ，即通过加入 $R$ 的逆关系，使其成为对称关系。
传递闭包：
- 定义：设 $R$ 是集合 $A$ 上的一个关系， $R$ 的传递闭包 $t(R)$ 是包含 $R$ 的最小传递关系。其形式为： $t(R) = \bigcup_{n=1}^{\infty} R^n$ ，即通过将 $R$ 复合多次，直到得到一个传递关系。

闭包运算的性质

自反闭包性质：
- $r(R)$ 是包含 $R$ 的最小自反关系。
- 即， $r(R)$ 包含 $R$ 中的所有关系，并确保每个元素与自身有关系。
对称闭包性质：
- $s(R)$ 是包含 $R$ 的最小对称关系。
- 对称闭包保证任意两个互有关联的元素 $xRy$ ，其逆关系 $yRx$ 也存在。
传递闭包性质：
- $t(R)$ 是包含 $R$ 的最小传递关系。
- 传递闭包确保关系的传递性：如果 $xRy$ 且 $yRz$ ，则必然有 $xRz$ 。

闭包运算的组合性质

闭包运算可以组合使用，以确保关系同时具备自反性、对称性和传递性。例如：
- 先进行自反闭包 $r(R)$ ，再进行对称闭包 $s(r(R))$ ，最后再进行传递闭包 $t(s(r(R)))$ ，可以得到一个既自反、对称又传递的关系。

次序关系

偏序关系 (Partial Order)

定义：若集合 $A$ $A$ 上的二元关系 $R$ $R$ 满足以下三个性质，则称 $R$ $R$ 为偏序关系：
- 自反性：对于任意 $x \in A$ ，有 $xRx$ ；
- 反对称性：若 $xRy$ 且 $yRx$ ，则 $x = y$ ；
- 传递性：若 $xRy$ 且 $yRz$ ，则 $xRz$ 。

例子：

自然数集合上的小于等于关系 $ \leq $ 是一个偏序关系。
集合 $P(A)$ 上的包含关系 $ \subseteq $ 是偏序关系。

严格偏序关系 (Strict Partial Order)

定义：严格偏序关系是不具有自反性的偏序关系。即，关系 $R$ $R$ 满足以下条件：
- 反自反性：对任意 $x \in A$ ，没有 $xRx$ ；
- 反对称性和传递性同样成立。

例子：

整数集上的“<”是一个严格偏序关系。

全序关系 (Total Order)

定义：全序关系是一种偏序关系，且集合中的任何两个元素都是可比的。
- 对任意 $x, y \in A$ ，要么 $xRy$ ，要么 $yRx$ 。

例子：

实数集上的小于等于关系 $ \leq $ 是全序关系。

哈斯图 (Hasse Diagram)

定义：哈斯图是一种简化的偏序关系图，用于表示偏序集合的关系结构，去掉了自反性和传递性导致的冗余边。

例子：

集合 $A = \{1, 2, 3, 4\}$ $A = {1, 2, 3, 4}$ 的偏序关系 $ \leq $ 的哈斯图：
1
2
3
4
5
6
7
1
|
2
|
3
|
4

等价关系

定义

等价关系是一种特殊的二元关系，满足以下三个性质：
- 自反性：对于任意 $x \in A$ ，有 $xRx$ ；
- 对称性：若 $xRy$ ，则 $yRx$ ；
- 传递性：若 $xRy$ 且 $yRz$ ，则 $xRz$ 。

例子：

实数上的相等关系是等价关系。
集合中的元素间的同类关系，如模3同余关系。

等价类 (Equivalence Class)

定义：对于集合 $A$ 上的等价关系 $R$ ，对于任意 $x \in A$ ，与 $x$ 有关系 $R$ 的所有元素构成一个等价类，记作 $[x]_R$ 。

例子：

模3同余关系下，集合 $A = \{1, 2, 3, 4, 5, 6, 7\}$ 的等价类为：
[
[1]_R = {1, 4, 7}, \quad [2]_R = {2, 5}, \quad [3]_R = {3, 6}
]

等价关系的图表示

等价关系可以通过无向图来表示。图的每个连通分支表示一个等价类。等价关系的简化关系图是无向图，每个结点对应一个元素。

例子：

模3同余关系的简化关系图：
1
2
3
1 - 4 - 7
2 - 5
3 - 6

划分 (Partition)

划分的定义

定义：设 $A$ 为一个集合，若集合的子集族 $\mathcal{P}$ 满足以下三个条件：
1. $\forall S \in \mathcal{P}, S \neq \emptyset$ ；
2. $\bigcup \mathcal{P} = A$ ；
3. 对于任意 $S_1, S_2 \in \mathcal{P}$ ，若 $S_1 \cap S_2 \neq \emptyset$ ，则 $S_1 = S_2$ 。
则称 $\mathcal{P}$ 为 $A$ 的一个划分。

等价关系与划分的联系

定理：若 $R$ 是集合 $A$ 上的等价关系，则商集 $A/R = \{[x]_R | x \in A\}$ 是集合 $A$ 的一个划分。
反之，若 $\mathcal{P}$ 是集合 $A$ 的一个划分，则存在等价关系 $R_{\mathcal{P}}$ ，使得 $\mathcal{P}$ 确定 $A$ 上的等价关系。