Základy teorie množin

Základy teorie množin Teorie Výběr základních pojmů: • • • • • • • • • • • •

Množina Podmnožina Prázdná množina Označení běžně používaných množin Množinová algebra (sjednocení, průnik, rozdíl) Doplněk množiny Potenční množina Kartézský součin Kartézská mocnina N-nární relace, binární relace, inverzní relace Zobrazení (na, do, z na, z do) N-nární operace

Výběr teorie: 1. Inkluze. Odlišení ⊆ a ⊂ X⊆Y říkáme, že X je podmnožinou nebo částí množiny Y jestliže (∀u)(u∈X → u∈Y) X⊂Y říkáme, že X je vlastní podmnožinou nebo vlastní částí množiny Y jestliže platí (X⊆Y) ∧ (X≠Y) Obecně o vlastnostech operací Zde si všimneme obecných vlastností operací aplikovaných na algebru množin. Reflexivita.............. A⊆A, A = A, …. pro ⊆ a = Symetrie................. A = B a B = A, ….. pro = Tranzitivita............ (X⊂Y) & (Y⊆Z) → (X⊂Z), (X⊆Y) & (Y⊆Z) → (X⊆Z), … pro ⊂, ⊆ Komutativnost...... X∪Y= Y∪X, X∩Y= Y∩X, …. pro ∩ a ∪ Asociativnost ........ (X∩Y) ∩Z = X∩ (Y∩Z), …. pro ∩, možné i pro ∪ Distributivnost....... X∩ (Y∪Z) = (X∩Y) ∪ (X∩Z), … pro vazbu mezi ∩ a ∪ X∪ (Y ∩Z) = (X∪Y) ∩ (X ∪Z)

N – nární relace Buď n přirozené číslo, A1, A2, …, An množiny. Relací ℜ mezi množinami A1, A2, …, An nazýváme každou podmnožinu ℜ ⊆ A1 x A2 x … x An . Jestliže platí (∀i)Ai = A, pak relaci ℜ ⊆ An nazýváme n-nární relací na A. Buďte X, Y neprázdné množiny. Binární relací ℜ mezi množinami X, Y (v tomto pořadí) nazveme každou podmnožinu kartézského součinu X x Y. Binární relace se mohou vyznačovat následujícími vlastnostmi (ověřit na =, <, >, ≤… v Z):

Symetrické a antisymetrické relace Binární relace ℜ na množině A je symetrická, jestliže ℜ⊆ℜ-1 , tj. ∀a,b∈A (aℜb ⇔ bℜa) Binární relace ℜ na množině A je antisymetrická, jestliže platí ∀a,b∈A (aℜb ∧ bℜa ⇒ a = b ) Vlastnosti: 1. Sjednocení, průnik a součin symetrických binárních relací na A je opět symetrická binární relace na A (důkaz indukcí). Př. 1. Relace ≠ na Z je symetrická 3≠4 ⇔ 4≠3 . 2. Relace dělitelnosti na N je antisymetrická (ale ne na Z). 3. Relace <, ≤, >, ≥ na Z+ jsou antisymetrické.

Tranzitivní relace Tranzitivní binární relace na A jsou relace pro které platí: ∀a,b,c∈A (aℜb ∧ bRc ⇒ aℜc ). Vlastnosti: 1. Binární relace na A je tranzitivní, právě když inverzní binární relace ℜ-1 je tranzitivní. Př. Jaké vlastnosti má binární relace < na množině Z ? Buďte a, b, c ∈ Z, potom: a
¬(a < a) (a < b) → ¬(b < a) (a < b) ∧ (b < c) → (a < c )

Dichotomické/souvislé relace Binární relace ℜ na množině A se nazývá dichotomická (souvislá) jestliže pro ni platí ℜ∪ℜ-1 = A2 . To je totéž jako ∀a,b∈A (aℜb ∨ bℜa) Vlastnosti: 1. ℜ je dichotomická, právě když ℜ-1 je dichotomická. 2. každá dichotomická binární relace je reflexivní. Př. 1. Úplná množina na A je dichotomická. 2. Relace ≤, ≥ jsou na Z, Q, R dichotomické. 3. Průnik dichotomických relací nemusí být dichotomický. Např. pro ℜ1 ={(a,a), (a,b), (b,b)} ℜ2 = {(a,a), (b,a), (b,b)} to platí. ℜ1 ∩ ℜ2 = {{(a,a), (b,b)} Ekvivalence Každá reflexivní, symetrická a tranzitivní binární relace na A se nazývá ekvivalencí na A. ∀a∈A platí aℜa, ∀a,b∈A (aℜb ⇔ bℜa), ∀a,b,c∈A (aℜb ∧ bℜc ⇒ aℜc ).

Zobrazením f množiny X do množiny Y nazýváme každou relaci f⊆ X x Y, pro kterou platí: každému prvku x∈X je přiřazen nejvýše jeden takový prvek y∈Y, že uspořádaná dvojice (x,y)∈f. Významově je tato definice plně v souladu s definicí na začátku kapitoly, definice se postavila nad relacemi. Pochopitelně, jestliže je zaručeno, že v zobrazení do každému prvku y množiny Y náleží prvek x množiny X takový, že (x,y)∈f , potom se jedná o zobrazení X Y. Zobrazením f z množiny X do množiny Y nazýváme každou relaci f⊆ X x Y, pro kterou platí: existuje alespoň jeden takový prvek x∈X ke kterému je přiřazen prvek y∈Y tak, že uspořádaná dvojice (x,y)∈f. Poznámka: 1. Zobrazení f z množiny X do množiny Y můžeme zapsat jako f: X Y. 2. Jestliže při zobrazení f : X Y je každému prvku x∈X přiřazen právě jeden prvek y∈Y, přechází toto zobrazení na zobrazení X do Y, tedy X Y. 3. V zobrazení f : X Y ne každý prvek y∈Y má v X přiřazen alespoň jeden vzor. Nechť pro množiny X,Y platí f: X Y. Jestliže každému prvku y∈Y náleží alespoň jeden vzor x∈X, potom mluvíme o zobrazení z množiny X na množinu Y a zapisujeme ve tvaru f : X Y. Poznámka: 1. Je zřejmé, že ne každý prvek x∈X má v množině Y svůj obraz. 2. Jestliže při zobrazení f: X Y je každému prvku x∈X přiřazen právě jeden prvek y∈Y a každý prvek y∈Y má alespoň jeden vzor x∈X, mluvíme o zobrazení X Y. 3. Zobrazení f: X Y a X Y se nazývají surjekcí (nakrytí). 4. Zobrazení f se nazývá prosté nebo injekcí (injekce – vložení), jestliže každé dva různé vzory x1 ≠ x2 mají různé obrazy f(x1)≠ f(x2) 5. Prosté zobrazení X Y se nazývá bijektivní (vzájemně jednoznačné, jedno-jedno korespodentní) zobrazení (bijekce je injekce a surjekce zároveň). 6. Zobrazení do a na mezi množinami X,Y je zvláštním případem binární relace mezi množinami X, Y.

N – nární operace Buď A množina a n přirozené číslo. Zobrazení f: An A nazýváme n–ární algebraickou operací na množině A. Číslo n∈N nazýváme četností operace. Pro n = 0 definujeme nulární operaci na A jako zvolení určitého prvku v množině A. Příkladem unární operace (n = 1) v množině Z je (-a), kde a∈Z. Tato unární operace je převodem celého čísla a na opačné. Další operace poskytuje algebra množin. Příkladem binární operace f: Z2 Z na Z jsou operace "sčítání, násobení, odčítání, dělení, …" Tyto operace mají dva operandy a píšou se ve tvaru a1 ⊕ a2 , kde ⊕ je symbol obecné binární operace (+, -, …).

Příklady: Podmnožiny, operace nad množinami 1. Zapište všechny podmnožiny množin {2,7}, {5,7,9}, {0}, φ 2. Napište všechny podmnožiny množiny A = {-3, 0, 0.5, 1}, které jsou současně podmnožinou množiny N Z {x∈R ; x < 1} 3. Zjistěte, které z následujících množin se rovnají {x∈Z ; x > 0}, {x∈R ; x ≤ 0}, {x∈N ; x-2< 2}, N, {0}, {1,2,3}, 3

{x∈R ; 3 x = x}, {x∈R ; x ≥ 0} 4. Určete doplněk množiny B v množině A, když: A = N, B ={x∈N ; x> 2} A = Z, B = {x∈Z ; x> 2}

5.

6. 7.

8.

A = R, B = {x∈R ; x 2 = - x} A = R, B = {x∈R ; x-1< 0} A = R, B = {x∈R ; x-2≥ 0} Stanovte průnik a sjednocení množin X, Y X = {-2,0,5,7}, Y = {-3,-1,0,4,7,9} X = {x∈Z ; x < -5} Y = {x∈Z ; x ≤ -1} X = N, Y = {x∈Z ; x< 3} X = N, Y = {x∈Z ; x <1} Specifikujte kdy je: A∩B=A, A∪B=A, B'A=A, B'A=φ, A∪B= A∩B Nalezněte všechny množiny X pro které je A X = B, jestliže A = {x∈N ; x ≤ 2}, B = { x∈N ; x <4} A = φ, B = {1,2} A = {1}, B = {2,3} Stanovte rozdíly A-B pro následující případy: A = {-3,-1,0,5}, B = {-1,0,1} A = { x∈Z ; x ≤ -2}, B = { x∈Z ; x <-7} A = Z, B = N A = N, B = { x∈Z ; x ≤ 2} A = Z-, B = { x∈Z ; x-1 <3}

9. Definujte: • sjednocení množin • kartézský součin množin • symetrickou relaci • ekvivalenci • injektivní zobrazení 10. Rozhodněte, zda platí 1. 2. 3. 4. 5.

A ∪ (B ∪ C) = (A ∪ B) ∪ C (A – B) ∩ C = (B – A) ∩ C A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A – (B ∪ C) = (A – B) ∩ (A – C) A × (B ∩ C) = (A × B) ∪ (A × C)

6. ∅ ∈ ∅ 7. ∅ ⊆ P(∅) 8. (∅,∅) ∈ {∅} × {∅} 9. {∅} ⊆ {{∅}} 10. |P(∅)| = 1 Kartézský součin a relace 1. Nalezněte kartézský součin A x B x C , kde A = {1, /, <}, b = {+, -, ?, *}, C = {0, 1, 2, 3}. 2. Navrhněte algoritmus, pomocí kterého snadno vypočtete úplný kartézský součin množin A1, A2, …, An . 3. Uveďte případy unárních a binárních operací v množině N. 4. Uveďte případy binárních relací v množině R. 5. Je dána entita oddělení = (název, budova, číslo posch., krestni_ved, prijmeni_ved ) svou populací. Napište kartézský součin jehož je populace podmnožinou. oddělení: název budova čís. posch. krestni_ved prijmeni_ved Ryby Obuv Hračky Potraviny Oblečení

1 1 2 2 3

1 2 1 2 1

Jan Petr Ivan Oldřich Tomáš

Moudrý Spálený Hlína Vrtkavý Smutný

Řešení: 1. A x B x C = {(x,y,z) x∈A, z∈B, y∈C} = { …. } 2. Jde o postupný výpočet n-tic (a1, a2, …an) pomocí trojúhelníkového přístupu. Začne se první pozicí a1 . Na tuto pozici dám první prvek množiny A1 . Na druhou pozici v n-tici dám první prvek druhé množiny, … , až na poslední pozici an dám první prvek množiny An . Vynikne tak první n-tice. Teď začnu postupovat od an . Na pozici an dám postupně další prvky množiny An. Vznikne tak dalších n-1 n-tic. V každé z těchto n-tic měním na předposlední pozici zbývající prvky množiny An-1. Postup dál směrem k A1 je již zřejmý. 3. -, +, *, / 4. =, <, >, ….. 5. Nejdříve stanovíme definiční obory jednotlivých atributů: Dnázev = {Ryby, Obuv, Hračky, Potraviny, Oblečení} Dbudova = {…} Dčís. posch. = {…} Dkrestní_ved = {…} Dprijmení_ved = {…} Potom platí, že oddělení ∈[ Dnázev x Dbudova x Dčís. posch x Dkrestní_ved x Dprijmení_ved ] Binární relace 1. Udělejte formální zápis dělitelnosti celých čísel a|b, kterou čteme …. a dělí b beze zbytku, jako binární relace na Z. R⊆ Z x Z R={(a,b) | a,b∈Z ∧ ∃c∈Z (b = c.a)}

2. Jaké vlastnosti má relace ≥ na množině Z ? a ≥ a ............................................... je pravdivé relace je reflexivní platí-li a ≥b potom b ≥ a platí ... relace je symetrická (a ≥ b) → (b ≥ a) je-li a ≥ b , b ≥ c potom je a ≥ c relace je tranzitivní (a ≥b) ∧ (b ≥ c) → (a ≥ c ) 3. Zdůvodněte vlastnosti dvojic binárních relací z množiny <, >, ≤, ≥, =, ≠ na Z. , ≤ a ≥ = a ≠ < a = ……. n-Nární relace 1. Na základě pochopení definice n-nární relace popište co jsou procedury pro třídění posloupnosti celých čísel. 2. Jak se dá klasifikovat tabulka Oddělení v konfrontaci s definicí n-nární relace? Není to náhodou n-nární relace, n=5 ? Zdůvodněte.

Řešení 1. Procedura třídění zpracovává každou výchozí n-tici celých čísel (x1, x2, …, xn )∈ Z x Z …x Z = Zn a transformuje tuto n-tici do setříděné n-tice (x'1, x'2, …, x'n ), která je opět z množiny Zn . Jelikož je množina setříděných n-tic podmnožinou množiny Zn , je jasné, že zřizuje jistou n-nární relaci "ℜ-Procedura setřídění". 2. Ano, tabulka Oddělení prezentuje jistou n-nární relaci, protože je podmnožinou součinu Dnázev x Dbudova x Dčís. posch x Dkrestní_ved x Dprijmení_ved . Takto vytvořená tabulka je populací entity Oddělení (klasický přístup k modelování reality), a tak je vlastně prezentována Db-relace1 v Coddově algebře ( Coddova algebra je postavena na nosiči, kterým je množina Db-relací). Zobrazení: 1. Zdůvodněte, že funkce y = x2 pro Dx =R není prosté zobrazení. Určete definiční obor tak, aby vzniklo prosté zobrazení a nalezněte k němu inverzní zobrazení. 2. Určete Dx pro zobrazení y = x . Rozhodněte, zda je toto zobrazení prosté. 3. Pomocí formálního jazyka teorie množin zapište operace A∪B, A-B, A∩B. 4. Graficky znázorněte následující typy zobrazení: z množiny A do množiny B množiny A do množiny B z množiny A na množinu B množiny A na množinu B 5. Definujte následující pojmy: kartézská mocnina, potence množiny, mohutnost kartézského součinu. Nechť A, B, C jsou neprázdné množiny o mohutnostech |A| = m, |B| = n, |C| = k, kolik prvků mají následující množiny: A x B x C; A x B x C; A x B x C x A; P(A) x P(B); 1

Db-relace je vlastně databázová relace

P(A x B).

Řešení 1. Funkce není prosté zobrazení, ačkoliv je to zobrazení na, protože (x) a (-x) mají stejný obraz. Prosté bude v Dx = (- ∞ ,0) a (0, + ∞ ) . V druhém případě (žlutě) k zobrazení existuje inverzní zobrazení y = x2 . 2. Pro Dx =R není prosté. 3. A∪B= {x(x∈A) ∨ (x∈B)} A-B ={x(x∈A) ∧ (x∉B)} A∩B ={x(x∈A) ∧ (x∈B)} závorky je možno vynechat 4. Operace lze zakreslit následovně:

z

z

do

do

na na

N-Nární operace 1. Uveďte případy unárních a binárních operací na množině N. 1. Nechť je pro a, b, k, z ∈ Z dána běžně používaná funkce Mod (a,b) = z, kde z je dáno vztahy: a = k.b + z , 0≤ z < b (z je tzv. nejmenší nezáporný zbytek). Vysvětlete, že Mod je binární operace. 2. Výběr podřetězce y z řetězce x je zapsán notací Mid(i,j,x), kde i…je pozice zleva od níž se začne vybírat, j…je počet vybraných znaků x…je řetězec z něhož zleva se vybírá. Co je Mid(i,j,x), když i,j∈Z a x∈Σ* ? Je to operace nebo relace ? Σ je abeceda řetězců, Σ* je množina všech řetězců definovaných nad abecedou Σ. 3. Buďte A,B,C čtvercové matice o rozměru n. Je procedura Součet (A,B,C,n) 3-nární operací? Řešení 1. 2. Výsledkem operace Mod je nezáporný zbytek z∈Z. Mod je skutečně binární operací, protože: jde o zobrazení f: Z x Z Z , tedy Z2 Z , kde f: ∀(a, b, k, z ∈ Z) ( a = k.b + z , 0≤ z < b )

3. Především je to zobrazení Z x Z x Σ* Σ* Současně je to 3-nární operace nad * množinami Z a Σ . Není to relace podle definice 3-5. 4. Ano, je. Jestliže je M množinou všech čtvercových matic o rozměru n∈N, potom f: C=A+B: M3 M je 3-nární operace v množině M.

Použité zdroje: Přednášky z předmětu Teoretické základy informatiky (prof. RNDr. Milan Mišovič, CSc.) Metodická elektronická podpora do předmětu TZI

Doporučené zdroje: Přednášky z předmětu Teoretické základy informatiky (prof. RNDr. Milan Mišovič, CSc.) Metodická elektronická podpora do předmětu TZI (dostupná pod kartou předmětu v UIS) !!! Internetové zdroje (výběr v adresáři tohoto dokumentu)