Množiny, Relace a Funkce V přehledu matematických formalismů informatiky se v této lekci zaměříme na základní „datové typy" matematiky, tj. na množiny, relace a funkce. 0 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. m SP* Stručný přehled lekce * Uvedení množin a operací množinového kalkulu. * Některé vlastnosti množin, princip inkluze a exkluze. * Relace a definice funkcí, základní vlastnosti. * Posloupnosti a rekurentní vztahy. Petr Hliněný. Fl MU Brnc__________________________Fl: IB000: Množiny. Relace a Funkce * Co je vlastně množina?c 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.' • Pozor, není skutečného rozdílu mezi „množinami" a „prvky". Množiny mohou být prvky jiných množin!^ • Příklady: 0, {a,b}, {b,a}, {a,b,a}, {{a,b}}, {0, {0}, {{0}}}, {a; | a; je liché přirozené číslo} Značení: Počet prvků (mohutnost) množiny A zapisujeme \A\. . |0|=O, |{0}| = 1, \{a,b,c}\=3, \{{a,b},c}\ =2n Značení množin a jejich prvků: • x € M „x }e prvkem množiny M", c • některé vlastnosti a G {a,b}, a ^ {{a, b}}, {a, b} € {{a, b}}, • prázdná množina 0, a £ 0, 0 € {0}, 0^0, • rovnost množin {a, b} = {b, a} = {a, b, a}, {a, b} ^ {{a, b}}. _________Hliněný, Fl MU Brno___________________________-I: IB000: Množiny, Relace a Funkce 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 také B 5 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ž iC_ß a i^ß (A je vlastní podmnožinou B).c Definice: Dvě množiny jsou si rovny A = B právě když A C B a B C A. • Podle definice jsou množiny A a B stejné, mají-li stejné prvky.D • Důkaz rovnosti množin A = B má obvykle dvě části: Odděleně se dokáží inkluze A C B a B C A. Detr Hliněný, Fl MU Brno FhlBOOO: Množiny, Relace a Funkce r Značení: Některé běžné množiny v matematice se značí * 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, c Poznámka: 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, d 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. Detr Hliněný, Fl MU Brno 4 Fl: IB000: Množiny, Relace a Funkce Definice: Sjednocení Li a průnik n dvou množin A, B definujeme A U B = {x I x € A nebo x € B} . An B = {x \ x G A a současně x € B} .c • Příklady {a, 6, c} U {a, d} = {a, 6, c, d}, {a, b, c} n {a, d} = {a}, c • Vždy platí „distributive" An (B U C) = (An B)U (AnC) a AU (B n C) = (AU B) n (AU C). Definice: Pro libovolný počet množin indexovaných pomocí / rozšířeně [J. Ai = {x | x € Ai pro nějaké i € /}□ . Hel "^ Ai = {x \ x G Ai pro každé í e /} x Nechť A» = {2 • í} pro každé í € N. Pak IJísn ^* Je množina všech sudých přirozených čísel. Nechť Bi = {x | x € N, x > í} pro každé í € N. Pak f|íeN #i = 0- Petr Hliněný, Fl MU Brno 5 Fl: IBOOO: Množiny, Relace a Funkce Definice: Rozdíl \ a symetrický rozdíl A dvou množin A, B definujeme A\B = {x \ x G A a současně x $. B} . AAB = (A\B)u(B\A).d • 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} • Vždy pro A C M platí ~Ä = A („dvojí" doplněk), c • Vždy pro A,BCM platí AuB = AnB a AnB = AuB. (Viz Vennovy diagramy.) Detr Hliněný, Fl MU Brno 6 Fl: IB000: Množiny, Relace a Funkce 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ě 6 = d.c Příklad 3.1. Co je podle definice (a, a) ľc (a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}, c D Definice 3.2. 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) I 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)}.a • Platí 0 x X = 0 pro každou množinu X. c • Mnemotechnická pomůcka \Ax B\ = \A\ • \B\. ^ Petr Hliněný, Fl MU Brno Fl: IB000: Množiny, Relace a Funkce Definice: Pro každé k € N, k > 0 definujeme uspořádanou k-tici (ai, • • •, a^) induktivně takto - (ai) =ai, - (ai, • • •, cti, ai+i) = ((ai, • • •, a»), aí+i).c Fakt: Platí (ai, • • •, a^) = (6i, • • •, b k) právě když a» = bi pro každé 1 < i < to Definice kartézského součinu více množin: Pro každé k € N definujeme Ai x • • • x Ak = {(ai, • • •, ük) \ cii G Ai pro každé 1 < i < k} . Příklad T? = %x%x% = {(í, j, k) \ í, j, k € %\. Co je A°?" {0}, neboť jediná uspořádaná 0-tice je právě prázdná Poznámka: Podle uvedené definice není součin asociativní, tj. obecně nemusí platit, že A x (B x C) = (A x B) x C. 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 Fl: IB000: Množiny, Relace a Funkce Definice 3.3. Potenční množina množiny A, neboli množina všech podmnožin, je definovaná vztahem 2A = {B\BCA}. • Platí například 2^ = {0, {a}, {b}, {a, b}}, . 20 = {0}, 2<0>»} = {0, {0}, {{0}}, {0, {0}}}, • 2WxW = {M(m)},{(M)M(m),(M)}}^ Věta 3.4. Počet prvků potenční množiny splňuje \2A\ = 2'A'.n Důkaz: Stručně indukcí podle \A\: Pro A = 0 platí \2A\ = |{0}| = 1. Pro každý další prvek b $ A rozdělíme všechny podmnožiny Au{6} „napolovic" na ty neobsahující b a na ty obsahující b, tudíž I2^u{6}i = 2 . i2A| = ol^l+i = ol^uWI ill D Petr Hliněný, Fl MU Brno __________________________IB000: Množiny, Relace a Funkce 3.3 Porovnávání a určení množin Věta 3.5. Pro každé dvě množiny A, B CM platí AuB = AnB. c Důkaz v obou směrech rovnosti. AU B C AnB: c Pro x G M platí x € A U B, právě když x £ 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é • 4u534n5: Pro x G M platí a; € An U, právě když x G A a zároveň x G B, neboli když zároveň x $ A a x $ B. * To znamená x ^ A U B, z čehož vyplývá požadované a; € A U B. D 3etr Hlinený, Fl MU Brno 10 Fl: IB000: Množiny, Relace a Věta 3.6. Pro každé tři množiny A, B, C platí A\(BnC) = (A\B) U(A\C).c Důkaz. • A\(BnC) C (A\B) U(A\C): * Je-li x £ A\(BCiC), pak x € A a zároveň x g. (BnC), neboli x $. B nebo x $. C. * Pro první možnost máme x € (A \ B), pro druhou x € (A \ C). • Naopak A \ (B n C) D (A\B) U(A\C): * Je-li xe(A\B) U(A\ C), pak xe(A\B) nebo z € (A\ C). * Pro první možnost máme x € A a zároveň x ^ B, z čehož plyne x G A a zároveň a; ^ (£> n C), a tudíž a; € A \ (B n C). * Druhá možnost je analogická. Petr Hliněný, Fl MU Brno 11 Fl: IBOOO: Množiny, Relace a Funkce D Charakteristický vektor (pod)množiny V případech, kdy všechny uvažované množiny jsou podmnožinami nějaké 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,x%, ■ ■ ■ ,xn}. Pro Ac X definujeme charakteristický vektor \A jako Xa = (ci, C2, ■ ■ ■, Cn), kde Cj = 1 pro Xi € A a Cj = 0 jinak. • 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. 3etr Hliněný, Fl MU Brno 12 Fl: IB000: Množiny, Relace a Funkce Princip inkluze a exkluze Tento důležitý a zajímavý kombinatorický princip je někdy také nazýván „princip zapojení a vypojení'. A /" X *\ B Věta 3.7. Počet prvků ve sjednocení dvou či tří množin spočítáme: \A\JB\ = \A\ + \B\ -\AnB\ \Aubuc\ = \A\ + \b\ + \c\ - \Anb\ - \Anc\ - \bnc\ + \AnBnc\i Všimněte si, že větu lze stejně tak využít k výpočtu počtu prvků v průniku množin... Funkce ^ď 3etr Hliněný, Fl MU Brno ItsOOO: Množiny, Kelace a Příklad 3.8. Z1000 televizí jich při první kontrole na výrobní lince má 5 vadnou obrazovku, 10 je poškrábaných a 12 má jinou zá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 n B n C\ = 3, \Af)B\ = 3 + 0, | A n C\ = 3 + 0, \B n C| = 3 + 4 do Věty 3.7 zjistíme výsledek 17. d d Poznámka. Jen stručně, bez důkazu a bližšího vysvětlení, si uvedeme obecnou formu principu inkluze a exkluze: 3 = 1 E (-d1"-1 0^/C{l,...,n} (Jeho znalost nebude v předmětu vyžadována. 3etr Hliněný, Fl MU Brno ľl: IB000: Množiny, Relace a Funkce 3.4 Relace a funkce mezi (nad) množinami Dalším důležitým základním „datovým typem" matematiky jsou relace, kterým vzhledem k jejich rozsáhlému použití v informatice věnujeme zvýšenou pozornost. Definice 3.9. Relace mezi množinami A\, ■ ■ ■, A^, pro k € N, je libovolná podmnožina kartézského součinu R Q Ai x • • • x Ak .c Pokud A\ = • • • = Ak = A, hovoříme o k-ární relaci R na A. c Příklady relací. • {(1, a), (2, a)} je relace mezi {1,2,3} a {a, b}. • {(i, 2 • i) | i € N} je binární relace na N.c • {(hjji + j) \ hj G N} je ternární relace na N. • {3 • í | í € N} je unární relace na N.u • Jaký význam vlastně mají unární a nulární relace na A? Petr Hliněný, Fl MU Bri______________________________: IB000: Množiny, Relace a Funkce Definice 3.10. (Totální) funkce z množiny A do množiny B je relace / mezi A a B taková, že pro každé x € A existuje právě jedno y € B takové, že (x,y) € /.□ Množina A se nazývá definiční obor a 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...) c Značení: Místo (x, y) € / 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í. • Definujeme funkci / : N —> N předpisem f (x) = x+8. Tj. / = {(x, x+8) x € N}.d • Definujeme funkci plus :NxN^N předpisem plus (i, j) = i + j. Tj. plus = {(i,j,i+j) | i,i G N}. Petr Hliněný. Fl MU Brno __________________________: IB000: Množiny. Relace a Funkce ŕ . Definice: Pokud naší definici funkce upravíme tak, že požadujeme pro každé x € A nejvýše jedno y € B takové, že (x,y) € /, obdržíme definici parciální funkce z A do B.c. V parciální funkci p nemusí být pro některé „vstupní" hodnoty x funkční hodnota definována. Pro nedefinovanou hodnotu používáme znak _L. c Další příklady funkcí. • Definujeme parciální funkci / : 7L —> N předpisem ., , í 3 + x jestliže x > 0. f (x) = < .. ~ ' J v ' [ _L jinak. Tj. f = {(x,3+x) J G N}, c • Také funkce / : R —> R daná běžným analytickým předpisem /O) = Vx je jen parciální - není definována pro x < O.c • Co je relace, přiřazující lidem v ČR jejich rodná čísla? „_________• Hliněný, Fl MU Brri(__________________________ Fl: IB000: Množiny, Relace a Funkce r 3.5 Posloupnosti a rekurentní vztahy Definice: Funkce p : N —> R se nazývá posloupnost. Mimo „funkčního" zápisu p(n) často používáme „indexovou" formu zápisu p,,p Poznámka: Obor hodnot posloupnosti může být i jiný než reálná čísla. Na posloupnost se také díváme jako na „seřazení" vybraných prvků z oboru hodnot, s povoleným opakováním hodnot (nemusí být prostá). 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, pí = 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ů -k. * 1, —1, 1, —1,... je posloupnost určená vztahem pi = (—1)*, i > 0. d * Pokud chceme stejnou posloupnost 1, —1, 1, —1,... zadat jako 1, tak ji určíme vzorcem qi = (—l)í_1. m • Posloupnost je rostoucí (a klesající), pokud pn+\ > Pn {Pn+i < Pn) pro všechna n. ^ Petr Hliněný, Fl MU Brno Fl: IB000: Množiny, Relace a Funkce 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á?) Ukázky rekurentních vztahů: • Zadáme-li posloupnost pn vztahy po = 1 a pn = 2pn_\ pro n > 0, pak platí pn = 2n pro všechna n. - • Obdobně můžeme zadat posloupnost qn vztahy q\ = 1 a qn = qn-\ + 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 /i = ^ = 1 a /„ = fn-i + fn-2 pro n > 2. 3etr Hliněný, Fl MU Brno 19 Fl: IB000: Množiny, Relace a Funkce