Množiny, relace a zobrazení
Množina
Set (mathematics)
Matematická struktura ve které se prvky neopakují, soubor objektů
Může být uspořádaná nebo neuspořádaná (vetšinou neuspořádaná)
Počet prvků definuje její velikost v případě, že je konečná. Jestliže máme dvě množiny A, B a existuje vzájemné přirazení prvků množiny B prvkům množiny A, pak říkáme, že množiny A, B mají stejnou mohutnost. Množina stejné mohutnosti jakou má množina přirozených čísel se nazývá spočetná. Nekonečná množina, která není spočetná se nazývá nespočetná (příkladem nespočetné množiny je množina všech reálných čísel. Naproti tomu množiny celých čísel Z a racionálních čísel Q jsou obě spočetné.)
Množinové operace (průnik, rozdíl, symetrický rozdíl (XOR), doplněk (nadmnožina bez podmnožiny) …)
Potenční množina – množina všech podmnožin (včetně prázdné a sama sebe), potenční množina množiny o n prvcích má 2n prvků.
Například celá čísla, reálná čísla, racionální čísla… to jsou všechno množiny.
Lze ji definovat výčtem nebo omezením
Uzavřenost množiny – když s prvky množiny provedu nějakou operaci, budou výsledkem zase prvky množiny.
Operace s množinami
Sjednocení
X ∪ Y = {x|x ∈ X ∨ x ∈ Y}
Průnik
X ∩ Y = {x|x ∈ X ∧ x ∈ Y}
Rozdíl
X \ Y = {x|x ∈ X ∧ x ∉ Y}
Symetrická diference množin
X ÷ Y = (X \ Y) ∪ (Y \ X)
Vlastnosti operací
Komutativnost
X ∪ Y = Y ∪ X
X ∩ Y = Y ∩ X
Rozdíl komutativní není!
Asociativita
(X ∪ Y) ∪ Z = X ∪ (Y ∪ Z)
(X ∩ Y) ∩ Z = X ∩ (Y ∩ Z)
Distributivnost
(X ∪ Y) ∩ Z = (X ∩ Z) ∪ (Y ∩ Z)
(X ∩ Y) ∪ Z = (X ∪ Z) ∩ (Y ∪ Z)
De Morganovy zákony
<m>overline{X ∪ Y} = overline{X} ∩ overline{Y}</m>
<m>overline{X ∩ Y} = overline{X} ∪ overline{Y}</m>
Relace
Binary relation
Symetrická – když mezi sebou prohodím prvky které jsou v relaci, budou stále v relaci (2 a 4 jsou sudá čísla, 4 a 2 jsou taky sudá čísla)
Antisymetrická – když je prohodím v relaci nebudou (2 < 4, ale 4 < 2 neplatí, vyjímkou je, pokud jsou oba prvky stejné, pak jaksi ani to prohození není znát)
-
Tranzitivní – Když je A v relaci s B, a B v relaci s C, tak i A je v relaci s C
-
Zobrazení
Zobrazení je přířazení prvků jedné množiny k prvkům z druhé. Funkce je speciálním případem zobrazení. Každé x má svoje y: každý prvek ze zobrazované množiny má přiřazený nějaký jeden prvek z druhé množiny (do které se zobrazuje). Rozlišují se tři základní typy:
Injektivní (prosté)
Každý prvek z Y má namapován nejvíce 1 prvek z X.
Surjektivní
Každý prvek z Y má namapován alespoň 1 prvek z X.
Bijektivní
Každý prvek z Y má namapován právě 1 prvek z X.
Svaz
Svaz je laicky uspořádatelná množina. U státnic ale řekneme, že množina X s relací R je svazem, pokud pro každou dvouprvkovou podmnožinu (v relaci R) lze definovat maximum a minimum. Btw. když jsou dva prvky stejné, tak to pořád je svaz (maximum i minimum jsou oba prvky).
Pozn.: tohle nebylo přímo zadané, ale bylo to na přijímačkách, takže dobré vědět.
Grupa
Grupa je množina s binární operací a je na ni uzavřená.
Grupa splňuje tři axiomy:
Asociativita: (a + b) + c = a + (b + c)
Existence neutrálního prvku: a + 0 = a
Existence inverzních prvků: a + (−a) = 0