3   Množiny, 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.
* Posloupnosti a rekurentní vztahy.
Petr Hliněný, Fl MU Brno, 2013
1/21
Fl: IB000: Množiny, množinové operace
3.1   Pojem množiny
Co je vlastně množinaľc
Na tuto otázku bohužel není zcela jednoduchá odpoveď. .. • Naivní pohled: „Množina je soubor prvků a je svými prvky plně určena, "c
• Příklady zápisu množin   0,   {a, b},   {b, a},   {a, b, a},   {{a, b}},
{0, {0}, {{0}}},   {x | x je liché přirozené číslo}.
Petr Hliněný, Fl MU Brno, 2013
2/21
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žiny". Prvky množiny tak může být cokoliv, mimo jiné i dalším 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ů, c
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, 2013
3/21
Fl: IB000: Množiny, množinové operace
Značení množin a jejich prvků:
• x G M    „x je prvkem množiny M",
• 0   je prázdni množina {}. c
Některé vlastnosti vztahu „být prvkem" jsou
• a£{a,6},  a0{{a,6}},  {a, 6} G {{a, 6}},    a 0 0, 0 G {0}, 0 0 0,c
• rovnost množin dle prvků {a, 6} = {6, a} = {a, 6, a}, {a, b} ^ {{a,b}}.c
Značení: Počet prvků (mohutnost) množiny A zapisujeme \A\.
• |0| = 0,    |{0}| = 1,   \{a, b, c}\ = 3,   \{{a, b}, c}\ = 2.
Petr Hliněný, Fl MU Brno, 2013
4/21
Fl: IB000: Množiny, množinové operace
Jednoduché srovnání množin
Vztah „být prvkem množiny" přirozeně nám podává i způsob porovnávání množin mezi sebou. Jedná se o klíčovou část teorie množin.
Definice: Množina A je podmnožinou množiny B, právě když každý prvek je prvkem B. Píšeme A C B nebo obráceně B ~D A.
Říkáme také, že se jedná o inkluzi. c
• Platí {a} C {a} C {a, b} £ {{a, b}},   0 C {0},
• A C B právě když A C B a A ^ B   (A je vlastní podmnožinou B).c
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 a B stejné, mají-li stejné prvkyx
• 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, 2013
5/21
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,
* 7L = {..., —2, — 1, 0,1, 2, 3,... } je množina celých čísel,
* = {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, c
Pojem nekonečné množiny se přímo v matematice objevil až teprve v 19. století a bylo s ním spojeno 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 Russelově paradoxu vrátíme v závěru našeho předmětu v Lekci 12.
Petr Hliněný, Fl MU Brno, 2013
6/21
Fl: IB000: Množiny, množinové operace
3.2   Množinové operace Základní operace
Definice 3.1. Sjednocení U a průnik n dvou množin A, B definujeme
AU B   =   {x I x G A nebo x G B}n .
A H B   =   {x | x G A a současně x G B} .
• Příklady {a, b, c} U {a, d} = {a, b, c, d},   {a, b, c} D {a, d} = {a}, c
• Vždy platí „distributivita" A n (B U C) = (A n B) U (A n C)
a A u (s n C) = (A U B) n (A U C)
Petr Hliněný, Fl MU Brno, 2013 7/21 Fl: IB000: Množiny, množinové operace
• a také „asociativita" A n (B n C) = (A n 5) n C (stejně pro U) a „komutativita" A n -B = i? n A (stejně pro U).
Definice: Pro libovolný počet množin indexovaných pomocí / rozšířeně
[^J  j Ai   =   {x | x G Ai pro nějaké i G /}□ . |^|  ^ Ai   =   {x | x G Aj pro každé i e /}.c
• Nechť Ai = {2- i} pro každé i G N. Pak Uíe]N Ai je množina všech sudých přirozených čísel.c
• Nechť Bi = {x | x G N, x > i} pro každé i G N. Pak f]ieM B,t = 0.
Petr Hliněný, Fl MU Brno, 2013
8/21
Fl: IB000: Množiny, množinové operace
Množinový rozdíl
Definice 3.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 B}n . AAB   =   (A \ B) U (B \ A) .□
A\B
AAB
• Příklady {a, b, c} \ {a, b, d} = {c},    {a, b, c}A{a, 6, d} = {c, d}, c
• Vždy platí například A \ (B D C) = {A \ B) U {A \ C) apodx
Definice: Pro libovolný počet množin indexovaných pomocí konečné / /\;,zj Ai = {x | x G Ai pro lichý počet i G /} .
Petr Hliněný, Fl MU Brno, 2013
9/21
Fl: IB000: Množiny, množinové operace
*   Definice: Nechť A C M. Doplněk 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, b, c}, pak {a, b} = {c}. Je-li M = {a, b}, pak {a, b} = 0. c
• Vždy pro ACM platí A = A („dvojí" doplněk), c
• Vždy pro A, B C M platí A U B = ~Ä n B a XŤlS = ÄUB. (Víz Vennovy diagramy.)
Petr Hliněný,  Fl MU Brno, 2013
10/21
Fl: IB000: Množiny, množinové operace
Uspořádané dvojice a kartézský součin
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a,b}}.c
Fakt: Platí (a, 6) = (c, d) právě když a = c a současně b = d.c
• Co je podle definice (a, a)?     (a, a) = {{a}, {a, a}} = {{a}, {a}} = {{«}}■□
Definice 3.3. 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 e A,b e B} .
c
• Příklady {a, b} x {a} = {(a, a), (6, a)},
{c, d} x {a, 6} = {(c, a), (c, 6), (<i, a), (<i, &)}.c
• Platí 0xX = 0 = Xx0pro každou množinu X. c
• Jednoduchá mnemotechnická pomůcka říká \A x B\ = |A| • .
Petr Hliněný,  Fl MU Brno, 2013 11/21 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 k) ind.
- (ai) = ai,
- (ai,-- - ,aj,ai+i) = ((ai,-- - , a^), ai+i)x
Fakt: Platí (ai, • • • , ak) = (&i, • • • , 6fc) právě když a\ = 6« pro každé 1 < i < kz
Definice kartézského součinu více množin: Pro každé A: G N definujeme
A\ x • • • x Ak = {(cii, • • • > čík) | cii £ M pro každé 1 < i < k} x
• Například ŕ = ZxSxZ = {(i, j, fc) | i, j,   G Z}.
• Co je A°?n   {0}, neboť jediná uspořádaná 0-ticeje právě prázdná 0.
Poznámka: Podle uvedené definice není součin asociativní, tj. obecně nemusí platit,
že A x (B x C) — (A x B) x Cx
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, 2013
12/21
Fl: IB000: Množiny, množinové operace
Potenční množina
Definice 3.4. Potenční množina množiny A,
neboli množina všech podmnožin, je definovaná vztahem
2A = {B | B C A} .
c
• Platí například 2^ = {0, {a}, {b}, {a, b}},
. 20 = {0},   2Í0'Í0» = {0, {0}, {{0}}, {0, {0}}},
• 2W*{a,6} = {0, {(a, a)}, {(a, b)}, {(a, a), (a, &)}}.□
Věta 3.5. Počet prvků potenční množiny splňuje \2A\ = 2^.n
Důkaz: Stručně indukcí podle \A\: Pro A = 0 platí \2A\ = |{0}| = 1.
Pro každý další prvek b 0 A rozdělíme všechny podmnožiny Au{6} „napolovic" na ty neobsahující b a na ty obsahující b, tudíž
2^u{ř>}| _ 2 . \2A\ = 2lAl+1 = 2lj4uíř'^
□
Petr Hliněný,  Fl MU Brno, 2013
13/21
Fl: IB000: Množiny, množinové operace
3.3   Porovnávání a určení množin
Věta 3.6. Pro každé dvě množiny A, B C M platí A U B =ÄnB.
Důkaz v obou směrech rovnosti.
• AU B CÄnŠ: c
* Pro x G M platí x G A U B, pravě když x 0 A U B, neboli když zároveň
x 0 A a x 0 B.
* To znamená x G A a zároveň x <E B, z čehož vyplývá požadované
x e A n -B. □
• AU B DÄnŠ:
* Pro x 6 M platí x £ A n -B, právě když x G A a zároveň x e -B, neboli když zároveň x 0 A a x 0 i3. c
* To znamená x 0 A U -B, z čehož vyplývá požadované x £ A U -B.
□
Petr Hliněný,  Fl MU Brno, 2013
14/21
Fl: IB000: Množiny, množinové operace
Věta 3.7. Pro každé tři množiny A, B, C platí
A\{BnC) = (A\B) U(A\C).c
Důkaz (viz ilustrační obrázek).
• A\(BHC) C (A\B) U(A\C):
* Je-li x G A \ (B n C), pak x G A a zároveň x g" (B n C), neboli x ^ B nebo x g" C.
* Pro první možnost máme x G (A \      pro druhou x G (A \ C).c
• Naopak A\(B(lC) 5 (A \ S) U(A\C):
* Je-li x G (A \ £) U (A \ C), pak x G (A \ £) 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 g" (B n C), a tudíž x G A \ (i? n C).c
* Druhá možnost je analogická.
□
Petr Hliněný,  Fl MU Brno, 2013
15/21
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 = {x±,X2,... ,xn}. Pro AC X definujeme charakteristický vektor \a jako
Xa = (ci,c2, ■ ■ ■, cn), kde Cj = 1 pro X{ £ A a q = 0 jinak.c
• Platí A = B právě když \a = 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, 2013
16/21
Fl: IB000: Množiny, množinové operace
Princip inkluze a exkluze
Tento důležitý a zajímavý kombinatorický princip je někdy také nazýván „princip zapojenia vypojení'.
Věta 3.8. Počet prvků ve sjednocení dvou či tří množin spočítáme:
\AUB\ = \A\ + \B\ -\AHB\ \AUBUC\ = \ A\ + \B\ + \C\ - \AHB\ - \Anc\ - \Bnc\ + \AnBnC\n
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, 2013
17/21
Fl: IB000: Množiny, množinové operace
Příklad 3.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? c
Řešení: Dosazením \A\ = 5, \B\ = 10, |C| = 12, \A n B n C\ = 3, |A n B| = 3 + 0, |A n C| = 3 + 0, |B n C| = 3 + 4 do Věty 3.8 zjistíme výsledek 17. □ C
Poznámka. Jen stručně, bez důkazu a bližšího vysvětlení, si uvedeme obecnou formu principu inkluze a exkluze:
E (-i)|íhl
M/C{l,...,n}
(Jeho znalost nebude v předmětu vyžadována.)
Petr Hliněný,  Fl MU Brno, 2013
18/21
Fl: IB000: Množiny, množinové operace
3.4   Posloupnosti a rekurentní vztahy
Definice: Uspořádaná fc-tice je také nazývána konečnou posloupností délky k.
• Nekonečná posloupnost zobecňuje toto pojetí na „nekonečná" k. c
• Nekonečná posloupnost p je zobrazením z N do svého oboru hodnot.
• Mimo „funkčního" zápisu p(n) často používáme „indexovou" formu p^.
Poznámka: Oborem hodnot posloupnosti obvykle bývá nějaká číselná množina, ale může to být i jakákoliv jiná množina, c
Také def. obor posl. může začínat od nuly nebo i od jedničky, jak je v aplikacích potřeba.
• Příklady posloupností:
* Po — 0, pi — 2,...,pi — 2i,... je posloupnost sudých nezáporných čísel.c
* 3, 3.1, 3.14, 3.141,... je posloupnost postupných dekadických rozvojů ir.
* 1, —1, 1, —1,... je posloupnost určená vztahem pi — (—1)\ i > 0. c
* Pokud chceme stejnou posloupnost 1, —1, 1, —1,... zadat jako qi, í > 1, tak ji určíme vzorcem qi — (—
Petr Hliněný,  Fl MU Brno, 2013
19/21
Fl: IB000: Množiny, množinové operace
Rekurentní definice posloupnosti
Slovem rekurentní označujeme takové definice (či popisy), které se v jistých bodech odvolávají samy na sebe.
(Už jste se setkali s „rekurzí" při programování? A víte, co znamená?) c Ukázky rekurentních vztahů:
• Zadáme-li posloupnost pn vztahy po = 1 a pn = 2pn_i pro n > 0, pak platí pn = 2n pro všechna n. c
• Obdobně můžeme zadat posloupnost qn vztahy q\ = 1 a qn = qn-i + n pro n > 1. Potom platí qn = ^n(n + 1) pro všechna n.
Uměli byste toto dokázat indukcí? c
• Známá Fibonacciho posloupnost je zadaná vztahy f1 = f2 = lafn = fn-i + fn-2 pro n > 2.
Petr Hliněný,  Fl MU Brno, 2013
20/21
Fl: IB000: Množiny, množinové operace
Příklad 3.10. Posloupnost f je zadaná rekurentní definicí
/(O) = 3    a    /(n+l) = 2-/(n) + l
pro všechna přirozená n. Určete hodnotu f(n) vzorcem v závislosti na n.
Řešení: V první fázi řešení takového příkladu musíme nějak „uhodnout" hledaný vzorec pro f(n). Jak? Zkusíme vypočítat několik prvních hodnot a uvidíme...
/(I) = 2-/(0) + l = 2-3+1 = 7
f(2) = 2-/(1) +1 = 2-7+1 = 15
/(3) = 2-/(2) +1 = 2-15+1 = 31
/(4) = 2 • /(3) + 1 = 2 • 31 + 1 = 63
Nepřipomínají nám tato čísla něco? Co třeba posloupnost 8 — 1, 16 — 1, 32—1, 64—1.. . ? Bystrému čtenáři se již asi podařilo uhodnout, že půjde o mocniny dvou snížené o 1. Přesněji, f(n) - 2n+2 - 1. □
Ve druhé nesmíme ale zapomenout správnost našeho „věštění" dokázat, nejlépe matematickou indukcí podle n. C
Petr Hliněný,  Fl MU Brno, 2013
21/21
Fl: IB000: Množiny, množinové operace