关系的复合

设 A、B 和 C 是集合，且 R 是从 A 到 B 的关系，S 是从 B 到 C 的关系。 即，R 是 A × B 的子集，S 是 B × C 的子集。 那么 R 和 S 会产生从 A 到 C 的关系，表示为 R◦S，定义为

关系 R◦S 称为 R 和 S 的合成；它有时简称为 RS。

设 R 是集合 A 上的关系，即 R 是从集合 A 到自身的关系。 那么 R◦R，即 R 与自身的合成，总是可以表示的。 另外，R◦R 有时表示为 R²。 类似地，R³ = R²◦R = R◦R◦R，等等。 因此，Rⁿ 是为所有正 n 定义的。

例 1：设 X = {4, 5, 6}, Y = {a, b, c} 和 Z = {l, m, n}。 考虑从 X 到 Y 的关系 R₁ 和从 Y 到 Z 的关系 R₂。

 R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)}
 R2 = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}

求关系 (i) R₁ o R₂ (ii) R₁o R₁^-1 的合成

解决方案

(i) 合成关系 R₁ o R₂ 如图所示

R₁ o R₂ = {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}

(ii) 合成关系 R₁o R₁^-1 如图所示

R₁o R₁^-1 = {(4, 4), (5, 5), (5, 6), (6, 4), (6, 5), (4, 6), (6, 6)}

关系和矩阵的合成

还有另一种找到 R◦S 的方法。 设 M_R 和 M_S 分别表示关系 R 和 S 的矩阵表示。 那么

示例

解答：关系 R 和 S 的矩阵如图所示

(i) 要获得关系 R 和 S 的合成。首先将 M_R 与 M_S 相乘，得到矩阵 M_R x M_S，如图所示

矩阵 M_R x M_S 中的非零条目表示 RoS 中相关的元素。 所以，

因此，关系 R 和 S 的合成 R o S 是

(ii) 首先，将矩阵 M_R 与自身相乘，如图所示

因此，关系 R 和 S 的合成 R o R 是

(iii) 将矩阵 M_S 与 M_R 相乘，得到矩阵 M_S x M_R，如图所示

矩阵 M_S x M_R 中的非零条目表示 S o R 中相关的元素。

因此，关系 S 和 R 的合成 S o R 是