离散数学笔记(5)——集合论(1)

离散数学笔记(5)——集合论(1)

关系

三个特殊关系

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

关系的性质

  1. 自反性:设 $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$。

  2. 反自反性:设 $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$。

  3. 对称性:设 $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)$。

    从关系图看对称性:在两个不同的结点之间,若有边的话,则有方向相反的两条边。

    从关系矩阵看对称性:以主对角线为对称的矩阵。

  4. 反对称性:设 $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$。

  5. 传递性:设 $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$。

复合关系的计算

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

性质

  1. 满足结合律:$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$。
    23
  2. $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$$

一般地,有:

  1. $R^0 = I_A$
  2. $R^m \circ R^n = R^{m + n}$
  3. $(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$$

计算方法

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

性质

令 $R$、$S$ 都是从 $X$ 到 $Y$ 的关系,则:

  1. $(R^c)^c = R$

  2. $(R \cup S)^c = R^c \cup S^c$

  3. $(R \cap S)^c = R^c \cap S^c$

  4. $\rm{dom} R^c = \rm{ran} R,\rm{ran} R^c = \rm{dom} R$

  5. $(R – S)^c = R^c – S^c$

  6. $R \subseteq S \Leftrightarrow R^c \subseteq S^c$

  7. $(\sim R)^c = \sim R^c$

  8. 令 $R$ 是从 $X$ 到 $Y$ 的关系,$S$ 是 $Y$ 到 $Z$ 的关系,则 $(R \circ S)^c = S^c \circ R^c$

  9. $R$ 是 $A$ 上关系,则 $R$ 是对称的,当且仅当 $R^C =R$

  10. $R$ 是 $A$ 上关系,则 $R$ 是反对称的,当且仅当 $R \cap R^c \subseteq I_A$

    24

  11. $R$ 是 $A$ 上关系,则 $R$ 是传递的,当且仅当 $R \circ R \subseteq R$

    25

  12. $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$ 上的对称关系。

26

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

27

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

28

关系的闭包运算

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

定义

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

  1. $R \subseteq R’$。
  2. $R’$ 是自反的(对称的、传递的)。
  3. $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$。

29

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

30

31

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

32

求 $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$)

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

性质

定理 5:$R$ 是 $A$ 上关系,则:

  1. $R$ 是自反的,当且仅当 $r(R) = R$。
  2. $R$ 是对称的,当且仅当 $s(R) = R$。
  3. $R$ 是传递的,当且仅当 $t(R) = R$。

定理 6:$R$ 是 $A$ 上关系,则:

  1. $R$ 是自反的,则 $s(R)$ 和 $t(R)$ 也自反。

  2. $R$ 是对称的,则 $r(R)$ 和 $t(R)$ 也对称。

  3. $R$ 是传递的,则 $r(R)$ 也传递。

    33

    34

    35

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

  1. $r(R_1) \subseteq r(R_2)$
  2. $s(R_1) \subseteq s(R_2)$
  3. $t(R_1) \subseteq t(R_2)$

36

定理 8:设 $R_1$、$R_2$ 是 $A$ 上关系,则:

  1. $r(R_1 \cup R_2) = r(R_1) \cup r(R_2)$
  2. $s(R_1 \cup R_2) = s(R_1) \cup s(R_2)$
  3. $t(R_1) \cup t(R_2) \subseteq t(R_1 \cup R_2)$

37

定理 9:设 $R$ 是 $A$ 上关系,则:

  1. $s(r(R)) = r(s(R))$
  2. $t(r(R)) = r(t(R))$
  3. $s(t(R)) \subseteq t(s(R))$

38

 

点赞 0

No Comments

Add your comment