复合（关系）

复合
术语名称	复合
英语名称	composition

关系的复合(composition of relations)指两个或多个关系依次首尾相接构成的关系。

定义

复合
运算名称	复合
运算符号	[math]\displaystyle{ \circ }[/math]
Latex	\circ
运算对象	关系
运算元数	2
运算结果	关系
定义域	[math]\displaystyle{ \mathcal{P}(X \times Y) \times \mathcal{P}(Y \times Z) }[/math]
陪域	[math]\displaystyle{ \mathcal{P}(X \times Z) }[/math]

对集合 [math]\displaystyle{ X }[/math] 到 [math]\displaystyle{ Y }[/math] 的关系 [math]\displaystyle{ R }[/math] 、 [math]\displaystyle{ Y }[/math] 到 [math]\displaystyle{ Z }[/math] 的关系 [math]\displaystyle{ S }[/math] ， 记 [math]\displaystyle{ RS = \left\{ (x,z) \mid \exists y ((x,y)\in R \land (y,z)\in S) \right\} = \left\{(x,z)\mid\exists y (x R y \land y S z) \right\} }[/math] ，称为 [math]\displaystyle{ S }[/math] 与 [math]\displaystyle{ R }[/math] 的复合(composition)，记作 [math]\displaystyle{ S\circ R }[/math] ，也称为 [math]\displaystyle{ R }[/math] 与 [math]\displaystyle{ S }[/math] 的逆序复合。

其他记法

需要注意，这一一运算有大量不一致的其他记法，需注意顺序对应关系。

• 左复合（上述记法）：记作 [math]\displaystyle{ S\circ R }[/math] 。其中后进行的关系被复合在左侧。
• 右复合：记作 [math]\displaystyle{ R\circ S }[/math] 。其中后进行的关系被复合在右侧，
• 记作 [math]\displaystyle{ RS }[/math] 。后进行的关系在右侧。
• 顺序复合：使用 [math]\displaystyle{ R ; S }[/math] 来区分右复合记号。

国内一般函数总是使用右复合，而关系左右复合都有人使用，但现行教材用左复合，及定义中列出的较多。 由于左右不统一会产生对记号 [math]\displaystyle{ \circ }[/math] 的额外理解成本， 不指出时本 wiki 使用左复合以减少混淆。

∘
字符	∘
Unicode码位	U+2218 Ring Operator

性质

• 表示
  • 两个关系的复合的关系矩阵是两个关系矩阵作为布尔矩阵的积，其中布尔矩阵乘法中元素的加法和乘法对应为逻辑或（逻辑加法）和逻辑与（逻辑乘法）。
• 结合律： [math]\displaystyle{ T \circ (S \circ R) = (T \circ S) \circ R }[/math]
• 对齐次关系：
  • [math]\displaystyle{ X }[/math] 上的关系关于关系的符合构成幺半群
  • 同一关系的复合定义为关系的幂。
• 特殊值
  • [math]\displaystyle{ R \circ \varnothing = \varnothing }[/math]， [math]\displaystyle{ \varnothing \circ R = \varnothing }[/math] （如果两个关系前后域满足复合条件）
    • 空关系是复合运算的零元。
  • [math]\displaystyle{ R \circ I = R }[/math]，[math]\displaystyle{ I \circ R = R }[/math]（如果两个关系前后域满足复合条件）
    • 恒等关系是复合运算的幺元。
• 分配律
  • 复合对并满足分配律： [math]\displaystyle{ (R \cup S) \circ T = (R \circ T) \cup (S \circ T) }[/math] ， [math]\displaystyle{ R \circ (S \cup T) = (R \circ S) \cup (R \circ T) }[/math]
  • 复合对交的关系满足： [math]\displaystyle{ (R \cap S) \circ T \subseteq (R \circ T) \cap (S \circ T) }[/math] 、 [math]\displaystyle{ R \circ (S \cap T) \subseteq (R \circ S) \cap (R \circ T) }[/math]
• 与逆关系
  • [math]\displaystyle{ (S \circ R)^{-1} = R^{-1} \circ S^{-1} }[/math]
    • 若 [math]\displaystyle{ R }[/math] 和 [math]\displaystyle{ S }[/math] 都是对称关系，则 [math]\displaystyle{ S \circ R }[/math] 是对称关系当且仅当 [math]\displaystyle{ R \circ S = S \circ R }[/math] 。
    • 若 [math]\displaystyle{ R }[/math] 和 [math]\displaystyle{ S }[/math] 都是等价关系且 [math]\displaystyle{ R \circ S = S \circ R }[/math]，则 [math]\displaystyle{ R \circ S }[/math] 也是等价关系。
• 若 [math]\displaystyle{ R_1 \subseteq R_2, S_1 \subseteq S_2 }[/math] ，则 [math]\displaystyle{ R_1 \circ S_1 \subseteq R_2 \circ S_2 }[/math] 。
• 如果两个关系都是左全、右全、左唯一或右唯一的，则复合后的关系也具有对应性质。

关系
定义属性	前域、后域、定义域 [math]\displaystyle{ \operatorname{dom} }[/math]、值域 [math]\displaystyle{ \operatorname{ran} }[/math]、域 [math]\displaystyle{ \operatorname{fld} }[/math]
特殊关系	空关系 [math]\displaystyle{ \varnothing }[/math]、恒等关系 [math]\displaystyle{ I }[/math]、全关系 [math]\displaystyle{ A\times B }[/math]
二元齐次关系类型	自反、反自反、对称、反对称、传递
运算	集合运算	交 [math]\displaystyle{ \cap }[/math]、并 [math]\displaystyle{ \cup }[/math]、补 [math]\displaystyle{ \bar{\bullet} }[/math]、差 [math]\displaystyle{ \setminus }[/math]
	类映射运算	转置/逆 [math]\displaystyle{ \bullet^\mathrm{T}/\bullet^{-1} }[/math]、复合 [math]\displaystyle{ \circ }[/math]（幂 [math]\displaystyle{ \bullet^n }[/math]）、限制 [math]\displaystyle{ \bullet_{|\bullet} }[/math]
	闭包运算	自反 [math]\displaystyle{ \operatorname{r}() }[/math]/[math]\displaystyle{ \bullet^= }[/math]、对称 [math]\displaystyle{ \operatorname{s}() }[/math]/[math]\displaystyle{ \bullet^\sim }[/math]、传递 [math]\displaystyle{ \operatorname{t}() }[/math]/[math]\displaystyle{ \bullet^+ }[/math]、自反传递 [math]\displaystyle{ \bullet^* }[/math]、等价 [math]\displaystyle{ \bullet^\equiv }[/math]

参考资料

1. https://en.wikipedia.org/wiki/Composition_of_relations