bináris kapcsolatok. Példák bináris kapcsolatokra

Meghatározás. Bináris reláció R párok részhalmazának nevezzük (a,b)∈R az A×B derékszögű szorzat, azaz R⊆A×B . Ugyanakkor sokan A az R reláció definíciós tartományának, a B halmazt értéktartománynak nevezzük.

Jelölés: aRb (azaz a és b R-hez viszonyítva). /

Megjegyzés: ha A = B, akkor R-ről azt mondjuk, hogy egy reláció az A halmazon.

A bináris relációk megadásának módjai

1. Lista (párok felsorolása), amelyekre ez az összefüggés teljesül.

2. Mátrix. Az R ∈ A × A bináris reláció, ahol A = (a 1, a 2 ,..., a n), megfelel egy n rendű négyzetmátrixnak, amelyben a c ij elem, amely az i metszéspontjában van. sor és a j-edik oszlop egyenlő 1-gyel, ha van R reláció a i és a j között, vagy 0-val, ha hiányzik:

Kapcsolati tulajdonságok

Legyen R reláció egy A, R ∈ A×A halmazon. Akkor az R reláció:

reflexszerűen, ha Ɐ a ∈ A: a R a (a reflexív reláció mátrixának főátlója csak egyeseket tartalmaz);

antireflexív, ha Ɐ a ∈ A: a R a (a reflexív relációs mátrix főátlója csak nullákat tartalmaz);

szimmetrikus, ha Ɐ a , b ∈ A: a R b ⇒ b R a (egy ilyen összefüggés mátrixa szimmetrikus a főátlóra, azaz c ij c ji);

antiszimmetrikus, ha Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (egy ilyen összefüggés mátrixában nincs szimmetrikus a főátlóhoz képest);

tranzitív módon, ha Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c sor, azaz c ij = 1 , akkor a j-edik sorban lévők mindegyike (ezek az egységek feleljenek meg k e koordinátának úgy, hogy c jk = 1) meg kell felelnie az i-edik sorban lévőknek ugyanazon k-x koordinátákon, azaz c ik = 1 (és talán más koordinátákon is).

Feladat 3.1. Határozza meg a természetes számok halmazán megadott R - "osztónak lenni" reláció tulajdonságait!

Döntés.

arány R = ((a,b):a osztó b):

reflexív, nem antireflexív, mivel bármely szám maradék nélkül osztja magát: a/a = 1 minden a∈N esetén;

nem szimmetrikus, antiszimmetrikus, például a 2 osztója 4-nek, de a 4 nem osztója 2-nek;

tranzitív módon, hiszen ha b/a ∈ N és c/b ∈ N, akkor c/a = b/a ⋅ c/b ∈ N, például ha 6/3 = 2∈N és 18/6 = 3∈N , akkor 18/3 = 18/6⋅6/3 = 6∈N.

Feladat 3.2. Határozza meg az R - "testvérnek lenni" reláció tulajdonságait egy emberhalmazon.
Döntés.

R arány = ((a,b):a - b testvére):

nem reflexív, antireflexív az aRa nyilvánvaló hiánya miatt minden a esetében;

nem szimmetrikus, mivel általában van aRb a testvér a és b testvér között, de nincs bRa;

nem antiszimmetrikus, hiszen ha a és b testvérek, akkor aRb és bRa, de a≠b;

tranzitívan, ha testvéreknek nevezzük azokat az embereket, akiknek közös szüleik (apa és anya).

Feladat 3.3. Határozza meg a szerkezeti elemek halmazán megadott R - "főnöknek lenni" reláció tulajdonságait!

Döntés.

R arány = ((a,b) : a - főnök b):

• nem reflexív, antireflexív, ha annak egy adott értelmezésben nincs értelme;
• nem szimmetrikus, antiszimmetrikus, mivel minden a≠b esetén az aRb és a bRa nem teljesül egyszerre;
• tranzitív módon, hiszen ha a a b feje és b a c feje, akkor a a c feje.

Határozzuk meg az M i halmazon mátrixszal meghatározott R i reláció tulajdonságait, ha:

1. R 1 "ugyanaz a maradék, ha osztva 5-tel"; M 1 a természetes számok halmaza.
2. R2 „egyenlő legyen”; M 2 a természetes számok halmaza.
3. R 3 "ugyanabban a városban élnek"; M 3 emberkészlet.
4. R 4 „legyen ismerős”; M 4 sok ember.
5. R 5 ((a,b):(a-b) - páros; M 5 számkészlet (1,2,3,4,5,6,7,8,9).
6. R 6 ((a,b):(a+b) - páros; M 6 számkészlet (1,2,3,4,5,6,7,8,9).
7. R7 ((a,b):(a+1) - osztó (a+b)); M 7 - készlet (1,2,3,4,5,6,7,8,9).
8. R8 ((a,b):a - osztó (a+b),a≠1); M 8 a természetes számok halmaza.
9. R 9 "testvérnek lenni"; M 9 - sok ember.
10. R 10 "leánynak lenni"; M 10 - sok ember.

Műveletek bináris relációkon

Legyenek R 1 , R 1 az A halmazon definiált relációk.

Unió R 1 ∪ R 2: R 1 ∪ R 2 = ((a, b) : (a, b) ∈ R 1 vagy (a, b) ∈ R 2 );

útkereszteződés R 1 ∩ R 2: R 1 ∩ R 2 = ((a,b) : (a,b) ∈ R 1 és (a,b) ∈ R 2 );

különbség R 1 \ R 2: R 1 \ R 2 = ((a, b) : (a, b) ∈ R 1 és (a, b) ∉ R 2 );

egyetemes viszony U: = ((a;b)/a ∈ A & b ∈ A). ;

kiegészítés R1U\R1, ahol U = A × A;

identitásviszony I: = ((a;a) / a ∈ A);

fordított összefüggés R-1 1 :R-1 1 = ((a,b) : (b,a) ∈ R 1 );

fogalmazás R 1 º R 2: R 1 º R 2: = ((a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b), ahol R 1 ⊂ A × C és R 2 ⊂ C×B;

Meghatározás. A kapcsolat mértéke Az R egy A halmazon az önmagával való összetétele.

Kijelölés:

Meghatározás. Ha R ⊂ A × B, akkor R º R -1-et hívunk az R reláció magja .

3.1. Tétel. Legyen R ⊂ A × A egy A halmazon definiált reláció.

1. R akkor és csak akkor reflexív (a továbbiakban a ⇔ jelet használjuk), amikor I ⊂ R.
2. R szimmetrikus ⇔ R = R -1 .
3. R tranzitív ⇔ R º R ⊂ R
4. R jelentése antiszimmetrikus ⇔ R ⌒ R -1 ⊂ I .
5. R antireflexív ⇔ R ⌒ I = ∅ .

Feladat 3.4 . Legyen R az (1,2,3) és (1,2,3,4) halmazok közötti összefüggés a párok felsorolásával: R = ((1,1), (2,3), (2, 4), (3.1), (3.4)). Ezenkívül S egy reláció az S = ((1,1), (1,2), (2,1), (3,1), (4,2) halmazok között. Számítsa ki az R -1 , S -1 és S º R értékeket. Ellenőrizze, hogy (S º R) -1 = R -1 , S -1 .

Döntés.
R-1 = ((1,1), (1,3), (3,2), (4,2), (4,3));
S-1 = ((1,1), (1,2), (1,3), (2,1), (2,4));
S° R = ((1,1), (1,2), (2,1), (2,2), (3,1), (3,2));
(S°R) -1 = ((1,1), (1,2), (1,3), (2,1), (2,2), (2,3));
R -1 º S -1 = ((1,1), (1,2), (1,3), (2,1), (2,2), (2,3)) = (S ºR) -egy.

Feladat 3.5 . Legyen R a "...szülő..." reláció és S a "...testvér..." reláció minden ember halmazán. Adjon rövid szóbeli leírást a kapcsolatról:

R-1, S-1, RºS, S-1ºR-1 és RºR.

Döntés.

R -1 - "... gyermek ..." reláció;

S -1 - kapcsolat "... testvér vagy nővér ...";

R º S - reláció "... szülő ...";

S -1 º R -1 - "... gyermek ..." reláció

R º R - kapcsolat "...nagymama vagy nagyapa..."

Önálló megoldási feladatok

1) Legyen R a "...apa..." reláció, S pedig a "...nővér..." reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

R -1 , S -1 , R º S , S -1 º R -1 , R º R.

2) Legyen R a "...testvér..." reláció, S pedig az "...anya..." reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

R -1 , S -1 , S º R, R -1 º S -1 , S º S.

3) Legyen R a "...nagyapa..." reláció, S pedig a "...fia..." reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

4) Legyen R a „...lánya...” reláció, S pedig a „...nagymama...” reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

5) Legyen R az "...unokahúga..." reláció, S pedig az "...apa..." reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

6) Legyen R a "testvér..." és S az "anya..." reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

R -1 , S -1 , R º S , S -1 º R -1 , S º S .

7) Legyen R a „...anya...” reláció, S pedig a „...nővér...” reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

R -1 , S1, R º S, S1 º R1, S º S.

8) Legyen R a „...fia...” reláció, S pedig a „...nagyapa...” reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

9) Legyen R a „...nővér...” reláció, S pedig az „...apa...” reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

R -1 , S -1 , R º S , S -1 º R -1 , S º S .

10) Legyen R a „...anya...” reláció, S pedig a „...testvér...” reláció az összes ember halmazán. Adjon szóbeli leírást a kapcsolatról:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

1. Reflexivitás:

2. Gyenge reflexió:

3. Erős reflexivitás:

4. Antireflexivitás:

5. Gyenge antireflexivitás:

6. Erős antireflexivitás:

7. Szimmetria:

8. Antiszimmetria:

9. Aszimmetria:

10. Erős linearitás:

11. Gyenge linearitás:

12. Tranzitivitás:

Reflexivitás, a bináris tulajdonság (bináris, binomiális) kapcsolatok, egybeeső tagú tárgypárok kielégíthetőségének kifejezése (úgymond a tárgy és "tükörképe" között): a kapcsolat R reflexívnek nevezzük, ha bármely objektumra x definíciójának területéről, xRx. A reflexív relációk tipikus és legfontosabb példái: típusrelációk egyenlőség (identitások, egyenértékűségek, hasonlóságok stb.: bármely tárgy önmagával egyenlő) és nem szigorú rendű relációk (bármely tárgy sem kevesebb, sem több önmagánál). Intuitív elképzelések az "egyenlőségről" (egyenértékűség, hasonlóság stb.), nyilvánvalóan tulajdonságokkal ruházva fel szimmetriaés tranzitivitást R. tulajdonsága is „kényszer”, mert az utolsó tulajdonság az első kettőből következik. Ezért kiderül, hogy sok olyan matematikában használt relációt, amely definíció szerint nem rendelkezik R.-vel, természetesnek bizonyul újradefiniálni őket úgy, hogy reflexióssá váljanak, például úgy tekintve, hogy az egyes sorok ill. sík párhuzamos önmagával, és így tovább.

1. fejezet A halmazelmélet elemei

1.1 Készletek

A matematikában használt legegyszerűbb adatstruktúra akkor jön létre, ha nincs kapcsolat a különálló izolált adatok között. Az ilyen adatok összessége az Egy csomó. A halmaz fogalma egy meghatározatlan fogalom. A készletnek nincs belső szerkezete. A halmaz felfogható olyan elemek gyűjteményének, amelyek valamilyen közös tulajdonsággal rendelkeznek. Ahhoz, hogy egy elemgyűjtemény halmaznak nevezhető legyen, a következő feltételeknek kell teljesülniük:

Kell lennie egy szabálynak, amely meghatározza, hogy egy adott elem egy adott gyűjteményhez tartozik-e.

Kell lennie egy szabálynak, amely megkülönbözteti az elemeket egymástól. (Ez különösen azt jelenti, hogy egy halmaz nem tartalmazhat kettőt azonos elemek).

A halmazokat általában nagy latin betűkkel jelöljük. Ha elem

halmazhoz tartozik, akkor ezt jelöljük:

Ha a halmaz minden eleme

szintén a halmaz eleme, akkor a halmazt annak mondjuk részhalmaz készletek:

Részhalmaz

készletet hívják saját részhalmaza, ha

A halmaz fogalmát használva összetettebb és értelmesebb objektumokat építhet.

1.2 Műveletek a készleteken

A halmazok fő műveletei a következők Unió, útkereszteződésés különbség.

1. definíció. Egyesület

2. definíció. átkelés két halmazt új halmaznak nevezünk

3. definíció. különbség két halmazt új halmaznak nevezünk

Ha az objektumok azon osztálya, amelyen különböző halmazokat határoztunk meg, jelöljük

(világegyetem), azután kiegészítés halmazok hívja a különbséget rendezett n-ku, hívja kapcsolati erő .

Megjegyzés. A reláció fogalma nem csak matematikai szempontból nagyon fontos. A kapcsolat fogalma tulajdonképpen minden relációs adatbázis-elmélet alapja. Amint az alább látható, az arányok matematikai megfelelői táblázatok. Maga az "adatok relációs reprezentációja" kifejezés, amelyet először Codd vezetett be, ebből a kifejezésből származik kapcsolat e meghatározás értelmében értendő.

Mivel bármely halmaz tekinthető az 1. fokú derékszögű szorzatnak, így bármely részhalmaz, mint bármely halmaz, tekinthető 1. fokú relációnak. Ez nem túl érdekes példa, csak arra utal, hogy az "1. fokú reláció" kifejezések és a "részhalmaz" szinonimák. A reláció fogalmának nem trivialitása akkor nyilvánul meg, ha a reláció mértéke nagyobb, mint 1. A kulcsfontosságú pont itt két:

Először is, a reláció minden eleme hasonló sorok. A sorok egységessége lehetővé teszi, hogy egy egyszerű táblázatban szereplő sorok analógjainak tekintsük őket, pl. táblázatban, amelyben minden sor ugyanannyi cellából áll, és a megfelelő cellák ugyanazokat az adattípusokat tartalmazzák. Például egy reláció, amely a következő három sorból áll ( (1, "Ivanov", 1000), (2, "Petrov", 2000), (3, "Sidorov", 3000) ) olyan táblázatnak tekinthető, amely adatokat tartalmaz alkalmazottai és fizetésük. Egy ilyen táblázatnak három sora és három oszlopa lenne, és minden oszlop azonos típusú adatokat tartalmazna.

Ezzel szemben vegyük az ( (1), (1,2), (1, 2,3) ) halmazt, amely heterogén numerikus sorok. Ez a halmaz egyikben sem reláció

, sem -ben, sem -ben. Lehetetlen egyszerű táblázatot készíteni a készletben található sorokból. Igaz, ezt a halmazt tekinthetjük 1-es fokú relációnak az összes lehetséges fokozatú numerikus sorok halmazán

A diszkrét matematika alapjai.

A halmaz fogalma. A halmazok közötti kapcsolat.

A halmaz olyan objektumok gyűjteménye, amelyek egy bizonyos tulajdonsággal rendelkeznek, egyetlen egésszé egyesülve.

A halmazt alkotó objektumokat ún elemeket készletek. Ahhoz, hogy egy bizonyos objektumkészletet halmaznak lehessen nevezni, a következő feltételeknek kell teljesülniük:

· Létre kell hozni egy olyan szabályt, amely alapján egy elem egy adott gyűjteményhez tartozik-e.

· Kell lennie egy szabálynak, amely alapján az elemeket meg lehet különböztetni egymástól.

A halmazokat nagybetűkkel, az elemeit kisbetűkkel jelöljük. A készletek megadásának módjai:

· Halmazelemek felsorolása. - véges halmazokhoz.

Jellemző tulajdonság megadása .

üres készlet- olyan halmaznak nevezzük, amely nem tartalmaz elemet (Ø).

Két halmazt egyenlőnek mondunk, ha azonos elemekből állnak. , A=B

Egy csomó B a halmaz részhalmazának nevezzük DE( , akkor és csak akkor, ha a halmaz összes eleme B a készlethez tartoznak A.

Például: , B =>

Ingatlan:

Megjegyzés: általában véve ugyanannak a halmaznak egy részhalmazát, amelyet ún egyetemes(u). Az univerzális készlet minden elemet tartalmaz.

Műveletek a készleteken.

A

B

1. Egyesület 2 A és B halmaznak nevezzük azt a halmazt, amelyhez az A vagy B halmaz elemei tartoznak (legalább az egyik halmaz elemei).

2.átkelés A 2 halmaz egy új halmaz, amely olyan elemekből áll, amelyek egyszerre tartoznak az első és a második halmazhoz.

szám: , ,

Tulajdonság: egyesülési és kereszteződési műveletek.

· Kommutativitás.

Az asszociativitás. ;

· Elosztó. ;

U

4.Kiegészítés. Ha egy DE az univerzális halmaz egy részhalmaza U, majd a halmaz kiegészítése DE sokaknak U(jelölve) a halmaz azon elemeiből álló halmaz U, amelyek nem tartoznak a készlethez DE.

Bináris relációk és tulajdonságaik.

Legyen DEés NÁL NÉL ezek származtatott természetű halmazok, tekintsünk egy rendezett elempárt (a, c) a ϵ A, c ϵ B rendelt "enks" jöhet szóba.

(a 1, a 2, a 3,…a n), ahol a 1 ϵ A 1; a 2 ϵ A 2; …; a n ϵ A n;

Halmazok derékszögű (közvetlen) szorzata A 1, A 2, ..., A n, halmaznak nevezzük, amely a formájú rendezett n k-ből áll.

Nr: M= {1,2,3}

M × M = M 2= {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

A derékszögű szorzat részhalmazai fokaránynak nevezzük n vagy enáris viszony. Ha egy n=2, akkor fontolja meg bináris kapcsolatokat. Mit mondanak erre egy 1, egy 2 bináris relációban vannak R, mikor a 1 R a 2.

Bináris reláció halmazon M a halmaz közvetlen szorzatának részhalmazának nevezzük nönmagán.

M × M = M 2= {(a, b)| a, b ϵ M) az előző példában az arány kisebb a halmazon M létrehozza a következő halmazt: ((1,2);(1,3); (2,3))

A bináris relációk különféle tulajdonságokkal rendelkeznek, többek között:

Reflexivitás: .

· Antireflexivitás (irreflexivitás): .

· Szimmetria: .

· Antiszimmetria: .

· Tranzitivitás: .

· Aszimmetria: .

A kapcsolatok típusai.

ekvivalencia reláció;

· Rendelési viszony.

v A reflexív tranzitív relációt kvázi-rendű relációnak nevezzük.

v A reflexív szimmetrikus tranzitív relációt ekvivalenciarelációnak nevezzük.

v A reflexív antiszimmetrikus tranzitív relációt (részleges) rendű relációnak nevezzük.

v Az antireflexív antiszimmetrikus tranzitív relációt szigorú rendű relációnak nevezzük.

bináris kapcsolatok.

Legyenek A és B tetszőleges halmazok. Vegyünk minden halmazból egy elemet, A-ból a-t, B-ből b-t, és írjuk fel őket így: (először az első halmaz egy eleme, majd a második halmaz egy eleme - vagyis számunkra fontos az elemek felvételi sorrendje). Egy ilyen objektumot hívnak rendelt pár. Egyenlő csak azokat a párokat vesszük figyelembe, amelyekben az azonos számú elemek egyenlőek. = , ha a = c és b = d. Nyilvánvalóan, ha a ≠ b, akkor ≠ .

Descartes termék tetszőleges A és B halmazok (jelölése: AB) az összes lehetséges rendezett párból álló halmaz, amelynek első eleme A-hoz, a második B-hez tartozik. Definíció szerint: AB = ( | aA és bB). Nyilvánvaló, hogy ha A≠B, akkor AB ≠ BA. Egy A halmaz önmagával való derékszögű szorzatát n-szeresnek nevezzük Descartes fokozat A (jelölése: A n).

5. példa Legyen A = (x, y) és B = (1, 2, 3).

AB=( , , , , , }.

BA=(<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.

AA = A 2 = ( , , , }.

BB = B 2 = (<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.

bináris reláció egy halmazon M az M halmaz néhány rendezett elempárjának halmaza. Ha r egy bináris reláció és egy pár ehhez a relációhoz tartozik, ezt írjuk: r vagy x r y. Nyilvánvaló, hogy r Н M 2 .

6. példa Set (<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>) egy bináris reláció az (1, 2, 3, 4, 5) halmazon.

7. példa Az egész számok halmazán lévő ³ reláció bináris reláció. Ez az űrlap rendezett párjainak végtelen halmaza , ahol x ³ y, x és y egész számok. Ez a reláció magában foglalja például a párokat<5, 3>, <2, 2>, <324, -23>és nem a párhoz tartoznak<5, 7>, <-3, 2>.

8. példa Az egyenlőség relációja az A halmazon bináris reláció: I A = ( | x О A). I A-t hívják átlós készlet A.

Mivel a bináris relációk halmazok, az egyesülés, a metszés, az összeadás és a különbség műveletei alkalmazhatók rájuk.

A meghatározás hatálya az r bináris reláció a D(r) = ( x | van olyan y, hogy xry ) halmaz. Értékterület az r bináris reláció az R(r) = ( y | van olyan x, hogy xry ).

hozzáállás, fordított az r Н M 2 bináris relációhoz az r -1 = ( | О r). Nyilvánvaló, hogy D(r -1) = R(r), R(r -1) = D(r), r - 1 Í M 2 .

Fogalmazás Az M halmazon definiált r 1 és r 2 bináris relációt r 2 o r 1 = () bináris relációnak nevezzük. | létezik ilyen О r 1 és Н r 2). Nyilvánvalóan r 2 o r 1 Í M 2 .

9. példa. Legyen egy r bináris reláció az M = (a, b, c, d), r = ( , , , ). Ekkor D(r) = (a, c), R(r) = (b, c, d), r -1 = ( , , , ), r o r = ( , , , ), r -1 vagy r = ( , , , ), r o r -1 = ( , , , , , , }.

Legyen r bináris reláció egy M halmazon. Az r relációt hívjuk fényvisszaverő, ha x r x bármely x О M esetén. Az r relációt hívjuk szimmetrikus, ha minden párral együtt párat is tartalmaz . Az r arányt nevezzük tranzitív, ha abból, hogy x r y és y r z az következik, hogy x r z. Az r arányt nevezzük antiszimmetrikus, ha nem tartalmaz egyidejűleg párokat és az M halmaz x ¹ y különböző elemei.

Jelöljük meg ezen tulajdonságok teljesítésének kritériumait.

Egy r bináris reláció egy M halmazon akkor és csak akkor reflexív, ha I M Н r.

Egy r bináris reláció akkor és csak akkor szimmetrikus, ha r = r -1.

Egy r bináris reláció egy M halmazon akkor és csak akkor antiszimmetrikus, ha r З r -1 = I M .

Egy r bináris reláció akkor és csak akkor tranzitív, ha r o r н r.

10. példa A 6. példából származó reláció antiszimmetrikus, de nem szimmetrikus, reflexív és tranzitív. A 7. példában szereplő reláció reflexív, antiszimmetrikus és tranzitív, de nem szimmetrikus. Az I A relációnak mind a négy figyelembe vett tulajdonsága van. Az r -1 o r és r o r -1 reláció szimmetrikus, tranzitív, de nem antiszimmetrikus és reflexív.

hozzáállás egyenértékűség M halmazon bináris relációnak nevezzük, amely tranzitív, szimmetrikus és reflexív M-en.

hozzáállás részleges rend az M halmazon tranzitív, antiszimmetrikus és reflexív M-en az r bináris relációt.

11. példa A 7. példából származó reláció egy részleges sorrendű reláció. Az I A reláció egy ekvivalenciareláció és egy részleges rend. A párhuzamosság relációja az egyenesek halmazán ekvivalenciareláció.

A "kapcsolat" fogalma természetesen ismerős számodra. Gyakran használjuk a beszédben. Például elmondhatjuk, hogy a csoportom összes diákjával jó viszonyban vagyok.

Az életben folyamatosan különböző kapcsolatokban élünk és különböző kapcsolatokba lépünk. Családtagjainkkal rokonsági viszonyban, iskolatársakkal - baráti viszonyban, az intézmény vezetőivel, ahol tanulunk, dolgozunk - alárendeltségi viszonyban, stb. Ebben az értelemben a reláció egy kapcsolat bizonyos jellege.

A 2.2. részben beszéltünk a matematikai objektumok közötti kapcsolatokról. Tehát egy halmazhoz tartozó elem az összetartozás, két halmaz pedig a befogadás vagy az egyenlőség viszonyában van.

Most megvizsgáljuk azokat a kapcsolatokat, amelyek a halmazok elemei között létezhetnek. Tehát azt mondtuk, hogy a vizsgált példában a halmazok elemei között létrejött kapcsolatot binárisnak nevezzük.

Lényegében a példában először az adott halmazok derékszögű szorzatát állítottuk össze, azaz. ezen halmazok összes elempárjának halmaza úgy, hogy a pár első eleme az első halmazhoz, a második pedig a másodikhoz tartozik. Ezután ezeknek a pároknak a halmazából kiválasztottuk azoknak a pároknak egy részhalmazát, amelyek megmutatják, hogy az egyes hallgatók melyik karon tanulnak.

Meghatározás 2.8. bináris reláció Lie halmazok között NÁL NÉL a derékszögű szorzat bármely részhalmazát nevezzük Ah V.

A bináris kapcsolatokat általában a görög ábécé betűivel jelölik: p ("rho"), a ("szigma"), | / ("psi") stb.

Ha p valamilyen bináris reláció a halmazok között DE és NÁL NÉL, akkor a bináris reláció definíciója szerint felírhatjuk, hogy p c c L x B.

Ha egy pár (a, b ) a p bináris relációhoz tartozik, azaz. (a, b ) e p, akkor azt mondjuk, hogy az elem a p relációban van az elemmel b, és írja be az arb. Tehát a fenti példában a „tanulni a karon” összefüggést vettük figyelembe. Akkor azt mondhatjuk, hogy Péter ebben a kapcsolatban áll a Matematikai Karral.

A matematikában bizonyos összefüggésekre vannak bizonyos jelek. Például,

Tekintettel arra, hogy a bináris reláció párok halmaza, így, mint minden halmaz, megadható vagy ezeknek a pároknak a felsorolásával, vagy egy jellemző tulajdonság megjelölésével az ehhez a relációhoz tartozó párok kiválasztására a Descartes-szorzatból.

Példa 2.6

Legyen két numerikus halmaz: A =(1, 3.5) és B =(2, 8, 10). Adjunk meg egy bináris o relációt ezen halmazok között felsorolással: a= ((1, 2), (5, 10)). Ugyanezt a relációt beállíthatjuk egy jellemző tulajdonsággal: egy bináris relációt számpárok alkotnak úgy, hogy az első halmazból származó szám kétszer kisebb, mint a második halmazból.

Példa 2.7

Tekintsen egy csoport diákot a tudományos csoportjában. Állítsuk fel a „barátnak lenni” kapcsolatot ebben a halmazban. Egy akadémiai csoport bármely diákpárjáról meg lehet mondani, hogy kapcsolatban állnak-e vagy sem. Még az is előfordulhat, hogy ez a bináris reláció üres halmazt alkot. Milyen esetben lesz?

Az utolsó példában figyelni kell arra, hogy nem két halmaz elemei között hoztunk létre kapcsolatot, hanem egy halmaz elemei között. Ez is lehetséges, és nem mond ellent a bináris reláció meghatározásának. Csak ebben az esetben a két halmaz derékszögű szorzata helyett a halmaz derékszögű négyzetét kell figyelembe venni.

Egy halmazon definiált bináris relációnak különböző tulajdonságai lehetnek. Tekintsük őket.

1. A reflexivitás tulajdonsága.

Meghatározás 2.9. fényvisszaverő , ha van ilyen a f L pár (a > a) e R.

hozzáállás"

2. A szimmetria tulajdonsága.

Meghatározás 2.10. Azt mondják, hogy az A halmazon adott p bináris reláció az szimmetrikus , ha bármely elemre a és b L-ből milyen párból ( a , b ) p relációban áll, ebből következik, hogy a ( b , a) R-hez kapcsolódik.

Például a valós számok halmazán definiált egyenlőség relációja szimmetrikus, hiszen ha a szám k egyenlő a számmal P ) majd a szám P egyenlő a számmal k. A „barátnak lenni” viszony szintén szimmetrikus.

Másrészt a nagyságrendi sorrend aránya (

3. Az antiszimmetria tulajdonsága.

Meghatározás 2.11. Azt mondják, hogy az A halmazon adott p bináris reláció az antiszimmetrikus at ha bármely elemre a és b A-ból abból, hogy az (i, /;) és (/;,) párok a) p relációban vannak, ebből következik a = b.

Például a valós számok halmazán a nagyságrendi reláció antiszimmetrikus. Hiszen ha ismert, hogy a számokhoz x és nál nél Kész x és nál nél akkor ez azt jelenti x - y. De az egyenesek párhuzamosságának relációja nem antiszimmetrikus, hiszen ha egy egyenes / párhuzamos egyenessel tés közvetlen t párhuzamos egyenessel /, akkor ez nem azt jelenti, hogy közvetlen / és t mérkőzés. Különbözőek lehetnek.

4. A tranzitivitás tulajdonsága.

Meghatározás 2.12. Azt mondják, hogy az A halmazon adott p bináris reláció az tranzitív nál nél ha bármely elemre a, b és val vel L-től milyen pároktól (i, b ) és (/?, c) p relációban állnak, ebből következik, hogy a pár (a, c) r-hez is kapcsolódik.

A tranzitivitás tulajdonságát a nagyságrendi sorrendiség, a párhuzamosság, a „relatívnak lenni” reláció birtokolják.

A vonalak merőlegességi relációja nem tranzitív (ezt mutasd meg képpel). A „barátnak lenni” reláció is lényegében nem tranzitív (bár van egy mondás, amelyben kifejeződik e kapcsolat tranzitivitásának vágya: „A barátom barátja az én barátom”).

A bináris relációknak csak a főbb tulajdonságait vettük figyelembe, amelyek két széles körben használt relációtípust határoznak meg.

Egyenértékűségi reláció (vagy ekvivalencia) egy bináris reláció, amely reflexivitás, szimmetria és tranzitivitás tulajdonságokkal rendelkezik.

rendelési viszony (vagy rendezés) egy bináris reláció, amely reflexivitás, antiszimmetria és tranzitivitás tulajdonságokkal rendelkezik.

Például az „osztálytársnak lenni” reláció egy ekvivalencia, mivel rendelkezik a reflexivitás, a szimmetria és a tranzitivitás tulajdonságával. A „nem magasabbnak lenni” reláció egy embercsoporton a rend viszonya.

Az ekvivalencia és a rendezési viszonyok nagyon fontosak a matematika különböző területein, és az ekvivalenciát a különböző objektumok osztályozása során alkalmazzák. Ennek megértéséhez először forduljunk egy olyan matematikai fogalomhoz, mint egy halmaz particionálása.

Meghatározás 2.13. hasítás készletek/! Ezt a halmazt diszjunkt részhalmazok uniójaként való ábrázolásának nevezzük, amelyeket ún partíció osztályok.

Annak ellenőrzéséhez, hogy egy halmaz partíciójával van-e dolgunk, két feltételt kell ellenőriznünk:

• a felosztással kapott részhalmazok uniója az eredeti halmaz;
• bármely két különálló részhalmaz metszéspontja az üres halmaz.

Az osztályozás elvégzésekor a partíciós osztályok az ún ekvivalencia osztályok. Hogyan épülnek fel ezek az osztályok?

Engedd a forgatásra DE valamilyen p ekvivalenciarelációt vezetünk be. Vegyünk bármilyen elemet a tól től DE és az összes elemet DE, akik együtt vannak a r kapcsán. Mindezek az elemek alkotják az elem ekvivalencia osztályt a. Nyilvánvaló, hogy maga az elem a ebbe az osztályba tartozik. Valóban, ha p egy ekvivalenciareláció, akkor megvan a reflexivitás tulajdonsága, azaz. (a) a) e p, ami azt jelenti, hogy maga az elem a az általa alkotott ekvivalenciaosztályba tartozik.

Bizonyítható, hogy egy halmaz különböző elemeinek ekvivalenciaosztályai vagy egybeesnek, vagy nem metszik egymást. Ebből a szempontból feltételezhetjük, hogy ezek az osztályok partíciós osztályoknak tekinthetők.

Valóban, van egy tétel, amely szerint ha egy ekvivalenciareláció adott egy halmazon, akkor ennek a halmaznak az elemeit tartalmazó összes ekvivalenciaosztály halmaza ennek a halmaznak a partíciója.

Másrészt bebizonyítható, hogy ha van egy halmaznak valamilyen partíciója, és ezen a halmazon bináris reláció van definiálva úgy, hogy a halmaz elempárja csak akkor van ebben a relációban, ha mindkettő a halmazhoz tartozik. ugyanaz a partíció osztály, akkor ez a bináris reláció ekvivalencia lesz.

Megpróbálhatja ezeket az állításokat saját maga bizonyítani, vagy elemezheti a műben szereplő bizonyítást.

Az ekvivalencia osztályok használatakor a halmazt részhalmazokra bontjuk, amelyek mindegyike tartalmaz valamilyen "ugyanazt" elemet. Például az összes pozitív tört halmaza felosztható ekvivalencia osztályokra a következő módon: 1) vegyünk minden nem redukálható

időzítési tört (például -); 2) minden ekvivalenciaosztályban

2 4 6 8 óra t

a meglévő törtekhez vegyük az összes vele egyenlő törtet - = - = - = 1akim

Így minden pozitív törtet felosztunk a megfelelő ekvivalenciaosztályokra. Minden ilyen osztály egy pozitív racionális szám.

• A Great Soviet Encyclopedia kijelenti, hogy „az attitűd az ember érzelmi-akarati attitűdje valamihez, i.e. helyzetének kifejezése; különböző tárgyak vagy egy adott tárgy aspektusainak mentális szembeállítása. D. N. Ushakov magyarázó szótárában „a kapcsolat kölcsönös kommunikáció, emberek, társadalmak, országok stb. közötti kapcsolat, amely valamilyen alapon kommunikációból alakul ki”.