Relációk halmazon, relációs gráfok, relációk tulajdonságai. Bináris relációk – MT1102: Lineáris algebra (Bevezetés a matematikába) – Üzleti számítástechnika. Részleges rend kapcsolat

A kapcsolatok tulajdonságai:

1) reflexivitás;

2) szimmetria;

3) tranzitivitás.

4) összekapcsoltság.

Hozzáállás R egy készleten x hívott fényvisszaverő, ha a halmaz egyes elemeiről x mondhatjuk, hogy kapcsolatban él R Magammal: xRx. Ha a reláció reflexív, akkor a gráf minden csúcsában van egy hurok. Ezzel szemben az a gráf, amelynek minden csúcsa tartalmaz egy hurkot, reflexív relációs gráf.

A reflexív összefüggésekre példa a természetes számok halmazán a „többszörös” reláció (minden szám önmaga többszöröse), a háromszögek hasonlóságának relációja (minden háromszög önmagához hasonló), valamint az „egyenlőség” relációja ( minden szám egyenlő önmagával) stb.

Vannak olyan relációk, amelyek nem rendelkeznek a reflexivitás tulajdonságával, például a szegmensek merőlegességének relációja: ab, ba(nincs egyetlen szegmens sem, amelyről azt lehetne mondani, hogy merőleges lenne önmagára) . Ezért ennek a kapcsolatnak a grafikonjában egyetlen hurok sincs.

A „hosszabb” reláció szegmenseknél, „2-vel több” természetes számoknál stb. nem rendelkezik reflexiós tulajdonsággal.

Hozzáállás R egy készleten x hívott tükröződésmentes, ha a halmaz bármely elemére x mindig hamis xRx: .

Vannak kapcsolatok, amelyek sem nem reflexívek, sem nem antireflexívek. Ilyen kapcsolatra példa a kapcsolati „pont x pontra szimmetrikusan nál nél viszonylag egyenes l", amely a sík pontjainak halmazán van meghatározva. Valójában egy egyenes minden pontja l szimmetrikusak önmagukra, és pontok, amelyek nem fekszenek egyenes vonalon l,önmagukban nem szimmetrikusak.

Hozzáállás R egy készleten x hívott szimmetrikus, ha a feltétel teljesül: attól, hogy az elem x az elemhez kapcsolódik y, ebből az következik, hogy az elem y kapcsolatban van R elemmel X:xRyyRx.

A szimmetrikus relációgráfnak a következő jellemzője van: minden innen érkező nyíllal együtt x Nak nek y, a grafikon egy innen induló nyilat tartalmaz y Nak nek x(35. ábra).

Példák a szimmetrikus összefüggésekre: a szegmensek „párhuzamosságának” viszonya, a szegmensek „merőlegességének” viszonya, a szakaszok „egyenlőségének” viszonya, a háromszögek hasonlóságának viszonya, a szegmensek „egyenlőségének” viszonya. törtek stb.

Vannak kapcsolatok, amelyek nem rendelkeznek a szimmetria tulajdonságával.

Valóban, ha a szegmens x hosszabb, mint a szegmens nál nél, majd a szegmens nál nél nem lehet hosszabb, mint a szegmens x. Ennek az összefüggésnek a gráfjában van egy sajátosság: a csúcsokat összekötő nyíl csak egy irányba mutat.

Hozzáállás R hívott antiszimmetrikus, ha bármely elemre xÉs y az igazságtól xRy hamisnak kell lennie yRx: : xRyyRx.

A „hosszabb” reláción kívül számos szegmensen más antiszimmetrikus relációk is léteznek. Például a „nagyobb, mint” reláció a számokhoz (ha x több nál nél, Azt nál nél nem lehet több x), a „további információ” attitűd stb.

Vannak relációk, amelyeknek nincs sem a szimmetria, sem az antiszimmetria tulajdonsága.

R reláció egy halmazon x hívott tranzitív, ha attól az elemtől x kapcsolatban van R elemmel y,és elem y kapcsolatban van R elemmel z, ebből az következik, hogy az elem x kapcsolatban van R elemmel z: xRyÉs yRzxRz.

Tranzitív relációs grafikon, amelyből minden nyílpár származik x Nak nek yés től y Nak nek z, innen induló nyilat tartalmaz x Nak nek z.

A szegmensek halmazán a „hosszabb” relációnak is megvan a tranzitivitási tulajdonsága: ha a szegmens A hosszabb, mint a szegmens b, vonalszakasz b hosszabb, mint a szegmens Val vel, majd a szegmens A hosszabb, mint a szegmens Val vel. A szegmensek halmazán az „egyenlőség” viszonyának tranzitivitása is van: (a=b, b=c)(a=c).

Vannak relációk, amelyek nem rendelkeznek a tranzitivitás tulajdonságával. Ilyen reláció például a merőlegességi reláció: ha egy szakasz A merőleges a szakaszra b, és a szegmens b merőleges a szakaszra Val vel, majd a szegmensek AÉs Val vel nem merőleges!

A relációknak van egy másik tulajdonsága is, amelyet az összetartozás tulajdonságának nevezünk, és azt a relációt, amely rendelkezik ezzel, összekapcsoltnak.

Hozzáállás R egy készleten x hívott csatlakoztatva, ha bármely elemre xÉs y ebből a halmazból teljesül a feltétel: ha xÉs y akkor sem x kapcsolatban van R elemmel y, vagy elem y kapcsolatban van R elemmel x. Szimbólumok használatával ez így írható: xyxRy vagy yRx.

Például a természetes számok „nagyobb, mint” relációjának megvan az összetartozás tulajdonsága: bármely eltérő x és y számra kijelenthető, x>y, vagy y>x.

Egy összefüggő relációs gráfban bármely két csúcsot egy nyíl köti össze. Az ellenkező állítás is igaz.

Vannak olyan kapcsolatok, amelyek nem rendelkeznek az összekapcsolódás tulajdonságával. Ilyen összefüggés például az oszthatóság relációja a természetes számok halmazán: nevezhetünk ilyen számokat x ill. y akármi is a szám x nem osztója egy számnak y, nincs szám y nem osztója egy számnak x(számok 17 És 11 , 3 És 10 stb.) .

Nézzünk néhány példát. Fellépő X=(1, 2, 4, 8, 12) a „szám” reláció adott x a szám többszöröse y" Szerkesszük meg ennek a kapcsolatnak a grafikonját, és fogalmazzuk meg tulajdonságait.

A törtek egyenlőségének relációját ekvivalenciarelációnak mondjuk.

Hozzáállás R egy készleten x hívott ekvivalencia reláció, ha egyszerre rendelkezik reflexivitás, szimmetria és tranzitivitás tulajdonságaival.

Példák az ekvivalencia relációkra: a geometriai alakzatok egyenlőségének relációi, az egyenesek párhuzamosságának relációi (feltéve, hogy az egybeeső egyeneseket párhuzamosnak tekintjük).

A „törtek egyenlőségének” fentebb tárgyalt relációjában a halmaz x három részhalmazra osztva: ( ; ; }, {; } , (). Ezek a részhalmazok nem metszik egymást, és egyesülésük egybeesik a halmazzal x, azaz a halmaznak van egy partíciója osztályokra.

Így, ha egy X halmazon ekvivalencia relációt adunk meg, akkor ennek a halmaznak egy partícióját generálja páronként diszjunkt részhalmazokra - ekvivalencia osztályokra.

Így megállapítottuk, hogy az egyenlőségi reláció a halmazon
x=( ;; ; ; ; ) megfelel ennek a halmaznak az ekvivalenciaosztályokra való felosztásának, amelyek mindegyike egymással egyenlő törtekből áll.

A halmaz osztályokba való felosztásának elve valamilyen ekvivalenciareláció segítségével a matematika egyik fontos elve. Miért?

Először is, az ekvivalens egyenértékűt, felcserélhetőt jelent. Ezért az azonos ekvivalenciaosztály elemei felcserélhetők. Így az azonos ekvivalenciaosztályba tartozó törtek (; ; ), az egyenlőség és a tört viszonya szempontjából megkülönböztethetetlenek helyettesíthető például egy másikkal . És ez a csere nem változtatja meg a számítások eredményét.

Másodszor, mivel az ekvivalenciaosztály olyan elemeket tartalmaz, amelyek valamilyen reláció szempontjából megkülönböztethetetlenek, úgy gondolják, hogy az ekvivalenciaosztályt bármely képviselője határozza meg, pl. osztály tetszőleges eleme. Így az egyenlő törtek bármely osztálya megadható az ehhez az osztályhoz tartozó bármely tört megadásával. Az egy képviselő által készített ekvivalencia osztály lehetővé teszi, hogy a halmaz összes eleme helyett egy ekvivalenciaosztályok képviselőinek halmazát tanulmányozza. Például a sokszögek halmazán definiált „ugyanolyan számú csúcsot” ekvivalenciareláció létrehozza ennek a halmaznak a felosztását háromszögek, négyszögek, ötszögek stb. osztályaira. egy bizonyos osztályban rejlő tulajdonságokat annak egyik képviselőjén veszik figyelembe.

Harmadszor, egy halmaz osztályokra particionálása ekvivalenciareláció segítségével új fogalmak bevezetésére szolgál. Például a „vonalköteg” fogalma úgy definiálható, mint ami a párhuzamos vonalaknak közös egymással.

Egy másik fontos kapcsolattípus a rendelési kapcsolat. Nézzük a problémát.A forgatáson x={3, 4, 5, 6, 7, 8, 9, 10 ) relációnak „ugyanaz a maradéka, ha osztva ezzel 3 " Ez a reláció létrehozza a halmaz egy partícióját x osztályokba: minden szám egybe fog esni, ha osztjuk vele 3 kiderül, hogy a maradék 0 (ezek számok 3, 6, 9 ). A másodikban - számok, osztva 3 a maradék az 1 (ezek számok 4, 7, 10 ). A harmadik tartalmazza mindazokat a számokat, amelyekkel osztva 3 a maradék az 2 (ezek számok 5, 8 ). Valójában a kapott halmazok nem metszik egymást, és egyesülésük egybeesik a halmazzal x. Ezért a relációnak „ugyanolyan maradványa van, ha elosztjuk vele 3 ", meghatározva a készüléken x, egy ekvivalencia reláció.

Hogy egy másik példát vegyünk, az osztályban lévő sok tanuló magasság vagy életkor szerint rendezhető. Megjegyzendő, hogy ennek az összefüggésnek az antiszimmetria és a tranzitivitás tulajdonságai vannak. Vagy mindenki ismeri a betűk sorrendjét az ábécében. Ezt a „kell” attitűd biztosítja.

Hozzáállás R egy készleten x hívott szigorú rend viszonya, ha egyszerre rendelkezik az antiszimmetria és a tranzitiv tulajdonságokkal. Például a " x< y».

Ha a reláció rendelkezik reflexivitás, antiszimmetria és tranzitivitás tulajdonságaival, akkor az is lesz nem szigorú kapcsolat. Például a " xy».

Példák a sorrendi relációkra: a „kisebb, mint” reláció természetes számok halmazán, a „rövidebb” reláció szegmensek halmazán. Ha egy rendbeli relációnak megvan az összetartozás tulajdonsága is, akkor annak mondjuk lineáris sorrendű összefüggés. Például a „kisebb, mint” reláció a természetes számok halmazán.

Egy csomó x hívott szabályos, ha rendelési viszony van megadva rajta.

Például sok X={2, 8, 12, 32 ) rendelhető a „kevesebb mint” relációval (41. ábra), vagy ezt a „többszörös” relációval (42. ábra). De mivel sorrendi relációk, a „kisebb, mint” és a „többszörös” relációk különböző módon rendezik a természetes számok halmazát. A „kevesebb, mint” reláció lehetővé teszi, hogy egy halmazból bármely két szám összehasonlítható legyen x, de a „többszörös” reláció nem rendelkezik ezzel a tulajdonsággal. Oké, pár szám. 8 És 12 nem kapcsolódik a „többszörös” relációhoz: ezt nem lehet mondani 8 többszörös 12 vagy 12 többszörös 8.

Nem szabad azt gondolni, hogy minden reláció ekvivalencia- és sorrendi viszonyokra oszlik. Rengeteg olyan reláció létezik, amelyek nem ekvivalenciarelációk, sem nem sorrendi relációk.

Descartes termék két szett x És Y készletnek nevezik mindenki rendezett párok ( x, y ) oly módon, hogy
, A
.

1. példa . Hadd .

Akkor , .

Ez nyilvánvaló
, azaz a halmazok műveletének derékszögű szorzata nem kommutatív.

Halmazok derékszögű szorzata
készletnek nevezik
minden megrendelt készlet
olyan, hogyHa
, akkor a derékszögű szorzatot jelöljük
.

Azt fogjuk mondani, hogy a levelezés adott q készletek között xÉs Y, ha rendelt hármast adnak
, Ahol
.Egy csomó x indulási területnek nevezzük, és Y– a levelezés érkezési területe q(jelöli
). Minden elem y párosítva
az elem képének nevezzük x (x– az elem prototípusa y) ehhez a levelezéshez q.

Levelezés
hívott kijelző készletek x sokban Y, ha minden elem
van egy képe
, azaz..

Kijelző
hívott funkcionális , ha minden elem
Megvan az egyetlen kép
:. Sok kép egy adott kijelzőhöz
által jelölve
:.

Ha a készlet
egybeesik a készlettel Y, akkor azt mondják
megjeleníti tovább Egy csomó Y.

Levelezés
hívott egy az egyhez (bijekció) , ha a) leképezés; b) funkcionálisan; c) megjeleníti x"fellépő Y; d) a feltételtől
kellene
.

Más szavakkal,
egy bijekció, ha minden elem
egyetlen képpel rendelkezik
, és minden elem
egyetlen prototípusa van
ezzel a kijelzővel:

(1.2)

1.2.2 Bináris reláció definíciója

Meghatározás. Sokakra mondják ezt x bináris reláció adott R, ha megadjuk a derékszögű szorzat egy részhalmazát
(azok.
).

2. példa . Hadd
Állítsuk be x a következő kapcsolatok:

– az egyenlőség viszonya;

– elsőbbségi viszony;

osztva – oszthatósági reláció.

Mindezek a kapcsolatok egy jellemző tulajdonság segítségével vannak megadva. Ennek a kapcsolatnak az elemeit az alábbiakban soroljuk fel:

Az a tény, hogy a pár ( x, y) ehhez a relációhoz tartozik R, írjuk:
vagy xRy. Például a kapcsolatra K 4. bejegyzés K a 2 azt jelenti, hogy 4 osztható 2-vel, azaz.

A meghatározás tartománya
bináris reláció R készletnek nevezik
Értéktartomány
készletnek nevezik

Igen, a kapcsolat miatt R a 2. példából a definíciós tartomány a halmaz
, és az értéktartomány a
.

1.2.3 Bináris reláció megadásának módszerei

A bináris reláció megadható egy jellemző tulajdonság megadásával vagy annak összes elemének felsorolásával. A bináris reláció meghatározásának vizuálisabb módjai a relációs gráf, relációs diagram, relációs gráf, relációs mátrix.

Menetrend a kapcsolatokat derékszögű koordinátarendszerben ábrázolják; a vízszintes tengely a definíciós tartományt, a függőleges tengely a relációs értékek halmazát jelöli; relációs elem ( x,y) a sík egy pontjának felel meg ezekkel a koordinátákkal. ábrán. Az 1.7,a) az arány grafikonját mutatja K 2. példa

Rendszer A kapcsolatokat két függőleges vonal ábrázolja, amelyek közül a bal oldali a kapcsolat definíciós tartományának, a jobb pedig a kapcsolat értékkészletének felel meg. Ha elem ( x,y) relációhoz tartozik R, majd a megfelelő pontokat
És
egyenes szakasz köti össze. ábrán. 1.7,b) az összefüggés diagramját mutatja K a 2. példából.

Grafikon kapcsolat
a következőképpen épül fel. A pontok – a halmaz elemei – tetszőleges sorrendben jelennek meg a síkon x. Pont pár xÉs nál nél akkor és csak akkor köti össze egy ív (egy vonal nyíllal), ha a ( x,y) relációhoz tartozik R. ábrán. 1.8,a) a relációs gráfot mutatja K 2. példa

Hadd
. Mátrix kapcsolat
Megvan n vonalak és n oszlopok, és annak eleme szabály határozza meg:

Az 1.8b) ábra a relációs mátrixot mutatja K 2. példa

A mindennapi életben folyamatosan foglalkoznunk kell a „kapcsolat” fogalmával. A kapcsolatok a halmaz elemei közötti kapcsolatok megadásának egyik módja.

Az unáris (egyhelyes) relációk valamilyen R attribútum jelenlétét tükrözik az M halmaz elemeiben (például „vörösnek lenni” az urnában lévő golyók halmazán).

A bináris (kéthelyű) relációk a kölcsönös definícióra szolgálnak

összefüggések, amelyek egy halmaz elempárjait jellemzik M.

Például a következő kapcsolatok definiálhatók egy emberek halmazán: „ugyanabban a városban élnek”, „ x irányításával dolgozik y", "fiúnak lenni", "idősnek lenni" stb. számkészleten: „szám a több szám b", "szám a egy szám osztója b", "számok aÉs b adja meg ugyanazt a maradékot, ha elosztja 3-mal."

A közvetlen termékben hol A- bármely egyetem sok hallgatója, B- sokféle tanult tárgy, a rendezett párok nagy részhalmaza azonosítható (a, b), amelynek tulajdona: „diák a tanulmányozza a témát b" A megszerkesztett részhalmaz azt a „tanulmányok” kapcsolatot tükrözi, amely a tanulók halmazai és az objektumok között keletkezik. A példák száma folytatható

A két objektum kapcsolata a közgazdaságtan, a földrajz, a biológia, a fizika, a nyelvészet, a matematika és más tudományok tanulmányozásának tárgya.

A két halmaz elemei közötti kapcsolatok szigorú matematikai leírásához bevezetjük a bináris reláció fogalmát.

Bináris kapcsolat az A és B halmazok közötta közvetlen szorzat R részhalmazának nevezzük. Abban az esetben, ha egyszerűen beszélhetünk hozzáállásról R tovább A.

1. példa. Írja fel a bináris relációkhoz tartozó rendezett párokat! R 1És R 2, meghatározva a készleteken AÉs : , . Részhalmaz R 1 párokból áll: . Részhalmaz.

R domain van egy halmaz az összes elemből Aúgy, hogy egyes elemek esetében . Más szóval, a definíció tartománya R a rendezett párok összes első koordinátájának halmaza R.

Többféle jelentés kapcsolat R de sok minden olyan, hogy egyesek számára . Más szóval, sok jelentéssel R a rendezett párok összes második koordinátájának halmaza R.

Az 1. példában for R 1 definíciós tartomány: , értékkészlet - . Mert R 2 definíciós tartomány: , értékkészlet: .

Sok esetben célszerű egy bináris reláció grafikus ábrázolását használni. Ez kétféleképpen történik: a síkon lévő pontok és nyilak segítségével.

Az első esetben két egymásra merőleges vonalat választunk vízszintes és függőleges tengelyként. A halmaz elemei a vízszintes tengelyen vannak ábrázolva Aés minden ponton keresztül húzz egy függőleges vonalat. A halmaz elemei a függőleges tengelyen vannak ábrázolva B, húzzon egy vízszintes vonalat minden ponton keresztül. A vízszintes és függőleges vonalak metszéspontjai egy közvetlen termék elemeit jelentik.

5. példa. Hagyjuk, .

Hadd R 1 rendezett párok felsorolásával meghatározott: . Bináris reláció R 2 egy halmazon a következő szabállyal van megadva: egy pár akkor van rendezve, ha a osztva b. Akkor R 2 párokból áll: .

Bináris relációk a 2. példából, R 1És R 2ábrán grafikusan láthatók. 6. és 7. ábra.

Rizs. 6 ábra. 7

A bináris reláció nyilakkal történő ábrázolásához a halmaz elemei a bal oldalon pontként jelennek meg A, jobb oldalon - készletek B. Minden párhoz (a, b) a bináris reláció tartalmazza R, a nyíl innen származik a Nak nek b, . Bináris reláció grafikus ábrázolása R 1 a 6. példában megadott a 8. ábrán látható.

8. ábra

A véges halmazokon lévő bináris relációk mátrixokkal adhatók meg. Tegyük fel, hogy kapunk egy bináris relációt R készletek között AÉs B. , .

A mátrix sorait a halmaz elemei számozzák A, és az oszlopok a halmaz elemei B. Mátrix cella a kereszteződésben én- oh vonalak és j Az oszlopot általában C ij jelölik, és a következőképpen kell kitölteni:

A kapott mátrix mérete .

6. példa. Legyen adott egy halmaz. Egy halmazon definiáljon egy relációt listával és mátrixszal R- "szigorúan kevesebbnek lenni."

Hozzáállás R hogyan tartalmazza egy halmaz az összes elempárt ( a, b) tól től M oly módon, hogy .

A fenti szabályok szerint összeállított relációs mátrix a következő formájú:

A bináris relációk tulajdonságai:

1. Bináris reláció R készleten hívják fényvisszaverő, ha bármely elemre a tól től M pár (a, a) tartozik R, azaz bárki számára tart a tól től M:

Kapcsolatok „ugyanabban a városban élnek”, „ugyanazon egyetemen tanulnak”, „ne legyetek többé” fényvisszaverőek.

2. Bináris relációt nevezünk tükröződésmentes, ha nem rendelkezik a reflexivitás tulajdonságával egyikre sem a:

Például a „nagyobbnak lenni”, „fiatalabbnak lenni” az antireflexiós kapcsolatok.

3. Bináris reláció R hívott szimmetrikus, ha bármely elemre aÉs b tól től M micsoda pár (a, b) tartozik R... ebből az következik, hogy a pár (b, a) tartozik R, azaz

Szimmetrikus egyenesek párhuzamossága, mert ha akkor // . Szimmetrikus kapcsolat„egyenlőnek lenni” bármely halmazon vagy „egyenlőnek lenni N-en”.

Az R reláció akkor és csak akkor szimmetrikus, ha R=R -1

4. Ha nem egyező elemekre a reláció igaz, de hamis, akkor a reláció antiszimmetrikus. Mondhatod másként is:

A kapcsolatok antiszimmetrikusak„nagyobbnak lenni”, „N-nel osztónak lenni”, „fiatalabbnak lenni”.

5. Bináris reláció R hívott tranzitív, ha annak a párnak bármely három elemére (a, b)És (időszámításunk előtt) tartozik R, ebből az következik, hogy az (a, c) pár tartozik R:

A kapcsolatok tranzitívak: „nagyobbnak lenni”, „párhuzamosnak lenni”, „egyenlőnek lenni” stb.

6. Bináris reláció R antitranzitív, ha nem rendelkezik a tranzitív tulajdonsággal.

Például egy sík egyeneseinek halmazára „merőlegesnek lenni” ( , , de ez nem igaz).

Mert Mivel a bináris reláció nem csak a párok közvetlen felsorolásával, hanem egy mátrixszal is megadható, célszerű utánajárni, hogy milyen tulajdonságok jellemzik a relációs mátrixot R, ha: 1) reflexív, 2) antireflexív, 3) szimmetrikus, 4) antiszimmetrikus, 5) tranzitív.

Hadd R A .R vagy mindkét irányban végrehajtódik, vagy egyáltalán nem. Így ha a mátrix egyet tartalmaz a metszéspontban én- oh vonalak és j- th oszlop, azaz C ij=1, akkor a kereszteződésben kell lennie j- oh vonalak és én- th oszlop, azaz C ji=1, és fordítva, ha C ji=1, akkor C ij=1. És így, a szimmetrikus relációs mátrix szimmetrikus a főátlóra.

4. R antiszimmetrikus, ha és a következő: . Ez azt jelenti, hogy a megfelelő mátrixban a sz én, j nem végezték ki C ij =C ji=1. És így, az antiszimmetrikus aránymátrixban nincsenek a főátlóra szimmetrikus egységek.

5. Meghívunk egy R bináris relációt egy nem üres A halmazon tranzitív Ha

A fenti feltételnek a mátrix bármely elemére teljesülnie kell. És fordítva, ha a mátrixban R van legalább egy elem C ij=1, amelyre ez a feltétel nem teljesül, akkor R nem tranzitív.

3. előadás.

3. pont. Kapcsolatok a halmazokkal. A bináris relációk tulajdonságai.

3.1. Bináris kapcsolatok.

Amikor két ember, például Szergej és Anna kapcsolatáról beszélnek, azt jelentik, hogy van egy bizonyos család, amelyhez tartoznak. A rendezett pár (Szergej, Anna) abban különbözik a többi rendezett emberpártól, hogy Szergej és Anna között van valamiféle kapcsolat (unokatestvér, apa stb.).

A matematikában két halmaz közvetlen szorzatának rendezett párjai között AÉs B (A´ B) a „speciális” párok azért is megkülönböztethetők, mert összetevőik között vannak olyan „rokonsági” kapcsolatok, amelyekkel mások nem rendelkeznek. Példaként tekintsük a készletet S néhány egyetem hallgatói és sok K ott tanított tanfolyamok. Közvetlen termékben S´ K kiválasztható a rendezett párok nagy részhalmaza ( s, k) az ingatlan birtokában: tanuló s tanfolyamon vesz részt k. A megszerkesztett részhalmaz a hallgatók és a kurzusok halmazai között természetesen kialakuló „...hallgat...” kapcsolatot tükrözi.

A két halmaz elemei közötti kapcsolatok szigorú matematikai leírásához bevezetjük a bináris reláció fogalmát.

Meghatározás 3.1. Bináris (vagy kettős )hozzáállás r készletek között AÉs B tetszőleges részhalmazt nevezünk A´ B, azaz

Különösen, ha A=B(azaz rÍ A 2), akkor azt mondják, hogy r egy reláció a halmazon A.

Elemek aÉs b hívják alkatrészek (vagy koordináták ) kapcsolat r.

Megjegyzés. Egyezzünk meg abban, hogy a halmazelemek közötti kapcsolatok jelölésére használjuk a görög ábécét: r, t, j, s, w stb.

Meghatározás 3.2. A meghatározás tartománya D r=( a| $ b, Mit a r b) (bal oldal). Értékek tartománya egy r bináris reláció halmazának nevezzük R r=( b| $ a, Mit a r b) (jobb oldali rész).

Példa 3. 1. Legyen két halmaz adott A=(1; 3; 5; 7) és B=(2; 4; 6). Állítsuk be a relációt a következőképpen t=(( x; y)Î A´ B | x+y=9). Ez a reláció a következő (3; 6), (5; 4) és (7; 2) párokból áll majd, amelyek t=((3; 6), (5; 4), (7;2) ) ). Ebben a példában D t=(3; 5; 7) és R t= B={2; 4; 6}.

Példa 3. 2. Az egyenlőségi reláció a valós számok halmazán az r=(( x; y) | xÉs y– valós számok és x egyenlő y). Ennek a kapcsolatnak van egy speciális jelölése: „=”. A definíciós tartomány egybeesik az értékek tartományával, és a valós számok halmaza, D r= R r.

Példa 3. 3. Hadd A– sok áru a boltban, ill B– valós számok halmaza. Aztán j=(( x; y)Î A´ B | y- ár x) – halmazok viszonya AÉs B.

Ha figyel a 3.1. példára, észre fogja venni, hogy ezt a relációt először t=(( x; y)Î A´ B | x+y=9), majd t=((3; 6), (5;4), (7;2)) alakban írjuk le. Ez azt sugallja, hogy a relációk halmazokon (vagy egy halmazon) többféleképpen megadhatók. Nézzük meg a bináris kapcsolatok meghatározásának módjait.

A kapcsolatok meghatározásának módszerei:

1) megfelelő állítmány használata;

2) rendezett párok halmaza;

3) grafikus formában: legyen AÉs B– két véges halmaz és r – egy bináris reláció közöttük. Ezen halmazok elemeit a síkon lévő pontok ábrázolják. Minden rendezett relációpárhoz r rajzol egy nyilat, amely összeköti a pár összetevőit reprezentáló pontokat. Az ilyen objektumot ún irányított gráf vagy kétjegyű mássalhangzó, a halmazok elemeit reprezentáló pontokat általában ún a gráf csúcsai.

4) mátrix formájában: legyen A={a 1, a 2, …, an) És B={b 1, b 2, …, bm), r – arány be A´ B. Mátrix ábrázolás r-t mátrixnak nevezzük M=[mij] méretben n´ m, amelyet a kapcsolatok határoznak meg

.

A mátrixreprezentáció egyébként egy reláció reprezentációja számítógépben.

Példa 3. 4. Legyen két halmaz adott A=(1; 3; 5; 7)és B=(2; 4; 6). Az összefüggést a következőképpen adjuk meg t=(( x; y) | x+y=9). Definiálja ezt a relációt rendezett párok halmazaként, egy digráfként, mátrix formájában.

Megoldás. 1) t=((3; 6), (5; 4), (7; 2)) - egy reláció definíciója rendezett párok halmazaként;

2) a megfelelő irányított gráf az ábrán látható.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,

Példa 3. 5 . Példaként tekinthetjük a javasoltat J. von Neumann(1903 – 1957) egy szekvenciális számítógép blokkvázlata, amely sok eszközből áll M:

,

Ahol a- beviteli eszköz, b– aritmetikai eszköz (processzor), c- vezérlő eszköz, d- memória eszköz, e- kimeneti eszköz.

Nézzük az eszközök közötti információcserét miÉs mj, amelyek az r ha a készüléktől való relációban vannak mi információ kerül a készülékbe mj.

Ezt a bináris relációt úgy határozhatjuk meg, hogy felsoroljuk mind a 14 rendezett elempárt:

A bináris relációt meghatározó megfelelő digráf az ábrán látható:

Ennek a bináris relációnak a mátrixábrázolása a következő:

. ,

A bináris relációknál a halmazelméleti műveleteket a szokásos módon határozzuk meg: unió, metszés stb.

Vezessünk be egy általánosított kapcsolatfogalmat.

Meghatározás 3.3. n-es hely (n-ary ) r reláció a közvetlen szorzat részhalmaza n halmazok, azaz rendezett halmazok halmaza ( sorok )

rÍ A 1 An={(a 1, …, an)| a 1О A 1Ù…Ù anÎ An}

Kényelmes többhelyes relációk definiálása segítségével relációs táblák . Ez a feladat megfelel a halmaz felsorolásának n-relációhoz r. A relációs táblákat széles körben használják a számítógépes gyakorlatban a relációs adatbázisokban. Vegye figyelembe, hogy a relációs táblákat a mindennapi gyakorlatban használják. Mindenféle termelési, pénzügyi, tudományos és egyéb jelentés gyakran relációs táblázatok formájában jelenik meg.

szó" relációs A latin szóból származik kapcsolat, ami oroszra fordítva „hozzáállást” jelent. Ezért a szakirodalomban a betűt használják a kapcsolat jelölésére R(latin) vagy r (görög).

Meghatározás 3.4. Legyen rÍ A´ B felé van hozzáállás A´ B. Ekkor az r-1 arányt nevezzük inverz reláció adott arányhoz r által A´ B, amelynek meghatározása a következő:

r-1=(( b, a) | (a, b)Îr).

Meghatározás 3.5. Legyen r Н A´ B felé van hozzáállás A´ B, a s Н B´ C – hozzáállás B´ C. Fogalmazás kapcsolatokat s és r t Н relációnak nevezzük A´ C, amelynek meghatározása a következő:

t=s◦r= (( a, c)| $bÎ B, mi (a, b)Îr És (b, c)Îs).

Példa 3. 6 . Hagyjuk és C=(, !, d, a). És legyen az r arány A´ Bés az arány s be B´ C formában adják meg:

r=((1, x), (1, y), (3, x)};

s=(( x,), (x, !), (y, d), ( y, à)}.

Keresse meg r-1 és s◦r, r◦s.

Megoldás. 1) Definíció szerint r-1=(( x, 1), (y, 1), (x, 3)};

2) Két reláció összetételének definícióját felhasználva megkapjuk

s◦r=((1,), (1, !), (1, d), (1, а), (3,), (3, !)),

óta (1, x)Îr és ( x,)Îs következik (1,)Îs◦r;

innen (1, x)Îr és ( x, !)Îs következik (1, !)Îs◦r;

innen (1, y)Îr és ( y, d)Î következik (1, d)Îs◦r;

innen (3, x)Îr és ( x, !)Îs következik (3, !)Îs◦r.

3.1. Tétel. Minden bináris relációra a következő tulajdonságok érvényesek:

2) ;

3) - a kompozíció asszociativitása.

Bizonyíték. Az 1. tulajdonság nyilvánvaló.

Bizonyítsuk be a 2. tulajdonságot. A második tulajdonság bizonyításához megmutatjuk, hogy az egyenlőség bal és jobb oldalára írt halmazok azonos elemekből állnak. Hagyja ( a; b) О (s◦r)-1 Û ( b; a) О s◦r Û $ c oly módon, hogy ( b; c) О r és ( c; a) О s Û $ c oly módon, hogy ( c; b) О r-1 és ( a; c) О s-1 Ш ( a; b) О r -1◦s -1.

Bizonyítsd be magad a 3. tulajdonságot.

3.2. A bináris relációk tulajdonságai.

Tekintsük a bináris relációk speciális tulajdonságait a halmazon A.

A bináris relációk tulajdonságai.

1. Arány r be A´ A hívott fényvisszaverő , Ha ( a,a) az r-hez tartozik mindenkinek a tól től A.

2. Az r relációt nevezzük tükröződésmentes , ha ebből ( a,b)Îr következik a¹ b.

3. Arány r szimmetrikusan , ha azért aÉs b hozzá tartozik A, tól től ( a,b) ebből következik, hogy ( b,a)Îr.

4. Az r relációt nevezzük antiszimmetrikus , ha azért aÉs b tól től A, tartozásból ( a,b) És ( b,a) r reláció arra utal a=b.

5. Arány r tranzitívan , ha azért a, bÉs c tól től A attól, hogy ( a,b)Îr és ( b,c)Îr, ebből az következik, hogy ( a,c)Îr.

Példa 3. 7. Hadd A=(1; 2; 3; 4; 5; 6). Ezen a halmazon az rÍ reláció adott A 2, amelynek alakja: r=((1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2) ), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)). Milyen tulajdonságai vannak ennek a kapcsolatnak?

Megoldás. 1) Ez a kapcsolat reflexív, hiszen mindegyikre aÎ A, (a; a)Îr.

2) A reláció nem antireflexív, mivel ennek a tulajdonságnak a feltétele nem teljesül. Például (2, 2)Îr, de ez nem jelenti azt, hogy 2¹2.

3) Tekintsünk minden lehetséges esetet, megmutatva, hogy az r reláció szimmetrikus:

	(a, b)Îr	(b, a)	(b, a)Îr?

4) Ez az összefüggés nem antiszimmetrikus, mivel (1, 2)Îr és (2,1)Îr, de ebből nem következik, hogy 1=2.

5) A közvetlen felsorolási módszerrel kimutatható, hogy az r reláció tranzitív.

	(a, b)Îr	(b, c)Îr	(a, c)	(a, c)Îr?

A mátrixábrázolás használata

határozza meg a bináris reláció tulajdonságait

1. Reflexivitás: Minden egyes a főátlón van, a nullákat vagy egyeseket csillagok jelölik.

.

2. Antireflexivitás: Minden nulla a főátlón.

3. Szimmetria: Ha .

4. Antiszimmetria: a főátlón kívüli összes elem nulla; a főátlón nullák is lehetnek.

.

A „*” művelet a következő szabály szerint történik: , Ahol , .

5. Tranzitivitás: Ha . A „◦” műveletet a szokásos szorzási szabály szerint hajtjuk végre, és figyelembe kell venni: .

3.3 Egyenértékűségi reláció. Részleges rend kapcsolat.

Az ekvivalenciareláció annak a helyzetnek a formalizálása, amikor egy halmaz két elemének hasonlóságáról (azonosságáról) beszélünk.

Meghatározás 3.6. Arány r be A Van ekvivalencia reláció, ha azt reflexív, szimmetrikus és tranzitív. Egyenértékűségi reláció a r b gyakran jelölik: a~ b.

Példa 3. 8 . Az egyenlőségi reláció az egész számok halmazán egy ekvivalencia reláció.

Példa 3. 9 . Az „azonos magasságú” reláció egy emberhalmaz ekvivalenciarelációja x.

Példa 3. 1 0 . Legyen ¢ az egész számok halmaza. Nevezzünk meg két számot xÉs y¢-től modulusban összehasonlíthatóm(mО¥) és írja be, ha ezeknek a számoknak a maradékai elosztása után m, azaz a különbség ( x-y) osztva m.

A „modulusban összehasonlítható” összefüggés m integers" egy ekvivalencia reláció a ¢ egész számok halmazán. Valóban:

ez az összefüggés reflexív, mert a " x΢ van x-x=0, ezért osztható vele m;

ez az összefüggés szimmetrikus, mert ha ( x-y) osztva m, akkor ( y-x) is osztható vele m;

ez a reláció tranzitív, mert ha ( x-y) osztva m, majd valamilyen egész számra t 1 van https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, innen , azaz ( x-z) osztva m.

Meghatározás 3.7. Arány r be A Van részleges rend kapcsolat, ha azt reflexív, antiszimmetrikus és tranzitívés a ° szimbólum jelzi.

A részleges sorrend fontos azokban a helyzetekben, amikor valamilyen módon szeretnénk jellemezni az elsőbbséget. Más szóval, döntse el, milyen feltételek mellett tekintse a halmaz egyik elemét jobbnak a másiknál.

Példa 3. 11 . Hozzáállás x£ y a valós számok halmazán részleges rendű reláció van. ,

Példa 3. 1 2 . Valamely egyetemes halmaz részhalmazainak halmazában U hozzáállás AÍ B részleges sorrendi összefüggés van.

Példa 3. 1 3 . Az alárendeltség szervezeti sémája egy intézményben a részleges rend viszonya egy beosztásban.

A részleges rendű reláció prototípusa a preferencia (predenciális) reláció intuitív fogalma. A preferenciareláció a problémák egy osztályát azonosítja, amelyek kombinálhatók választási probléma probléma a legjobb tárgy .

Probléma megfogalmazása: legyen tárgyak gyűjteménye Aés a preferencia szerint össze kell hasonlítani őket, azaz be kell állítani a preferencia relációt a halmazon Aés azonosítsa a legjobb tárgyakat.

Preferencia kapcsolat P, amely a következőképpen definiálható: " aPb, a, bÎ AÛ objektum a nem kevésbé előnyös, mint a tárgy b"reflexív és antiszimmetrikus jelentésű (egyik tárgy sem rosszabb önmagánál, és ha az objektum a nem rosszabb bÉs b nem rosszabb a, akkor preferenciában ugyanazok). Természetes azt feltételezni, hogy a kapcsolat P tranzitív módon (bár abban az esetben, ha például a preferenciákat ellentétes érdekű emberek csoportja tárgyalja, ez a tulajdonság sérülhet), pl. P– részleges rend kapcsolat.

Az objektumok preferencia szerinti összehasonlításának egyik lehetséges módja az körű , azaz az objektumok rendezése a csökkenő preferencia vagy ekvivalencia szerint. A rangsorolás eredményeként a preferenciakapcsolat szempontjából a „legjobb” vagy „legrosszabb” objektumokat azonosítjuk.

Felhasználási területek problémák a legjobb tárgy kiválasztásának problémájával kapcsolatban: döntéselmélet, alkalmazott matematika, technológia, közgazdaságtan, szociológia, pszichológia.

Definíciók

• 1. Az A és B halmazok elemei közötti bináris reláció a RAB, RAA derékszögű szorzat bármely részhalmaza.
• 2. Ha A=B, akkor R bináris reláció A-n.
• 3. Megnevezés: (x, y)R xRy.
• 4. Egy R bináris reláció definíciós tartománya az R = (x: létezik olyan y, amelyre (x, y)R) halmaz.
• 5. Egy R bináris reláció értéktartománya az R = halmaz (y: létezik olyan x, hogy (x, y)R).
• 6. Az A és B elemek közötti R bináris reláció komplementere az R = (AB) R halmaz.
• 7. Az R bináris reláció inverz relációja az R1 = ((y, x) : (x, y)R halmaz.
• 8. Az R1AB és R2BC relációk szorzata az R1 R2 = ((x, y) : létezik zB úgy, hogy (x, z)R1 és (z, y)R2).
• 9. Egy f relációt A-tól B-ig tartó függvénynek nevezünk, ha két feltétel teljesül:
  • a) f = A, f B
  • b) minden x, y1, y2 esetén abból, hogy (x, y1)f és (x, y2)f, az következik, hogy y1=y2.
• 10. Az f összefüggést A-tól B-ig tartó függvénynek nevezzük, ha az első bekezdésben f = A, f = B.
• 11. Jelölés: (x, y)f y = f(x).
• 12. Az iA: AA azonosítófüggvényt a következőképpen definiáljuk: iA(x) = x.
• 13. Egy f függvényt 1-1 függvénynek nevezünk, ha bármely x1, x2, y esetén abból, hogy y = f(x1) és y = f(x2) x1=x2 következik.
• 14. f függvény: AB egy az egyhez megfeleltetést biztosít A és B között, ha f = A, f = B és f 1-1 függvény.
• 15. Az R bináris reláció tulajdonságai az A halmazon:
  • - reflexivitás: (x, x)R minden xA-ra.
  • - irreflexivitás: (x, x)R minden xA-ra.
  • - szimmetria: (x, y)R (y, x)R.
  • - antiszimmetria: (x, y)R és (y, x)R x=y.
  • - tranzitivitás: (x, y)R és (y, z)R (x, z)R.
  • - dichotómia: vagy (x, y)R vagy (y, x)R minden xA és yA esetén.
• 16. A P(A) A1, A2, ..., Ar halmazok az A halmaz egy partícióját alkotják, ha
• - Аi, i = 1, ..., r,
• - A = A1A2...Ar,
• - AiAj = , i j.

Az Аi, i = 1, ..., r részhalmazokat partícióblokknak nevezzük.

• 17. Az ekvivalencia egy A halmazon reflexív, tranzitív és szimmetrikus reláció A-n.
• 18. Egy x elem ekvivalenciaosztálya R ekvivalenciával az [x]R=(y: (x, y)R halmaz.
• 19. Az A faktorhalmaz R-vel az A halmaz elemeinek ekvivalenciaosztályainak halmaza. Megnevezés: A/R.
• 20. Az ekvivalenciaosztályok (az A/R faktorhalmaz elemei) az A halmaz egy partícióját alkotják. Megfordítva. Az A halmaz bármely partíciója megfelel egy R ekvivalenciarelációnak, amelynek ekvivalenciaosztályai egybeesnek a megadott partíció blokkjaival. Eltérően. Az A halmaz minden eleme az A/R valamelyik ekvivalenciaosztályába esik. Az ekvivalenciaosztályok vagy nem metszik egymást, vagy egybeesnek.
• 21. Az előrendelés egy A halmazon egy reflexív és tranzitív reláció A-n.
• 22. Az A halmazon lévő részleges rend reflexív, tranzitív és antiszimmetrikus reláció az A-n.
• 23. Az A halmaz lineáris sorrendje egy reflexív, tranzitív és antiszimmetrikus reláció A halmazon, amely kielégíti a dichotómia tulajdonságot.

Legyen A=(1, 2, 3), B=(a, b). Írjuk ki a derékszögű szorzatot: AB = ( (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) ). Vegyük ennek a derékszögű szorzatnak bármelyik részhalmazát: R = ( (1, a), (1, b), (2, b) ). Ekkor R egy bináris reláció az A és B halmazokon.

Ez a reláció függvény lesz? Ellenőrizzük két 9a) és 9b) feltétel teljesülését. Az R reláció definíciós tartománya az R = (1, 2) (1, 2, 3) halmaz, vagyis az első feltétel nem teljesül, ezért az egyik párat hozzá kell adni R-hez: (3, a) vagy (3, b). Ha mindkét párt összeadja, akkor a második feltétel nem teljesül, mivel ab. Ugyanezen okból ki kell zárni az egyik párat az R-ből: (1, a) vagy (1, b). Így az R = ( (1, a), (2, b), (3, b) ) reláció függvény. Vegye figyelembe, hogy az R nem 1-1 függvény.

Adott A és B halmazokon a következő relációk is függvények lesznek: ( (1, a), (2, a), (3, a) ), ( (1, a), (2, a), (3 , b ) ), ( (1, b), (2, b), (3, b) ) stb.

Legyen A=(1, 2, 3). Egy példa az A halmaz relációjára: R = ( (1, 1), (2, 1), (2, 3) ). Egy példa az A halmaz függvényére: f = ( (1, 1), (2, 1), (3, 3) ).

Példák problémamegoldásra

1. Keresse meg az R, R, R1, RR, RR1, R1R értékeket, ha R = ((x, y) | x, y D és x+y0).

Ha (x, y)R, akkor x és y minden valós számon átfut. Ezért R = R = D.

Ha (x, y)R, akkor x+y0, ami azt jelenti, hogy y+x0 és (y, x)R. Ezért R1=R.

Bármely xD, yD esetén z=-|max(x, y)|-1, majd x+z0 és z+y0, azaz. (x, z)R és (z, y)R. Ezért RR = RR1 = R1R = D2.

2. Mely R bináris relációkra igaz R1= R?

Legyen RAB. Két eset lehetséges:

• (1) AB. Vegyük az xAB-t. Ezután (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Ellentmondás.
• (2) AB=. Mivel R1BA és RAB, akkor R1= R= . Az R1 =-ből az következik, hogy R =. Az R =-ből az következik, hogy R=AB. Ellentmondás.

Ezért ha A és B, akkor ilyen R relációk nem léteznek.

3. A valós számok D halmazán az R összefüggést a következőképpen definiáljuk: (x, y)R (x-y) racionális szám. Bizonyítsuk be, hogy R ekvivalencia.

Reflexivitás:

Bármely xD esetén x-x=0 racionális szám. Mert (x, x)R.

Szimmetria:

Ha (x, y)R, akkor x-y = . Ekkor y-x=-(x-y)=- racionális szám. Ezért (y, x)R.

Tranzitivitás:

Ha (x, y)R, (y, z)R, akkor x-y = és y-z =. Ezt a két egyenletet összeadva azt kapjuk, hogy x-z = + racionális szám. Ezért (x, z)R.

Ezért R egy ekvivalencia.

4. A D2 sík partíciója az a) ábrán látható blokkokból áll. Írja fel az ennek a partíciónak megfelelő R ekvivalenciarelációt és az ekvivalenciaosztályokat!

Hasonló feladat a b) és c) ponthoz.

a) két pont ekvivalens, ha egy y=2x+b alakú egyenesen fekszik, ahol b bármely valós szám.

b) két pont (x1,y1) és (x2,y2) ekvivalens, ha (x1 egész része egyenlő x2 egész részével) és (y1 egész része egyenlő y2 egész részével).

c) döntsd el magad.

Önállóan megoldandó problémák

• 1. Bizonyítsuk be, hogy ha f egy függvény A-tól B-ig és g egy B-től C-ig, akkor fg egy A-tól C-ig tartó függvény.
• 2. Legyen A és B véges halmazok, amelyek m, illetve n elemből állnak.

Hány bináris kapcsolat van az A és B halmaz elemei között?

Hány függvény van A-tól B-ig?

Hány 1-1 függvény van A-tól B-ig?

Milyen m és n esetén van egy az egyhez megfelelés A és B között?

3. Bizonyítsuk be, hogy f akkor és csak akkor teljesíti az f(AB)=f(A)f(B) feltételt bármely A-ra és B-re, ha f 1-1 függvény.