Fie A, B și C mulțimi și fie R o relație de la A la B și fie S o relație de la B la C. Adică, R este o submulțime a lui A × B și S este o submulțime a lui B × C. Atunci R și S dau naștere unei relații de la A la C indicată prin R◦S și definită prin:

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

Relația R◦S este cunoscută compoziția lui R și S; este uneori notat simplu prin RS.

Fie R o relație pe o mulțime A, adică R este o relație de la o mulțime A la sine. Atunci R◦R, compoziția lui R cu sine, este întotdeauna reprezentată. De asemenea, R◦R este uneori notat cu R². În mod similar, R³= R²◦R = R◦R◦R și așa mai departe. Astfel Rⁿeste definit pentru toate n pozitive.

Exemplul 1: Fie X = {4, 5, 6}, Y = {a, b, c} și Z = {l, m, n}. Luați în considerare relația R₁de la X la Y și R₂de la Y la Z.

 R<sub>1</sub> = {(4, a), (4, b), (5, c), (6, a), (6, c)} R<sub>2</sub> = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)} 

Găsiți compoziția relației (i) R₁R₂ (ii) R₁R₁^-1

Soluţie:

(i) Relația de compoziție R₁R₂așa cum se arată în fig:

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

(ii) Relația de compoziție R₁R₁^-1așa cum se arată în fig:

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

Compoziția relațiilor și a matricilor

Există un alt mod de a găsi R◦S. Fie M_Rsi m_Sse notează respectiv reprezentările matriceale ale relaţiilor R şi S. Atunci

Exemplu

 Let P = {2, 3, 4, 5}. Consider the relation R and S on P defined by R = {(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 

Soluţie: Matricele relației R și S sunt prezentate în fig:

(i) Pentru a obține compoziția relației R și S. Mai întâi înmulțiți M_Rcu m_Spentru a obține matricea M_Rx M_Sașa cum se arată în fig:

Intrările diferite de zero din matricea M_Rx M_Sspune elementele legate în RoS. Asa de,

Prin urmare compoziția R o S a relației R și S este

 R o S = {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (4, 2), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}. 

(ii) În primul rând, înmulțiți matricea M_Rde la sine, așa cum se arată în fig

Prin urmare compoziția R o R a relației R și S este

 R o R = {(2, 2), (3, 2), (3, 3), (3, 4), (4, 2), (4, 5), (5, 2), (5, 3), (5, 5)} 

(iii) Înmulțiți matricea M_Scu m_Rpentru a obține matricea M_Sx M_Rașa cum se arată în fig:

Intrările diferite de zero din matricea M_Sx M_Rspune elementele legate în S o R.

Prin urmare compoziția S o R a relației S și R este

 S o R = {(2, 4) , (2, 5), (3, 3), (3, 4), (3, 5), (4, 2), (4, 4), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}.