离散数学笔记（5）——集合论（1）

wzf2000
2019年10月15日

离散数学笔记（5）——集合论（1）

Contents

关系

三个特殊关系

空关系：因为 $\varnothing \subseteq A \times B(A \times A)$，所以称之为从 $A$ 到 $B$ （或 $A$ ）上的空关系。
全域关系：即 $A \times A$，称之为 $A$ 上的全域关系，记为 $E_A$。
$A$ 上的恒等关系 $I_A$：$I_A \subseteq A \times A$，且 $I_A = \{\langle x,x \rangle|x \in A\}$，称之为 $A$ 上的恒等关系。

关系的性质

自反性：设 $R$ 是集合 $A$ 的关系，如果对于任意 $x \in A$，都有 $\langle x,x \rangle \in R$（$xRx$），则称 $R$ 是 $A$ 中的自反关系。即：$R$ 是 $A$ 中自反的 $\Leftrightarrow \forall x (x \in A \to xRx)$。
从关系图看自反性：每个结点都有环。
从关系矩阵看自反性：主对角线都为 $1$。
反自反性：设 $R$ 是集合 $A$ 的关系，如果对于任意 $x \in A$，都有 $\langle x,x \rangle \not \in R$，则称 $R$ 是 $A$ 中的反自反关系。即：$R$ 是 $A$ 中反自反的 $\Leftrightarrow \forall x (x \in A \to \langle x,x \rangle \not \in R)$。
从关系图看反自反性：每个结点都无环。
从关系矩阵看反自反性：主对角线都为 $0$。
对称性：设 $R$ 是集合 $A$ 的关系，如果对于任意 $x,y \in A$，如果有 $xRy$，必有 $yRx$，则称 $R$ 是 $A$ 中的对称关系。即：$R$ 是 $A$ 中对称的 $\Leftrightarrow \forall x \forall y ((x \in A \land y \in A \land xRy) \to yRx)$。
从关系图看对称性：在两个不同的结点之间，若有边的话，则有方向相反的两条边。
从关系矩阵看对称性：以主对角线为对称的矩阵。
反对称性：设 $R$ 是集合 $A$ 的关系，如果对于任意 $x,y \in A$，如果有 $xRy$ 和 $yRx$，就有 $x = y$，则称 $R$ 是 $A$ 中的反对称关系。即：$R$ 是 $A$ 中反对称的 $\Leftrightarrow \forall x \forall y ((x \in A \land y \in A \land xRy \land yRx) \to x = y) \\ \Leftrightarrow \forall x \forall y ((x \in A \land y \in A \land x \not =y \land xRy) \to y \not R x)$
从关系图看反对称性：在两个不同的结点之间最多有一条边。
从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个 $1$。
传递性：设 $R$ 是集合 $A$ 的关系，如果对于任意 $x,y,z \in A$，如果有 $xRy$ 和 $yRz$，就有 $xRz$，则称 $R$ 是 $A$ 中的传递关系。即：$R$ 在 $A$ 中传递 $\Leftrightarrow \forall x \forall y \forall z ((x \in A \land y \in A \land z \in A \land xRy \land yRz) \to xRz)$。
从关系图和关系矩阵中不易看清是否有传递性。

复合关系

定义

设 $R$ 是从 $X$ 到 $Y$ 的关系，$S$ 是从 $Y$ 到 $Z$ 的关系，则 $R$ 和 $S$ 的复合关系记作 $R \circ S$ 。

$$R \circ S = \{\langle x,z \rangle|x \in X \land z \in Z \land \exists y (y \in Y \land \langle x,y \rangle \in R \land \langle y,z \rangle \in S)\}$$

规定 $R \circ \varnothing = \varnothing \circ R = \varnothing$。

复合关系的计算

枚举法
有向图法
关系矩阵法：$c_{ij} = \lor_{k=1}^{n} a_{ik}\land b_{kj}$

性质

满足结合律：$R \subseteq A \times B,S \subseteq B \times C,T \subseteq C \times D$，则 $R \circ (S \circ T) = (R \circ S) \circ T$。
$R$ 是 $A$ 到 $B$ 的关系，则 $R \circ I_B = I_A \circ R = R$。

关系的乘幂

令 $R$ 是 $A$ 上关系，由于复合运算可结合，所以关系的复合可以写成乘幂形式。即：

$$R \circ R = R^2,R^2 \circ R = R \circ R^2 = R^3,\cdots$$

一般地，有：

$R^0 = I_A$
$R^m \circ R^n = R^{m + n}$
$(R^m)^n = R^{mn}$

（$m,n$ 为非负整数）

逆关系

定义

$R$ 是从 $A$ 到 $B$ 的关系，如果将R中的所有序偶的两个元素的位置互换，得到一个从 $B$ 到 $A$ 的关系，称之为 $R$ 的逆关系，记作 $R^{-1}$ ，或 $R^C$。

$$R^c = \{\langle y,x \rangle|\langle x,y \rangle \in R\}$$

$$\langle y,x \rangle \in R^c \Leftrightarrow \langle x,y \rangle \in R$$

计算方法

枚举法
$R^c$ 的有向图：所有边的方向颠倒
$R^c$ 的矩阵 $M_{R^{-1}} = (M_R)^T$ 即为 $R$ 矩阵的转置。

性质

令 $R$、$S$ 都是从 $X$ 到 $Y$ 的关系，则：

$(R^c)^c = R$
$(R \cup S)^c = R^c \cup S^c$
$(R \cap S)^c = R^c \cap S^c$
$\rm{dom} R^c = \rm{ran} R,\rm{ran} R^c = \rm{dom} R$
$(R - S)^c = R^c - S^c$
$R \subseteq S \Leftrightarrow R^c \subseteq S^c$
$(\sim R)^c = \sim R^c$
令 $R$ 是从 $X$ 到 $Y$ 的关系，$S$ 是 $Y$ 到 $Z$ 的关系，则 $(R \circ S)^c = S^c \circ R^c$
$R$ 是 $A$ 上关系，则 $R$ 是对称的，当且仅当 $R^C =R$
$R$ 是 $A$ 上关系，则 $R$ 是反对称的，当且仅当 $R \cap R^c \subseteq I_A$
$R$ 是 $A$ 上关系，则 $R$ 是传递的，当且仅当 $R \circ R \subseteq R$
$R$ 是 $A$ 上关系，则 $R$ 是自反的，当且仅当 $I_A \subseteq R$

一些相关结论

定理 1：设 $R_1$、$R_2$ 是 $A$ 上的自反关系，则 $R_1^C$、$R_1 \cap R_2$、$R_1 \cup R_2$ 也是 $A$ 上的自反关系。

定理 2：设 $R_1$、$R_2$ 是 $A$ 上的对称关系，则 $R_1^C$、$R_1 \cap R_2$、$R_1 \cup R_2$ 也是 $A$ 上的对称关系。

定理 3：设 $R_1$、$R_2$ 是 $A$ 上的传递关系，则 $R_1^C$、$R_1 \cap R_2$ 也是 $A$ 上的传递关系。

定理 4：设 $R_1$、$R_2$ 是 $A$ 上的反对称关系，则 $R_1^C$、$R_1 \cap R_2$ 也是 $A$ 上的反对称关系。

关系的闭包运算

设 $R$ 是 $A$ 上的关系，有时希望给R增加一些有序对，构成新关系 $R’$，使得 $R’$ 具有自反性或对称性或传递性，但不希望 $R’$ 太大，即希望增加的有序对尽量少，这就是闭包的思想。

定义

给定 $A$ 中关系 $R$,若 $A$ 上另一个关系 $R’$，满足：

$R \subseteq R'$。
$R'$ 是自反的（对称的、传递的）。
$R'$ 是“最小的”，即对于任何 $A$ 上自反（对称、传递）的关系 $R''$，如果 $R \subseteq R''$，就有 $R' \subseteq R''$。

则称 $R'$ 是 $R$ 的自反（对称、传递）闭包，记作 $r(R)(s(R),t(R))$。

计算方法

定理 1：给定 $A$ 中关系 $R$，则 $r(R) = R \cup I_A$。

定理 2：给定 $A$ 中关系 $R$，则 $s(R) = R \cup R^c$。

定理 3：给定 $A$ 中关系 $R$，则 $t(R) = R \cup R^2 \cup R^3 \cup \cdots$。

定理 4：给定 $A$ 中关系 $R$,如果 $A$ 是有限集合，$|A| = n$,则 $t(R) = R \cup R^2 \cup \cdots \cup R^n$。

求 $t(R)$ 的矩阵 Warshall 算法：

$|X| = n$，$R \subseteq X \times X$，令 $M_R = A$，则 $M_{R^k} = A^k$，于是 $t(R)$ 的逻辑矩阵 $M_{R^+} = A + A^2 + \cdots + A^k + \cdots$

（算法中 $+$ 都是指逻辑加，即 $\cup$）

置新矩阵 $A := M_R$。
置 $i=1$。
对所有 $j$，如果 $A[j,i] = 1$，则对 $k = 1,2,\cdots,n$，$A[j,k] := A[j,k] + A[i,k]$。
$i$ 加 $1$。
如果 $i \le n$，则转到步骤 3，否则停止。

性质

定理 5：$R$ 是 $A$ 上关系，则：

$R$ 是自反的，当且仅当 $r(R) = R$。
$R$ 是对称的，当且仅当 $s(R) = R$。
$R$ 是传递的，当且仅当 $t(R) = R$。

定理 6：$R$ 是 $A$ 上关系，则：

$R$ 是自反的，则 $s(R)$ 和 $t(R)$ 也自反。
$R$ 是对称的，则 $r(R)$ 和 $t(R)$ 也对称。
$R$ 是传递的，则 $r(R)$ 也传递。

定理 7：设 $R_1$、$R_2$ 是 $A$ 上关系，如果 $R_1 \subseteq R_2$ ，则：

$r(R_1) \subseteq r(R_2)$
$s(R_1) \subseteq s(R_2)$
$t(R_1) \subseteq t(R_2)$

定理 8：设 $R_1$、$R_2$ 是 $A$ 上关系，则：

$r(R_1 \cup R_2) = r(R_1) \cup r(R_2)$
$s(R_1 \cup R_2) = s(R_1) \cup s(R_2)$
$t(R_1) \cup t(R_2) \subseteq t(R_1 \cup R_2)$

定理 9：设 $R$ 是 $A$ 上关系，则：

$s(r(R)) = r(s(R))$
$t(r(R)) = r(t(R))$
$s(t(R)) \subseteq t(s(R))$

离散数学笔记

112 次浏览

No Comments