r.
3   Množiny, Relace a Funkce
V přehledu matematických formalismů informatiky se v teto lekci zaměříme na základní „datové typy" matematiky, tj. na mnoZiny, relace a funkce. O mnoZiních jste sice zajiste slyseli uZ na zakladní skole, ale podstatou naseho predmetu je uvest povetsinou neformálne zname pojmy na patricnou formalní uroven nutnou pro teoreticke základy informatiky.
StruCny přehled lekce
* Uvedení množin a operací množinového kalkulu.
* Nékteré vlastnosti množin, princip inklužé a exklužé.
* Relace a definice funkcí, žakladn í vlastnosti.
* Posloupnosti a rekurentn í vžtahy.
'etr Hliněný.  FI MU Brno
FI: IB000: Množiny, Relace a Funkce
3.1   Pojem množiny
Ý   Co je vlastne množinaľc
Na tuto otazku bohužel není zcela jednoduchá odpoved'...
• Naivní pohled: „Množina je soubor prvku a je svými prvky plně určena."t
• Pozor, není skuteCneho rozdílu mezi „množinami" a „prvky". Množiny mohou byt prvky jinych mnozinlc
• Príklady:   0,   (a, b},   {b, a},    (a, b, a},   {{a, b}},   (0, {0}, {{0}}},
{x | x je liche přirozene Císlo}c
Značení: Pocet prvku (mohutnost) mnoziny A zapisujeme |A|.
• |0| =0,   |{0}| = 1,   |{a,b,c}| =3,   |{{a,b},c}| =2u
Značení mnozin a jejich prvku:
• x € M    „x je prvkem mnoziny M". t
• nektere vlastnosti a € {a, b},   a € {{a, b}},   {a, b} € {{a, b}},
• prázdná mnozina 0,   a € 0,   0 € {0},   0 € 0,
{{a, b}}.
;inv. Relace ;
• rovnost mnořzin {a, b} = {b, a} = {a, b, a},   {a, b} =
Petr Hliněný.  FI MU Brno_2_FI: IB000: Mnoziny Relace a Funkce
r.
^
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 takě B 5 A; říkáme takě, že se jedná o inkluzi. c
• A c B práve když A C B a A = B   (A je vlastní podmnožinou B).c
Definice: Dve množiny jsou si rovny A = B práve když A C B a B C A.
• Podle definice jsou množiny A a B stejne, majá-li stejne prvky.c
• DUkaž rovnosti množin A = B má obvykle dve Cásti: Oddelene se dokáží inkluže A C B a B C A.
Petr Hliněný,  FI MU Brno___FI: IB000: Množiny, Relace a Funkce
• Platí (aj C (oj C {0,6} C {{a, b}},
0C {0},
Značení: Některé běžné množiny v matematice se značí
* N = {0,1, 2, 3,... } je množina přirozených čísel,
* TL = {..., —2, —1, 0,1, 2, 3,... } je množina celých čísel,
* Ti+ = {1, 2, 3,... } je množina celých kladných čísel,
* Q je množina racionalních císel (žlomků).
* K, je množina realnych císel. c
Poznámka: Tyto ůvedene císelne množiny jsoů vesmes nekonečné, na roždíl od konecnych množin uvažovaných v predchožím „naivn ím" pohledů. c
Pojem nekonecne množiny se prímo v matematice objevil až teprve v 19. století a bylo s n ím spojeno nekolik paradoxů ůkažůj íc ích, že naivn í pohled na teorii množin pro nekonecne množiny nedostacůje. My se k problematice nekonecnych množin, Kantorove vete a Růsselove paradoxů vrat íme v žaverů naseho predmetů.
etr Hliněný,  FI MU Brno___FI: IB000: Množiny, Relace a Funkce
3.2   Množinové operace
Definice: Sjednoceni U a průnik n dvou množin A, B definujeme
A U B   =   {x | x G A nebo x G B]n ,
A n B   =   {x | x G A a soucasne x G B} .c
• Příklady {a,b,c} U {a,d} = {a,b,c,d},   {a,b,c} n {a,d} = {a}. □
• Vždy platí „distributivita" A n (B U C) = (A n B) U (A n C)
a A U (B n C) = (A U B) n (A U C).
Definice: Pro libovolný pocet množin indexovaných pomocí I rožSíreně
UAi   =   {x | x G Aj pro nejake i G I}□ , P).g/ Aj   =   {x | x G Aj pro každe i G I} .□
• Necht Aj = {2 • i} pro každe i G N. Pak Ujg]N Aj je množina vSech sudých přirožených císel.c
• Necht Bj = {x | x G N, x > i} pro každe i G N. Pak f|jeN Bj = 0.
3etr Hliněný,  FI MU Brno__I: IB000: Množiny, Relace a Funkce__S
r.
Definice: Rozdíl \ a symetrický rozdíl A dvou množin A, B definujeme
• Příklady [a, b, c} \ [a, b, d} = {c},    {a,b,c}A{a,b,d} = {c, d}. c
• Vždy platí například A \ (B n C) = (A \ B) U (A \ C) apod. c
Definice: Nechť ACM. Doplněk A vzhledem k M je množina Ä = M\A.
• Jedná se o poněkud specifickou operaci, která musí být vztažena vzhledem k nosný množině M ! c
• Je-li M = {a, b, c}, pak {a, b} = {c}. Je-li M = {a, b}, pak {a, b} = 0. c
• Vždy pro A C M platí ~A = A („dvojí" doplněk), c
• Vždy pro A,B C M platí A(J B = ~An B a AnB = Iu5. (Viž Vennovy diagramy.)
Petr Hliněný,  FI MU Brno___FI: IB000: Množiny, Relace a Funkce
A\B
AAB
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, b) = (c, d) práve když a = c a soucasne b = d.c
Příklad 3.1. Co je podle definice (a, a) ?c
(a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}. c □
Definice 3.2. Kartézský součin dvou množin A, B definujeme jako množinu vSech uspořádaných dvojic ze složek z A a B
A x B = {(a, b) | a € A, b € B} .
• Příklady {a, b} x {a} = {(a, a), (b, a)},
{c, d} x {a, b} = {(c, a), (c, b), (d, a), (d, b)}.c
• Platí 0 x X = 0 pro každou množinu X. c
• Mnemotechnický pommcka
|A x B| = |A| • |B|.
Petr Hliněný,  FI MU Brno___FI: IB000: Množiny, Relace a Funkce
Skládání součinu
Definice: Pro každé k € N, k > 0 definujeme uspořádanou k-tici (ai, • • • , ak) induktivně takto
- (ai) = ai,
- (ai, • • • ,ai,ai+i) = ((ai, • • • ,a»),ai+i).□
Fákt: Platí (ai, • • • ,ak) =      • • • ,bk) pravé když ai = bi pro každé 1 < i < k
Definice kartázskáho součinu více množin: Pro každé k € N definujeme
Ai x • • • x Ak = {(ai, • • • , ak) | ai € Ai pro každe 1 < i < k} .
• Príklad3 = 7L x%x% = {(i, j,k) | i,j,k € Z}.
• Co je A°?n   {0}, nebol! jedina usporadana 0-ticeje prave praždna 0.
Poznámka: Podle uvedene definice nen í soucin asociativn í, tj. obecne nemusí platit,
že A x (B x C) = (A x B) x C.□
V matematicke praxi je nekdy vyhodnejsí uvažovat „upravenou" definici, podle níž soucin asociativn í je. Pro ucely teto přednasky nen í podstatne, k jake definici se prikloníme. Prežentovane definice a vety „funguj í" pro obe varianty.
Petr Hliněný,  FI MU Brno___FI: IB000: Množiny, Relace a Funkce
r.
Potenční množina
Definiče 3.3. Potenční množina množiny A,
neboli množina vsech podmnožin, je definovaná vžtahem
2A = {B | B C A} .
• Platí například 2{íl>6} = {0, {a}, {b}, {a, b}},
• 20 = {0}, 2{0>{0}} = {0, {0}, {{0}}, {0, {0}}},
• 2MxW>} = {0, {(a, a)}, {(a, b)}, {(a, a), (a,b)}}.c
Veta 3.4. Počet prvků potenční množiny splňuje |2A| = 2|A|.c Důkaž: StruCne indukcí podle |A|: Pro A = 0 platí |2A| = |{0}| = 1.
Pro každy dalsí prvek b ^ A rozdelíme všechny podmnožiny A U {b} „napolovic" na ty neobsahující b a na ty obsahující b, tudíž
Petr Hliněný, FI MU
= 2 • |2A|
2|A|+1 = 2|AU{6}|
-I: IB000: Množiny, Relace a Funkce
□
r.
3.3   Porovnávání a určení množin Věta 3.5. Pro každé dvě množiny A, B C M platí A u B = A~nB. c
DUkáž v obou směrech rovnosti.
• AU B CÄHB: c
* Pro x € M platia; € A U B, právě když x g A U B, neboli když zároveň x g A a x g B.
* To znamená x € A a zároveň x € B, z čehož vyplývá požadované a; € InB. c
* Pro x € M platí a; € A n U, právě když x G A a zároveň x € B, neboli
když zároveň x g A a x g B.
* To znamená x g A U B, z čehož vyplývá požadované a; € A U 13.
□
3etr Hliněný,  FI MU Brno
FI: IB000: Množiny, Relace a Funkce
Věta 3.6. Pro každé tři množiny A, B, C platí
A \ (B n C) = (A \ B) U (A \ C) .c
Důkaz.
• A \ (B n C) C (A \ B) U (A \ C):
* Je-li x € A \ (B n C), pak x € A a zároveň x ^ (B n C), neboli x € B nebo x € C.
* Pro první moZnost máme x € (A \ B), pro druhou x € (A \ C).c
• Naopak A \ (B n C) D (A \ B) U (A \ C):
* Je-li x € (A \ B) U (A \ C), pak x € (A \ B) nebo x € (A \ C).
* Pro první moZnost mame x € A a zaroveň x € B,
z cehoZ plyne x € A a zaroveň x € (B n C), a tudíZ x € A \ (B n C).c
* Druha moznost je analogicka.
□
3etr Hliněný,  FI MU Brno
FI: IB000: Množiny, Relace a Funkce
Charakteristický vektor (pod)množiny
V přápadech, kdy vsechny uvažovane množiny jsou podmnožinami nejake nosné množiny X, což nená neobvykle v programatorskych aplikacách, s vyhodou vyuřžijeme nasleduj íc í reprežentaci mnořžin.
Definice: Mejme nosnou množinu X = ... , xn}. Pro A C X definu-
jeme charakteristicky vektor xa jako
Xa = (c1, c2,..., cn), kde cj = 1 pro xj € A a c = 0 jinak.
• Platí A = B právě když \a = Xb■
• Množinově opěracě jsou realizovány „bitovými funkcemi" sjednocen í ~ OR, prUnik ~ AND, symetricky rožd íl ~ XOR^
3etr Hlineny,  FI MU Brno_12_FI: IB000: Množiny, Relace a Funkce
Princip inkluze a exkluze
Tento důležitý a zajímavý kombinatorický princip je nekdy take nazýván „princip zapojení a vypojení'.
Veta 3.7. Počet prvků ve sjednocení dvou či tří množin spočítáme:
|a U b| = |a| + |b| - |a n b|
|a u b u C| = |a| + |b| + |c| - |a n b| - |a n C| - |b n c| + A n b n C|c
Vsimnete si, ze vetu lze stejne tak vyuzít k vypočtu poctu prvku v pruniku mnozin.
Petr Hlineny.  FI MU Brno_13_FI: IB000: Množiny. Relace a Funkce
r.
Příklad 3.8. Z1000 televizí jich při první kontrole na výrobní lince ma 5 vadnou obrazovku, 10 je poškrábaných a 12 ma jinou vadu. Přitom 3 televize mají současně všechny tři vadý a 4 jine jsou poěkrabane a mají jinou vadu. Kolik televizí je celkem vadných? □
Řešení: Dosažen í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 Vety 3.7 žjistíme výsledek 17. □ □
Poznámka. Jen strůcne, bež důkažů a bližsího vysvetlení, si ůvedeme obecnoů formů principů inklůže a exklůže:
n
U Aj
e (—d'"-1 -inAi
0=/C{1,...,n> \i€l
(Jeho žnalost nebůde v předmetů vyžadovana.)
3etr Hlineny,  FI MU Brno
FI: IB000: Množiny, Relace a Funkce
3.4   Relace a funkce mezi (nad) mnoZinami
Dalsím duležitým žákladním „datovým typem" matematiky jsou relace, kterym vžhledem k jejich rožsíhlemu použití v informatice venujeme žvyšenou po-žornost.
Definice 3.9. Relace meži množinami Ai, • • • ,    , pro k € N, je libovolní podmnožina kartežskeho souánu
R C A1 x • • • x Ak .c
Pokud A1 = • • • = Afc = A, hovoríme o k-ární relaci R na A. c
Příklady relací.
• {(1, a), (2, a)} je relace meži {1,2,3} a {a, b}.
• {(i, 2 • i) | i € N} je binírní relace na N.c
• {(i, j, i + j) | i, j € N} je ternarní relace na N.
• {3 • i | i € N} je unarní relace na N.c
• Jaky vyžnam vlastne mají unarní a nularní relace na A?
Petr Hlineny,  FI MU Brno_15_FI: IB000: Množiny, Relace a Funkce
Funkce mezi množinami
Definice 3.10. (Totální) funkce ž množiny A do množiny B
je relace f meži A a B takový, že pro každe x € A existuje práve jedno y € B
takove, že (x, y) € f .c
Množina A se nažývá definiční obor a množina B obor hodnot funkce f.
Neformálne receno, ve funkci f je každe „vstupní" hodnote x přiražena jednožnacne „výstupní" hodnota y.
(V obecne relaci pocty „priraženych" dvojic neomežujeme.. .) c ZnaCení: Místo (x,y) € f píšeme obvykle f (x) = y.
Zapis f : A — B ríka, že f je funkce s def. oborem A a oborem hodnot B.c Funkcím se take říkí zobrazení.
• Definujeme funkci f : N — N předpisem f (x) = x+8. Tj. f = {(x,x+8) | x € IN}.n
• Definujeme funkci plus : N x N — N předpisem plus (i, j) = i + j. Tj. plus = {(i, j, i + j) | i, j € N}.
Petr Hlineny,  FI MU Brno_16_FI: IB000: Množiny, Relace a Funkce
r.
Definice: Pokud nasí definici funkce upraváme tak, že požadujeme pro každe x € A nejvyse jedno y € B takove, že (x, y) € f, obdrž áme definici parciální funkce ž A do B .c
V parcialn á funkci p nemusá byt pro nektere „vstupn á" hodnoty x funkcn á hodnota definovana.
Pro nedefinovanou hodnotu použ ávame žnak _L. c Dalřs í přr íklady funkc í. • Definujeme parcialn í funkci f \7L — N předpisem
Tj. f = {(x, 3 + x) | x € N}. c
• Takě funkcě f : R — K, daná běžným analytickým předpisem
/(x) =
jě jěn parcialn í - něn í děfinovana pro x < 0.c
• Co jě rělacě, přiražuj ící liděm v CR jějich rodna císla?
'etr Hlineny,  FI MU Brno
FI: IB000: Množiny, Relace a Funkce
3.5   Posloupnosti a rekurentní vztahý
Definice: Funkce p : N —> R se nažyva posloupnost.
Mimo „funkcního" žapisu p(n) casto používame „indexovou" formu žapisu pc
Poznamka: Obor hodnot posloupnosti muže byt i jiny než realna císla. Na posloupnost se take dívíme jako na „seražení" vybranych prvku ž oboru hodnot, s povolenym opakovaním hodnot (nemusí byt prosta). c
Take def. obor posl. muže žacínat od nuly nebo i od jedničky, jak je v aplikacích potřeba.
• Príklady posloupností:
* p0 = 0, pi = 2,... ,pj = 2i,... je posloupnost sudych nežapornych císel.c
* 3, 3.1, 3.14, 3.141,... je posloupnost postupnych dekadickych rožvoju n.
* 1, —1, 1, —1,... je posloupnost urcena vžtahem pj = (—i > 0. c
* Pokud chceme stejnou posloupnost 1, —1, 1, —1,... žadat jako qjt i > 1, tak ji urcíme vžorcem </j = ( —c
• Posloupnost je rostoucí (ci klesající), pokud pra+1 > pn (pn+1 < pn) pro vsechna n.
Petr Hlineny,  FI MU Brno
FI: IB000: Množiny, Relace a Funkce
r.
Rekurentní definice posloupnosti
Slovem rekurentní ožnacujeme takove definice (ci popisy), ktere se v jistych bodech odvolavaj í samy na sebe.
(Už jste se setkali s „rekurž í" při programovan í? A víte, co žnamena?) Ukažky rekurentních vztáhU:
• Zadame-li posloupnost pn vžtahy p° = 1 a pn = 2pn-i pro n > 0, pak plat í pn = 2n pro vsechna n. □
• Obdobne mužeme žadat posloupnost qn vžtahy qi = 1 a qn = qn-i + n pro n > 1. Potom platí qn = \n(n + 1) pro všechna n.
Umeli byste toto dokažat indukcí? □
• Znama Fibonacciho posloupnost je žadana vžtahy fi = f2 = 1 a fn =
fn-i + fn-2 pro n > 2.
Petr Hlineny,  FI MU Brno
FI: IB000: Množiny, Relace a Funkce
Příklad 3.11. Posloupnost f je zadaná rekurentní definicí
f (0) = 3    a    f (n + 1) = 2 • f (n) + 1
pro vsečhna přirozená n. Určete hodnotu f (n) vzorcem v závislosti na n. c
Řešení: V první faži řesenítakoveho príkladu musíme nejak „uhodnout" hledaný vžorec pro f (n). Jak? Zkusíme vypocítat nekolik prvních hodnot a uvidíme. ..
f(1)	= 2 •	f(0) + 1	=2	3 + 1 = 7
f(2)	= 2 •	f(1)+1	=2	7 + 1 = 15
f(3)	= 2 •	f(2) + 1	=2	15 + 1 = 31
f (4)	= 2 •	f(3) + 1	=2	31 + 1 = 63
Nepřipomínají nam tato císla neco? Co třeba posloupnost 8 — 1, 16 — 1, 32 — 1, 64 — 1.. . ? Bystrému ctenari se již asi podarilo uhodnout, že půjde o mocniny dvou snížene o 1. Přesneji, f (n) = 2n+2 — 1. c
Ve druhe nesm íme ale žapomenout spravnost nařseho vřeřstřen í" dokažat, nejlepe matematickou indukc í podle n. □
3etr Hlineny,  FI MU Brno
FI: IB000: Množiny, Relace a Funkce