Definice

1. Binární relace mezi prvky množin A A V nazývá se jakákoli podmnožina kartézského součinu RÍA´B, RÍA´A.

2. Pokud A=B, Že R- Tento binární relace na A.

3. Označení: (x, y)ÎR Û xRy.

4. Doména binární relace R- to je hodně d R = (x: existuje y takové, že (x, y) ОR}.

5. Rozsah hodnot binární relace R- to je hodně r R = (y: existuje X takové, že (x, y) ОR}.

6. Přidání binární relace R mezi prvky A A V- to je hodně -R = (A´B)\R.

7. Obrácený postoj pro binární relaci R- to je hodně R-1 = ((y, x) : (x, y)ÎR).

8. Produkt vztahů R 1 ÍA´B A R 2 ÍB´C – je to postoj R 1 × R 2 = {(x, y): existuje zÎB takové, že (x, z) ОR 1 A (z, y) ОR 2}.

9. přístup F volal funkce z A PROTI V, pokud jsou splněny dvě podmínky:

A) df = A, r f N V

b) pro všechny X,y 1,y 2 z čeho (x, y 1) Оf A (x, y 2) Оf by měl y 1 = y 2.

10. přístup F nazývaná funkce A na V, je-li v prvním odstavci splněno df = A, rf = B.

11. Označení: (x, y)Îf Û y = f(x).

12. Identické funkce i A: A®A je definován takto: i A (x) = x.

13. Funkce F volal 1-1 -funkce, pokud k nějakému x 1, x 2, y z čeho y = f(x 1) A y = f(x 2) by měl x 1 = x 2.

14. Funkce f: A®B provádí osobní korespondence mezi A A V, Pokud df = A, rf = B A F je funkce 1-1.

15. Vlastnosti binární relace R na sadě A:

- reflexivita: (x, x) ОR pro všechny xÎA.

- neflexibilita: (x, x)ÏR pro všechny xÎA.

- symetrie: (x, y)ÎR Þ (y, x)ÎR.

- antisymetrie: (x, y) ОR a (y, x) ОR Þ x=y.

- tranzitivita: (x, y) ОR a (y, z) ОR Þ (x, z) ОR.

- dichotomie: nebo (x, y) ОR nebo (y, x) ОR pro všechny xÎA A yÎA.

16. Sady A 1, A 2, ..., A r z P(A) formulář rozdělit sady A, Pokud

- A i ¹ Æ, i=1, ..., r,

- A = A 1 ÈA 2 È...ÈA r,

- A i ÇA j = Æ, i¹j.

Podmnožiny A i, i=1, ..., r, jsou nazývány štípání bloků.

17. Rovnocennost na sadě A je reflexivní, tranzitivní a symetrický vztah na A.

18. Ekvivalenční třídaživel X podle ekvivalence R- to je hodně [x] R = (y: (x, y)ÎR).

19. Sada faktorůA Podle R je množina tříd ekvivalence prvků množiny A. Označení: A/R.

20. Třídy ekvivalence (prvky faktorové množiny A/R) tvoří oddíl sady A. Zadní. Libovolný oddíl sady A odpovídá vztahu ekvivalence R, jehož třídy ekvivalence se shodují s bloky zadaného oddílu. Jinak. Každý prvek sady A spadá do nějaké třídy ekvivalence z A/R. Třídy ekvivalence se buď neprotínají, nebo se shodují.

21. Předobjednávka na sadě A je reflexivní a tranzitivní vztah na A.

22. Částečná objednávka na sadě A je reflexivní, tranzitivní a antisymetrický vztah na A.

23. Lineární řád na sadě A je reflexivní, tranzitivní a antisymetrický vztah na A, splňující vlastnost dichotomie.

Příklad 1.

Nechat A = (1, 2 , 3} , B = (a, b). Napišme kartézský součin: A´B = ( (1, A), (1 , b), (2 , A), (2 , b), (3 , A), (3 , b)). Vezměme libovolnou podmnožinu tohoto kartézského součinu: R = ((1, A), (1 , b), (2 , b)). Pak R je binární relace na množinách A A B.

Bude tento vztah funkcí? Zkontrolujme splnění dvou podmínek 9a) a 9b). Doména definice vztahu R- to je hodně d R = (1, 2) ¹ (1, 2, 3), to znamená, že první podmínka není splněna, proto v R musíte přidat jeden z párů: (3 , A) nebo (3 , b). Pokud sečtete oba páry, druhá podmínka nebude splněna, protože a¹b. Ze stejného důvodu od R musíte vyhodit jeden z párů: (1 , A) nebo (1 , b). Takže postoj R¢ = ( (1, A), (2 , b), (3 , b)) je funkce. všimněte si, že R¢ není funkce 1-1.

Na dané sestavy A A V Následující vztahy budou také funkcemi: { (1 , A), (2 , A), (3 , a)), { (1 , A), (2 , A), (3 , b)), { (1 , b), (2 , b), (3 , b)) atd.

Příklad 2

Nechat A = (1, 2 , 3} . Příklad relace na množině A je R = ( (1, 1), (2, 1), (2, 3) ). Příklad funkce na množině A je f = ( (1, 1), (2, 1), (3, 3) ).

Příklady řešení problémů

1. Najděte d R,r R,R-1,R×R,R×R -1,R -1×R Pro R = ((x, y) | x, y О D a x+y£0).

Li (x, y) ОR, Že X A y prochází všemi reálnými čísly. Proto d R= r R = D.

Li (x, y) ОR, Že x+y0£, znamená y+x 0 £ A (y, x) ОR. Proto R-1 =R.

Pro jakékoli xÎD, yÎD Pojďme vzít z=-|max(x, y)|-1, Pak x+z£0 a z+y£0, tj. (x, z) ОR A (z, y) ОR.Proto RxR = RxR-1= R-1 x R = D2.

2. Pro jaké binární relace R veletrh R-1 = -R?

Nechat RÍA´B. Existují dva možné případy:

(1) AÇB¹Æ. Pojďme vzít xÎAÇB. Pak (x, x)ÎR Û (x, x)ÎR -1 Û (x, x)Î-R Û (x, x)Î(A´B) \ R Û (x, x)ÏR. Rozpor.

(2) AÇB=Æ. Protože R -1 ÍB´A, A -RÍA'B, Že R-1 = -R= A. Z R-1 = Æ z toho vyplývá R = Æ. Z -R = Æ z toho vyplývá R=A'B. Rozpor.

Proto pokud A¹Æ A B¹Æ, pak takové vztahy R neexistuje.

3. Na place D reálná čísla definujeme poměr R následujícím způsobem: (x, y) ОR Û (x–y)- racionální číslo. Dokázat to R existuje ekvivalence.

Reflexivita:

Pro každého xÎD x-x=0- racionální číslo. Protože (x, x) ОR.

Symetrie:

Li (x, y) ОR, Že x-y =. Pak y-x=-(x-y)=- – racionální číslo. Proto (y, x) ОR.

Přechodnost:

Li (x, y) ОR, (y, z) ОR, Že x-y = a y-z =. Když sečteme tyto dvě rovnice, dostaneme to x-z = + - racionální číslo. Proto (x, z) ОR.

Proto, R je ekvivalence.

4. Rozdělení roviny D 2 sestává z bloků znázorněných na obrázku a). Napište vztah ekvivalence R, odpovídající tomuto oddílu, a třídy ekvivalence.

Podobná úloha pro b) ac).

a) dva body jsou ekvivalentní, pokud leží na přímce formuláře y=2x+b, Kde b– libovolné reálné číslo.

b) dva body (x 1, y 1) A (x 2, y 2) jsou ekvivalentní if (celočíselná část x 1 rovná celé části x 2) a (celočíselná část y 1 rovná celé části y 2).

c) rozhodnout se sám.

Úkoly pro samostatné řešení:

1. Dokažte, že pokud F existuje funkce od A PROTI B A G existuje funkce od B PROTI C, Že f×g existuje funkce od A PROTI C.

2. Nechat A A B– konečné množiny skládající se z m respektive n prvků.

a) Kolik binárních relací existuje mezi prvky množin? A A B?

b) Z kolika funkcí je A PROTI B?

c) Z kolika funkcí 1-1 je A PROTI B?

d) V čem m A n existuje mezi nimi vzájemná korespondence A A B?

3. Dokažte to F splňuje podmínku f(AÇB)=f(A)Çf(B) pro jakékoli A A B tehdy a jen kdy F jsou 1-1 funkce.

KOMBINATORIKA

Součin všech přirozených čísel z 1 před n označeno:

n! = 1·2·3·…·(n-1)·n, 0! = 1

Nechat X=(x 1, x 2, ..., x n)- to je hodně n Prvky, k £ n.

Ubytování prvky z X hlasitost k je uspořádaná podmnožina k prvky patřící k X.

Počet objemových umístění k z n

= n k(myšleno místa)

Pokud pro každého i-th of k pozice, ze kterých můžete jednu umístit Qi prvků množiny X, pak se počet takových umístění rovná:

(q 1 , q 2 , ..., q n) = q 1 × q 2 × ... × q n

Počet objemových umístění k z n

= n(n-1)(n-2) … (n - k + 1)=

Přeskupení prvky z X- toto je umístění prvků z X hlasitost n.

Počet permutací z n různé prvky:

=Pn= n!

Li n prvky obsahují Qi Prvky i- třída, q 1 + q 2 + ... + q m = n a prvky stejného druhu jsou totožné, pak se počet permutací rovná:

Pn (q 1, q 2, ..., q m) =

Kombinace prvky z X hlasitost k je neuspořádaná podmnožina k prvky patřící k X.

Kombinace, umístění a permutace mohou být také s opakováním prvků sady X(neomezené a omezené).

Počet kombinací objemů k z n různé prvky bez opakování:

Počet kombinací objemů k z n různé prvky s neomezeným opakováním:

Binomická věta:

Vlastnosti:

(2)

(4)

(5)

Při řešení kombinatorických úloh se často používají následující kombinatorická pravidla:

1. Pravidlo součtu. Pokud lze objekt A vybrat n způsoby a objekt B jinými m způsoby, pak lze volbu „buď A nebo B“ provést n+m způsoby.
2. Pravidlo produktu. Pokud lze objekt A vybrat n způsoby a po každé z těchto voleb lze naopak vybrat objekt B m způsoby, pak výběr „A a B“ v tomto pořadí lze provést n×m způsoby.

Příklad úkolu. Z 12 dívek a 10 chlapců je vybráno pětičlenné družstvo. Kolika způsoby lze tento tým vybrat tak, aby neobsahoval více než tři mladé muže?

Řešení. Podmínka „ne více než tři“ znamená, že tým může zahrnout nebo 3 mladí muži, nebo 2 mladí muži, nebo 1 mladý muž, nebo ani jeden mladý muž. Problém tedy rozlišuje čtyři různé případy. V souladu s pravidlem sčítání musíte v každém z těchto případů spočítat počet možností a složit jejich.

Podívejme se na první případ. Musíte spočítat, kolika způsoby si můžete vybrat z 12 dívek a 10 chlapců tým složený ze 3 chlapců a 2 dívek. Z 10 chlapců si můžete vybrat 3 kluky různými způsoby. Za každé tři vybrané chlapce můžete vybrat také 2 dívky z 12. Proto funguje pravidlo násobení a v prvním případě je počet možností příkazu roven ×.

Podobně ve druhém případě: ×.

Ve třetím případě: × .

Ve čtvrtém případě: .

Konečná odpověď: × + × + × + .

Příklady řešení problémů

№1.17. n (n>2) lidí sedí u kulatého stolu. Dvě umístění budeme považovat za identická, pokud má každá osoba v obou případech stejné sousedy. Kolika způsoby je možné sedět u stolu?

Řešení.

Celkový počet možných uspořádání sedadel se rovná počtu permutací n prvků P n = n! Odpovídající však musí být z těchto uspořádání sedadel vyloučeny. Vztah sousedství je zachován při cyklických permutacích (je jich n) a při symetrickém odrazu (také je jich n):

Proto celkem způsoby (rozděl, protože pravidlo násobení)

№1.19. Z balíčku obsahujícího 52 karet se lízne 10 karet. V kolika případech bude mezi těmito kartami alespoň jedno eso?

Řešení.

Existuje pouze 10 způsobů, jak odstranit 10 karet z balíčku. Z těchto případů nebude ve vzorku ani jedno eso. Proto odpověď zní.

№1.20. Kolika způsoby lze vytvořit tři páry n šachistů?

Řešení.

Nejprve vybereme 6 lidí z n šachistů. Existují způsoby, jak to udělat. Nyní rozdělíme každou šestku do dvojic. K tomu postavme 6 šachistů v řadě za předpokladu, že mají jména: a, b, c, d, e, f. To se dá udělat 6! způsoby. Pořadí v rámci každého páru a pořadí samotných párů však pro nás nejsou důležité. Permutace, ve kterých si šachisté mění místa ve dvojicích 2 3. Permutace, ve kterých jsou páry 3 prohozeny!. Proto existují způsoby, jak rozdělit 6 šachistů do dvojic. Odpovědět .

№1.24. Kolik čísel od 0 do 10 n neobsahují dvě po sobě jdoucí stejné číslice?

Řešení.

Uvažujme všechna n-ciferná čísla. První číslici můžeme zvolit 9 způsoby. Aby se druhá číslice lišila od první, lze ji vybrat také 9 způsoby. Počet takových n-ciferných čísel se rovná počtu umístění objemu n 9 prvků s neomezeným opakováním, tzn. se rovná 9 n pro n>1 a 10 pro n=1.

Proto je odpověď 10+9 2 +9 3 +...+9 n. Číslo 10 n není vhodné.

TEORIE ALGORITHMU

· Nechť N je množina přirozených čísel včetně nuly.

· V této části kurzu budou uvažovány funkce mnoha proměnných f n (x 1, ..., x n) definovaných na určité množině MÍN n s přirozenými hodnotami, tzn. f n (x 1, ..., x n)ÎN, x i ÎN pro i=1, ..., n nebo f n Í N n +1 .

· Funkce f n (x 1, ..., x n) se nazývá všude definovaná, pokud její definiční obor je N n, tzn. pro libovolnou množinu n přirozených čísel existuje přirozené číslo, které je hodnotou funkce f n.

· Nejjednodušší funkce definované všude:

1. s(x)=x+1 pro libovolné x;

2. o(x)=0 pro libovolné x;

3. I n m (x 1, ..., x m, ..., x n) = x m.

Tyto nejjednodušší funkce jsou definovány všude a lze z nich pomocí konečného počtu aplikací níže představených operátorů konstruovat složitější funkce.

· Operátor superpozice:

Funkce h n (x 1 , ..., x n) se získá z funkcí g m, f n 1, ..., f n m pomocí operátoru superpozice, pokud h n (x 1, ..., x n) = g m (f n 1 ( x 1, ..., x n), ..., f n m (x 1, ..., x n)).

· Operátor primitivní rekurze:

Funkce f n +1 (x 1, ..., x n, y) se získá z funkcí g n (x 1, ..., x n) a h n +2 (x 1, ..., x n, y, z ) pomocí primitivního operátoru rekurze, pokud jej lze specifikovat schématem primitivní rekurze:

æf n+1 (x 1, ..., x n, 0) = g n (x 1, ..., x n),

èf n+1 (x 1, ..., x n, y+1) = h n+2 (x 1, ..., x n, y, f n+1 (x 1, ..., x n, y )).

· Operátor minimalizace:

Funkce f n (x 1 , ..., x n) se získá z funkce g n +1 (x 1, ..., x n, y) pomocí minimalizačního operátoru a značí se f n (x 1, ..., x n )=můj, Pokud:

f n (x 1 , ..., x n) je definováno a rovná se y Û g n +1 (x 1 , ..., x n, 0), ..., g n +1 (x 1, ..., x n , y-1) jsou definovány a nerovnají se nule a gn +1 (x 1, ..., x n, y) = 0.

(Můžete také říci: „Funkce f n (x 1, ..., x n) je rovna minimální hodnotě y, při které se funkce g n +1 stane nulou.)

· Primitivní rekurzivní funkce (prf)

Funkce f n +1 (x 1 , ..., x n , y) se nazývá primitivní rekurzivní, pokud ji lze získat z jednoduchých funkcí pomocí konečného počtu aplikací operátorů superpozice a primitivní rekurze.

Je třeba poznamenat, že všechny primitivní rekurzivní funkce jsou definovány všude.

· Částečně rekurzivní funkce (prf)

O funkci f n + 1 (x 1, ..., x n, y) se říká, že je částečně rekurzivní, pokud ji lze získat z jednoduchých funkcí pomocí konečného počtu aplikací operátorů superpozice, primitivní rekurze a minimalizace.

· Z definic je snadné vidět, že primitivně rekurzivní funkce jsou také částečně rekurzivní. Existují však částečně rekurzivní funkce, které nejsou primitivní rekurzivní.

Příklady řešení problémů

1. Dokažte, že následující funkce jsou primitivně rekurzivní.

Řešení. Funkci f(x) lze získat aplikací operátoru superpozice nkrát na nejjednodušší funkci s(x).

Řešení. Funkce f(x) může být specifikována následujícím primitivním rekurzním schématem:

æf(x, 0) = x = I 1 1 (x),

èf(x, y+1) = x+y+1=f(x,y)+1=s(f(x,y))=s(I 3 3 (x,y,f(x,y) )).

Zde má funkce g(x) tvar g(x)= I 1 1 (x) a je podle očekávání funkcí jedné proměnné. A funkce h(x,y,z) má tvar h(x,y,z)=s(I 3 3 (x,y,z)) a je funkcí tří proměnných.

Všimněte si, že funkce g(x) a h(x,y,z) jsou prf, protože g(x) je třetí nejjednodušší funkce a h(x,y,z) lze získat z nejjednodušších funkcí s(x) a I 3 3 (x,y,z) použitím operátoru superpozice.

Protože funkci f(x,y) lze získat pomocí primitivního rekurzivního operátoru z primitivních rekurzivních funkcí g(x) a h(x,y,z), pak f(x,y) je prf.

Řešení. Funkci f(x) lze specifikovat následujícím schématem primitivní rekurze:

æf(x, 0) = 0 = o(x),

èf(x, y+1) = x(y+1)=xy+x=f(x,y)+x= I 3 3 (x,y,f(x,y)))+ I 3 1 ( x,y,f(x,y))).

Protože funkci f(x,y) lze získat pomocí primitivního rekurzivního operátoru z primitivních rekurzivních funkcí g(x)=o(x) a h(x,y,z) = I 3 3 (x,y,z )) + I 3 1 (x,y,z)), pak f(x,y) – prf.

2. Nechť g(x 1 , ..., x n ,y) je primitivní rekurzivní funkce. Dokažte, že následující funkce je primitivní rekurzivní:

Řešení. Zvláštností této funkce je, že sumace se provádí přes proměnný počet členů. Funkce f n +1 však může být specifikována následujícím schématem primitivní rekurze:

æf(x 1 , ..., x n , 0) = g(x 1 , ..., x n ,0) – prf,

èf(x 1 , ..., x n , y+1) = = f(x 1 , ..., x n, y) + g(x 1 , ..., x n ,y+1) – součet prf g a samotná funkce f.

3. Dokažte, že následující funkce je částečně rekurzivní.

Řešení. Ukažme, že funkci f(x,y) lze získat pomocí minimalizačního operátoru.

Nechť x³y, pak f(x,y) je definováno a nabývá určité hodnoty: f(x,y) = x-y = z. Jak vypočítat z? Můžeme navrhnout následující metodu: začněte od nuly, iterujte všechny hodnoty z v pořadí, dokud není splněna podmínka x-y=z, nebo x-y-z=0. Určitě tam bude takové z, protože x-y³0. Pokud x-y<0, то ни какое натуральное z не подойдет.

Programátor by to napsal takto:

bez znaménka int f(x,y)

while((x-y-z)!=0) z++;

Totéž lze napsat z hlediska operátoru minimalizace:

f(x, y)=mz[|x–y–z|=0]

Modul je nutný, aby funkce g(x,y,z)=|x–y–z| byla stanovena, i když x–y<0. Заметим, что g(x,y,z)=|x–y–z| является примитивно рекурсивной, т.к. может быть получена с помощью конечного числа применений оператора суперпозиции к простейшим функциям.

a) funkce, která není nikde definována (tj. funkce s prázdnou doménou definice);

b)

C)

Relace definovaná na množině může mít řadu vlastností, jmenovitě:

2. Reflexivita

Definice. přístup R různými způsoby X se nazývá reflexivní, pokud každý prvek X sady X je ve vztahu R Se mnou.

Pomocí symbolů lze tento vztah zapsat následovně:

R reflektivně na X Û(" XÎ X) x R x

Příklad. Vztah rovnosti na množině segmentů je reflexivní, protože každý segment je roven sám sobě.

Reflexní relační graf má smyčky ve všech vrcholech.

2. Antireflexivita

Definice. přístup R různými způsoby X se nazývá antireflexní, pokud žádný prvek X sady X ne ve vztahu R Se mnou.

R antireflexní na X Û(" XÎ X)

Příklad. Přímý vztah X kolmo k přímce na» na sadě přímek roviny je antireflexní, protože žádná přímka roviny není kolmá sama k sobě.

Antireflexní graf postoje neobsahuje jedinou smyčku.

Všimněte si, že existují vztahy, které nejsou ani reflexivní, ani antireflexní. Uvažujme například vztah „bod X do bodu symetrický na„na sadě bodů v rovině.

Tečka X do bodu symetrický X- skutečný; tečka na do bodu symetrický na– nepravda, proto nemůžeme tvrdit, že všechny body roviny jsou samy o sobě symetrické, a také nemůžeme tvrdit, že ani jeden bod roviny není symetrický sám se sebou.

3. Symetrie

Definice. přístup R různými způsoby X se nazývá symetrický jestliže, ze skutečnosti, že prvek X je ve vztahu R s prvkem na, z toho vyplývá, že prvek na je ve vztahu R s prvkem X.

R symetrický X Û(" X, naÎ X) x R y Þ y R x

Příklad. Přímý vztah X protíná čáru na na množině přímek roviny“ je symetrický, protože pokud je rovný X protíná čáru na, pak řádek na určitě překročí hranici X.

Graf symetrického vztahu spolu s každou šipkou z bodu X přesně na by měla obsahovat šipku spojující stejné body, ale v opačném směru.

4. Asymetrie

Definice. přístup R různými způsoby X se nazývá asymetrický, pokud pro žádné prvky X, na z mnoha X nemůže se stát, že by živel X je ve vztahu R s prvkem na a prvek na je ve vztahu R s prvkem X.

R asymetrické X Û(" X, naÎ X) x R y Þ

Příklad. Přístup " X < na» asymetricky, protože pro žádnou dvojici prvků X, na nedá se to říci zároveň X < na A na<X.

Asymetrický vztahový graf nemá žádné smyčky, a pokud jsou dva vrcholy grafu spojeny šipkou, pak existuje pouze jedna šipka.

5. Antisymetrie

Definice. přístup R různými způsoby X se nazývá antisymetrický jestliže, ze skutečnosti, že X je ve vztahu s na, A na je ve vztahu s X z toho vyplývá X = u

R antisymetrický X Û(" X, naÎ X) x R y Ù y R xÞ x = y

Příklad. Přístup " X£ na» antisymetricky, protože podmínky X£ na A na£ X jsou prováděny současně pouze tehdy, když X = u

Antisymetrický graf relace má smyčky, a pokud jsou dva vrcholy grafu spojeny šipkou, pak existuje pouze jedna šipka.

6. Tranzitivita

Definice. přístup R různými způsoby X se nazývá tranzitivní, pokud pro nějaké prvky X, na, z z mnoha X z čeho X je ve vztahu s na, A na je ve vztahu s z z toho vyplývá X je ve vztahu s z.

R transitivenona X Û(" X, na, zÎ X) x R y Ù y R zÞ x R z

Příklad. Přístup " X násobek na» tranzitivní, protože pokud je první číslo násobkem druhého a druhé je násobkem třetího, pak první číslo bude násobkem třetího.

Tranzitivní vztahový graf s každou dvojicí šipek od X Na na a od na Na z obsahuje šipku vycházející z X Na z.

7. Konektivita

Definice. přístup R různými způsoby X se nazývá připojený jestliže pro nějaké prvky X, na z mnoha X x je ve vztahu s na nebo na je ve vztahu s X nebo x = y.

R připojeno X Û(" X, na, zÎ X) x R y Ú y R zÚ X= na

Jinými slovy: postoj R různými způsoby X se nazývá spojený, pokud pro jakékoli odlišné prvky X, na z mnoha X x je ve vztahu s na nebo na je ve vztahu s X nebo x = y.

Příklad. Přístup " X< na» koherentně, protože bez ohledu na to, jaká reálná čísla vezmeme, jedno z nich bude určitě větší než druhé nebo se budou rovnat.

V grafu souvislých vztahů jsou všechny vrcholy navzájem spojeny šipkami.

Příklad. Zkontrolujte, jaké má vlastnosti

přístup " X - dělič na“, definované na sadě

X= {2; 3; 4; 6; 8}.

1) tento vztah je reflexivní, protože každé číslo z dané množiny je dělitelem sebe sama;

2) tento vztah nemá vlastnost antireflexivity;

3) vlastnost symetrie není splněna, protože například 2 je dělitel 4, ale 4 není dělitel 2;

4) tento vztah je antisymetrický: dvě čísla mohou být současně navzájem děliteli pouze tehdy, jsou-li tato čísla rovna;

5) vztah je tranzitivní, protože pokud je jedno číslo dělitelem druhého a druhé je dělitelem třetího, pak první číslo bude nutně dělitelem třetího;

6) vztah nemá vlastnost spojitosti, protože například čísla 2 a 3 na grafu nejsou spojena šipkou, protože dvě různá čísla 2 a 3 nejsou navzájem dělitelé.

Tento vztah má tedy vlastnosti reflexivity, asymetrie a tranzitivity.

§ 3. Vztah ekvivalence.
Souvislost mezi relací ekvivalence a rozdělením množiny do tříd

Definice. přístup R na sadě X se nazývá relace ekvivalence, pokud je reflexivní, symetrická a tranzitivní.

Příklad. Zvažte vztah" X spolužák na„na mnoha studentech pedagogické fakulty. Má následující vlastnosti:

1) reflexivita, protože každý žák je svým spolužákem;

2) symetrie, protože pokud student X na, pak student na je spolužákem studenta X;

3) tranzitivita, protože pokud student X- spolužák na a student na– spolužák z, pak student X bude studentovým spolužákem z.

Tento vztah má tedy vlastnosti reflexivity, symetrie a tranzitivity, a je tedy relací ekvivalence. Mnoho studentů Pedagogické fakulty lze přitom rozdělit do podskupin, které tvoří studenti studující ve stejném oboru. Získáme 5 podmnožin.

Vztahy ekvivalence jsou také např. vztah rovnoběžnosti přímek, vztah rovnosti obrazců. Každý takový vztah je spojen s rozdělením sady do tříd.

Teorém. Pokud je nastaveno X daný vztah ekvivalence, pak rozdělí tuto množinu na párově disjunktní podmnožiny (třídy ekvivalence).

Platí také obrácené tvrzení: pokud je na množině definován jakýkoli vztah X, vygeneruje rozdělení této množiny do tříd, pak jde o relaci ekvivalence.

Příklad. Na place X= (1; 2; 3; 4; 5; 6; 7; 8) je specifikován vztah „mít stejný zbytek při dělení 3“. Je to vztah ekvivalence?

Sestavme graf tohoto vztahu:

Tento vztah má vlastnosti reflexivity, symetrie a tranzitivity, jedná se tedy o relaci ekvivalence a rozděluje množinu X do tříd ekvivalence. V každé třídě ekvivalence budou čísla, která po dělení 3 dávají stejný zbytek: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

Má se za to, že třídu ekvivalence určuje kterýkoli z jejích zástupců, tzn. libovolný prvek této třídy. Třídu stejných zlomků lze tedy specifikovat zadáním libovolného zlomku patřícího do této třídy.

V počátečním kurzu matematiky se také setkáváme se vztahy ekvivalence, např. „výrazy X A na mají stejné číselné hodnoty", "obr X rovnající se postavě na».

Pro definování obecného pojmu binární relace na množině uděláme totéž jako v případě korespondencí,

těch. Podívejme se nejprve na konkrétní příklad. Nechť je množině X = (2, 4, 6, 8) dán vztah „menší než“. To znamená, že pro libovolná dvě čísla z množiny X můžeme říct, které je menší: 2< 4, 2 < 6, 2 < 8, 4 < 6, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все эти пары есть элементы декартова произведения X х X, поэтому об отношении «меньше», заданном на множестве X, можно сказать, что оно является подмножеством множества X х X.

Obecně jsou binární relace na množině X definovány následujícím způsobem:

Definice. Binární relace na množině X je jakákoli podmnožina kartézského součinu X x X.

Protože v budoucnu budeme uvažovat pouze binární vztahy, slovo „binární“ bude zpravidla vynecháno.

Dohodněme se, že vztahy budeme označovat písmeny R, S, T, P atd.

Jestliže R jsou relace na množině X, pak podle definice R X x X. Pokud je naopak dána nějaká podmnožina množiny X x X, pak definuje nějakou relaci R na množině X.

Tvrzení, že prvky x a y jsou ve vztahu k R, lze zapsat následovně: (x, y) R nebo x R y. Poslední záznam zní: "Prvek x je ve vztahu R k prvku y."

Vztahy jsou definovány stejným způsobem jako korespondence. Relace může být definována výpisem dvojic prvků množiny X, které jsou v této relaci. Formy reprezentace takových párů mohou být různé - jsou podobné formám upřesňování korespondencí. Rozdíly se týkají upřesňování vztahů pomocí grafu.

Sestavme například graf relací „méně než“ na množině X = (2, 4, 6, 8). Prvky množiny X k tomu znázorníme jako body (nazývají se vrcholy grafu) a vztah „menší než“ jako šipku (obr. 1).

Na stejné množině X můžeme uvažovat další relaci – „násobek“. Graf tohoto vztahu bude mít v každém vrcholu smyčku (šipku, jejíž začátek a konec se shodují), protože každé číslo je násobkem sebe sama (obr. 2).

Vztah lze specifikovat pomocí klauzule se dvěma proměnnými. Jsou tedy uvedeny například vztahy „menší než“ a „násobek“ diskutované výše a krátký tvar vět „číslo x je menší než číslo y“ a „číslo x je násobkem čísla y“. " se používá. Některé takové věty lze napsat pomocí symbolů. Například vztahy „menší než“ a „násobek“ lze zadat v následujícím tvaru: „x<у», «х у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или х – у = 3).

Pro relaci R zadanou na množině X je vždy možné zadat relaci R -1, její inverzní - je definována stejně jako korespondence inverzní k dané. Pokud je například R vztah „x je menší než y“, pak jeho inverzní bude vztah „y je větší než x“.

V počáteční výuce matematiky se často používá pojem relace inverzní k danému. Například, aby nedošlo k chybě při výběru akce, kterou chcete vyřešit problém: „Péťa má 7 tužek, což je o 2 méně než Boris. Kolik tužek má Bori? - bude přeformulováno: „Péťa má 7 tužek a Boris má 2 další. Kolik tužek má Bori? Vidíme, že přeformulování se scvrklo na nahrazení vztahu „méně o 2“ jeho inverzním vztahem „více o 2“.

Vlastnosti vztahů

Zjistili jsme, že binární relace na množině X je množina uspořádaných dvojic prvků patřících do kartézského součinu XxX. To je matematická podstata každého vztahu. Ale stejně jako všechny ostatní koncepty mají vztahy vlastnosti. Byly identifikovány studiem různých specifických vztahů. V našem kurzu budeme studovat jen několik vlastností; Podívejme se na sadu segmentů zobrazených na obr. 3, vztahy kolmosti, rovnosti a „delšího“. Sestavme grafy těchto vztahů (obr. 4) a porovnejme je.

Vidíme, že graf vztahu rovnosti se od ostatních dvou liší přítomností smyček v každém z jeho vrcholů. Tyto smyčky jsou výsledkem skutečnosti, že vztah rovnosti segmentů má tu vlastnost, že jakýkoli segment je roven sám sobě. Říká se, že vztah rovnosti má vlastnost reflexivita nebo jen co to je reflexně .

Definice. Relace R na množině X se nazývá reflexivní, jestliže o každém prvku množiny X lze říci, že je ve vztahu R sám se sebou.

R je reflexivní na X<=>xRx pro libovolné x X

Je-li relace R reflexivní na množině X, pak každý vrchol grafu této relace má smyčku. Platí to i naopak: graf, jehož každý vrchol má smyčku, definuje vztahy, které mají vlastnost reflexivity.

Příklady reflexivních vztahů:

Relace je „násobek“ na množině přirozených čísel (každé přirozené číslo je násobkem sebe sama);

Vztah podobnosti mezi trojúhelníky (každý trojúhelník je podobný sám sobě).

Existují vztahy, které nemají vlastnost reflexivity. Toto je například vztah kolmosti na množině úseček: neexistuje jediný úsečka, o které by se dalo říci, že je kolmá sama k sobě. V grafu vztahu kolmosti tedy není jediná smyčka (obr. 4). Relace „delší“ pro segmenty také nemá vlastnost reflexivity.

Věnujme nyní pozornost grafům vztahů kolmosti a rovnosti úseček. Jsou si „podobné“ v tom, že pokud je jedna šipka spojující dvojici prvků, pak jistě existuje další spojující stejné prvky, ale jdoucí opačným směrem. Tato vlastnost grafu odráží vlastnosti, které mají vztahy rovnoběžnosti a rovnosti segmentů:

Pokud je jeden segment kolmý k jinému segmentu, pak tento „další“ je kolmý k prvnímu;

Pokud se jeden segment rovná jinému segmentu, pak se tento „ostatní“ rovná prvnímu.

Říká se, že vztahy kolmosti a rovnosti segmentů mají vlastnost symetrie nebo jednoduše symetrické.

Definice. Relace R na množině X se nazývá symetrická, je-li splněna následující podmínka: ze skutečnosti, že prvek x je ve vztahu mezi R a prvkem y, vyplývá, že prvek y je také ve vztahu mezi R a prvkem x.

Pomocí symbolů lze tento vztah zapsat následovně:

R je symetrické na X<=>(xRy => yRx)

Symetrický vztahový graf má zvláštní vlastnost: spolu s každou šipkou jdoucí od x do y obsahuje graf také šipku jdoucí od y do x. Platí i opačné tvrzení. Graf obsahující každou šipku jdoucí od x do y a šipku jdoucí od y do x je graf symetrických vztahů.

Kromě dvou uvažovaných příkladů symetrických vztahů přidáváme následující:

Vztah rovnoběžnosti na množině přímek (je-li přímka x rovnoběžná s přímkou ​​y, pak přímka y je rovnoběžná s přímkou ​​x);

Vztah podobnosti mezi trojúhelníky (je-li trojúhelník F podobný trojúhelníku P, pak trojúhelník P je podobný trojúhelníku F).

Existují vztahy, které nemají vlastnost symetrie. Toto je například vztah „delší“ na množině segmentů. Pokud je segment x delší než segment y, pak segment y nemůže být delší než segment x. O vztahu „delší“ říkají, že má vlastnost antisymetrie nebo je prostě antisymetrický.

Definice. Relace R na množině X se nazývá antisymetrická, jestliže pro různé prvky x a y z množiny X je splněna tato podmínka: z toho, že x je ve vztahu R s prvkem y, vyplývá, že prvek y není ve vztahu R s prvkem x .

antisymetrické na X<=>(xRy a x≠y => )

Antisymetrický relační graf má zvláštní vlastnost: jsou-li dva vrcholy grafu spojeny šipkou, pak existuje pouze jedna šipka. Platí to i obráceně: graf, jehož vrcholy jsou spojeny pouze jednou šipkou, je antisymetrický relační graf.

Kromě „delšího“ vztahu na množině segmentů mají například vlastnost antisymetrie:

Vztah „větší než“ pro čísla (pokud je x větší než y, pak y nemůže být větší než x);

Vztah „větší o 2“ pro čísla (pokud je x větší než y o 2, pak y nemůže být větší než x o 2).

Existují vztahy, které nemají ani vlastnost symetrie, ani vlastnost antisymetrie. Vezměme si například vztah „být sestrou“ k mnoha dětem ze stejné rodiny. Ať jsou v rodině tři děti: Katya, Masha a Tolya. Pak bude graf vztahu „být sestrou“ stejný jako na obrázku 5. Ukazuje, že tento vztah nemá ani vlastnost symetrie, ani vlastnost antisymetrie.

Věnujme ještě jednou pozornost jedné vlastnosti „delšího“ relace grafu (obr. 4). Vidíte na něm: jsou-li šipky taženy z E Na A a od A Na S, tedy šipka od E Na S; pokud jsou šipky od E Na b a od b Na S, tedy šipku a od E Na S atd. Tato vlastnost grafu odráží důležitou vlastnost „delšího“ vztahu: je-li první segment delší než druhý a druhý delší než třetí, pak je první delší než třetí. Říká se, že tento vztah má vlastnost tranzitivity nebo jednoduše tranzitivní.

Definice. Relace R na množině X se nazývá tranzitivní, pokud je splněna následující podmínka: ze skutečnosti, že prvek x je ve vztahu mezi R a prvkem y a prvek y je ve vztahu mezi R a prvkem z, vyplývá, že prvek x je ve vztahu mezi R a prvkem z.

Pomocí symbolů lze tuto definici zapsat takto:

R je tranzitivní na X<=>(xRy a yRz => xRz)

Tranzitivní vztahový graf s každou dvojicí šipek vycházejících z X Na na A na Na z, obsahuje šipku jdoucí z X Na z. Platí i opačné tvrzení.

Kromě vztahu „delší“ na množině segmentů má vztah rovnosti vlastnost tranzitivity: pokud segment X rovný segmentu na a segment na rovný segmentu z, pak segment X rovný segmentu z. Tato vlastnost se odráží i v grafu vztahu rovnosti (obr. 4)

Existují vztahy, které nemají vlastnost tranzitivity. Takový vztah je například vztah kolmosti: je-li segment a kolmý k segmentu d a segment d je kolmý k segmentu b, pak segmenty a a b nejsou kolmé!

Uvažujme další vlastnost relací, která se nazývá vlastnost spojitosti, a vztah, který ji má, se nazývá spojený.

Definice. O relaci R na množině X říkáme, že je souvislá, jestliže pro libovolné prvky x a y z množiny X je splněna tato podmínka: z toho, že x a y jsou různé, vyplývá, že buď x je ve vztahu R s prvek y nebo prvek y je ve vztahu R s prvkem x.

Pomocí symbolů lze tuto definici zapsat takto:

R je připojen na množinu X<=>(x≠y xRy nebo yRx)

Například relace „větší než“ pro přirozená čísla mají vlastnost spojitosti: pro jakákoli odlišná čísla x a y lze říci, že buď x>y nebo y>x.

V grafu souvislých vztahů jsou libovolné dva vrcholy spojeny šipkou. Platí i opačné tvrzení.

Existují vztahy, které nemají vlastnost propojenosti. Takovým vztahem je například relace dělitelnosti na množině přirozených čísel: čísla můžeme nazývat hnu taková, že ani číslo x není dělitelem čísla y, ani číslo y není dělitelem čísla x.

Vybrané vlastnosti umožňují analyzovat různé vztahy z obecné perspektivy - přítomnost (nebo nepřítomnost) určitých vlastností v nich.

Shrneme-li tedy vše, co bylo řečeno o vztahu rovnosti definované na množině segmentů (obr. 4), ukáže se, že je reflexivní, symetrický a tranzitivní. Relace „delší“ na stejné množině segmentů je antisymetrická a tranzitivní a relace kolmosti je symetrická, ale nemá vlastnosti reflexivity a tranzitivity. Všechny tyto vztahy na dané množině

segmenty nejsou spojeny.

Úkol 1. Formulujte vlastnosti vztahu R definovaného pomocí grafu (obr. 6).

Řešení. Vztah R- je antisymetrický, protože vrcholy grafu jsou spojeny pouze jednou šipkou.

Relace R je tranzitivní, protože s dvojicí šipek vycházejících z b Na A a od A Na S, graf má šipku směřující od b Na S.

Vztah R je spojený, protože libovolné dva vrcholy jsou spojeny šipkou.

Relace R nemá vlastnost reflexivity, protože graf má vrcholy, které nemají smyčku.

Úkol 2. Formulujte vlastnosti vztahu „více než 2krát“ definovaného na množině přirozených čísel.

Řešení. „2 krát více“ je zkrácená forma vztahu „číslo x je dvojnásobek čísla y“. Tento vztah je antisymetrický, protože podmínka je splněna: z toho, že číslo x je 2x větší než číslo y, vyplývá, že číslo y není 2x větší než číslo x.

Tento vztah nemá vlastnost reflexivity, protože o žádném čísle nelze říci, že by bylo 2x větší než ono.

Daný vztah není tranzitivní, protože z toho, že číslo X další číslo na o 2 a číslo y je větší než číslo z o 2, z toho vyplývá, že číslo X nemůže být víc než číslo z dne 2.

Tento vztah na množině přirozených čísel nemá vlastnost spojitosti, protože existují dvojice čísel x a y takové, že ani číslo není dvakrát větší než y, ani číslo y není dvakrát větší než x. Například jsou to čísla 7 a 3,5 a 8 atd.

Nechat R je nějaká binární relace na množině X a x, y, z jsou libovolné její prvky. Pokud je prvek x ve vztahu R s prvkem y, pak napište xRy.

1. Relace R na množině X se nazývá reflexivní, pokud je každý prvek množiny v této relaci sám se sebou.

R -reflexní na X<=>xRx za jakékoli x € X

Je-li vztah R reflexivní, pak v každém vrcholu grafu existuje smyčka. Například vztahy rovnosti a rovnoběžnosti pro segmenty jsou reflexivní, ale vztahy kolmosti a „delšího“ reflexivní nejsou. To se odráží v grafech na obrázku 42.

2. Relace R na množině X se nazývá symetrická, jestliže z toho, že prvek x je v daném vztahu s prvkem y, vyplývá, že prvek y je ve stejném vztahu s prvkem x.

R - symetrické na (xYay =>y Rx)

Symetrický vztahový graf obsahuje párové šipky jdoucí v opačných směrech. Vztahy rovnoběžnosti, kolmosti a rovnosti pro segmenty jsou symetrické, ale „delší“ vztah symetrický není (obr. 42).

3. Relace R na množině X se nazývá antisymetrická, jestliže pro různé prvky x a y z množiny X z toho, že prvek x je v dané relaci s prvkem y, vyplývá, že prvek y není v tomto vztahu s prvkem x.

R - antisymetrické na X « (xRy a xy ≠ yRx)

Poznámka: overbar označuje negaci výroku.

V antisymetrickém grafu vztahů mohou být dva body spojeny pouze jednou šipkou. Příkladem takového vztahu je „delší“ vztah pro segmenty (obr. 42). Vztahy rovnoběžnosti, kolmosti a rovnosti nejsou antisymetrické. Existují vztahy, které nejsou ani symetrické, ani antisymetrické, například vztah „být bratrem“ (obr. 40).

4. Relace R na množině X se nazývá tranzitivní, jestliže z toho, že prvek x je v dané relaci s prvkem y a prvek y je v této relaci s prvkem z, vyplývá, že prvek x je v daný vztah s prvkem Z

R - tranzitivní na A≠ (xRy a yRz=> xRz)

V grafech „delších“, rovnoběžných a rovnoprávnostních vztahů na obrázku 42 si můžete všimnout, že pokud šipka jde od prvního prvku k druhému a od druhého ke třetímu, pak určitě existuje šipka jdoucí z prvního prvku. prvek do třetice. Tyto vztahy jsou tranzitivní. Kolmost segmentů nemá vlastnost tranzitivity.

Existují další vlastnosti vztahů mezi prvky jedné množiny, které neuvažujeme.

Stejný vztah může mít několik vlastností. Takže například na množině segmentů je vztah „rovná se“ reflexivní, symetrický, tranzitivní; vztah „více“ je antisymetrický a tranzitivní.

Pokud je relace na množině X reflexivní, symetrická a tranzitivní, pak jde o relaci ekvivalence na této množině. Takové vztahy rozdělují množinu X do tříd.

Tyto vztahy se projevují například při plnění úkolů: „Nasbírejte stejně dlouhé proužky a seřaďte je do skupin“, „Uspořádejte koule tak, aby každá krabice obsahovala koule stejné barvy.“ Vztahy ekvivalence („být stejně dlouhý“, „být stejné barvy“) v tomto případě určují rozdělení sad pruhů a kuliček do tříd.

Pokud je relace na množině 1 tranzitivní a antisymetrická, pak se nazývá relace řádu na této množině.

Množina s daným řádovým vztahem se nazývá uspořádaná množina.

Například při plnění úkolů: „Porovnejte proužky na šířku a seřaďte je od nejužšího k nejširšímu“, „Porovnejte čísla a seřaďte kartičky s čísly v pořadí“, děti seřadí prvky sad proužků a karet s čísly. používání objednávkových vztahů; „být širší“, „následovat“.

Obecně platí, že vztahy ekvivalence a řádu hrají u dětí velkou roli při vytváření správných představ o klasifikaci a řazení množin. Kromě toho existuje mnoho dalších vztahů, které nejsou ani vztahy ekvivalence, ani vztahy řádu.

6. Jaká je charakteristická vlastnost množiny?

7. V jakých vztazích mohou existovat množiny? Uveďte vysvětlení pro každý případ a znázorněte je pomocí Eulerových kruhů.

8. Definujte podmnožinu. Uveďte příklad množin, z nichž jedna je podmnožinou jiné. Napište jejich vztah pomocí symbolů.

9. Definujte stejné množiny. Uveďte příklady dvou stejných množin. Napište jejich vztah pomocí symbolů.

10. Definujte průsečík dvou množin a znázorněte jej pomocí Eulerových kružnic pro každý jednotlivý případ.

11. Definujte spojení dvou množin a znázorněte je pomocí Eulerových kružnic pro každý jednotlivý případ.

12. Definujte rozdíl mezi dvěma množinami a znázorněte jej pomocí Eulerových kružnic pro každý jednotlivý případ.

13. Definujte doplněk a znázorněte jej pomocí Eulerových kružnic.

14. Co se nazývá rozdělení množiny do tříd? Vyjmenujte podmínky správné klasifikace.

15. Co se nazývá korespondence mezi dvěma množinami? Pojmenujte metody pro specifikaci korespondence.

16. Jaký druh korespondence se nazývá individuální?

17. Jaké množiny se nazývají rovné?

18. Jaké množiny se nazývají ekvivalentní?

19. Vyjmenujte způsoby definování relací na množině.

20. Jaký vztah na množině se nazývá reflexivní?

21. Jaký vztah na množině se nazývá symetrický?

22. Jaký vztah na množině se nazývá antisymetrický?

23. Jaký vztah na množině se nazývá tranzitivní?

24. Definujte vztah ekvivalence.

25. Definujte objednávkový vztah.

26. Která sada se nazývá uspořádaná?

Nechť nějaká neprázdná množina A a R je určitou podmnožinou kartézského čtverce množiny A: R  A  A.

přístup R na sadě A nazývaná podmnožina množiny A A(nebo A 2 ). Tím pádem přístup existuje zvláštní případ korespondence, kdy se oblast příjezdu shoduje s oblastí odletu. Stejně jako korespondence je relace uspořádaná dvojice, kde oba prvky patří do stejné množiny.

R  A  A = ((a, b) | aA, bA, (a, b)R).

Skutečnost, že ( A, b)R lze napsat takto: A R b. Zní: " A je v poměru R k b“ nebo „mezi A A b platí vztah R." Jinak napiš :( A, b)R nebo AR b.

Příklady vztahů na množině čísel jsou následující: „=“, „“, „“, „>“ atd. Na množině zaměstnanců firmy je postoj „být šéfem“ nebo „být podřízeným“, na množině příbuzných – „být předkem“, „být bratrem“, „být otec“ atd.

Uvažované vztahy se nazývají binární (dvoumístné) homogenní vztahy a jsou v matematice nejdůležitější. Spolu s nimi také zvažují P-místní popř P-ary vztahy:

R  A  A … A = A n = ((a 1 , a 2 ,…a n) | a 1 , a 2 ,…a n  A).

Protože vztahy jsou speciálním případem korespondence, lze k jejich definování použít všechny dříve popsané metody.

Je zřejmé, že zadáním vztahu maticovým způsobem získáme čtvercovou matici.

S geometrickým (grafickým) znázorněním vztahu získáme diagram, který obsahuje:

vrcholy, označené tečkami nebo kroužky, které odpovídají prvkům množiny,

a oblouky (čáry) odpovídající dvojicím prvků zahrnutých v binárních relacích, označené čarami se šipkami směřujícími z vrcholu odpovídajícímu prvku A k vrcholu odpovídajícímu prvku b , Pokud A Rb .

Takový obrazec se nazývá orientovaný graf (nebo digraf) binární relace.

Problém 4.9.1 . Poměr "být dělitelem na množině M = (1, 2, 3, 4)" lze zadat matice:

výpis: R = ((1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), ((4,4) ));

geometricky (graficky):

1. Zapište uspořádané dvojice patřící k následujícím binárním relacím na množině A = (1, 2, 3, 4, 5, 6, 7):

R1 = ((x, y)| x, yA; x + y = 9);

R2 = ((x, y)| x, yA; x< y}.

2. Vztah R na množině X = (a, b, c, d) je dán maticí

,

ve kterém pořadí řádků a sloupců odpovídá pořadí zapsaných prvků. Vypište uspořádané dvojice patřící do tohoto vztahu. Znázorněte vztah pomocí grafu.

3. Vztah na množině A = (1, 2, 3, 4) je znázorněn grafem. Nezbytné:

seznam uspořádaných párů patřících do R;

vypište odpovídající matici;

definovat tento vztah pomocí predikátů.

(Odpovědět: a-b= 1).

4.10. Základní typy (vlastnosti) binárních relací

Nechť je dána binární relace R na sadě A 2 : R  A  A = (( A, b) | AA, bA, ( A, b)R)

Binární relace R na sadě A volal reflexní, pokud k nějakému AA provedeno ARA, tedy ( A,A)R. Hlavní diagonála matice reflexivních vztahů se skládá z jednotek. Reflexní graf relace má nutně smyčky v každém vrcholu.

Příklady reflexivní vztahy: , =,  na množině reálných čísel, „nebýt šéfem“ na množině zaměstnanců.

Binární relace R na množině A se nazývá antireflexní (nereflexivní), pokud nějaké AA vztah není splněn ARA, tedy ( A,A)R. Hlavní diagonála matice ireflexivních vztahů se skládá z nul. Nereflexivní graf vztahů nemá žádné smyčky.

Příklady antireflexivní vztahy:<, >na množině reálných čísel, kolmost přímek na množinu přímek.

Binární relace R na sadě A volal symetrický, pokud k nějakému A, bA z ARb by měl bRA, tedy pokud ( A, b)R, pak a ( b, A)R. Symetrická relační matice je symetrická podle své hlavní diagonály ( σ ij = σ ji). Graf symetrických vztahů není orientovaný (okraje jsou zobrazeny bez šipek). Každý pár vrcholů je zde spojen neorientovanou hranou.

Příklady symetrické vztahy:  na množině reálných čísel, „související“ na množině lidí.

Binární relace R na sadě A volal:

protisymetrický, pokud k nějakému A, bA z ARb A bRA z toho vyplývá A=b. Tedy pokud ( A, b)R A( b, A)R, pak z toho vyplývá A=b. Antisymetrická poměrová matice podél hlavní diagonály má samé jedničky a nemá žádnou dvojici jedniček umístěných na symetrických místech vzhledem k hlavní diagonále. Jinými slovy, všechno σ ii=1, a pokud σ ij=1, pak povinné σ ji=0. Antisymetrický vztahový graf má smyčky v každém vrcholu a vrcholy jsou spojeny pouze jedním směrovaným obloukem.

Příklady antisymetrické vztahy: , ,  na množině reálných čísel; ,  na soupravách;

Asymetrický, pokud k nějakému A, bA z ARb následuje nedodržení bRA, tedy pokud ( A, b)R, Že ( b, A) R. Asymetrická poměrová matice podél hlavní diagonály má nuly ( σ ij=0) všechny a žádné symetrické páry jedniček (pokud σ ij=1, pak povinné σ ji=0). Asymetrický vztahový graf nemá žádné smyčky a vrcholy jsou spojeny jedním směrovaným obloukem.

Příklady asymetrických vztahů:<, >na množině reálných čísel, „být otcem“ na množině lidí.

Binární relace R na sadě A volal tranzitivnínom, pokud k nějakému A, b, SA z ARb A bRA z toho vyplývá, že ARS. Tedy pokud ( A, b)R A( b, S)R z toho vyplývá, že ( A, S)R. Matice tranzitivní relace se vyznačuje tím, že pokud σ ij=1 a σ jm=1, pak povinné σ im=1. Graf tranzitivních vztahů je takový, že pokud jsou například první-druhý a druhý-třetí vrchol spojeny oblouky, pak nutně existují oblouky od prvního ke třetímu vrcholu.

Příklady tranzitivní vztahy:<, , =, >,  na množině reálných čísel; „být šéfem“ mnoha zaměstnanců.

Binární relace R na sadě A volal antitranzitivnínom, pokud k nějakému A, b, SA z ARb A bRA z toho vyplývá, že není splněna ARS. Tedy pokud ( A, b)R A( b, S)R z toho vyplývá, že ( A, S) R. Matice antitranzitivního vztahu se vyznačuje tím, že pokud σ ij=1 a σ jm=1, pak povinné σ im=0. Graf antitranzitivního vztahu je takový, že pokud jsou například první-druhý a druhý-třetí vrchol spojeny oblouky, pak nutně neexistuje žádný oblouk od prvního ke třetímu vrcholu.

Příklady antitranzitivních vztahů: „nesoulad parity“ na množině celých čísel; „být bezprostředním nadřízeným“ mnoha zaměstnanců.

Pokud relace nemá nějakou vlastnost, pak přidáním chybějících dvojic můžete získat novou relaci s touto vlastností. Množina takto chybějících dvojic se nazývá zkrat vztahy k této nemovitosti. Označuje se jako R* . Tímto způsobem můžete získat reflexní, symetrické a tranzitivní uzavření.

Problém 4.10.1. Na množině A = (1, 2, 3, 4) platí vztah R=(( A,b)| A,bA, A+b-sudé číslo). Určete typ tohoto vztahu.

Řešení. Matice tohoto vztahu:

. Je zřejmé, že vztah ano reflexní, protože jednotky jsou umístěny podél hlavní diagonály. To symetricky: σ 13 = σ 31, σ 24 = σ 42. Přechodně: (1,3)R, (3,1)R a (1,1)R; (2,4)R, (4,2)R a (2,2)R atd.

Problém 4.10.2. Jaké vlastnosti má množina A = ( A, b, C, d) má binární vztah R = (( A,b), (b,d), (A,d), (b,A), (b,C)}?

Řešení . Sestrojme matici tohoto vztahu a jeho graf:

přístup nereflexivně, protože všechny σ ii= 0. It Ne symetricky, protože σ 23 =1 a σ 32 =0, avšak σ 12 =σ 21 =1. přístup Ne tranzitivně, protože σ 12 = 1, σ 23 = 1 a σ 13 = 0; a12 = 1, a21 = 1 a a11 = 0; ale zároveň σ 12 =1, σ 24 =1 a σ 14 =1.

Problém 4.10.3. Na množině A = (1,2,3,4,5) je dán vztah R = ((1,2), (2,3), (2,4), (4,5)). Určete typ vztahu a najděte následující uzávěry pro R:

reflexní;

symetrický;

tranzitivní.

Řešení. Vztah je ireflexivní, protože neexistuje jediný prvek formuláře ( A,A). Asymetrický, protože neobsahuje dvojice tvaru ( A,b) A ( b,A) a všechny diagonální prvky jsou 0. Antitranzitivní, protože (1,2)R, (2,3)R, ale (1,3)R. Podobně (2,4)R, (4,5)R a (2,5)R atd.

reflexní uzavření daného vztahu R * =((1,1), (2,2), (3,3), (4,4), (5,5));

symetrické uzavření: R*=((2,1), (3,2), (4,2), (5,4));

tranzitivní uzávěr: R*=((1,3), (1,4), (2,5)). Uvažujme graf původního vztahu a výsledného tranzitivního vztahu.

Problémy pro samostatné řešení.

1. Je dán vztah R = ((1,1), (1,2), (1,3), (3,1), (2,3)). Určete jeho typ a najděte uzávěry na základě reflexivity, symetrie a tranzitivity.

2. Vztah na množině slov ruského jazyka je definován takto: A R b právě tehdy, pokud mají alespoň jedno společné písmeno. Určete typ vztahu na množině A = (kráva, kočár, závit, sekera).

3. Uveďte příklady binárních relací na množině A = (1, 2) a B = (1, 2, 3), což by bylo:

není reflexivní, není symetrický, není tranzitivní;

reflexivní, nesymetrický, netranzitivní;

symetrické, ale ne reflexivní a ne tranzitivní;

tranzitivní, ale ne reflexivní a nesymetrické;

reflexní, symetrické, ale ne tranzitivní;

reflexní, tranzitivní, ale ne symetrické;

nereflexní, symetrické, tranzitivní;

reflexní, symetrické, tranzitivní.