Petr Hliněný, FI MU Brno 1 FI: IB000: Množiny, Relace a Funkce 3 Množiny, Relace a Funkce3 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. 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. 2 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ý, FI MU Brno 2 FI: IB000: Množiny, Relace a Funkce 3.1 Pojem množiny3.1 Pojem množiny * Co je vlastně množina?2 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. 2 * Pozor, není skutečného rozdílu mezi ,,množinami a ,,prvky . Množiny mohou být prvky jiných množin!2 * Příklady: , {a, b}, {b, a}, {a, b, a}, {{a, b}}, {, {}, {{}}}, {x | x je liché přirozené číslo}2 Značení: Počet prvků (mohutnost) množiny A zapisujeme |A|. * || = 0, |{}| = 1, |{a, b, c}| = 3, |{{a, b}, c}| = 22 Značení množin a jejich prvků: * x M ,,x je prvkem množiny M . 2 * některé vlastnosti a {a, b}, a {{a, b}}, {a, b} {{a, b}}, * prázdná množina , a , {}, , * rovnost množin {a, b} = {b, a} = {a, b, a}, {a, b} = {{a, b}}. Petr Hliněný, FI MU Brno 3 FI: IB000: Množiny, Relace a Funkce Definice: Množina A je podmnožinou množiny B, právě když každý prvek A je prvkem B. Píšeme A B nebo také B A; říkáme také, že se jedná o inkluzi. 2 * Platí {a} {a} {a, b} {{a, b}}, {}, * A B právě když A B a A = B (A je vlastní podmnožinou B).2 Definice: Dvě množiny jsou si rovny A = B právě když A B a B A. * Podle definice jsou množiny A a B stejné, mají-li stejné prvky.2 * Důkaz rovnosti množin A = B má obvykle dvě části: Odděleně se dokáží inkluze A B a B A. Petr Hliněný, FI MU Brno 4 FI: IB000: Množiny, Relace a Funkce Značení: Některé běžné množiny v matematice se značí = {0, 1, 2, 3, . . .} je množina přirozených čísel, = {. . . , -2, -1, 0, 1, 2, 3, . . .} je množina celých čísel, + = {1, 2, 3, . . .} je množina celých kladných čísel, É je množina racionálních čísel (zlomků). je množina reálných čísel. 2 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. 2 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. Petr Hliněný, FI MU Brno 5 FI: IB000: Množiny, Relace a Funkce 3.2 Množinové operace3.2 Množinové operace Definice: Sjednocení a průnik dvou množin A, B definujeme A B = {x | x A nebo x B}2 , A B = {x | x A a současně x B} .2 * Příklady {a, b, c} {a, d} = {a, b, c, d}, {a, b, c} {a, d} = {a}. 2 * Vždy platí ,,distributivita A (B C) = (A B) (A C) a A (B C) = (A B) (A C). 2 Definice: Pro libovolný počet množin indexovaných pomocí I rozšířeně iI Ai = {x | x Ai pro nějaké i I}2 , iI Ai = {x | x Ai pro každé i I} .2 * Nechť Ai = {2 i} pro každé i . Pak i Ai je množina všech sudých přirozených čísel.2 * Nechť Bi = {x | x , x i} pro každé i . Pak i Bi = . Petr Hliněný, FI MU Brno 6 FI: IB000: Množiny, Relace a Funkce Definice: Rozdíl \ a symetrický rozdíl dvou množin A, B definujeme A \ B = {x | x A a současně x B}2 , AB = (A \ B) (B \ A) .2 * Příklady {a, b, c} \ {a, b, d} = {c}, {a, b, c}{a, b, d} = {c, d}. 2 * Vždy platí například A \ (B C) = (A \ B) (A \ C) apod. 2 Definice: Nechť A 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 ! 2 * Je-li M = {a, b, c}, pak {a, b} = {c}. Je-li M = {a, b}, pak {a, b} = . 2 * Vždy pro A M platí A = A (,,dvojí doplněk). 2 * Vždy pro A, B M platí A B = A B a A B = A B. (Viz Vennovy diagramy.) Petr Hliněný, FI MU Brno 7 FI: 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}}.2 Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d.2 Příklad 3.1. Co je podle definice (a, a)?2 (a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}. 2 2 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 A × B = {(a, b) | a A, b B} . 2 * Příklady {a, b} × {a} = {(a, a), (b, a)}, {c, d} × {a, b} = {(c, a), (c, b), (d, a), (d, b)}.2 * Platí × X = pro každou množinu X. 2 * Mnemotechnická pomůcka |A × B| = |A| |B| . Petr Hliněný, FI MU Brno 8 FI: IB000: Množiny, Relace a Funkce Skládání součinu Definice: Pro každé k , k > 0 definujeme uspořádanou k-tici (a1, , ak) induktivně takto ­ (a1) = a1, ­ (a1, , ai, ai+1) = ((a1, , ai), ai+1).2 Fakt: Platí (a1, , ak) = (b1, , bk) právě když ai = bi pro každé 1 i k.2 Definice kartézského součinu více množin: Pro každé k definujeme A1 × × Ak = {(a1, , ak) | ai Ai pro každé 1 i k} .2 * Příklad 3 = × × = {(i, j, k) | i, j, k }. * Co je A0?2 {}, 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 × (B × C) = (A × B) × C.2 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ý, FI MU Brno 9 FI: IB000: Množiny, Relace a Funkce Potenční množina Definice 3.3. Potenční množina množiny A, neboli množina všech podmnožin, je definovaná vztahem 2A = {B | B A} . 2 * Platí například 2{a,b} = {, {a}, {b}, {a, b}}, * 2 = {}, 2{,{}} = {, {}, {{}}, {, {}}}, * 2{a}×{a,b} = {, {(a, a)}, {(a, b)}, {(a, a), (a, b)}}.2 Věta 3.4. Počet prvků potenční množiny splňuje |2A| = 2|A|.2 Důkaz: Stručně indukcí podle |A|: Pro A = platí |2A| = |{}| = 1. Pro každý další prvek b A rozdělíme všechny podmnožiny A{b} ,,napolovic na ty neobsahující b a na ty obsahující b, tudíž |2A{b} | = 2 |2A | = 2|A|+1 . 2 Petr Hliněný, FI MU Brno 10 FI: IB000: Množiny, Relace a Funkce 3.3 Porovnávání a určení množin3.3 Porovnávání a určení množin Věta 3.5. Pro každé dvě množiny A, B M platí A B = A B. 2 Důkaz v obou směrech rovnosti. * A B A B: 2 Pro x M platí x A B, právě když x A B, neboli když zároveň x A a x B. To znamená x A a zároveň x B, z čehož vyplývá požadované x A B. 2 * A B A B: Pro x M platí x A B, právě když x A a zároveň x B, neboli když zároveň x A a x B. 2 To znamená x A B, z čehož vyplývá požadované x A B. 2 Petr Hliněný, FI MU Brno 11 FI: IB000: Množiny, Relace a Funkce Věta 3.6. Pro každé tři množiny A, B, C platí A \ (B C) = (A \ B) (A \ C) .2 Důkaz. * A \ (B C) (A \ B) (A \ C): Je-li x A \ (B C), pak x A a zároveň x (B C), neboli x B nebo x C. Pro první možnost máme x (A \ B), pro druhou x (A \ C).2 * Naopak A \ (B C) (A \ B) (A \ C): Je-li x (A \ B) (A \ C), pak x (A \ B) nebo x (A \ C). Pro první možnost máme x A a zároveň x B, z čehož plyne x A a zároveň x (B C), a tudíž x A \ (B C).2 Druhá možnost je analogická. 2 Petr Hliněný, FI MU Brno 12 FI: IB000: Množiny, Relace a Funkce 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 = {x1, x2, . . . , xn}. Pro A X definujeme charakteristický vektor A jako A = (c1, c2, . . . , cn), kde ci = 1 pro xi A a ci = 0 jinak.2 * Platí A = B právě když A = B. * Množinové operace jsou realizovány ,,bitovými funkcemi sjednocení OR, průnik AND, symetrický rozdíl XOR. Petr Hliněný, FI MU Brno 13 FI: 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í . Věta 3.7. Počet prvků ve sjednocení dvou či tří množin spočítáme: |A B| = |A| + |B| - |A B| |A B C| = |A| + |B| + |C| - |A B| - |A C| - |B C| + |A B C|2 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ý, FI MU Brno 14 FI: IB000: Množiny, Relace a Funkce Příklad 3.8. 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 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? 2 Řešení: Dosazením |A| = 5, |B| = 10, |C| = 12, |A B C| = 3, |A B| = 3 + 0, |A C| = 3 + 0, |B C| = 3 + 4 do Věty 3.7 zjistíme výsledek 17. 22 Poznámka. Jen stručně, bez důkazu a bližšího vysvětlení, si uvedeme obecnou formu principu inkluze a exkluze: n j=1 Aj = =I{1,...,n} (-1)|I|-1 iI Ai (Jeho znalost nebude v předmětu vyžadována.) Petr Hliněný, FI MU Brno 15 FI: IB000: Množiny, Relace a Funkce 3.4 Relace a funkce mezi (nad) množinami3.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 pozor- nost. Definice 3.9. Relace mezi množinami A1, , Ak, pro k , je libovolná podmnožina kartézského součinu R A1 × × Ak .2 Pokud A1 = = Ak = A, hovoříme o k-ární relaci R na A. 2 Příklady relací. * {(1, a), (2, a)} je relace mezi {1, 2, 3} a {a, b}. * {(i, 2 i) | i } je binární relace na .2 * {(i, j, i + j) | i, j } je ternární relace na . * {3 i | i } je unární relace na .2 * Jaký význam vlastně mají unární a nulární relace na A? Petr Hliněný, FI MU Brno 16 FI: IB000: Množiny, Relace a Funkce Funkce mezi množinami Definice 3.10. (Totální) funkce z množiny A do množiny B je relace f mezi A a B taková, že pro každé x A existuje právě jedno y B takové, že (x, y) f.2 Množina A se nazývá definiční obor a množina B obor hodnot funkce f. Neformálně řečeno, ve funkci f 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. . . ) 2 Značení: Místo (x, y) f píšeme obvykle f(x) = y. Zápis f : A B říká, že f je funkce s def. oborem A a oborem hodnot B.2 Funkcím se také říká zobrazení. * Definujeme funkci f : předpisem f(x) = x+8. Tj. f = {(x, x+8) | x }.2 * Definujeme funkci plus : × předpisem plus(i, j) = i + j. Tj. plus = {(i, j, i + j) | i, j }. Petr Hliněný, FI MU Brno 17 FI: 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) f, obdržíme definici parciální funkce z A do B.2 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 . 2 Další příklady funkcí. * Definujeme parciální funkci f : předpisem f(x) = 3 + x jestliže x 0, jinak. Tj. f = {(x, 3 + x) | x }. 2 * Také funkce f : daná běžným analytickým předpisem f(x) = x je jen parciální ­ není definována pro x < 0.2 * Co je relace, přiřazující lidem v ČR jejich rodná čísla? Petr Hliněný, FI MU Brno 18 FI: IB000: Množiny, Relace a Funkce 3.5 Posloupnosti a rekurentní vztahy3.5 Posloupnosti a rekurentní vztahy Definice: Funkce p : se nazývá posloupnost. Mimo ,,funkčního zápisu p(n) často používáme ,,indexovou formu zápisu pn.2 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á). 2 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í: p0 = 0, p1 = 2, . . . , pi = 2i, . . . je posloupnost sudých nezáporných čísel.2 3, 3.1, 3.14, 3.141, . . . je posloupnost postupných dekadických rozvojů . 1, -1, 1, -1, . . . je posloupnost určená vztahem pi = (-1)i , i 0. 2 Pokud chceme stejnou posloupnost 1, -1, 1, -1, . . . zadat jako qi, i 1, tak ji určíme vzorcem qi = (-1)i-1 . 2 * Posloupnost je rostoucí (či klesající), pokud pn+1 > pn ( pn+1 < pn ) pro všechna n. Petr Hliněný, FI MU Brno 19 FI: IB000: Množiny, Relace a Funkce 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á?) 2 Ukázky rekurentních vztahů: * Zadáme-li posloupnost pn vztahy p0 = 1 a pn = 2pn-1 pro n > 0, pak platí pn = 2n pro všechna n. 2 * Obdobně můžeme zadat posloupnost qn vztahy q1 = 1 a qn = qn-1 + n pro n > 1. Potom platí qn = 1 2n(n + 1) pro všechna n. Uměli byste toto dokázat indukcí? 2 * Známá Fibonacciho posloupnost je zadaná vztahy f1 = f2 = 1 a fn = fn-1 + fn-2 pro n > 2.