第七章 关系

6.1 关系及其性质

定义6.1 任何有序偶的集合称为二元关系.

注意关键词 有序 偶 集合 二元 请问空集是吗?

从\(X\)到\(Y\)的关系\(R\)满足\(R \subseteq X \times Y\). 若\(<x, y> \in R\)则表示成\(xRy\), 读作"\(x\)与\(y\)有关系\(R\).

若\(R\)是由集合\(X\)到集合\(Y\)的一个关系, 则对于任意\(x \in X, y \in Y\), 有且只有两种情况之一:

1. \(x\)与\(y\)有关系\(R\);
2. \(x\)与\(y\)不存在关系\(R\);

一个二元关系可以用一个二元谓词来表示, 即表示为 若\(R = {<x, y> | P(x, y)}\), 则\((\forall x)(\forall y)(P(x, y) \leftrightarrow <x, y> \in R)\)

数学上的大于关系, 平方关系等也可以类似表示

定义6.2 设任一关系\(R\), \(R\)中所有有序偶\(<x, y>\)的第一个元的集合, 称为\(R\)的定义域, 记为\(dom(R)\); 第二个元的集合, 称为\(R\)的值域, 记为\(ran(R)\), 即

\[ dom(R) = \{x | (\exist y)(<x, y> \in R)\}\\ ran(R) = \{y | (\exist x)(<x, y> \in R)\} \]

dom即domain, ran即range

设\(X\)和\(Y\)是任意两个集合, 对于\(X\)到\(Y\)的关系\(R\), 有\(dom(R) \subseteq X, ran(R) \subseteq Y\). 如果\(X = Y\), 则\(R\)是\(X\)到\(X\)的关系, 或称\(R\)是\(X\)上的关系.

集合\(X \times X\)称为\(X\)上的全域关系, 记作\(U_X\). 作为\(X \times X\)的子集的空集\(\varnothing\),称为\(X\)上的空关系. \(X\)上的恒等关系, 记作\(I_X\)

\[ U_X = \{<x_i, x_j> | x_i, x_j \in X\}\\ I_X = \{<x, x> | x \in X\} \]

对于有穷集合上的关系, 可以用矩阵和图来表示, 称为关系矩阵和关系图.

设\(X = \{x_1, x_2, ..., x_m\}, Y = \{y_1, y_2, ..., y_n\}\), \(R\)是\(X\)到\(Y\)的关系, \(R\)的关系矩阵是一个\(m \times n\)阶矩阵, 其第\(i\)行第\(j\)列的元素记为\(r_{ij}\), 按下式取值:

\[ r_{ij} = \begin{cases} 0, 如果x_i \overline{R} y_j\\ 1, 如果x_i R y_j \end{cases} \]

关系的表示可以帮助理解和识别关系的性质/种类

6.2 关系的运算

关系是有序偶的集合, 所以对于关系可以进行各种集合运算, 运算结果仍然是一个有序偶集合, 也就是一个新的运算, 它定义了一个新的关系.

定义6.4 设\(R\)和\(S\)表示从\(X\)到\(Y\)的两个关系, 则\(R \cap S, R \cup S, R - S, \sim R\)也都表示从\(X\)到\(Y\)的关系, 并且 $$ x(R \cap S)y \Leftrightarrow xRy \wedge xSy\ x(R \cup S)y \Leftrightarrow xRy \vee xSy\ x(R - S)y \Leftrightarrow xRy \wedge x \overline{S} y\ x(\sim R)y \Leftrightarrow x \overline{R} y $$

注意补集运算是相对于全集的运算

关系作为一种有序偶的集合, 还有复合运算

定义6.5 设\(R\)是从\(X\)到\(Y\)的关系, \(S\)是从\(Y\)到\(Z\)的关系, 则称\(X\)到\(Z\)的一个关系\(R \circ S\)为\(R\)和\(S\)的复合关系, 即

\[ R \circ S = \{<x, z> | x \in X \wedge z \in Z \wedge (\exist y)(y \in Y \wedge xRy \wedge ySz)\} \]

如果\(R\)的值域与\(S\)的定义域的交集是空集,则复合关系\(R \circ S\)也是空集.

一般复合运算是不复合交换律的,但是复合运算复合结合律

定理6.1 设\(R, S, P\)分别是从\(X\)到\(Y\), \(Y\)到\(Z\), \(Z\)到\(W\)的关系, 则\((R \circ S) \circ P = R \circ (S \circ P)\).

证明 对任意\(<x, w>\). $$ \in (R \circ S) \circ P\ \Leftrightarrow (\exist z)[ \in R \circ S \wedge \in P]\ \Leftrightarrow (\exist z)(\exist y)[ \in R \wedge \in S \wedge \in P]\ \Leftrightarrow (\exist y)(\exist z)[ \in R \wedge \in S \wedge \in P]\ \Leftrightarrow (\exist y)[ \in R \wedge (\exist z)( \in S \wedge \in P)]\ \Leftrightarrow (\exist y)[ \in R \wedge \in S \circ P]\ \Leftrightarrow \in R \circ (S \circ P) $$

关系的运算满足结合律, 因此可以把括号直接去掉写为\(R \circ S \circ P\)

当\(R\)是在集合\(X\)上的关系时, \(R\)能与其自身复合任意次得出在集合\(X\)上的一个新关系, 由此可以归纳定义一种信运算如下

定义6.6 设\(R\)是集合\(X\)上的二元关系, \(n \in N\), 则\(R\)的\(n\)次幂, 表示为\(R^n\)定义如下:

1. \(R^0\)是集合\(X\)上的恒等关系. \(R^0 = I_X = \{<x, x> | x \in X\}\)
2. \(R^{n + 1} = R^n \circ R\)

容易证明, 若\(m, n \in N\)有

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

两个关系的复合也可以用矩阵运算来表示

定义6.7 设\(R\)是从\(X\)到\(Y\)的关系. 它的逆关系记作\(R^{-1}\), 是\(Y\)到\(X\)的关系. 其中\(R^{-1}\)包含所有\(R\)中的有序偶的逆序偶, 即

\[ R^{-1} = \{<y, x> | x \in X \wedge y \in Y \wedge xRy\} \]

定理6.2 设\(R\)是从\(X\)到\(Y\)的关系, \(S\)是从\(Y\)到\(Z\)的关系, 则有

\[ (R \circ S)^{-1} = S^{-1} \circ R^{-1}. \]

定义6.8 设\(R\)是集合\(X\)上的二元关系, 关系\(R'\)称为自反(对称, 传递)闭包, 满足下列三个条件:

1. \(R'\)是自反的(对称的, 传递的)
2. \(R \subseteq R'\)
3. 对于任何自反的(对称的, 传递的)关系\(R''\), 如果有\(R \subseteq R''\), 则\(R' \subseteq R''\).

一般用\(r(R), s(R), t(R)\)分别表示\(R\)的自反闭包, 对称闭包和传递闭包.

6.3 次序关系

集合