Relace uspořádání

příkady (řešené)   |   neřešené úlohy   |   řešení 



Výroková logika

Výrokové formy

Množinové vztahy

Množinové operace

Složené výrokové formy

Kartézský součin

Binární relace

Relace ekvivalence

Relace uspořádání

Relace zobrazení






Vytvoř písemku

Příklady (řešené)

1. Relaci R znázorněnou na uzlovém grafu doplňte tak, že vytvoříte lineárně uspořádanou množinu.


Řešení:

Z grafu plyne K = {1, x, 3, z, 5}, R = {(3,1), (z, x), (5, z)}.
Lineárně uspořádanou množinu (K, R) vytvoříme, jestliže v množině K bude
definována relace lineárního uspořádání. Přičemž lineární uspořádání je relace, která splňuje vlastnosti:
a) antisymetrie, b) tranzitivnosti, c) konektivnosti.

Tzn.
a)  a, b  K : [a ≠ b  (a, b)  R] => (b, a)  R,
b)  a, b, c K : [(a,b) R (b,c)  R] => (a,c)  R,
c)  a, b  K :  a ≠ b => [(a, b)  R V (b, a)  R].

Relace je současně antisymetrická a souvislá (tj. konektivní),
pak a, b  K : a ≠ b => [(a, b) R(b, a)  R].
Na uzlovém grafu znázorníme uvedenou vlastnost tak, že každé dva různé uzly jsou spojeny právě jednou orientovanou hranou, přičemž vzhledem k řešení úlohy musí být zachována tranzitivnost. Ostatní vlastnosti relace R nejsou splněny, tzn. že R není ani reflexivní, ani antireflexivní; na uzlovém grafu se musí objevit alespoň jedna, nejvýše však čtyři smyčky.
Relace splňující uvedené podmínky jsou např. tyto:
R1 = {(5,z), (3,1), (z,x), (5,x), (5,1), (1,x), (1,z), (5,3), (3,z), (3,x), (x,x)},
(K,R1) = {5,3,1,z,x}


R2 = {(6,z),(3,1),(z,x),(6,x),(5,3),(5,1)(z,3),(z,1),(3,x),(x,1),(x,x),(z,z)},   (K, R2) = {5,z,3,x,1}


2.  V množině A = {k,l,m,n} je definována relace U = {(m,n), (l,l), (I, k), (k,n), (l,n)}. Určete všechny její vlastnosti a nazvěte ji. Bude-li to možné, doplňte ji minimálním počtem uspořádaných dvojic tak, aby vznikla relace lineárního uspořádání. Zapište ji.

Řešení:
Relaci U určenou výčtem prvků znázorníme uzlovým grafem:

Relace není reflexivní (nejsou smyčky u všech uzlů).
Relace není antireflexivní (je smyčka alespoň u jednoho uzlu).
Relace není symetrická (např. ke hraně (m,n) není (n,m)).
Relace je antisymetrická (každé dva různé uzly jsou spojeny nejvýše jednou hranou).
Relace je tranzitivní (podmínka definice je splněna).
Relace není konektivní (každé dva různé uzly nejsou spojeny alespoň jednou hranou).
Relace U je relací uspořádání.
Máme-li vytvořit relaci lineárního uspořádání, pak relace U musí být i konektivní. Tato vlastnost bude splněna doplněním uspořádaných dvojic mezi uzly k, m a I, m; tím vzniknou 3 nové relace U1
 až U3.
a)  U1 = {(m,n),(l,l),(l,k),(k,n),(l,n),(l,m),(k,m)}, (A,U1) = {l,k,m,n}; I je první a n poslední prvek (A,U1);
b)  U2 = {(m,n),(l,l),(l,k),(k,n),(l,n),(l,m),(m,k)}, (A,U2) = {I,m,k,n}; I je první a n poslední prvek (A,U2);
c)  U3 = {(m,n),(l,l),(l,k),(k,n),(m,l),(m,k),(l,n)}, (A,U3) = {m,I,k,n}; m je první a n poslední prvek (A,U3).




Neřešené úlohy :


1. Rozhodněte o typu relace uspořádání R, jestliže R M x M, kde M = {3,4,5,6},
R = {(4,3),(5,3),(5,4),(6,6),(3,3)}



2. Rozhodněte o typu relace uspořádání R, jestliže R M x M, kde M = {3,4,5,6},
R = {(6,3),(6,5),(5,4),(6,4)}


3. Rozhodněte o typu relace uspořádání R, jestliže R M x M, kde M = {3,4,5,6},
R = {(4,4),(5,5),(6,6),(3,5),(3,3)}



4. Rozhodněte o typu relace uspořádání R, jestliže R M x M, kde M = {3,4,5,6},
R = {(5,5),(5,4),(3,5),(3,4),(6,5),(6,4),(6,3)}



5. Rozhodněte o typu relace uspořádání R, jestliže R M x M, kde M = {3,4,5,6},
R = {(6,5),(3,6),(3,5),(4,6),(4,5),(4,3)}



6. Rozhodněte o typu relace uspořádání R, jestliže R M x M, kde M = {3,4,5,6},
R = {(3,3),(4,4),(5,5),(6,6),(5,4),(5,3),(5,6),(4,3),(4,6),(6,3)}



7. Ověřte, zda relace U = {(4,1), (2,4), (3,4), (2, 3), (3,1), (2,1)} v množině M = {1,2,3,4} je ostré lineární uspořádání; je-li tomu tak, zapište ostře lineárně uspořádanou množinu.


8. V množině T = {1,2,3,4,5} vytvořte relaci R lineárního uspořádání. Tuto relaci znázorněte na uzlovém grafu a zapište ji výčtem prvků.


9.  Uzlové grafy následujících relací doplňte tak, aby představovaly relace ostrého lineárního a lineárního uspořádání.




10. V množině L jednociferných lichých přirozených čísel zapište relaci lineárního uspořádání U,  vytvořte lineárně uspořádanou množinu (L,U).


11.  Vytvořte relaci U lineárního uspořádání v množině A = {3,4,5,6,7}, víte-li, že prvek 6 je prvním a prvek 3 třetím prvkem (A, R).


12.  Zapište výčtem prvků všechny relace U ostrého lineárního uspořádání v množině M = {xN, x | 4}. Je každé z těchto uspořádání dobré?


13.  Vytvořte alespoň tři relace ostrého lineárního uspořádání v množině A = {xC; x | 5} a graficky je znázorněte.


14.  V množině A = {k, I, m, n, o} vytvořte relaci ostrého lineárního R1 a lineárního uspořádání R2; zapište (A, R2).


15.  V množině B = {xC; 2  ≤ x < 7} vytvořte všechny relace ostrého lineárního uspořádání, platí-li, že sudé číslo předchází před lichým a větší sudé před menším sudým.


16. V množině A = {1,2,..., 6} je definována relace T = {(2, 2), (1, 5), (3, 2), (3,3), (4,4), (1,1), (6, 5), (6,6), (5,5)}. Určete všechny její vlastnosti a pojmenujte ji.



17.  Co musí splňovat množina M, abychom ji mohli nazvat  uspořádanou množinou?



18.  Nechť (A, R) je lineárně uspořádaná množina. Jak se nazývá prvk a A , jestliže platí :
  x A : x ≠ a  =>  a


19. 
Nechť (A, R) je lineárně uspořádaná množina. Jak se nazývá prvk a A , jestliže platí :
  x A : x ≠ a  =>  x


Řešení :


1.  Relace uspořádání.


2.  Relace ostrého uspořádání.


3.  Relace neostrého uspořádání.


4.  Relace lineárního uspořádání.


5.  Relace ostrého lineárního uspořádání.


6.  Relace neostrého lineárního uspořádání.


7.  Relace U je AR, AS, T, K; M   = {2,3,4,1} je ostře lineárně uspořádaná množina. K řešení úlohy můžete využít uzlového grafu.



8.
  Např.: R = {(3,1), (3,2), (3,4), (3,5), (4,1), (4, 2), (4,5), (2,1), (2, 5), (1,5), (2,2)}.




9.  a) Nemá řešení, daná relace již není tranzitivní,
b) Např.: ostré lineární uspořádání          lineární uspořádání




10. L = {1,3,5,7,9}; např.:
U = {(3,1), (3,5), (3, 7), (3,9), (9,1), (9,5), (9,7), (5,1), (7,1), (7,5), (5,5)},
(L, U) = {3,9,7,5,1}.



11.  Např.: U = {(6, 3), (6,4), (6,5), (6, 7), (4,3), (4,5), (4, 7), (3,5), (3,7), (5, 7), (4,4)}.



12. 
U1 = {(l,2), (1,4), (2,4)}, U2 = {(1,2), (1,4), (4,2)},
U3 = {(2,1),(2,4),(1,4)}, U4 = {(2,1), (2,4), (4,1)},
U5 = {(4,1),(4,2), (2,1)}, U6 = {(4,1),(4,2), (1,2)}.



13.  A = {1, -1,5, -5}, tj. např.:



14.  R2 = R1 {(l, l), (k, k)}  tj. (A,R2) = {o,n,m,l,k}.



15.  R1 = {(2,3), (2,5), (4,5), (4,3), (6,3), (6,5), (6,4), (6,2), (4,2), (3,5)},.....
R2 = {(2,3), (2,5), (4,5), (4,3), (6,3), (6,5), (6,4), (6,2), (4,2), (5,3)}.



16. Vlastnosti relace T: R, AS, T; T je relace neostrého uspořádání.


17.  V množině M musí být definována relace uspořádání.


18.  První prvek množiny A.


19.  Poslední prvek množiny A.