2   Množiny a množinové operace
V přehledu matematických formalismů informatiky se v této lekci zaměříme na první základní „datový typ" matematiky, tj. na množiny. O množinách jste sice zajisté slyšeli už na základní škole, ale podstatou našeho předmětu je uvést povětšinou neformálně známé pojmy na patřičnou formální úroveň nutnou pro teoretické základy informatiky.
Stručný přehled lekce
* Uvedení množin a operací množinového kalkulu.
* Uspořádané fc-tice a kartézský součin.
* Porovnávania určení množin. Princip inkluze a exkluze.
* Relace a funkce mezi množinami.
□
Petr Hliněný, Fl MU Brno, 2017
1/23
Fl: IB000: Množiny, množinové operace
2.1   Pojem množiny Co je vlastně množinaľn
Na tuto otázku bohužel není zcela jednoduchá odpověď. . . • Naivní pohled: „Množina je soubor prvků a je svými prvky plně určena, "u
• Příklady zápisu množin   0,   {a, b},   {&, a},   {a, 6, a},   {{a, 6}},
{0, {0}, {{0}}},   {x | x je liché přirozené číslo}.
Petr Hliněný, Fl MU Brno, 2017
2/23
Fl: IB000: Množiny, množinové operace
Co je ale pak prvek?
Tady pozor, pojem prvku sám o sobě nemá matematický význam, svého významu totiž nabývá pouze ve spojení „být prvkem množiny11. Prvky množiny tak může být cokoliv, mimo jiné i další množiny.
Relativitu významu vztahu „prvek-množina" si můžeme přiblížit třeba na vztahu „podřízený-nadřízený" z běžného pracovního života. Tam také nemá smysl jen říkat, že je někdo podřízeným, aniž řekneme také jeho nadřízeného. Přitom i vedoucí je někomu ještě podřízený a naopak i ten poslední podřízený pracovník může být pánem třeba svého psa. Podobně je tomu s množinou jako „nadřízenou" svých prvků.
Ale přece jenom. .. v dobře definovaném kontextu lze (omezeně) mluvit o prvcích jako samostatných entitách. Formálně se například jedná o prvky pevně dané nosné množiny.
Petr Hliněný, Fl MU Brno, 2017
3/23
Fl: IB000: Množiny, množinové operace
Zápis množiny
Značení množin a jejich prvků:
• x £ M    „x je prvkem množiny M",
• 0   je prázdná množina {}.
Některé vlastnosti vztahu „být prvkem" jsou
• a£{a,6}, a0{{a,6}},  {a, 6} £ {{a, 6}},  na 0 0, 0 G {0}, 0 0 0,n
• rovnost množin dle prvků {a, b} = {&, a} = {a, 6, a},  {a, 6} 7^ {{a, b}}.c
Značení: Počet prvků (mohutnost) množiny A zapisujeme \A
. |0| = 0,   |{0}| = 1,   |{a, 6, c}| = 3,   |{{a, 6}, c}| = 2.
Petr Hliněný, Fl MU Brno, 2017
4/23
Fl: IB000: Množiny, množinové operace
Jednoduché srovnání množin
Vztah „být prvkem množiny" nám přirozeně podává i způsob porovnávání množin mezi sebou. Jedná se o klíčovou část, čili hlavní nástroj teorie množin.
Definice: Množina A je podmnožinou množiny B, právě když každý prvek A je prvkem B. Píšeme A C B nebo obráceně B ~D A.
Říkáme také, že se jedná o inkluzi. □
• Platí {a} C {a} C {a, b} £ {{a, &}},   0 C {0},
• A C B právě když A C B a A ^ B   (A je v7asŕA7/xpodmnožinou B).
Z naivní definice množiny pak přímo vyplývá následující:
Definice: Dvě množiny jsou si rovny A — B právě když A C B a B C A.
• Podle naivní definice jsou totiž množiny A b B stejné, mají-li stejné prvky.
• Důkaz rovnosti množin A = B má obvykle dvě části: Odděleně se dokáží inkluze A C B a B C A.
Petr Hliněný, Fl MU Brno, 2017
5/23
Fl: IB000: Množiny, množinové operace
Ukázky nekonečných množin
Značení: Běžné číselné množiny v matematice jsou následující
* N = {0,1, 2, 3,... } je množina přirozených čísel,
* Z = {..., —2, —1, 0,1, 2, 3,... } je množina celých čísel,
* Z+ = {1, 2, 3,... } je množina celých kladných čísel,
* (Q je množina racionálních čísel (zlomků).
* R je množina reálných čísel.
Tyto uvedené číselné množiny jsou vesměs nekonečné, na rozdíl od konečných množin uvažovaných v předchozím „naivním" pohledu. □
Pojem nekonečné množiny se přímo v matematice objevil až teprve v 19. století a brzy se s ním spojilo několik paradoxů ukazujících, že naivní pohled na teorii množin pro nekonečné množiny nedostačuje. My se k problematice nekonečných množin, Kantorově větě a Russelovu paradoxu vrátíme v závěru našeho předmětu v Lekci 11.
Petr Hliněný, Fl MU Brno, 2017
6/23
Fl: IB000: Množiny, množinové operace
r
2.2   Množinové operace
Sjednocení a průnik
Definice 2.1. Sjednocení U a průnik n dvou množin A, B definujeme
AuB   =   {x \ x e A nebo x G B}n , AD B   =   {x \ x E A a současně x £ B} .c
AU B
AnB
Příklady {a, 6, c} U {a, d} = {a, 6, c, d},   {a, 6, c} n {a, d} = {a}
Petr Hliněný, Fl MU Brno, 2017
7/23
Fl: IB000: Množiny, množinové operace
r
Sjednocení a průnik
AnB
AU B
{x | x G A nebo x G S} ,
{x | x G A a současně x G S} .
• Vždy platí „distributivita" A n (S U C) = (A n S) U (A n C)
a A u (s n C) = (A u s) n (A U C) □
• a také „asociativita" An(BnC) = (iílB)nC (stejně pro U) a „komutativita" in5 = Bni (stejně pro U). □
Definice: Pro libovolný počet množin indexovaných pomocí / rozšířeně
• Nechť Ai — {2'í} pro každé i G N. Pak Užgn^ je množina všech sudých přirozených čísel.c
• Nechť Bi = {x\xe'N,x>i} pro každé i G N. Pak fVN ^ =
{x | x G     pro nějaké i G /}
{x I x G Ai pro každé iG/}.[
Petr Hliněný, Fl MU Brno, 2017
8/23
Fl: IB000: Množiny, množinové operace
■r
Množinový rozdíl
Definice 2.2. Rozdíl \ a symetrický rozdíl A dvou množin A, B definujeme
A\B   =   {x \ x E A a současně x 0 £>}□ , AAB   =   (A\B) U (B\A) .□
A\B
AAB
• Příklady {a, 6, c} \ {a, 6, cř} = {c},    {a, 6, c}A{a, 6, cř} = {c, cř}.
• Vždy platí například A \ (B n C) = (A \ B) U (A \ C) apod.n
Definice: Pro libovolný počet množin indexovaných pomocí konečné /
A\ — {x | x G Ai pro lichý počet i G /} .
Petr Hliněný, Fl MU Brno, 2017
9/23
Fl: IB000: Množiny, množinové operace
Doplněk k množině
Definice: Nechť A C M. Doplňkem A vzhledem k M je množina A = M\A.
• Jedná se o poněkud specifickou operaci, která musí být vztažena vzhledem k nosné množině M!
Je-li M = {a, 6, c}, pak {a, b} = {c}. Je-li M = {a, b}, pak {a, 6} = 0. □
• Vždy pro ACM platí A — A („dvojí" doplněk).
• Vždy pro A, B C M platí AuB = InŠa AnB = ÄUB. (Viz Vennovy diagramy.)
Petr Hliněný, Fl MU Brno, 2017
10/23
Fl: IB000: Množiny, množinové operace
■r
Potenční množina
Definice 2.3. Potenční množina množiny A,
neboli množina všech podmnožin, je definovaná vztahem
2A = {B | B C A}.
□
• Platí například 2^6> = {0, {a}, {&}, {a, &}},
• 20 = {0},   2Í0'W> = {0, {0}, {{0}}, {0, {0}}}, □
Věta 2.4. Počeŕ prvků potenční množiny splňuje \2A\ = 2lALn
Důkaz: Důkaz jen stručně naznačíme (pro přesnější zápis důkazu by se použila matematická indukce z Lekce 3).
Jak vybereme jednu podmnožinu B C A? Například tak, že pro každý z \A prvků množiny A se nezávisle rozhodneme, zda jej zařadíme do B nebo ne. To jsou dvě možnosti pro výběr každého prvku b G A a podle principu nezávislých výběrů je celkový počet různých podmnožin množiny A roven
2A = 2 • 2 • ... • 2 = 2'/i' . □
Petr Hliněný, Fl MU Brno, 2017
11/23
Fl: IB000: Množiny, množinové operace
r
2.3   Kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, &}}.□
Fakt: Platí (a, 6) = (c, d) právě když a = c a současně 6 = d.c • Co je dle definice (a, a)?c (a, a) = {{a}, {a, a}} = {{a}, {a}} =
Definice 2.5. Kartézský součin dvou množin A,B definujeme jako množinu všech uspořádaných dvojic ze složek z A a B
Ax B = {(a, b) | a G A, 6 G 5}.
□
Příklady {a, 6} x {a} = {(a, a), (6, a)},
{c, d} x {a, 6} = {(c, a), (c, 6), (d, a), (d, 6)}.c
Platí 0xX = 0 = Xx0pro každou množinu X. □
Jednoduchá mnemotechnická pomůcka říká A x B
A • B
Petr Hliněný, Fl MU Brno, 2017
12/23
Fl: IB000: Množiny, množinové operace
Skládání součinu
Definice: Pro k G N, k > 0 definujeme uspořádanou k-tici (ai, • • • , a^) ind.
- (ai) ai,
- (ai, <22, • • • , a^, ai+i) = ((ai, a2, • • • , a^), a^+i).n
Fakt: Platí (ai, • • • , a^) = (&i, • * * 5 fyfc) právě když    = bi pro každé 1 < i < hj
Definice kartézského součinu více množin: Pro každé /c G N definujeme
Ai x A2 x • • • x Ak = {(tti, ^2, • • • , dk) \ clí e Ai pro každé 1 < i < k} .□
• Například Z3 = ZxZxZ = {(i, j, fc) | ij,k G Z}.
• Co je A°?n   {0}, neboť jediná uspořádaná 0-tice je právě prázdná 0.
Poznámka: Podle uvedené definice není kartézský součin asociativní, tj. obecně nemusí platit, že A x (B x C) = (A x B) x C.n
V matematické praxi je někdy výhodnější uvažovat upravenou definici, podle níž součin asociativní je. Pro účely této přednášky není podstatné, k jaké definici se přikloníme. Prezentované definice a věty „fungují" pro obě varianty.
Petr Hliněný, Fl MU Brno, 2017 13/23 Fl: IB000: Množiny, množinové operace
2.4   Porovnávání a určení množin
Věta 2.6. Pro každé dvě množiny A, B C M platí A U B = ÄnB. □
Důkaz v obou směrech rovnosti (viz ilustrační obrázek).
• AU B C AnB: □
* Pro x G M platí x G A U B, právě když x ^ AU B, neboli když zároveň
x 0 A a x 0 B.
* To znamená x G A a zároveň x G S, z čehož vyplývá požadované
• AU B DÄHB:
* Pro x G M platí      AílB, právě když x G A a zároveň x £ B, neboli když zároveň x ^ A b x ^ B.
* To znamená x ^ AU B, z čehož vyplývá požadované x G A U B.
□
Petr Hliněný, Fl MU Brno, 2017
14/23
Fl: IB000: Množiny, množinové operace
Věta 2.7. Pro každé tři množiny A, B, C platí
A \ (B n C) = (A \ B) U(A\C).
Důkaz (viz ilustrační obrázek).c
• A\(BHC) C (A \ B) U(A\C):
* Je-li x G A \ (B H C), pak x G A a zároveň x 0 (B n C), neboli x ^ B nebo x ^ C.
* Pro první možnost máme pro druhou x E (A \ C).ľ
• Naopak A\(BnC) D (A \ B) U(A\C)\
* Je-li xe(A\B) U (A \ C), pak x G (A \ B) nebo x G (A \ C).
* Pro první možnost máme x G A a zároveň x ^ B,
z čehož plyne x G A a zároveň x^(BnC),a tudíž xGÍ\(Bn C).n
* Druhá možnost je analogická.
□
Petr Hliněný, Fl MU Brno, 2017
15/23
Fl: IB000: Množiny, množinové operace
Charakteristický vektor (pod)množiny
V případech, kdy všechny uvažované množiny jsou podmnožinami nějaké konečné nosné množiny X, což není neobvyklé v programátorských aplikacích, s výhodou využijeme následující reprezentaci množin.
Definice: Mějme nosnou množinu X — {xi, £2, • • • 3 %n}- Pro AC X definujeme charakteristický vektor xa jako
Xa — (ci, c2,..., cn), kde q = 1 pro x\ £ A a q = 0 jinak.c
• Platí A — B právě když xa = Xb-
• Množinové operace jsou realizovány „bitovými funkcemi"
sjednocení ^ OR, průnik ^ AND, symetrický rozdíl ^ XOR.
Petr Hliněný, Fl MU Brno, 2017
16/23
Fl: IB000: Množiny, množinové operace
r
Princip inkluze a exkluze
Tento důležitý a zajímavý kombinatorický princip je někdy také nazýván „princip zapojení a vypojení
Věta 2.8. Počet prvků ve sjednocení dvou či tří množin spočítáme:
AuB = A + B - AnB
Aubuc = A + B + c - AnB - Anc - Bnc + AnBnc
□
A
A
b
b
Všimněte si, že větu lze stejně tak využít k výpočtu počtu prvků v průniku množin
Petr Hliněný, Fl MU Brno, 2017
17/23
Fl: IB000: Množiny, množinové operace
■r
Příklad 2.9. Z 1000 televizí jich při první kontrole na výrobní lince má 5 vadnou obrazovku, 10 je poškrábaných a 12 má jinou vadu. Přitom 3 televize mají současně všechny tři vady a 4 jiné jsou poškrábané a mají jinou vadu. Kolik televizí je celkem vadných? í
Řešení: Dosazením \A\ = 5, \B\ = 10, \C\ = 12, \A H B n C\ = 3, \A H B\ = 3 + 0, A H Cl =3 + 0, |£ H C\ = 3 + 4 do Věty 2.8 zjistíme výsledek 17. □ □
Poznámka. Jen stručně, bez důkazu a bližšího vysvětlení, si uvedeme obecnou formu principu inkluze a exkluze:
n
0^/C{l,...,n}
n a
(Jeho znalost nebude v předmětu vyžadována.)
Petr Hliněný, Fl MU Brno, 2017
18/23
Fl: IB000: Množiny, množinové operace
■r
2.5   Relace a funkce
Vedle množin jsou dalším důležitým základním „datovým typem" matematiky relace, které nyní zavedeme a kterým vzhledem k jejich mnohotvárnému použití v informatice věnujeme významnou pozornost i v příštích lekcích.
Definice 2.10. Relace mezi množinami Ai,^,--- ,pro k £ N, je libovolná podmnožina kartézského součinu
R ^ Ai x A2 x • • • x Ak .□
Pokud A\ — A2 — • • • = Ak = A, hovoříme o k-ární relaci R na A.
Příklady relací.
• {(1, a), (2, a), (2, b)} je relace mezi {1, 2, 3} a {a, b}.
• {(i, 2 • i) | i G N} je binární relace na N.c
• {(i, j, i + j) | i, j G N} je ternárnírelace na N.
• {3 • z | z G N} je unární relace na N.c
• Jaký význam vlastně mají unární a nulární relace na A?
Petr Hliněný, Fl MU Brno, 2017
19/23
Fl: IB000: Množiny, množinové operace
Funkce mezi množinami
Definice 2.11. (Totální) funkce z množiny A do množiny B
je relace / mezi A a B taková, že pro každé x G A existuje právě jedno y G B
takové, že (x, y) G /.□
Množina A se nazývá definiční obor b množina B obor hodnot funkce /.
Neformálně řečeno, ve funkci / je každé „vstupní" hodnotě x přiřazena jednoznačně „výstupní" hodnota y. (V obecné relaci počty „přiřazených" dvojic neomezujeme...)
Petr Hliněný, Fl MU Brno, 2017
20/23
Fl: IB000: Množiny, množinové operace
■r
Značení: Místo (x, y) G / píšeme obvykle f (x) = y.
Zápis / : A —> B říká, že / je funkce s def. oborem A a oborem hodnot B.c Funkcím se také říká zobrazení.
Příklady funkcí jsou třeba následující.
• Definujeme funkci / : N —> N předpisem f (x) = x + 8.
Pak / = {(>, x + 8) | x G N}.n
• Definujeme funkci plus :NxN^N předpisem plus (i, j) = i + j. Pak plus = {(i, j, i + j) | i, j G N}.
Petr Hliněný, Fl MU Brno, 2017
21/23
Fl: IB000: Množiny, množinové operace
^Parciální (částečné) funkce
Definice: Pokud naši Definici 2.11 upravíme tak, že požadujeme pro každé x e A nejvýše jedno y G B takové, že (x, y) G /, obdržíme definici parciální funkce z A do B.
V parciální funkci / nemusí být pro některé „vstupní" hodnoty x funkční hodnota definována (viz například f (2) v uvedeném obrázku).
Pro nedefinovanou hodnotu používáme znak _L
Petr Hliněný, Fl MU Brno, 2017
22/23
Fl: IB000: Množiny, množinové operace
Nasleduje několik příkladů parciálních funkcí. • Definujeme parciální funkci / : Z —> N předpisem
f(x) =
3 + x jestliže x > 0. _L jinak.
Tj. / = {(x,3 + x) | x G N}. □
Také funkce / : R —> R daná běžným analytickým předpisem
/(z) logx
je jen parciální - není definována pro x < O.c
Co je relace, přiřazující lidem v ČR jejich (česká) rodná čísla?
Petr Hliněný, Fl MU Brno, 2017
23/23
Fl: IB000: Množiny, množinové operace