Relációk lezárásai

Egy reláció lezárása azt jelenti, hogy a relációt kibővítjük a lehető legkisebb mértékben ahhoz, hogy egy adott tulajdonságnak megfeleljen. Leggyakrabban reflexív, szimmetrikus vagy tranzitív lezárásról beszélünk.

Reflexív lezárás

A reflexív lezárásban minden elemhez hozzáadjuk az (a,a) párokat, hogy a reláció reflexív legyen.

Például ha R = { (1,2) } és A = {1,2}, akkor R_ref = { (1,2), (1,1), (2,2) }.

Szimmetrikus lezárás

A szimmetrikus lezárásban minden párhoz hozzáadjuk a fordított párt is, hogy a reláció szimmetrikus legyen.

Például ha R = { (1,2) }, akkor R_sym = { (1,2), (2,1) }.

Tranzitív lezárás

A tranzitív lezárásban minden olyan párt hozzáadunk, amely a tranzitivitás miatt következik. Ez a legkisebb tranzitív reláció, amely tartalmazza az eredeti relációt.

Másképp: ha (a,b) ∈ R és (b,c) ∈ R, akkor (a,c) is benne lesz a tranzitív lezárásban. Például ha R = { (1,2), (2,3) }, akkor R_trans = { (1,2), (2,3), (1,3) }.

Példa a három lezárás összehasonlítására

Legyen A = {1,2,3} és R = { (1,2), (2,3) }.

• Reflexív lezárás: { (1,2), (2,3), (1,1), (2,2), (3,3) }
• Szimmetrikus lezárás: { (1,2), (2,1), (2,3), (3,2) }
• Tranzitív lezárás: { (1,2), (2,3), (1,3) }

Tulajdonságok

• A lezárás mindig a legkisebb reláció, amely kielégíti az adott tulajdonságot.
• A reflexív lezárás mindig tartalmazza az összes (a,a) párt.
• A szimmetrikus lezárás mindig tartalmazza az összes fordított párt.
• A tranzitív lezárás tartalmaz minden olyan kapcsolatot, amely köztes elemek láncolatából következik.

Összefoglalás

A relációk lezárásai lehetővé teszik, hogy egy relációt kiegészítsünk a szükséges párokkal, így reflexívvé, szimmetrikussá vagy tranzitívvá tegyük. Ez kulcsfontosságú a matematikában, mert sok bizonyítás és algoritmus alapja ezekre épül.

Gyakorló feladat