Relációk kompozíciója

Két reláció kompozíciója egy új relációt hoz létre úgy, hogy az első relációt 'összekapcsoljuk' a másodikkal. Ha az első relációban egy elem kapcsolódik egy köztes elemhez, és a második relációban ez a köztes elem kapcsolódik egy harmadikhoz, akkor a kompozícióban az első elem kapcsolódik a harmadikhoz.

Formális definíció

Magyarul: először az S relációt alkalmazzuk, majd az R relációt. Ha S összekapcsolja a-t b-vel, és R összekapcsolja b-t c-vel, akkor a kompozíció (R ∘ S) összekapcsolja a-t c-vel.

Példa a kompozícióra

Tegyük fel, hogy van két reláció:

• S = „testvére” reláció emberek között.
• R = „gyermeke” reláció emberek között.

Az R ∘ S kompozíció azt adja meg, hogy ki a testvérem gyermeke – vagyis az unokaöcsém/unokahúgom.

Tulajdonságok

• A kompozíció nem kommutatív: általában R ∘ S ≠ S ∘ R.
• A kompozíció asszociatív: (R ∘ S) ∘ T = R ∘ (S ∘ T).
• Még ha R és S relációk tranzitívek is, a kompozíciójuk nem feltétlenül lesz tranzitív.

További példa

Legyen S = { (1,2), (2,3) } és R = { (2,4), (3,5) }. Ekkor a kompozíció R ∘ S = { (1,4), (2,5) }, mert 1 kapcsolódik 2-höz S-ben, 2 kapcsolódik 4-hez R-ben, így 1 kapcsolódik 4-hez a kompozícióban; hasonlóan 2 kapcsolódik 3-hoz, és 3 kapcsolódik 5-höz, így (2,5) is benne van.

Összefoglalás

A relációk kompozíciója lehetővé teszi, hogy két különböző kapcsolatot egymás után alkalmazzunk, és így új kapcsolatot hozzunk létre. Ez hasznos eszköz a matematikában és az informatikában, például gráfok, adatbázisok és függvények elemzésénél.

Gyakorló feladat