关系理论#

笛卡尔积的性质#

• 笛卡尔积不满足交换律 $A \times B \neq B \times A$
• $A \times B = \varnothing$当且仅当$A = \varnothing \lor B = \varnothing$
• 笛卡尔积不满足结合律；
• 对于两个有限集，$|A \times B| = | B \times A | = |A| \times |B|$
• 笛卡尔积对于并运算和交运算满足分配律

推广#

• n重有序组：将n个元素按照一定次序排列而成的有序n元组$<a_1, a_2, a_3, ..., a_n>$

• 笛卡尔积：设有n个集合$A_1, A_2, A_3, ..., A_n$，则$A_1 \times A_2 \times A_3 ... A_n = \{<a_1, a_2, a_3, ..., a_n> | a_i \in A_i, i = 1, 2, 3, ..., n \}$

定义域和值域#

本质上函数(function)，也是一组二元关系，表示一种多对1的二元关系映射。 设R是A到B的二元关系，A为关系R的前域，B为关系R的后域；

令： $C = \{ x | x \in A, \exist y \in B, <x, y> \in R \}$

$D = \{ y | y \in B, \exist x \in A, <x, y> \in R \}$

则C为R的定义域(domain)，D为R的值域(range)，记为$D = ran R$

$fldR = domR \lor ranR$为R的域(field)

推广：n元关系#

n个非空集合所对应的笛卡尔积的任意子集R，称作这n个非空集合之间的n元关系

关系的复合运算#

设A, B, C三个集合，R是A到B的关系，S是B到C的关系。

则：R与S的复合关系（合成关系）(composite relation)，记为$R \circ S$，是A到C的关系。 $R \circ S = \{ <x, z> | (x \in A) \land (z \in c) \land (\exist y)(y \in B \land xRy \land ySz) \}$

即：R与S的复合关系就是A到B再到C传递得出关系。对应有向图中由A元素到C元素的路径。

关系的逆运算#

对于A到B的关系R，那么B到A的关系叫做R的逆关系，记为：$R^{-1} = \{ <b, a> | <a, b> \in R \}$，其中："$^{-1}$" 称作逆运算

• 关系矩阵中，表示为矩阵的转置
• 有向图中，将边调转方向

关系的运算定律#

设 $I_A$ 表示为集合A恒等关系，包含集合A中所有自己到自己的关系。

• 结合律：$(R \circ S_1) \circ S_2 = R \circ (S_1 \circ S_2)$
• 同一律：$I \circ R = R$
• 分配律：
  • 分配率中，属于同两个集合的关系先∩再运算得到的关系是先运算再∩得到的子集。
  • $R \circ (S_1 \land S_2) \subseteq (R \circ S_1) \land (R \circ S_2)$
  • 对于并运算直接相等。
• 逆运算：$(R \circ S)^{-1} = S^{-1} \circ R^{-1}$，路径反向
  • 逆运算对于并、交、补不需要换顺序。

关系的幂运算#

关系的复合运算（$\circ$）可以满足幂运算。

• $R^0 = I_A$
• $R^1 = R$

幂运算收敛定理：

• 求R的n次幂，当达到某一次幂后，结果保持不变（某个非空集合，或者空集）。

关系性质的判定定理#

1. R是自反的，当且仅当$I_A \subseteq R$

   包含I_A的所有元素

2. R是反自反的，当且仅当$R \land I_A = \varnothing$

   没有不存在I_A的元素

3. R是对称的，当且仅当$R = R^{-1}$
4. R是反对称的，当且仅当$R \land R^{-1} \subseteq I_A$
5. R是传递的，当且仅当$R \circ R \subseteq R$

关系性质的保守性#

• 如图

对于逆运算和交运算，能够保持原来的性质 并运算不能保证反对称和传递 复合运算只有自反性 补运算只能保证反自反、对称、反对称

关系的闭包#

闭包(closure)问题：给给定的关系中添加最少的元素，使其具有需要的特殊性质。

设R是集合A上的关系，存在A上的另一个关系R’，满足：

1. R’ 是自反的（对称的、传递的）
2. 对任何自反的（对称的、传递的）关系R”，如果R $\subseteq$ R”，就有R’ $\subseteq$ R”，则称R’ 是 R的自反闭包(reflexive closure)(对称闭包(symmetric closure)、传递闭包(transitive closure))，记为r(R),s(R),t(R)

R的性质不清楚，但是加上R’后就得到一个特殊性质的R”