集合关系的构成关系的构成|离散数学

设A, B和C, 令R为从A到B的关系, 令S为从B到C的关系。即, R为A×B的子集, S为B×的子集。 C.然后R和S产生一个由R?S表示并由下式定义的从A到C的关系：

a (R?S)c if for some b ∈ B we have aRb and bSc. That is, R ? S = {(a, c)| there exists b ∈ B for which (a, b) ∈ R and (b, c) ∈ S}

关系R?S已知R和S的组成；它有时简单地用RS表示。
令R是集合A上的关系, 即R是从集合A到自身的关系。然后总是表示R?R, 即R本身的组成。同样, R？R有时用R2表示。同样, R3 =R2?R=R?R?R, 依此类推。因此, 为所有正n定义了Rn。
示例1：设X = {4, 5, 6}, Y = {a, b, c}和Z = {l, m, n}。考虑从X到Y的关系R1和从Y到Z的关系R2。

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）R1 o R2（ii）R1o R1-1的组成
解：
（i）组成关系R1到R2如图所示：

R1 o R2 = {（4, l）, （4, n）, （4, m）, （5, l）, （5, m）, （5, n）, （6, l）, （6, m）, （6, n）}
（ii）组成关系R1o R1-1如图所示：

R1o R1-1 = {（4, 4）, （5, 5）, （5, 6）, （6, 4）, （6, 5）, （4, 6）, （6, 6）}
关系和矩阵的组成找到R?S的另一种方法。令MR和MS分别表示关系R和S的矩阵表示。
例

Let P = {2, 3, 4, 5}. Consider the relation R and S on P defined byR = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}.Find the matrices of the above relations.Use matrices to find the following composition of the relation R and S.(i)RoS (ii)RoR (iii)SoR

解决方案：关系R和S的矩阵如图所示：

（i）获得关系R和S的组成。首先将MR与MS相乘, 得到矩阵MR x MS, 如图所示：
矩阵MR x MS中的非零条目告诉RoS中相关的元素。所以,

因此, 关系R和S的成分R o S为