Let R $\subseteq$ A $\times$ B, S $\subseteq$ B $\times$ C, be two relations. Then, composition of the relations R and S denoted by SoR $\subseteq$ A $\times$ C and is defined by (a, c) $\in$ SoR iff $\exists$b $\in$ B s.t.
(a, b) $\in$ R, (b, c) $in$ S
e.g., Let A = {1, 2, 3}, B = {a, b, c, d}, C = {$\alpha$, $\beta$, $\gamma$}
R $\subseteq$ (A $\times$ B) = {(1, a), (1, c), (2, d)}
S $\subseteq$ (B $\times$ C) = {(a, $\alpha$), (c, $\gamma$), (d, $\beta$)}
Then, SoR $\subseteq$ (A $\times$ C) = {(1, $\alpha$), (1, $\gamma$), (2, $\beta$)}
Note
- One should be careful in computing the relation RoS. Actually, SoR starts with R and RoS starts with S.
- In general, SoR $\neq$ RoS
- $(SoR)^{-1}=R^{-1}oS^{-1}$, known as reversal rule.
Simple Problem 1
If R is a relation from a set A to the set B and S is a relation from B to C, then the relation SoR
(a) is from C to A
(b) is from A to C
(c) does not exist
(d) None of these
If R is a relation from a set A to the set B and S is a relation from B to C, then the relation SoR
(a) is from C to A
(b) is from A to C
(c) does not exist
(d) None of these
Answer:
Given, R $\subseteq$ (A $\times$ B) and S $\subseteq$ (B $\times$ C)
We, have
SoR $\subseteq$ (A $\times$ C)
So, SoR $\subseteq$ (A $\times$ B)
Simple Problem 2
Let a relation R be defined by
R = {(4, 5), (1, 4), (4, 6), (7, 6), (3, 7)}. The relation $RoR^{-1}$ is given by
(a) {(1, 1), (4, 4), (7, 4), (4, 7), (7, 7)}
(b) {(1, 1), (4, 4), (4, 7), (7, 4), (7, 7), (3, 3)}
(c) {(1, 5), (1, 6), (3, 6)}
(d) None of the above
(a) {(1, 1), (4, 4), (7, 4), (4, 7), (7, 7)}
(b) {(1, 1), (4, 4), (4, 7), (7, 4), (7, 7), (3, 3)}
(c) {(1, 5), (1, 6), (3, 6)}
(d) None of the above
Answer: (b)
Given R = {(4, 5), (1, 4), (4, 6), (7, 6), (3, 7)}
So, $R^{-1}$ = {(5, 4), (4, 1), (6, 4), (6, 7), (7, 3)}
⇒ $R^{-1}$oR= {(4, 4), (1, 1), (4, 7), (7, 4), (7, 7), (3, 3)}
Contents:
Post a Comment for "Composition of Relations"