Kempelen Farkas Hallgatói Információs Központ

A reflexív, szimmetrikus és tranzitív crisp relációkat – mint a 4.5. ábrán is láttuk – ekvivalenciarelációknak nevezzük. Az ekvivalenciarelációk az alaphalmazt ún. ekvivalenciaosztályokra particionálják, ugyanis minden X -beli x elemhez hozzárendelhető egy A x halmaz, amelybe az x -szel relációban lévő elemek tartoznak:

A x = { y ∣ 〈 x , y 〉 ∈ R ( X , X ) } .

A reflexivitás miatt x maga is eleme az A x halmaznak, továbbá a szimmetria és a tranzitivitás következményeként A x minden eleme relációban van a halmaz többi elemével is. Az is megállapítható, hogy A x -en kívüli elemmel egy A x -beli elem sincs relációban. Az A x halmaz az R reláció egy ekvivalenciaosztálya, melynek reprezentáns eleme x . Mivel minden X -beli elem pontosan egy ekvivalenciaosztályba tartozik, ezért ezek az osztályok a reláció alaphalmazának egy particionálását adják (melyet X ∕ R -rel jelölünk).

A reflexív, szimmetrikus és tranzitív relációkat a fuzzy kontextusban fuzzy ekvivalenciarelációnak vagy hasonlósági relációnak hívjuk. A crisp relációktól való megkülönböztetés végett a könyvben többnyire az utóbbi elnevezést használjuk.

A hasonlósági relációkat kétfajta megközelítés szerint lehet interpretálni. Az első alapján az elemeket crisp halmazokba csoportosíthatjuk úgy, hogy a halmazon belüli elemek közti reláció értéke egy adott küszöbértéket haladjon meg. Természetesen ha ez az érték 1 , akkor crisp ekvivalenciarelációt kapunk.

Második lehetőség, hogy az X elemein egy kitüntetett x ∈ X elemhez való hasonlóságot definiálunk. Ekkor minden x ∈ X elemhez rendelhető egy fuzzy halmazként definiálható hasonlósági osztály, ahol az elemhez való hasonlóság mértékét a tagságifüggvény-érték adja meg. Ez a definíció is az ekvivalenciareláció általánosításának tekinthető, hiszen ha egy osztályban minden elem 1 mértékben hasonló x -hez, míg más elemhez 0 mértékben, akkor egyben egy crisp ekvivaleciaosztályt kapunk.

A felbontási elv szerint (lásd 8.4.1. pont), minden fuzzy reláció α -vágatok uniójára dekomponálható:

R = ⋃ α ∈ ( 0,1 ] α ⋅ R α .

Az olvasóra hagyjuk annak az egyszerű állításnak a belátását, hogy ha R egy hasonlósági reláció, akkor R minden egyes α -vágata ( α ∈ ( 0,1 ] ) egy crisp ekvivalenciarelációt ad ( R α ). Minden α értékhez tartozó ekvivalenciareláció particionálást definiál X -en. Jelöljük π ( R α ) -val az R α ekvivalenciarelációhoz tartozó particionálást. Két elem nyilván akkor és csak akkor tartozik azonos partícióba, ha R ( x , y ) ≥ α . Minden hasonlósági relációhoz hozzárendelhető az általa indukált α -particionálások halmaza:

Π ( R ) = { π ( R α ) ∣ α ∈ ( 0,1 ] } .

melyek egymásba ágyazottak abban az értelemben, hogy π ( R α ) a π ( R β ) particionálás finomítása, ha α ≥ β .

A hasonlósági osztályokat a fentebb leírt módon kaphatjuk meg a hasonlósági relációkból. Egy R ( X , X ) reláció minden x eleméhez rendelhető egy az alaphalmazon értelmezett fuzzy halmaz, és minden y ∈ X -re, a tagsági függvény értéke R ( x , y ) . Leszámítva a crisp ekvivalenciaosztály szélsőséges esetét, a hasonlósági osztályok fuzzyk, és így nem diszjunktak.

A hasonlósági osztályokat rendszerint tagsági mátrixokkal ábrázoljuk. Ha adott egy hasonlósági reláció, akkor egy tetszőleges elem hasonlósági mátrixa az eredeti mátrixnak az a sora, mely az adott elemhez tartozik.

Azokat a relációkat, melyek csupán reflexívek és szimmetrikusak (de nem tranzitívak), kompatibilitási vagy toleranciarelációnak, néha szomszédsági relációnak nevezzük.

Fontos fogalom a kompatibilitási relációkkal kapcsolatban a kompatibilitási osztály. Legyen adott egy R ( X , X ) tolerancia reláció. Ekkor az A ⊂ X halmazt, melynek minden x , y elemére 〈 x , y 〉 ∈ R (tehát amelyen belül érvényes a tranzitivitás), kompatibilitási osztálynak nevezzük. Az ún. legnagyobb kompatibilitási osztály olyan tulajdonsággal is rendelkezik, hogy nem részhalmaza egyetlen más kompatibilitási osztálynak sem. Az R reláció legnagyobb kompatibilitási osztályainak családja az X ( R által indukált) teljes lefedése.

4.6. ábra - Kompatibilitási reláció ábrázolása reflexív irányítatlan gráffal (a hurokélek elhagyásával)

Ha R fuzzy reláció, akkor a kompatibilitási osztályokat általánosabban, tetszőleges α tagsági értékre definiálhatjuk. Így az α -kompatibilis osztály, egy olyan részhalmaza a relációnak, amelyre

A ( α ) = { x , y ∈ A ∣ R ( x , y ) ≥ α }

fennáll. Hasonlóképpen az előző bekezdésben ismertetett crisp megfelelők értelemszerű általánosításaiként adhatjuk meg a legnagyobb α -kompatibilitási osztály és a teljes α -lefedés fogalmait.

A kompatibilitási relációkat általában reflexív irányítatlan gráfokkal ábrázoljuk. A reflexivitás miatt minden csúcshoz tartozik egy hurokél (olyan él, mely a csúcsot önmagával köti össze), amit a gráf megjelenítésénél az egyszerűség és átláthatóság kedvéért elhagyunk ugyan, de úgy tekintjük, mintha ott lenne. Mivel a szimmetrikus reláció a kapcsolat meglétét mindkét irányban garantálja, a csúcsok közti élek irányítatlanok. Az élek mellett feltüntetjük a megfelelő tagsági értékeket (lásd 4.6. ábra).

Példaként tekintsük az alábbi relációt:

R ¯ ¯ = 1 0,6 0,4 0 0 0 0 0 0,6 1 0,6 0 0 0 0,8 0,3 0,4 0,6 1 0 0 0 0,4 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0,3 0 0 0 0 0 0 0,3 1 0 0 0 0,8 0,4 0 0 0 1 0,4 0 0,3 0 0 0 0 0,4 1 ,

melyet a 4.6. ábrán is megfigyelhetünk. Ez kompatibilitási reláció, mivel a mátrix szimmetrikus és minden főátlójában szereplő érték 1 . A teljes α -lefedés a lényeges α />/ 0 -szintekre Λ R = { 0 , 0,3 , 0,4 , 0,6 , 0,8 , 1 } , amint azt a 4.7. ábra mutatja meg.

4.7. ábra - Kompatibilitási reláció teljes α -lefedése

Általában valamely kompatibilitási reláció α -lefedése nem képezi az alaphalmaz particionálását, noha ez természetesen előfordulhat. Ilyen például a 4.7. ábra relációja a 0,8 és 1 értékekre. Mivel éppen a tranzitivitás hiánya az, ami a kompatibilitási és hasonlósági relációkat megkülönbözteti egymástól, bármely kompatibilitási reláció tranzitív lezártja hasonlósági reláció lesz.

A harmadik jelentős bináris relációtípus, mellyel kiemelten foglalkozunk, a rendezések csoportja.

A reflexív, antiszimmetrikus és tranzitív crisp relációkat részben rendezésnek (vagy parciális rendezésnek) hívjuk. Jelöljük a részben rendezést ≺ jellel, azaz x ≺ y azt jelenti, hogy x megelőzi y -t és 〈 x , y 〉 ∈ R . Az R − 1 ( X , X ) inverz részben rendezési relációt a ≻ szimbólummal jelöljük, eszerint y ≻ x azt jelenti, hogy y az x rákövetkezője. Ha nincs olyan z elem, hogy x ≺ z és z ≺ y , de x ≺ y teljesül, akkor x az y közvetlen megelőzője, analóg módon, ha nincs olyan z , hogy y ≻ z és z ≻ x , de y ≻ x , akkor y az x közvetlen rákövetkezője.

Vegyük észre, hogy a részben rendezés tulajdonságai nem garantálják, hogy bármely két elemre az x ≺ y és y ≺ x reláció közül valamelyik is fennáll. Vannak olyan párok, melyben az x sem nem megelőzője, sem nem rákövetkezője az y -nak; az ilyeneket nem összehasonlítható pároknak nevezzük.

A parciális rendezéssel összefüggésben a következő alapvető fogalmakat vezetjük még be.

Figyeljük meg, hogy valamely részben rendezésnek legfeljebb egy első, illetve utolsó eleme lehet, de minimális vagy maximális eleme több is. Ha létezik első/utolsó elem, akkor csak egy minimális/maximális elem van, és az megegyezik az első/utolsó elemmel. Valamely parciális rendezés első, illetve utolsó eleme az inverz relációnak rendre az utolsó, illetve első eleme.

Legyen adott az X halmaz és ezen egy R részben rendezés, A pedig legyen X részhalmaza: A ⊂ X . Ha x ∈ X és x ≺ y minden y ∈ A esetén, akkor x az A halmaz X -en való parciális rendezés szerinti alsó korlátja. Ha x ∈ X és y ≺ x minden y ∈ A esetén, akkor x az A halmaz X -en való parciális rendezés szerinti felső korlátja. Ha egy alsó korlát minden alsó korlátnak a rákövetkezője, akkor legnagyobb alsó korlátnak nevezzük, hasonlóan, ha egy felső korlát az összes többi felső korlátnak megelőzője, akkor legkisebb felső korlátnak hívjuk.

Az olyan rendezést, mely X minden kételemű részhalmazához tartalmaz legnagyobb alsó korlátot és legkisebb felső korlátot, hálónak nevezzük.

A (crisp) rendezésekkel kapcsolatos fogalmak ismertetése után térjünk rá ezek fuzzy megfelelőire. A reflexív, antiszimmetrikus és (valamilyen értelemben) tranzitív fuzzy relációkat fuzzy részben rendezésnek nevezzük. Tetszőleges max-min tranzitivitással rendelkező fuzzy részben rendezés felbontható crisp rendezésekre ugyanolyan módon, ahogy azt a hasonlósági relációknál láttuk: a reláció minden jelentős α -vágataként képzett crisp rendezés létrehozásával, melyek a fuzzy rendezés fokozatos finomítását adják.

Bármely fuzzy rendezés esetén az alaphalmaz minden x eleméhez két fuzzy halmazt rendelhetünk. Az elsőt x domináló osztályának nevezzük, melyet R ≥ [ x ] szimbólummal jelölünk, s melynek értéke

R ≥ [ x ] = R ( x , y ) , y ∈ X .

Ebben a halmazban tehát a rendezés szerint megadott mértékben szerepelnek az x -et domináló elemek.

A második fuzzy halmaz az x dominált osztálya, melyet a R ≤ [ x ] szimbólum jelöl

R ≤ [ x ] = R ( y , x ) , y ∈ X .

Ebben a halmazban a relációban megadott tagságifüggvény-értékkel szerepelnek az x által dominált elemek.

Az x ∈ X elem nemdominált, illetve nemdomináló akkor és csak akkor, ha rendre R ( x , y ) = 0 , illetve R ( y , x ) = 0 minden y ∈ X -re.

Legyen X az R reláció alaphalmaza, s A ennek részhalmaza. Ekkor az A halmaz fuzzy felső korlátját az

U ( R , A ) = ⋂ x ∈ A R ≥ [ x ]

összefüggéssel definiálhatjuk, ahol ∩ egy megfelelő fuzzy metszetet (t-normát) jelöl. Ha létezik az A halmaznak legkisebb felső korlátja, akkor az az U ( R , A ) halmaz azon (egyetlen) eleme melyre,

U ( R , A ) ( x ) />/ 0 és R ( x , y ) />/ 0

teljesül az U ( R , A ) tartójának minden y elemére.

Legyen az R fuzzy részben rendezés az X = { a , b , c , d , e , f } alaphalmazon az alábbi tagsági mátrixszal megadva:

R ¯ ¯ = 1 0 0 0 0 0 0,7 1 0 0 0 0 1 0,9 1 0,2 0,7 0 0,8 0,8 0 1 0,5 0 0,9 0,8 0 0 1 0 1 1 0,1 0,2 0,9 1 .

Az egyes elemek domináló osztályát a mátrixnak az adott elemhez tartozó sora adja. A mátrix oszlopai az elemek dominált osztályát határozzák meg. A példában szereplő mátrixban a nemdominált, f pedig nemdomináló elem. Az A = { c , b } részhalmaz felső korlátja a c és b elemek domináló halmazainak metszeteként állítható elő:

U ( R , { c , b } ) = 0,7 ∕ a + 0,9 ∕ b

Jelen esetben a ZADEH-féle metszetet alkalmaztuk. Az A h almaz legkisebb felső korlátja az a elem. A 4.8. ábrán az egyes α -vágatok által képzett crisp rendezéseket mutatjuk be. Megfigyelhető, hogy α növelésével a rendezés egyre gyengébb lesz.

4.8. ábra - Fuzzy részbenrendezés α -vágatai

A fuzzy relációk, valamint az e szakaszban tárgyalt hasonlósági, kompatibilitási és fuzzy rendezési relációk fogalmát elsőként ZADEH vezette be [156]. A bináris relációkat a fuzzy elméletről megjelent legelső monográfiában KAUFMANN tanulmányozta részletesen [57].