Fakulta Informatiky
Masarykova Univerzita
Matematické Základy Informatiky
(FI: IBOOO)
Prof. RNDr. Petr Hliněný, Ph.D.
hlineny@f i.muni.cz
23. října 2024
Obsažný a dobře přístupný úvod do nezbytných formálních matematických základů moderní informatiky, doplněný řadou interaktivních cvičení v IS MU.
Výukový text pro předmět IBOOO na FI MU od roku 2012, navazující z velké části na původní výukové texty Úvodu do Informatiky z dřívějších let.
Verze 3.91 (2024)
© 2006-2024 Petr Hliněný, FI MU.
0.1    O tomto textu a jeho studiu
Vážení čtenáři,
dostává se vám do rukou výukový text Matematické Základy Informatiky, který je primárně určený pro studenty stejnojmenného předmětu na FI MU Brno. Seznamuje čtenáře s několika formálními matematickými oblastmi důležitými pro úspěšné studium moderní informatiky.
Náš text svým obsahem volně navazuje na původní slidy předmětu IB000 sepsané A. Kučerou do roku 2005 a rozšířené autorem v letech 2006-11 o volný text a komentáře. Od roku 2012 však byl obsah některých pasáží podstatně změněn či přímo vyměněn za nový - nejzřetelnější změnou je zahrnutí úvodu do teorie grafů. K další výrazné změně dochází v letech 2017-18, kdy je posílena látka matematické logiky a důkazů matematickou indukcí a zároveň omezeny části pojednávající o formalizaci algoritmů (ve prospěch předmětu IB002).
Učební text je psán strukturovaným matematickým přístupem, s velkým důrazem na přesnost a formalitu vyjadřování v nutných partiích. Na druhou stranu jsou strohá matematická vyjádření pokud možno doplněna obsáhlými neformálními komentáři, které mají studentům ulehčit pochopení látky. V žádném případě však čtenáři nemají zaměňovat neformální komentáře za matematické definice - v případě nejasností vždy platí to, co přesně říká formální definice.
Mimo textu samotného (jak jej zde vidíte) jsou z téhož zdoje vytvářeny i přednáškové slidy předmětu, které najdete například v IS MU. Slidy však pochopitelně obsahují jen část textu a jsou jinak formátovány.
Interaktivní osnova a odpovědníky
http://is.muni.cz/el/1433/podzim2024/IB000/index.qwarp
Nedílnou součástí celého výukového textu jsou interaktivní osnova předmětu IB000 v IS MU a z ní odkazované online odpovědníky sloužící k procvičování probrané látky na jednoduchých i složitějších příkladech. To je také důvod, proč tento text obsahuje jen nemnoho příkladů k řešení k probírané látce - od čtenáře očekáváme, že si látku bude procvičovat sám online na zmíněných odpovědnících, obsahujících až tisíce příkladů desítek typů. Třebaže pro studenty předmětu IB000 jsou organizována také každotýdenní cvičení, ta nemohou zcela pokrýt potřebnou rutinu získanou opakovaným samostatným procvičením látky v příkladech. K praktickému pochopení přednesených znalostí i k jejich budoucím aplikacím je důkladné procvičení nezbytné.
ii
Obsah
0.1   O tomto textu a jeho studiu......................... ii
1 Základní formalismy matematiky 1
1.1 Význam matematických tvrzení....................... 1
1.2 Úvod do matematického dokazování..................... 2
1.3 Výroky..................................... 4
1.4 Formální výroková logika........................... 6
2 Matematická logika a důkazy 9
2.1 Kvantifikace a predikátová logika...................... 9
2.2 Normální tvar logických formulí....................... 12
2.3 Tvoření matematických důkazů....................... 13
3 Množiny a množinové operace 16
3.1 Pojem množiny................................ 16
3.2 Množinové operace.............................. 18
3.3 Kartézský součin............................... 19
3.4 Porovnávání a určení množin ........................ 20
3.5 Relace a funkce................................ 22
4 Techniky matematických důkazů 25
4.1 Přehled základních důkazových technik................... 25
4.2 Věty typu „právě tehdy (když)"....................... 27
4.3 Matematická indukce............................. 28
4.4 Komentáře k matematické indukci...................... 30
5 Rekurze a induktivní definice 34
5.1 Posloupnosti a rekurentní vztahy ...................... 34
5.2 Rekurze s více parametry a indukce..................... 37
5.3 Induktivní definice množin.......................... 39
6 Strukturální indukce 42
6.1 Jednoznačnost induktivních definic..................... 42
6.2 Induktivní definice funkcí........................... 43
6.3 Použití strukturální indukce......................... 44
6.4 Nazpět k matematické logice......................... 46
7 Relace a jejich vlastnosti 49
7.1 Reprezentace konečných relací........................ 49
7.2 Vlastnosti binárních relací.......................... 50
7.3 Uzávěry relací................................. 52
7.4 Tranzitivní relace............................... 54
8 Ekvivalence, Uspořádané množiny 57
8.1 Relace ekvivalence a rozklady........................ 57
8.2 Uspořádané množiny............................. 59
8.3 Pojmy uspořádaných množin......................... 62
8.4 Relace předuspořádání............................ 64
iii
9 Skládání relací a funkcí 67
9.1 Inverze a skládání relací........................... 67
9.2 Praktické použití skládání.......................... 68
9.3 Vlastnosti funkcí............................... 70
9.4 Skládání funkcí, permutace.......................... 72
10 Pojem grafu 75
10.1 Definice grafu................................. 75
10.2 Podgrafy a isomorfismus........................... 78
10.3 Souvislost, komponenty a vzdálenost .................... 82
10.4 Základní pojmy orientovaných grafů..................... 85
10.5 Dodatek: 7 mostů jedním tahem....................... 88
11 Stromy a kostry grafů 91
11.1 Stromy - grafy bez kružnic.......................... 91
11.2 Problém minimální kostry.......................... 94
11.3 Dodatek: Výběr různých reprezentantů................... 97
11.4 Příklady použití grafů ............................ 98
12 Nekonečné množiny, Zastavení algoritmu 100
12.1 O nekonečných množinách a kardinalitě................... 100
12.2 „Naivní" množinové paradoxy........................ 102
12.3 Algoritmická neřešitelnost problému zastavení............... 104
iv
1   Základní formalismy matematiky
Úvod
Začneme nejprve několika obecnými poznámkami ke smyslu a směřování celého našeho předmětu. Jak sami poznáte, studium informatiky neznamená jen „naučit se nějaký programovací jazyk", nýbrž zahrnuje celý soubor dalších relevantních předmětů, mezi nimiž najdeme i formální (matematicko—teoretické) základy moderní informatiky A právě odborný nadhled nad celou informatikou včetně nezbytné formální teorie odliší obyčejného počítačového dělníka („počítačové lopaty") od skutečného a jistě lépe placeného IT experta.
Na tomto místě přichází náš odborný předmět Matematické Základy Informatiky, který má za úkol vás na studium formálních základů moderní informatiky připravit. K tomu je nezbytné začít poněkud zostra - zdůrazněním přesného matematického vyjadřování, výrokové logiky a principů logických úsudků a matematických důkazů. Nelekejte se však hned v první lekci a s chutí se dejte do dalšího studia, po překonání případného prvotního šoku to nebude až tak obtížné. ..
Cíle
Hlavním cílem této úvodní lekce je rozebrat formální strukturu a zápis matematických tvrzení (vět). Při tomto rozboru se naučíte chápat smysl matematických vyjádření (výroků) pohledem výrokové logiky a pracovat s touto formalizací. Také zjistíte, jak se v matematice správně argumentuje a jak by měl vypadat matematický důkaz.
1.1   Význam matematických tvrzení
Matematika coby vědní disciplína (tudíž i teoretická informatika jako její součást) se vyznačuje velmi přísnými formálními požadavky na korektnost vyjadřování a argumentace. Proto si již od prvních krůčků v tomto předmětu musíme ujasnit, jak mají matematická tvrzení (nazývaná prostě matematické věty) správně vypadat a jaký je jejich význam. Matematické tvrzení je obvykle vysloveno ve tvaru
„Jestliže platí předpoklady, pak platí závěr".
Tomuto tvaru se odborně říká implikace. Pro pochopení významu je klíčové vždy správně identifikovat, co jsou v dané větě ony zmíněné předpoklady a co je závěrem. A k dosažení této dovednosti nezbývá, než se cvičit a cvičit na příkladech...
Komentář: Příklady běžné formulace matematických vět:
* Je-li x > 1, pak platí x2 > x.
* Konečná množina má konečně mnoho podmnožin.
* sm2(a) + cos2(a) = 1.
* Graf je rovinný, jestliže neobsahuje podrozdělení K§ nebo K^.
Co přesně nám uvedené matematické věty říkají? Všimněme si, že mnohdy jsou některé „samozřejmé" předpoklady vět vynechány, například, že x je reálné číslo nebo že a ve třetím bodě je úhel, případně se tvrzení implicitně odvolávají na obecně známé definice, například, co je to graf K§ ve čtvrtém bodě. Často nám k lepšímu pochopení toho, co je tvrzeno a je třeba dokázat, pomůže pouhé rozepsání definic pojmů, které se v dané větě vyskytují.
1
O pravdivosti implikace
Hned na začátek výkladu zdůrazňujeme, jak moc důležité je pochopit správný logický význam matematického tvrzení vysloveného zmíněnou formou implikace („jestliže pak ..."). Pravdivost takového tvrzení je třeba chápat v následujícím významu:
Pro každou situaci, ve které jsou splněny všechny předpoklady, (*) je platný i závěr tvrzení.
Volně řečeno, z předchozího kritéria (*) vyplývá, že pokud předpoklady nejsou splněny nebo jsou sporné, tak celé tvrzení je platné bez ohledu na pravdivost závěru!
Příklad 1.1. Je pravdivé následující matematické tvrzení?
Věta. Mějme dvě kuličky, červenou a modrou. Jestliže červená kulička je těžší než modrá a zároveň je modrá kulička těžší než ta červená, tak jsou obě kuličky ve skutečnosti zelené.
„ To přece nemůže být pravda, jak může být jedna kulička těžší než druhá a naopak zároveň? Jak mohou být nakonec obě zelené? To je celé nějaká blbost... "
Ano, výše uvedené jsou typické laické reakce na uvedenou větu. Přesto však tato věta pravdivá je! Stačí se vrátit o kousek výše ke kritériu - Pro každou situaci, ve které jsou splněny všechny předpoklady je platný i závěr tvrzení - které je zjevně naplněno. Nenaleznete totiž situaci, ve které by byly splněny oba předpoklady zároveň, a tudíž ve všech takových neexistujících situacích si můžete říkat cokoliv, třeba že kuličky jsou zelené. □
Příklad 1.2. Anna a Klára přišly na přednášku a usadily se do lavic. Proč je pravdivé toto matematické tvrzení?
Věta. Jestliže Anna sedí v první řadě lavic a zároveň Anna sedí v poslední řadě lavic, tak Klára nesedí ve druhé řadě lavic.
Opět je třeba se pečlivě zamyslet nad významem předpokladů a závěru. Avšak tentokrát není situace předpokladů tak triviálně sporná, jako byla v Příkladu 1.1. Kdy tedy mohou nastat oba předpoklady (o tom, kde sedí Anna) zároveň? Když první řada lavic je zároveň řadou poslední. Neboli posluchárna má jen (nejvýše) jednu řadu lavic a Klára tudíž v druhé řadě nemůže sedět. Pravdivost celé věty je tímto potvrzena. □
1.2   Uvod do matematického dokazování
S přísnými formálními požadavky na korektnost vyjádření a argumentace v matematice se pojí otázka, jak správně svá tvrzení zdůvodňovat. Krátce lze říci, že korektně postavená matematická argumentace musí vést od přijatých předpokladů v elementárních krocích směrem k požadovanému závěru (a nikdy ne naopak!).
Definice 1.3. Matematický důkaz .
Uvažme matematickou větu (neboli tvrzení) tvaru
„Jestliže platí předpoklady, pak platí závěr".
Důkaz této věty je konečná posloupnost tvrzení, kde • každé tvrzení je buď
2
* předpoklad, nebo
* obecně přijatá „pravda" - axiom, nebo
* plyne z předchozích a dříve dokázaných tvrzení podle nějakého „akceptovaného" logického principu - odvozovacího pravidla;
• poslední tvrzení je závěr.
Komentář: O potřebné úrovni formality matematických důkazů a o běžných důkazových technikách se dozvíme dále v příštích lekcích. Pro úplný začátek si jen celou problematiku uvedeme názornými ukázkami. Ctěte si tyto ukázky pečlivě, i pokud jste se již s matematickým dokazováním setkali a (či nebo) vám následující příklady připadají zcela primitivní. Později, u složitějších důkazů, se právě k takovým jednoduchým ukázkám můžete vracet a lépe na nich pochopit, jak to správně a přesně v matematice „chodí".
Příklad 1.4. Uvažujme následující matematické tvrzení (které jistě už znáte). Věta. Jestliže x je součtem dvou lichých čísel, pak x je sudé.
Poznámka pro připomenutí:
- Sudé číslo je celé číslo dělitelné 2, tj. tvaru 2k, kde k je celé číslo (ano, i 0 či —2 jsou sudá celá čísla a jsou dělitelná dvěma).
- Liché číslo je celé číslo nedělitelné 2, tj. tvaru 2k + 1, kde k je celé.
Důkaz postupuje v následujících formálních krocích: tvrzení zdůvodnění
1)	a	= 2k-\	- 1, k celé	předpoklad
2)	b	= 21 +	1, / celé	předpoklad
3)	X	= a +	b = 2k + 21 + H	h 1   z 1,2) a komutativity sčítání (axiom)
4)	X	= 2(k	+ 0 + 2-1	ze 3) a distributivnosti násobení (axiom
5)	X	= 2(k	+ / + 1)	ze 4) a opět distributivnosti násobení
6)	X	= 2m,	m celé	z5)am = fc + í+ lje celé číslo (axiom
Příklad 1.5. Dokažte následující tvrzení:
Věta. Jestliže x a y jsou racionální čísla pro která platí x < y, pak existuje racionální číslo z pro které platí x < z < y.
Důkaz po krocích (s již trochu méně formálním zápisem) zní:
1) Nechť z = 2±2 =x + ^ = y- Vfi.
2) Číslo z je racionální, neboť x a, y jsou racionální.
3) Platí z > x, neboť ^ > 0.
4) Dále platí z < y, neboť opět       > 0.
5) Celkem x < z < y.
3
Jak čtenář asi sám vidí, tento strohý formální zápis (i když matematicky kompletní) si zaslouží alespoň krátký vysvětlující komentář. Takový komentář, ať už se objeví před nebo hned po formálních argumentech, sice není součástí důkazu samotného, velmi však napomáhá správnému pochopení a má své nezastupitelné místo. Nezapomínejte na to ve svých vlastních budoucích matematických důkazech.
Konkrétně v tomto příkladě je velmi vhodné poznamenat, že klíčový krok (1) popisuje námi vymyšlenou (prostě uhodnutou) algebraickou konstrukci, která vede k požadovanému číslu z. Zbylé kroky (2-5) pak jen snadno zdůvodňují, že nalezené z má všechny požadované vlastnosti.
□
Poznámka. Alternativní matematické formulace Věty z Příkladu 1.5 mohou znít:
- Pro každé x, y £ Q, kde x < y, existuje z G Q takové, že x < z < y.
- Množina racionálních čísel je hustá.
1.3 Výroky
Důležitým pevným mostem mezi běžnou mluvou a přesným matematickým formalismem je pojem výroku. Jeho správné uchopení nám pomůže při chápání významu matematických výroků i v práci s nimi, což je klíčovou náplní tohoto oddílu.
Definice 1.6. Výrok v přirozené mluvě:
V běžné mluvě za výrok považujeme (každé) tvrzení, o kterém má smysl platně prohlásit, že je buď pravdivé, nebo nepravdivé.
Komentář: Ukážeme si několik příkladů - které z nich jsou výroky?
* Dnes už v Brně pršelo.
* Předmět FI: IB000 se vyučuje v prvním ročníku.
* Platí 2 + 3 = 6.
* To je bez problémů. (Co?)
* Platí x > 3.
* Pro každé celé číslo x platí, že x > 3.
Všimněte si, že pravdivost výroku by mělo být možné rozhodnout bez skrytých souvislostí (kontextu), a proto čtvrtý a pátý příklad za výroky nepovažujeme. Poslední příklad již zase výrokem je, neboť obor hodnot x je jednoznačně vymezen tzv. kvantifikací.
Z více jednoduchých výroků vytváříme výroky složitější pomocí tzv. logických spojek.
Komentář: Následuje několik dalších příkladů.
* Množina {a, b} má více než jeden prvek a není nekonečná.
* Jestliže Karel váží přes 90 kg, nejedu s ním výtahem.
* Jestliže má tato kráva 10 nohou, pak mají všechny domy modrou střechu. Zastavme se na chvíli nad posledním výrokem. Co nám říká? Je pravdivý? Skutečně mají všechny domy modrou střechu a před námi stojí kráva s 10 nohama? (Ano, výrok je pravdivý, viz definice či pravdivostní tabulka implikace.)
Schopnost porozumět podobným větám je součást lidského způsobu uvažování a z tohoto hlediska nemá přímou souvislost s matematikou (je to „přirozená logika"). Formálni (matematická) logika pak v podobném duchu definuje jazyk matematiky a přitom odstraňuje nejednoznačnosti přirozeného jazyka.
4
Ukázka argumentace s výroky
Matematické věty jsou často tzv. složené („platí ... a/nebo tudíž ... ") a v tom případě je třeba umět správně vyvodit celkovou platnost z platnosti jednotlivých elementů. Tomuto se budeme věnovat přesněji v Oddíle 1.4, ale již nyní si pro ukázku rozebereme následující logickou hádanku, navazující na téma Příkladu 1.2.
Příklad 1.7. Uvažujme libovolně vybrané studenty X, Y, Z sedící v posluchárně na přednášce IB000 takové, že pro ně platí:
a) X sedí v první řadě,
b) Y sedí v řadě hned za X,
c) Z sedí ve stejné řadě jako Y.
Věta. Jestliže zároveň platí (a),(b),(c), pak student Z sedí ve druhé řadě.
Vaším úkolem je platnost uvedeného tvrzení dokázat a také zdůvodnit, že (a),(b),(c) dohromady tvoří minimální soubor předpokladů, který ještě zajistí platnost tvrzení.
Pro začátek osvětlíme (blíže viz Oddíl 8.3) význam slova minimální, kdy je myšlen výběr předpokladů takový, že odebráním libovolného z nich již platnost uvedeného tvrzení „Z sedí ve druhé řadě" bude porušena.
První část úkolu je snadná, jakmile platí (a) a (b) zároveň, tak student Y sedí ve druhé řadě (hned za první řadou) a podle (c) pak také student Z sedí ve druhé řadě.
V druhé části nahlédneme, že pokud kterýkoliv z předpokladů (a),(b),(c) vynecháme, rozebráním těchto tří možností najdeme platná rozesazení (tj. konkrétní protipříklady), při kterých zbylé dva předpoklady budou splněny, avšak Z v druhé řadě sedět nebude:
• Například pokud vynecháme (b), může Y sedět v první řadě spolu s X a stejně tak Z. Formálně uvádíme konkrétní protipříklad studentů X, Y, Z, kteří sedí všichni v první řadě a tudíž splňují podmínky (a) a (c), ale nesplňují závěr, že Z sedí ve druhé řadě.
• Dále vezměme studenty X, Z v první řadě a F ve druhé řadě. Tento protipříklad splňuje podmínky (a) a (b), ale zase nesplňuje závěr.
• Nakonec vezměme studenty X v druhé řadě a ľ, Z ve třetí řadě. Tento protipříklad splňuje podmínky (b) a (c), ale zase nesplňuje závěr.
Takže soubor předpokladů (a),(b),(c) je minimální. □
Komentář: Zvídavého čtenáře může napadnout, zdali naše protipříklady jsou skutečně platné, když třeba posluchárna z Příkladu 1.7 bude mít jen dva sloupce. Usadíme pak všechny tři studenty X, Y, Z do první řady? Toto však vůbec nepředstavuje problém nejméně ze dvou důvodů, které si zde rozebereme.
Za prvé, matematická věta v příkladu má tvar implikace a již víme, že implikace je platná, pokud v každé situaci vyhovující zapsaným předpokladům je platný i závěr. A stačí si představit (pro náš účel) situaci, kdy daná posluchárna má alespoň 3 sloupce (což žádný z předpokladů neomezuje) a je to, jak má být.
Za druhé, proč by studenti X, Y, Z museli být tři různí? Pokud zvolíme třeba Y = Z jako téhož studenta (uvědomte si, že X, Y, Z hrají roli proměnných a dvě různě označené proměnné klidně mohou nabývat stejné hodnoty), tak s žádným s uvedených předpokladů nebudeme v rozporu.
5
1.4   Formální výroková logika
Všimněte si, že podle Definice 1.6 každému výroku běžné mluvy prostě můžeme přiřadit logickou hodnotu 0 (falše) nebo 1 (true) a dále se nestarat o jazykový význam... Proto jazykové výroky v matematice můžeme nahradit výrokovými proměnnými, které značíme velkými písmeny A,B,C,... a přiřadíme jim hodnotu 0 nebo 1 (nejspíše podle toho, jaký význam v našem světě uvažované výroky mají).
Definice: Výroková formule (značíme Lp,a,ip,...) vzniká z výrokových proměnných pomocí závorek a logických spojek, které z později vysvětlených důvodů dělíme na
* základní spojky -i negace a =>- implikace
* a odvozené spojky V disjunkce, A konjunkce a ekvivalence.
Poznámka: Uvedená definice je instancí tzv. induktivní deňnice, jíž se budeme blíže věnovat v Lekci 6, a proto ji zde zatím uvádíme jen v hodně zjednodušené podobě.
Komentář: Při zápise výrokových formulí je potřeba dávat pozor na správné závorkování, aby formule měla jednoznačný význam. Na intuitivní úrovni to ilustrujeme takto:
a nesprávně    A =ř B =ř C   - znamená toto (A =4> B) =4> C nebo A =4> (B =4> C)l
Komentář: Výrokové logické spojky konjunkce a disjunkce mají přirozené jazykové vyjádření „a" a „nebo" (jen pozor, abyste při disjunkci pak nebrali „nebo" jako výlučné, tedy bez uvažování platnosti obou možností zároveň).
Negace odpovídá přirozenému vyjádření „neplatí, že... " (a je poněkud neintuitivní říkat negaci logická spojka, když nespojuje dvě části výroku, ale říká se to tak).
Jazykovému vyjádření spojky implikace jsme se bohatě věnovali Oddíle 1.1.
Pro logickou ekvivalenci jednoduché a přirozené vyjádření v našem jazyce není, ale nejblíže krátkému a přesnému jazykovému vyjádření je obrat „právě když", který mimo jiné používáme níže. Tento obrat však není jazykově pěkný a ve složitějších souvětích často vidíme víceslovná vyjádření ekvivalence mezi větami souvětí; příkladům se budeme věnovat v Oddíle 4.2.
Matematicko-logický význam výrokovým formulím pak dodává následující definice. Srovnejte si každý krok této definice se svým přirozeným logickým uvažováním.
Definice 1.8. Sémantika (význam) výrokové logiky.
Nechť valuace (ohodnocení) je funkce v : Prom —> {0,1} na všech (dotčených) výrokových proměnných. Pro každou valuaci v definujeme funkci Sv(o~), vyhodnocení^formule o, induktivně (tj. po krocích) takto:
* Sjy(A) := v(A) pro každé A G Prom.
Správně
A,    (A)=>(B),    A^B,   ^A^B, AVBV^C
0   jestliže Sv(ip) = 1 a Sv(ip) = 0;
6
Sv{fp A ip) = 1    právě když     (<Sj,(</?) = 1 a současně Sv(ij)) = 1). * iSv(v? ^ '(/') := Sv({ip =>- ip) A     =>• </?)); to jinými slovy znamená
«5j/(</? ^ ■(/>) = 1   právě když platí jedna z následujících podmínek
- Sv(ip) = 1 a současně Su(i(j) = 1
- nebo Sv(íp) = 0 a současně Su(ip) = 0. □
Poznámka: Tento předpis (Def. 1.8) podává nejen deňnici funkce Sv, ale také návod na to, jak ji pro daný argument vypočítat.
Pravdivostní tabulky
V praxi často vyhodnocení logické výrokové formule zapisujeme do tzv. pravdivostní tabulky. Tato tabulka typicky má sloupce pro jednotlivé proměnné, případné „meziformule" (pomůcka pro snazší vyplnění) a výslednou formuli. Řádků je 2P (počet valuací), kde p je počet použitých proměnných.
Pro naše účely postačí uvést pravdivostní tabulku instruktážním příkladem. Čtenáři nechť si vyplní podle Definice 1.8 vlastní pravdivostní tabulky dalších výrokových formulí, viz také příslušné cvičné odpovědníky v IS MU.
Příklad 1.9. Jaká je pravdivostní tabulka pro formuli (A     B) \J B \J C?
A	B	c	A ^B	(A     B) V B V C
0	0	0	1	1
0	0	1	1	1
0	1	0	1	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1
□
Splnitelnost formulí a tautologie
Definice: Formule ip je splnitelná, pokud pro některou valuaci v platí, že Sv(íp) = 1. Formule je nesplnitelná (říká se také kontradikcé), pokud není splnitelná. Formule 99 je vždy pravdivá, neboli výroková tautologie, psáno |= ip, pokud pro každou valuaci v platí, že Syiy) = 1.
Řekneme, že dvě formule íp,i(j jsou ekvivalentní, právě když |= ip ip.
Tvrzení 1.10. Následující formule jsou tautologiemi:
* |= A V -iA
* |= -1 -iA ^ A
* \=(AA(A=> B)) B
* |= (-,#     -,A) ^(A^ B)
7
* |= {-^A 4 (5 A -.5)) =>• A
Komentář: Jak poznáme tautologie v pravdivostní tabulce? Snadno, v posledním sloupci jsou samé hodnoty 1. A jak ekvivalentní formule? Jejich poslední sloupce jsou shodné.
Ekvivalentní formule pravdivostní tabulkou
Příklad 1.11. Jsou následující dvě výrokové formule (A =>- B) A (B V A) a (C A B) V (B A -.C) ekvivalentní?
Pozor ale při řešení na zkratkovité úvahy ve stylu „přece ty formule mají různé množiny proměnných, tak ekvivalentní být nemůžou"!
Zopakujme si definici ekvivalentních formulí a z ní nahlédneme, že musíme využít pravdivostní tabulku kombinující všechny tři proměnné vyskytující se v našich formulích, tj. vyplníme pravdivostní tabulku takto:
A	B	c	(A^5)A(BV A)	(C A 5) V (B A -.C)
0	0	0	0	0
0	0	1	0	0
0	1	0	1	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	0
1	1	0	1	1
1	1	1	1	1
Ano, dané formule jsou ekvivalentní. □
Navazující studium
Látka této úvodní lekce má velmi široký záběr. S potřebou formálního zápisu tvrzení a důkazů se setkáte nejen v tomto, ale i ve všech dalších matematických a teoreticko-informatických předmětech, které zároveň studujete či budete studovat, a principy budou stále stejné. Proto seje snažte pochopit a zažít už na zde uvedených jednoduchých příkladech a vše si procvičte. A pokud vám stále „jde hlava kolem" z logického matematického vyjadřování (a to jsme teprve u pouhé výrokové logiky!), můžete se také zkusit podívat na hezkou úvodní (středoškolskou) knížku Antonína Sochora - Logika pro všechny ochotné myslet, Karolinum 2011.
8
2   Matematická logika a důkazy
Úvod
Po úvodním představení matematických formalismů již čtenář ví o výrokové logice a její užitečnosti, ale taký si jistě všiml velkých omezení samotné výrokové logiky, spočívajících především v nemožnosti využívat vnějších souvislostí (kontextu) ve výrocích a jejich vyhodnocení. Například, mluvíme-li v jednom výroku o studentovi s červeným svetrem a v jiném výroku o studentovi s brýlemi, výroková logika nám nijak neumožňuje nastolit, že se má u obou výroků jednat o stejného (nejmenovaného) studenta ze skupiny.
Zhruba řečeno, výrokové logice chybí možnost „parametrizace" výroků, což znamená zavedení omezeného a dobře defínovaného kontextu pro každé tvrzení, ve kterém pak můžeme už jednotlivé výroky vyhodnocovat podle pravidel výrokové logiky. Takovou parametrizaci si lze v jednoduché ukázce představit jako proměnnou X, jež třeba nabývá hodnot ze skupiny našich studentů a umožňuje nám hovořit v různých výrocích o stejném nespecifíkovaném studentovi X. S tímto přístupem následně operuje obecnější predikátová logika, která je hlavní náplní této lekce.
Z historického hlediska je ještě vhodné zmínit, že logika jako fílozofícká disciplína se intenzivně vyvíjí už od dob antiky, ale ke skutečnému rozmachu formální logiky coby součásti matematiky došlo až od začátku 20. století. (S přispěním třeba Russelova paradoxu a převratných Gódelových prací.)
Cíle
V této lekci pokračujeme ve formalizaci základů matematiky lehkým uvedením mocné predikátové logiky a souvisejícím vysvětlením role kvantifíkátorů v logice. Také se blíže podíváme na problematiku nalézání či tvorby matematických důkazů obecně. Tím uzavřeme látku načatou v předchozí lekci.
2.1   Kvantifikace a predikátová logika
Dříve popsaná výroková logika je velmi omezená faktem, že každý výrok musí být (tzv. absolutně) vyhodnocen jako pravda nebo nepravda. Co když však chceme zpracovat tvrzení typu „den D v Brně pršelo"? Jeho pravdivostní hodnota přece závisí na tom, co dosadíme za den D, a tudíž jej nelze považovat za výrok výrokové logiky.
Řešení nám nabízí následující obecnější přístup predikátové matematické logiky.
• Predikátová logika pracuje s predikáty. Predikáty jsou „parametrizované výrokyCÍ, které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu parametrů. Výrokové proměnné lze chápat jako predikáty bez parametrů.
• Predikátová logika je tak obecnější než logika výroková; každá formule výrokové logiky je i formulí predikátové logiky, ale ne obráceně.
Komentář: To, že predikátová logika zobecňuje výrokovou logiku, doslova znamená, že v predikátové logice můžete používat všechny výrokové proměnné a spojky ve stejném významu jako ve výrokové logice. K tomu navíc přibudou ony predikáty a takzvané kvantifikátory.
Pro neformální přiblížení si uvedeme několik ukázek predikátů:
* x > 3 (parametrem je zde iěR),
* 'čísla x a y jsou nesoudělná' (parametry x,y £ N),
* obecně jsou predikáty psány P(x,y), kde x,y jsou libovolné parametry. Následně pak můžeme psát formule ve stylu (a více viz následující definice)
9
* (P(x,y)AQ(x,z)) -+R(y,z),
* (P(x,y)AQ(y,z)) -+ ^R{x,z).
Parametrům predikátů se také říká proměnné, ale je třeba dávat pozor, aby se nepletly s výrokovými proměnnými, jedná se o jiné objekty nabývající jiných hodnot.
Syntaxe a sémantika predikátové logiky
Čtenář by měl v tomto místě vzít na vědomí, že naše definice vztahující se k predikátové logice jsou velmi velmi zjednodušené a nenahrazují kurz matematické logiky! Přesto poskytnou alespoň základní povědomí o této problematice (a hlavně o použití kvantifikace v tvrzeních) pro potřeby matematické formalizace v našem kurzu.
Definice: Z predikátů (zahrnují i výrokové proměnné) lze vytvářet predikátové formule pomocí už známých výrokových spojek (viz Oddíl 1.4) a takzvaných kvantifíkátorů. Přesněji, nechť ip je formule výrokové či predikátové logiky, pak také
• {všeobecný kvantifikátor) formule \/x. ip a
• {existenční kvantifikátor) formule 3x . ip jsou formulemi predikátové logiky.
Komentář: Pro ukázku složitějšího zápisu si uvedeme například predikátovou formuli:
Vx . 3y . {x + 2 < y A     . (x + y + z > 2024))
Náš zápis predikátových formulí ve stylu Vx . p není jediný možný, často se také setkáte se zápisy Vx: p nebo \/x{p). Všechny tyto tři způsoby můžete používat, ale nemíchejte je dohromady v jedné formuli.
Definice 2.1. Zjednodušená sémantika (význam) predikátové logiky. Uvažujme libovolnou množinu (nebo třídu) ti, zvanou univerzum, a předpokládejme, že každý predikátový parametr (proměnná) x,y,... má zvolenou hodnotu z ti. Vyhodnocení predikátové formule o pak definujeme induktivně takto:
• Každý predikát P{x, y,...) se vyhodnotí (na 0 nebo 1) jako výrok v aktuálním kontextu, tj. vzhledem k aktuálně zvoleným hodnotám svých parametrů x,y,....
• Výrokové spojky jsou vyhodnoceny podle pravidel Definice 1.8.
• Formule tvaru \/x. ip se vyhodnotí jako pravdivá (1), právě když pro každou volbu parametru x G U je pravdivá formule ip.
• Formule tvaru 3x. ip se vyhodnotí jako pravdivá (1), právě když existuje alespoň jedna volba parametru x G U, pro kterou je pravdivá formule ip.
Komentář: Pozorného čtenáře napadne, že Definice 2.1 nedává konzistentní návod na vyhodnocení takové predikátové formule, ve které se některá proměnná vyskytuje mimo kvantifikátor. Nejde však o chybu, nýbrž o přirozenou vlastnost - proměnné nemající svůj kvantifikátor (zvané volné proměnné formule) totiž musí být zafixovány zvenčí před samotným vyhodnocením. (Jde o obdobu problematiky neinicializovaných proměnných v počítačových programech.)
Fakt: Je-li každá proměnná - parametr predikátu - v dané formuli kvantifikovaná (tj. formule je uzavřená), pak je celá formule buď pravdivá nebo nepravdivá.
10
Příklad 2.2. Ukažme si vyjádření následujících slovních výroků uzavřenými formulemi v predikátové logice:
• Výrok „každé prvočíslo větší než 2 je liché" za použití predikátů Pr(n) a Li(n) vyjadřujících po řadě prvočíselnost a lichost n;
\/n [(ííGNA Pr(n) A n>2) => Li(n)],
přičemž lze podrobněji elementárně rozepsat Li(n) = 3k G N (n = 2k + 1) (= je „definiční rovnítko" pro logické formule).
• Každé celé číslo n > 1, které není prvočíslem, je dělitelné nějakým celým číslem y takovým, že n ^ y a y > 1;
Vn[(neZAn>lA -iPr(n)) =4> 3í/(í/GZAí/> lAn/?/A Poznámka: V tomto předmětu počítáme 0 za přirozené číslo.
Značení: Při zápisu formulí predikátové logiky se často používají některé úpravy a zjednodušení (již jsme si řekli o možném psaní \/x: p>), které nyní neformálně shrneme.
* Pokud píšeme více kvantifikátorů za sebou, vynecháváme zbytečně opakované symboly jako \/x\/y\/z3s3t. p> , nebo dokonce \/x, y, z 3s, t (ip).
* Jsou-li ve formuli p> některé parametry predikátů bez kvantifikace („neuzavřené"), například x, y,..., pak mohou být v zápise zdůrazněny jako parametry samotné formule p>(x,y,...). Například p>(x,y) = 3z(x < z < y).
* Další možná modifikace se týká univerza, ze kterého se vybírají hodnoty kvantifikovaných proměnných. Zatímco striktně bychom měli psát \/n{n E Z =^ n2 > n), často vidíme jiný možný zápis ViíGZ (n2 > n). Na naši úrovni zjednodušeného pojetí predikátové logiky mezi těmito dvěma zápisy není rozdíl.
Jak na pochopení kvantifikátorů
Používání kvantifikátorů si neformálně přiblížíme pár příklady. Na jednu stranu je (asi) význam použití jednotlivého všeobecného či existenčního kvantifikátoru zřejmý z výše uvedeného popisu, na druhou stranu už tak jednoduché není kombinování více kvantifikátorů v jednom tvrzení. Podívejme se třeba na následující ukázku:
Příklad 2.3. Proč na pořadíkvantifíkátorů velmi záleží:
• Pro každého studenta A v posluchárně platí, že existuje student B v posluchárně takový, že A je kamarád B.
• Existuje student B v posluchárně, že pro každého studenta A v posluchárně platí, že A je kamarád B.
Vidíte ten propastný rozdíl ve významech uvedených dvou uzavřených predikátových formulí? Přitom jsme jen syntakticky zaměnili pořadí kvantifikace A a B. □
Druhý, již složitější příklad, nám ukazuje, že kvantifikátory potkáme (skrytě) i v situacích, kde na první syntaktický pohled žádná kvantifikace není.
Příklad 2.4. Pepíček si přinesl ze školy domácí úkol z matematiky:
11
Pro dané a = 3,b = A, c = 5 vypočtěte hodnotu výrazu (a + c — 5)(G + 3) — b.
Bohužel, jak vidíte, udělal do zadání kaňku # a teď neví, zda pod kaňkou bylo písmeno a, b nebo c. „To je ale smůla", řekl si Pepíček, „můj příklad teď nemohu jednoznačně vypočítat. Přitom by stačilo změnit v zadání jen jednu z hodnot a, b nebo c a ten příklad by už měl jednoznačné řešení i s tou mou nešťastnou kaňkou!". Vysvětlete a zdůvodněte, co tímto Pepíček myslel.
V příkladě jsou dvě roviny, ve kterých musíme argumentovat. Za prvé, že pro uvedené zadání domácího úkolu existují dvě (alespoň) různá přiřazení jednoho ze symbolů a, b, c kaňce taková, že výsledné hodnoty budou různé. To je snadno vidět, třeba pro b na místě kaňky vypočítáme hodnotu 17, kdežto pro c na místě kaňky vypočítáme 20. Takže Pepíček opravdu nemohl zadaný úkol jednoznačně vyřešit.
Ve druhé rovině je našim úkolem najít a ověřit, že existuje změna hodnoty jednoho z a, b, c taková, že pro každé přiřazení jednoho ze symbolů a, b, c kaňce v domácím úkolu vyjde výsledná hodnota výrazu stejně. Potom jednoznačné řešení existuje i s kaňkou a chytrý Pepíček jej najde. Takových vhodných změn je dokonce více, například „c = 5" změníme na „c = 2" a hodnota výrazu vyjde 0 • (© + 3) — 4 = —4 bez ohledu na to, co se skrývá pod kaňkou.
Vidíte, jak důležité bylo v našem řešení pochopit a explicitně vyjádřit skryté kvantifikátory Pepíčkových úvah? Zbytek pak už vychází docela snadno. □
2.2   Normální tvar logických formulí
Po formálních částech pojednání o logice se dostáváme k jednomu specifickému úskalí chápání přirozené logiky, totiž že přesný význam tvrzení se zanořenými negacemi (není pravda, že ...) je někdy skutečně obtížné pochopit. Co například říká následující?
„Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad."
Výrokové formule se proto pro lepší pochopení obvykle prezentují v tzv. normálním tvaru, ve kterém se negace zanořených podformulí nevyskytují, formálně:
Definice: Formule ip je v normálním tvaru, pokud se v ní operátor negace aplikuje pouze na výrokové proměnné (případně na predikáty v případě predikátové formule).
Komentář: Pro ilustraci, k formuli —<(A =4> B) je ekvivalentní normální tvar A A —*B, k formuli -.(C A (-iA B)) je ekvivalentní -.C V (->A A -.£), k formuli ->{(A B) C) je ekvivalentní (A =4> B) A -iC. A pokud důsledně aplikujeme přirozené pravidlo dvojí negace (|= —t—t A 4^ A), tak výše napsané tvrzení „...nemám nerad" si převedeme na lépe srozumitelný tvar:
„ Nemusím říct, že tě mám nerad."
Podobné převody složitých tvrzení tvaru „Není pravda, že ..." na normální tvar je však velmi obtížné dělat z hlavy. Jak vůbec poznáme, že náš převod byl správný? Stačí si (třeba) vyplnit pravdivostní tabulku. Celkově výhodnější pak je se naučit čistě mechanický postup, kterým převedeme i velmi složitou formuli do normálního tvaru bez velké duševní námahy.
12
Negace formule v normálním tvaru
Použitím následujících neformálních „přepisovacích" pravidel dokážeme převést každou formuli predikátové logiky na normální tvar:
• Je-li daná (již znegovaná) formule tvaru -1(99 =>- ip), bude přepsána na tvar (ip A —iip):
-i{ip => 4>)       ^       p A -iip
• Podobně:
—i(íp\/ijj) —np A —iip
-i(ipAif)) -op V-11J)
-i(<p <=>> ip) ^       -op <=>> ip
• Pro kvantifikátory se pak použije následující intuitivní převod:
-i(3x. ip)       ^ "ix.—iip
-i(\/x . ip)       ^       3x .-op
Plný formální popis této metody převodu do normálního tvaru ponecháváme na budoucí Oddíl 6.4.
Komentář: Uvažme výrokovou formuli —i(A =4> ~i(B V —i{C => —iA))). Užitím uvedeného postupu ji upravíme takto:
-■(A =^ -i(B V —■(—iC =4> -iA))) ~> A A -i(-i(B V —iC =4> -iA))) ~> AA(BVn(nC^nA)) ^    A A (5 V (-.C A -.(-.A))) ~>
AA(BV(nCAA))
Formuli A A (B V (-1C A A)) lze dále zjednodušit na ekvivalentní formuli A A (ž? V _,C). To ale je již z našeho pohledu matematicky neformální (heuristický) postup.
Obdobně uvažme predikátovou formuli -i( Mx3y —iP(x, y)). Tu užitím našeho postupu upravíme následovně:
-i( \/x3y —iP(x, y))   ~>   3x -i( Ely —iP(x, y)) ~> ElxVy -i(-iP(i, y))    ~>   ElxVy P(x,y)
2.3   Tvoření matematických důkazů
Závěrem lekce se vrátíme ke druhému pilíři správné formalizace matematiky - k přesným důkazům. Dokončíme nyní lehký úvod do matematického dokazování z Lekce 1.
V dřívějším textu jsme viděli několik různorodých ukázek matematických důkazů, od zcela formálního přístupu po velmi uvolněný text. Přirozenou otázkou teď je, jak moc formální mají správné matematické důkazy vlastně být?
• Záleží, komu je důkaz určen — konzument musí být schopen „snadno" ověřit korektnost každého tvrzení v důkazu a plně pochopit, z čeho vyplývá.
• Je tedy hlavně na vás zvolit tu správnou úroveň formálnosti zápisu vět i důkazů podle situace.
13
• Avšak vůbec neplatí, že čím více formálních matematických symbolů v důkazu použijete místo běžného jazyka, tím by byl důkaz přesnější a lepší - často bývá výsledek právě opačný.
A jak na ten správný matematický důkaz máme přijít?
• No..., nalézání matematických důkazů je tvůrčí činnost, která není vůbec snadná a jako taková vyžaduje tvůrčí (přímo „umělecké") matematické vlohy. I pokud takové vlohy (zatím) v sobě necítíte, snažte se jí alespoň trochu přiučit.
Dokazovat či vyvracet tvrzení?
Představme si, že našim úkolem je rozhodnout platnost matematického tvrzení. Neboli nám není shůry řečeno, že tvrzení platí, ale mohou nastat obě možnosti platí / neplatí. Jak pak matematicky správně zdůvodníme nalezenou odpověď?
• Záleží na odpovědi samotné... Pokud je to ANO (platí), prostě podáme důkaz tvrzení podle výše uvedených zvyklostí. Pokud je odpověď NE, tak naopak podáme důkaz negace daného tvrzení.
Poměrně častým případem je matematická věta T, která tvrdí nějaký závěr pro širokou oblast vstupních možností. Potom je postup následující:
• Pokud T platí, nezbývá než podat vyčerpávající důkaz platnosti pro všechny vstupy.
• Avšak pokud T je nepravdivá, stačí uhodnout vhodný protipříklad a jen pro něj dokázat, že při platnosti všech předpokladů závěr tvrzení platný není. Ke slovíčku „stačí" ještě dodáváme, že pro správné matematické vyvrácení nepravdivého tvrzení T protipříklad uvést přímo musíte (viz pravidlo -i(Vrr. <p) ^ 3x.
Komentář: Při dostatečně pokročilé úrovni znalostí matematiky si sice lze představit i jiné způsoby dokazování existence protipříkladu k našemu tvrzení T, než nalezení konkrétního protipříkladu, ale ty jsou zcela mimo oblast našeho předmětu i běžného studia na FI.
Komentář: Také se již podruhé (po Příkladu 1.5) se dostáváme k fenoménu „uhodnutí" některé součásti důkazu. Jak se k němu máme stavět (je to vůbec dovoleno udělat)? Ale ano, pokud váš důkaz bude matematicky správný, nikdo nebude namítat, že jste v něm něco jen šťastně uhodli. V takovém správném „uhodnutí" věcí právě spočívá ta zmíněná tvůrčí stránka vytváření matematických důkazů.
A nyní se znovu vraťte na začátek Oddílu 1.1 a srovnejte si výše uvedené se základními poznatky o významu matematických vět...
Příklad 2.5. Rozhodněte platnost následujícího tvrzení: Pro všechna reálná x platí
x2 + 3x + 2 > 0 .
Důkaz: Standardními algebraickými postupy si můžeme upravit vztah na x2 + 3x + 2 = (x + 1) • (x + 2) > 0. Co nám tato úprava naznačuje? Například to, že k porušení daného tvrzení stačí volit x tak, aby jedna ze závorek byla kladná a druhá záporná. To nastane třeba pro x = — |.
Pro vyvrácení tvrzení nám tedy stačí začít volbou protipříkladu reálného čísla x = — | (není nutno zdůvodňovat, jak jsme jej „uhodli"!) a následně dokázat úpravou
x2 + 3x + 2 = (x + 1) • (x + 2) = ("! + !)• (~+2) =        •        = -\ <0. Dané tvrzení tudíž není platné. □
14
Konstruktivní a existenční důkazy
Z hlediska praktické využitelnosti je vhodné rozlišovat tyto dvě kategorie důkazů (třebaže z formálně-matematického pohledu mezi nimi kvalitativní rozdíl není).
• Důkaz z Příkladu 1.5 je konstruktivní Dokázali jsme nejen, že číslo z existuje, ale podali jsme také návod (či algoritmus), jak ho pro dané x a, y sestrojit.
• Existenční důkaz je takový, kde se prokáže existence nějakého objektu bez toho, aby byl podán použitelný návod na jeho konstrukci. Třebaže to může vypadat divně, nějak se snažit dokazovat existenci něčeho, co nedokážeme sestrojit, ale takové situace skutečně v matematice nastávají a existenční důkazy jsou v nich užitečné.
Příklad 2.6.  Cistě existenčního důkazu.
Věta. Existuje program, který vypíše na obrazovku čísla tažená ve 45. tahu sportky v roce 2024.
Důkaz: Existuje pouze konečně mnoho možných výsledků losování 45. tahu sportky v roce 2024. Pro každý možný výsledek existuje program, který tento daný výsledek vypíše na obrazovku. Mezi těmito programy je tedy jistě takový, který vypíše právě ten výsledek, který bude ve 45. tahu sportky v roce 2024 skutečně vylosován. ^
Komentář: To je ale podvod, že? A přece není... Formálně správně to je prostě tak a tečka.
Příklad 2.7.  Pravděpodobnostního existenčního důkazu.
Věta. Na dané množině bodů je zvoleno libovolně n2 podmnožin, každá o n prvcích. Dokažte pro dostatečně velká n, že všechny body lze obarvit dvěma barvami tak, aby žádná zvolená podmnožina nebyla jednobarevná.
Důkaz: U každého bodu si „hodíme mincŕ a podle výsledku zvolíme barvu červeně nebo modře. (Nezávislé volby s pravděpodobností |.) Pravděpodobnost, že konkrétně zvolených n bodů vyjde jednobarevných, je jen ^ = 21_n.
Pro n2 podmnožin tak je pravděpodobnost, že některá z nich vyjde jednobarevná, shora ohraničená součtem
n2
21-" + • • • + 21-" =-- ->0.
v-v-'
n2
Jelikož je toto číslo (pravděpodobnost) pro n > 7 menší než 1, určitě bude existovat nějaké obarvení bez jednobarevných zvolených podmnožin. □
Komentář: Zkuste si sami v obou posledních příkladech přijít s konstruktivním důkazem, tj. takovým, který hledané řešení sestrojí. Pokud se vám to povede, budete skutečně dobří (a možná také bohatí)...
Navazující studium
Látka této lekce navazuje na velmi široký záběr Lekce 1 a dokončuje její nakousnuté poznatky. Přesto je celá matematická logika v našem textu uvedena jen velmi omezeně na nejlehčí akceptovatelné intuitivní úrovni a její další rozvoj je ponechán samostatným kurzům. Zájemce o studium matematických hlubin logiky a třeba slavných Gódelových poznatků na FI MU můžeme později odkázat na předmět MA007 Matematická logika.
S poblematikou matematického dokazování se však budete dále setkávat v průběhu celé výuky tohoto předmětu i navazujících kurzů.
15
3   Množiny a množinové operace
Úvod
V přehledu matematických formalismů informatiky se v další lekci zaměříme na základní datové typy matematiky, tj. na množiny, relace a funkce. Netradiční sousloví „datové typy" matematiky zde volíme záměrně, abychom zdůraznili jejich fundamentální roli pro výstavbu navazující matematické teorie v analogii k programování.
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. V případě konečné teorie množin si zde vystačíme s tzv. „naivním" pohledem, který dostatečně matematicky přesně vystihuje všechny jejich konečné aspekty (o komplikacích okolo nekonečných množin se krátce zmíníme až v Lekci 12).
Na rozdíl od množin se relacím v jejich abstraktní podobě mnoho pozornosti na nižších stupních výuky nevěnuje. Sice jste se již určitě setkali s pojmem funkce, ale to nejspíše jen ve spojení s aritmetickými a analytickými funkcemi („ vzorečky") typu x +1, x2 — y, či sin x, 1 + cos x2, atd. Jak uvidíte v této lekci, pojmy relace i funkce jsou zcela abstraktní a nemusí se k nim vázat žádný analytický vzorec výpočtu či podobné předpisy.
Cíle
V této lekci si ukážeme první krok k seriózně vybudované matematické teorii množin -tzv. naivní teorii množin, která nám velmi dobře poslouží ve všech konečných případech. Na to navážeme zavedením základního množinového kalkulu a shrnutím běžných vlastností množin. Závěrem si řekneme o abstraktní deňnici relace a funkce na množinách, kteréžto pojmy budou rozvedeny v navazujících lekcích.
3.1   Pojem množiny
Položme si hned na úvod tu nej důležitější otázku: Co je vlastně množina?
Na tuto otázku bohužel není zcela jednoduchá odpověď... Abychom se vůbec někam v našem úvodu dostali, spokojíme se zatím jen s přirozeným „naivním pohledem".
Definice naivní teorie množin: „Množina je soubor prvků a je svými prvky plně určena. " Komentář: Příklady zápisu množin výčtem prvků
0,   {a,b},   {b, a},   {a,b,a},   {{a, b}},   {0, {0}, {{0}}},   {x \ x je liché přirozené číslo}.
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ší množiny.
Komentář: 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.
Značení množin a jejich prvků:
• x G M    „x je prvkem množiny M",
• 0   je prázdná množina {}.
16
Komentář: Některé vlastnosti vztahu „být prvkem" jsou
* at{a,b}, a^{{a,b}},  {a, b} E {{a, &}}, a 0 0, 0 G {0}, 0 0 0,
* rovnost množin dle svých prvků {a,b} = {b, a} = {a,b,a},  {a, b} 7^ {{a, b}}. Značení: Počet prvků (mohutnost) množiny A zapisujeme \A\.
Komentář: Například |0| = 0,   |{0}| = 1,   \{a,b,c}\=3,   \{{a, b}, c}\ = 2.
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, b}},   0 C {0},
* A C B, právě když A C B &, A ^ B   (A je vlastni podmnož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ě tehdy, když A C B & B C A.
* Podle naivní definice jsou totiž množiny A a, 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.
Příklad 3.1. Vyjádřete předchozí defínice podmnožiny a rovnosti množin formálním jazykem predikátové logiky.
Řešení: V tomto případě máme k dispozici jediný predikát 'G' (být prvkem) a univerzum je neomezené. Překladem uvedených definic píšeme:
lA C B'= Vx.xeA^xeB
lA = B1 = Vx. (x G A => x G B) A (x G B => x G A)
□
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.
Komentář: 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, Cantorově větě a Russelovu paradoxu vrátíme v závěru našeho předmětu v Lekci 12.
17
3.2   Množinové operace
Začněme se základními operacemi množinového kalkulu, které zajisté na intuitivní úrovni již ovládáte ze školy. Pro formální úplnost podáme jejich přesné definice, na které se můžete odvolávat v důkazech.
Sjednocení a průnik
Definice 3.2. Sjednocení U a průnik H dvou množin A, B definujeme
AU B   =   {x \ x e A nebo x G B} ,
A H B   =   {x \ x £ A & současně x G B} .
Komentář: Pro neformální pochopení věci je velmi užitečné si množinové operace a vztahy zobrazovat tzv. Vennovými diagramy, které zobrazují jednotlivé množiny a v nich „oblasti" prvků s daným vztahem k zobrazeným množinám. V našem případě to je takto:
* Příklady {a, b, c} U {a, d} = {a, b, c, d},   {a, b, c} fl {a, d} = {a}.
* Vždy platí „distributivita"   A H (B U C) = (A f] B) U (A f] C) a A U (B D C) = (AU B) n (AU C)
* a také „asociativita" Ar\(BC\C) = (Ar\B)C\C (stejně pro U) a „komutativita" AC\B = B H A (stejně pro U).
Komentář: Asociativita a komutativita operací sjednocení a průniku je na jednu stranu zcela přirozená, na druhou stranu však velmi důležitá například pro platnost následující definice.
Definice: Pro libovolný počet množin indexovaných pomocí I rozšířeně definujeme
Komentář: Nechť Ai = {2 • i} pro každé i G N. Pak UíeN je množina všech sudých přirozených čísel. Nechť B{ = {x \ x G N, x > i} pro každé i G N. Pak HíeN Bi = 0.
Množinový rozdíl
Definice 3.3. Rozdíl \ a symetrický rozdíl A dvou množin A, B definujeme
{x | x G Ai pro nejaké i E 1}
{x | x G Ai pro každé i G /} .
A\B AAB
A\B
AAB
18
* Příklady {a, b, c} \ {a, b, d} = {c},    {a, b, c}A{a, b, d} = {c, d}.
* Vždy platí například A \ (B H C) = (A \ B) U (A \ C) apod.
Definice: Pro libovolný počet množin indexovaných pomocí konečné I rozšířeně definujeme *
l\iei Ai = {x \ x E Ai pro lichý počet i E 1} .
Komentář: Povšimněte si, že operace rozdílu není asociativní ani komutativní (ostatně stejně je tomu u aritmetického rozdílu). Symetrický rozdíl už asociativní i komutativní je, není to však na první pohled vidět. Uměli byste toto dokázat?
Definice: Nechť A C M. Doplňkem A vzhledem k M je množina A = M \ A.
Komentář: 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.
* Vždy pro ACM platí A = A („dvojí" doplněk).
* Vždy pro A, B C M platí A U B =In5a A f] B = ÄUB. (Viz Věta 3.7.) 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} .
* Platí například 2^ = {0, {a}, {&}, {a, b}},
* 20 = {0},   2W0» = {0,{0},{{0}},{0,{0}}},
Věta 3.5. Počet prvků potenční množiny splňuje \2A\ = 2'^'.
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 4). 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 E 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|A|. □
3.3   Kartézský součin
Zatímco prvky v množinách jsou zcela neuspořádané, jsou mnohé situace, kdy musíme pracovat se „seřazenými" výčty prvků. V teorii množin lze takovéto seřazení definovat oklikou následovně:
Definice: Uspořádaná dvojice (a, b) je zadána množinou {{a}, {a, b}}.
Fakt: Platí (a, b) = (c, d) právě tehdy, když a = c a současně b = d. Uměli byste toto sami dokázat přímo z podané definice?
19
* Co je podle definice (a, a)? Je to (a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}.
S uspořádanými dvojicemi prvků je přímo svázán nadmíru důležitý pojem součinu dvou množin, který se zavádí takto:
Definice 3.6. 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 x B = {(a, b) | a G A, b G B} .
* Příklady {a, b} x {a} = {(a, a), (6, a)}, {c, d} x {a, b} = {(c, a), (c, b), (d, a), (d, b)}.
* Platí 0xX = 0 = Xx0 pro každou množinu X.
* Jednoduchá mnemotechnická pomůcka říká |Axi?| = |A| • |5| . Každá dvojice z A x B totiž odpovídá nezávislému výběru prvku z A a, prvku z B.
Uspořádání prvků a součiny množin nemusí být omezeny jen na dvojice, jejich snadného zobecnění na libovolné konečné počty členů lze dosáhnout následujícími definicemi.
Definice: Pro každé k G N, k > 0 definujeme uspořádanou k-tící (ai, • • • , ak) induktivně
- (ai) = ai,
- (a1; a2, ■ ■ ■ , ai, ai+1) = ((<2i, a2, ■ ■ ■ , aj), ai+1).
Všimněte si, že tato definice používá tzv. rekurentní vztah, blíže viz Oddíl 5.1.
Fakt: Platí (a1; • • • , a^) = (&i, • • • ,      právě když    = 6j pro každé i G N kde 1 < i < k.
Definice kartézského součinu více množin: Pro každé A; G N definujeme
A\ x A2 x ■ ■ ■ x Ak = {(ai,a2, ■ ■ ■ , a^) \ ai £ Ai pro každé 1 < i < k} .
Navíc pokud jsou množiny Ai indexovány přes libovolnou konečnou množinu I 3 i, tak jejich kartézský součin krátce píšeme jako X iejAi.
* Například Z3 = ZxZxZ =        k) |      k G Z}.
* Co je A°l   {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. 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.
3.4   Porovnávání a určení množin
Pro obecnou ilustraci formálního množinového kalkulu si ukažme dva důkazy rovností mezi množinovými výrazy. Podobně lze (rozepsáním příslušných definic) rutinně dokazovat další množinové vztahy.
Věta 3.7. Pro každé dvě množiny A, B C M platí AU B = A C\ B.
20
Důkaz v obou směrech rovnosti (viz ilustrační obrázek).
. AU B CÄÍ15: Pro x E M platí x E A U B, právě když x G' A U B, neboli když zároveň x E1 A a x E1 B. To znamená x E A a, zároveň x E B, z čehož vyplývá požadované x E Ad B.
• AU B D Afl-B: Pro x E M platí x G Aľl5, právě když x E A a zároveň x E B, neboli když zároveň x E1 A a x E1 B. To znamená x G' A U B, z čehož vyplývá požadované x E A U B.
Věta 3.8. Pro každé tři množiny A, B, C platí
A\(BHC) = (A\B) U(A\C).
Důkaz (viz ilustrační obrázek).
. A \ (B n C) C (A \ B) U (A \ C): Je-li x E A \ (B H C), pak x E A a zároveň x E1 (B C\ C), neboli x E1 B nebo x E1 C. Pro první možnost máme x E (A\ B), pro druhou x E (A\C).
. Naopak A \ (B H C) D (A \ B) U (A \ C): Je-li x E (A\ B) U (A \ C), pak x E (A\ B) nebo x E (A\C). Pro první možnost máme x E A a zároveň x E1 B, z čehož plyne x E A a zároveň x G' {B H C), a tudíž x E A \ (B H C). Druhá možnost je analogická. ^
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 = {x1}x2,... ,xn}. Pro A C X definujeme charakteristický vektor xa jako
Xa = (cij c2j • • • j cn)? kde q = 1 pro x,i E A a q = 0 jinak.
Užitečnost této reprezentace je ilustrována také následnými fakty.
• Platí A = B právě když x a = Xb-
• Množinové operace jsou realizovány „bitovými funkcemi"
sjednocení ~ OR, průnik ~ AND, symetrický rozdíl ~ XOR.
21
Princip inkluze a exkluze
Tento důležitý a zajímavý kombinatorický princip je někdy také nazýván „princip zapojeni a vypojení1". Používá se ke zjišťování počtů prvků množin s neprázdnými průniky.
Věta 3.9. Počet prvků ve sjednoceni dvou čí tři množin spočítáme:
\Al)B\ = \A\ + \B\ -\Ar\B\
\AUBUC\ = \A\ + \B\ + \C\ -\Ar\B\ - \AnC\ - \BnC\ + \AnBnC\
A
A
B
B
Důkaz: Uvedeme si podrobný důkaz prvního vztahu |A U 5| = \A\ + \B\ — \AC\ B\, přičemž druhá část je analogická (viz obrázková ilustrace). Nechť x G A U B. Pokud i^B, tak je x G A a prvek x je započítán na pravé straně \A\ + \B\ — \A H B\ právě jednou v \A\. Obdobně je to v případě x G' A. Nakonec pro x G A H B je ve vztahu \A\ + \B\ — \AC\ B\ tento prvek x započítán také 1 + 1 — 1 = 1 krát. □
Komentář: Všimněte si, že Větu 3.9 lze stejně tak využít k výpočtu počtu prvků v průniku množin...
Příklad 3.10. 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 n B n C\ = 3, (zde pozor) \Ar\B\ = 3 + 0, \A n C\ = 3 + 0, \B n C\ = 3 + 4 do Věty 3.9 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:
LU
E (
0^/C{l,...,n}
.1)1/1-1.
iei
(Jeho znalost nebude v předmětu vyžadována.)
3.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 3.11. Relace mezi množinami A\, A2, ■ ■ ■ , Ak, pro k G N,
je libovolná podmnožina kartézského součinu
R C A1 x A2 x • • • x Ak.
Pokud Ai = A2 = ■ ■ ■ = Ak = A, hovoříme o k-ární relací R na A. Speciálně tak mluvíme třeba o binární (k = 2), ternárni (k = 3) nebo unární (k = 1) relaci.
22
Komentář: 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.
* i + j)        G N} je ternární relace na N.
* {3 • i | i G N} je unární relace na N.
* Jaký význam vlastně mají unární a nulární relace na A?
Uvědomme si, jak obecně je relace definována - její definice umožňuje podchytit skutečně libovolné „vztahy" mezi prvky téže i různých množin. V praxi se relace velmi široce využívají třeba v relačních databázích...
Funkce mezi množinami
První školní setkání s instancemi relací povětšinou proběhne u pojmu funkce. Ovšem tradiční školní pojetí funkce ji obvykle identifikuje s nějakým výpočetním (analytickým) předpisem či vzorcem. Pojem funkce je však daleko obecnější a zcela abstraktní, což si v tomto oddíle bohatě ilustrujeme a poslouží nám to i pro lepší pochopení obecnějšího pojmu relace.
Definice 3.12. (Totální) funkce z množiny A do množiny B
je relace / mezi A a, B taková, že pro každé x E A existuje právě jedno y E B takové, že (x, y) G /. Množina A se nazývá definiční obor funkce f. Funkcím se také říká zobrazení.
Poznámka: Množinu B lze nazvat oborem hodnot, ale častější terminologie je, že oborem hodnot funkce / s definičním oborem A je podmnožina množiny B sestávající z těch y, pro něž existuje x G A takové, že (x,y) G /. Pro náš výklad není podstatné, k čemu se přikloníme.
Komentář: Neformálně řečeno, ve funkci / je každé „vstupní" hodnotě x přiřazena jednoznačně „výstupní" hodnota y. Naopak v obecné relaci počty „přiřazených" hodnot neomezujeme. Přiřazené „výstupní" hodnoty tvoří obor hodnot (příp. jeho podmnožinu). Například v ukázce na obrázku to jsou {a, b, d} C B.
Pokud je funkce dána výčtem všech svých dvojic, lze definiční obor z tohoto výčtu jednoznačně odvodit (je to množina těch prvních složek dvojic), avšak obecně je definiční obor nedílnou součástí definice konkrétní funkce, neboť v obvyklém případě implicitních definic funkcí (třeba vztahem) jej nelze vždy jednoznačně odvodit.
Značení: Pro funkce místo (x,y) G / píšeme obvykle f(x) = y. Zápis / : A —>• B říká, že / je funkce s definičním oborem A a oborem hodnot, který je podmnožinou B.
Komentář: Příklady funkcí jsou třeba následující.
* Definujeme funkci / : N —> N předpisem f (x) = x + 8. Pak / = {(x, x + 8) | x G N}.
23
* Definujeme funkci plus :NxN-íN předpisem plus (i, j) = i + j. Pak plus = {(i, j, i + j) \i,j G N}.
Definice: Pokud naši Definici 3.12 upravíme tak, že požadujeme pro každé x E A nejvýše jedno y E B takové, že (x, y) E /, obdržíme definici parciálni funkce z A do B.
Komentář:
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.
Komentář: Následuje několik příkladů parciálních funkcí. * Definujeme parciální funkci / : TL —> N předpisem
/(*)
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 f(x) = log x je jen parciální - není definována pro x < 0.
* Co je relace, přiřazující lidem v ČR jejich (česká) rodná čísla?
Navazující studium
I když jste se s "množinami" setkávali už od základní školy, do formálně matematické teorie množin asi nahlédnete na VS poprvé. I když některé čtenáře množství zde uvedených symbolů a pojmů možná nejprve vyleká, jedná se vesměs o velmi intuitivní věci, které není problém pochopit byt7 z ilustračních obrázků a příkladů. Naučte se s konečnými množinami a relacemi dobře pracovat alespoň na té intuitivní úrovni, jakou v této lekci vidíte. Ostane, jak již bylo psáno, množiny jsou základním stavebním kamenem celé matematiky.
V dalších lekcích budeme důležité pojmy relací a funkcí dále rozvíjet. Mimo naší tzv. naivní teorie množin si lehký náhled na obecně nekonečné množiny a jejich zdánlivé paradoxy i informatické aplikace (jako třeba problém zastavení) ukážeme nakonec v Lekci 12...
24
4   Techniky matematických důkazů
Úvod
Náš hlubší úvod do matematických formalismů pro informatiku pokračujeme základním přehledem technik matematických důkazů. Pro vysvětlení, z Lekce 1 sice víme, že matematický důkaz má jednotnou formu Defínice 1.3, ale nyní se budeme věnovat takříkajíc šablonám, podle nichž můžeme (snadněji) korektní důkaz sestavit.
Třebaže matematické dokazování a příslušné techniky mohou někomu připadat neprůhledné (a zpočátku možná zbytečné), jejich pochopení a zvládnutí není samoúčelné, neboť nám pomáhá si mnoho uvědomit o studovaných problémech samotných. Konečně, jak si můžeme být jisti svými poznatky, když bychom pro ně nebyli schopni poskytnout důkazy? Během studia tohoto předmětu poznáte (a ti méně šťastní až s překvapením u zkoušky), že podstata toho, k čemu naším výkladem směřujeme, se dá neformálně shrnout slovy „ naučit se přesně vyjadřovat a být si svými tvrzeními naprosto jisti" a analogicky později „naučit se navrhovat správné algoritmy a být si i svými programy naprosto jisti".
Cíle
Cílem této lekce je popsat základní techniky matematických důkazů, z nichž největší důraz klademe na matematickou indukci. Každý student by se měl alespoň naučit formálně psané důkazy číst a chápat, nejlépe i sám umět jednoduché důkazy tvořit.
4.1   Přehled základních důkazových technik
V matematice je často používaných několik následujících způsobů - technik, jak k danému tvrzení sestavit korektní formální důkaz. (Uvědomme si, že jedno tvrzení mívá mnoho různých, stejně korektních důkazů; ty se však mohou výrazně lišit svou složitostí a čitelností. Uváděné techniky nám pomohou najít důkaz co nejjednodušší.) Tyto techniky si v bodech shrneme zde:
• Přímé odvození. To je způsob, o kterém jsme se dosud bavili.
Komentář: Postupujeme přímo od předpokladů k závěru, což vypadá nejpřirozeněji, ale sami poznáte, že taková „přímá" cesta bývá obtížně k nalezení.
• Kontmpozíce (také obměnou - „obrácením", či nepřímý důkaz). Místo věty
„Jestliže platí předpoklady, pak platí závěr." budeme dokazovat ekvivalentní větu
„Jestliže neplatí závěr, pak neplatí alespoň jeden z předpokladům
Komentář: Na rozdíl od přímého odvození se obvykle lépe hledá cesta „pozpátku", určitě tento fenomén znáte například z hledání cest v dětských bludištích.
• Důkaz sporem. Místo věty
„Jestliže platí předpoklady, pak platí závěr." budeme dokazovat větu
„Jestliže platí předpoklady a platí opak závěru, pak platí... "
- nějaké zjevně nepravdivé tvrzení, nebo případně
- závěr (tj. opak jeho opaku) či opak jednoho z předpokladů.
Komentář: Třebaže tato šablona vypadá trochu složitě, stará dobrá matematická moudrost praví: „Nevíte-li, jak nějakou větu dokázat, zkuste důkaz sporem... "
25
• Matematická indukce. Pokročilá technika, kterou popíšeme později... Tyto techniky asi nejlépe ilustrujeme následujícími příklady důkazů.
Příklad důkazu kontrapozicí
Definice: Prvočíslo je celé číslo p > 1, které nemá jiné dělitele než lap.
Příklad 4.1. Na důkaz kontrapozicí (obměnou).
Věta. Jestliže p je prvočíslo větší než 2, pak p je liché. Důkaz obměněného tvrzení: Místo uvedeného znění věty budeme dokazovat, že je-li p sudé, pak p není větší než 2 nebo p není prvočíslo.
Připomínáme, že podle definice je p sudé, právě když lze psát p = 2 • k, kde k je celé. Jsou jen dvě snadno řešitelné možnosti:
• k < 1. Pak p = 2 • k není větší než 2.
• k > 1. Pak p = 2 • k není prvočíslo podle definice. □
Poznámka: Důkazy kontrapozicí pracují s negací (opakem) předpokladů a závěru. Je-li např. závěrem komplikované tvrzení tvaru
„z toho, že z A a B plyne C, vyplývá, že z A nebo C plyne A a B",
není snadné pouhou intuicí zjistit, co je vlastně jeho negací. Proto je vhodné si nejprve opak závěru přepsat do takzvaného normálního tvaru, který byl vysvětlen v Oddílu 2.2.
Příklady důkazu sporem
Příklad 4.2.  Jiný, kratší přístup k Důkazu 4.1.
Věta. Jestliže p je prvočíslo větší než 2, pak p je liché.
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2 • k pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo). ^
Důkaz sporem je natolik specifický a důležitý v matematice, že si zaslouží širší vysvětlení. Co je vlastně jeho podstatou? Je to (zcela přirozený) předpoklad, že v konzistentní teorii nelze zároveň odvodit tvrzení i jeho negaci. Jestliže tedy ve schématu
„Jestliže platí předpoklady a platí opak závěru, pak platí závěr nebo opak jednoho z předpokladů, nebo platí jiné zjevně nepravdivé tvrzení."
odvodíme k některému předpokladu jeho opak, nebo případně jiné tvrzení, které odporuje všeobecně přijatým faktům (přesněji axiomům, například 0 = 1), pak něco musí být „špatně". Co však v našem tvrzení může (nezapomeňte předpoklad konzistence) být chybné? Původní předpoklady byly dány, takže zbývá jedině náš dodatečný předpoklad, že platí opak závěru. Tudíž opak závěru nemůže nikdy platit a dvojí negací odvodíme, že platí původní závěr.
Příklad 4.3. Opět sporem.
Věta. Číslo \/2 není racionální.
26
Důkaz sporem: Nechť tedy y/2 je racionální, tj. nechť existují celá kladná čísla r, s taková, že y/2 = r/s. Můžeme navíc předpokládat, že r je nejmenší možné takové celé kladné číslo.
- Pak 2 = r2/s2, tedy r2 = 2 • s2, proto r2 je dělitelné dvěma. Z toho plyne, že i r je dělitelné dvěma (proč? opět na to můžete jít sporem...).
- Jelikož r je dělitelné dvěma, je r2 dělitelné dokonce čtyřmi, tedy r2 = 4 • m pro nějaké celé m. Pak ale také 4 • m = 2 • s2, tedy 2 • m = s2 a proto s2 je dělitelné dvěma.
- Z toho plyne, že s je také dělitelné dvěma. Celkem dostáváme, že r' = r/2 i s' = s/2 jsou celá, platí y/2 = r/s = r'/s' a přitom r' < r, což je spor s předpokladem, že r bylo nejmenší možné takové číslo. □
Komentář:  „Nevíte-li, jak nějakou větu dokázat, zkuste důkaz sporem... "
4.2   Věty typu „právě tehdy (když)"
Uvažujme nyní (v matematice poměrně hojné) věty tvaru
„Nechť platí předpoklady P. Pak tvrzení A platí právě tehdy, platí-li tvrzení B." Příklady jiných jazykových formulací téže věty jsou:
* Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy, když platí tvrzení B.
* Za předpokladů P je tvrzení B nutnou a postačující podmínkou pro platnost tvrzení A.
* Za předpokladů P je tvrzení A nutnou a postačující podmínkou pro platnost tvrzení B.
Fakt: Plný důkaz vět tohoto tvaru má vždy dvě části(!). Je třeba dokázat:
* Jestliže platí předpoklady P a tvrzení A, pak platí tvrzení B.
* Jestliže platí předpoklady P a tvrzení B, pak platí tvrzení A.
Komentář: Je možno se někdy oddělenému zpracování obou částí či směrů důkazu u tvrzení tvaru ekvivalence („právě když") vyhnout? Ano, stačí dělat pouze tzv. ekvivalentní úpravy, ale je to dosti nebezpečné. Co například tvrzení „a = b právě když ax = bxÍLl To přece dokážeme vynásobením obou stran rovnosti stejným číslem x...
Je to sice téměř pravda, ale(!) musíme si všimnout, že násobení obou stran rovnosti je ekvivalentní úpravou jen pro x 7^ 0; jinak nazpět dělíme nulou (což na světě dokáže snad pouze Chuck Norris). Zapamatujte si, že nejlepší cestou, jak se takovým chybám a problémům vyhnout, je skutečně poctivě dokazovat každý směr ekvivalence zvlášť.
Následující příklad je záměrně poněkud krkolomný, aby ukázal situaci, ve které se oba směry dokazované ekvivalence výrazně liší a nelze je vyslovovat dohromady.
Příklad 4.4. Na důkaz typu „právě tehdy (když)".
Věta. Pro každé dvě množiny A, B platí, že 2A = 2B právě tehdy, když A2 = B2 (připomínáme, že 2A označuje potenční množinu a A2 znamená A x A).
Důkaz: Nezapomínáme, že našim úkolem je dokázat oba směry tvrzení (implikace zleva doprava a zprava doleva). Přitom obě implikace budeme dokazovat obměnou, symbolicky jako 2A/2B A2 / B2.
27
Začneme s prvním směrem: Je-li 2 7^ 2 , pak existuje množina X taková, že X C A a X <2 B (nebo naopak - což se řeší symetricky). X <2 B přitom podle definice znamená, že pro nějaké y E X platí y ^ B. Zároveň však y G A. Proto (y, y) G Ä2, ale (y, y) ^ B2, neboli A2 ^ B2.
V opačném směru postupujeme z předpokladu A2 7^ B2. Zase (s ohledem na symetrii) z toho odvodíme, že existuje uspořádaná dvojice taková, že (x,y) G Ä2, ale (x, y) ^ B2. Z posledního vyplývá, že x ^ B nebo y ^ B. Opět bez újmy na obecnosti můžeme vzít jen případ x ^ B. Avšak z (x, y) G A2 vidíme, že x E A. Proto {x} G 2A, ale {x} ^ 2B, neboli 2A ^ 2B. □
4.3   Matematická indukce
Pokud se souhrnně podíváme na důkazové techniky v matematice, všimneme si, že matematickou indukci lze považovat za „dvorní" důkazovou technikou diskrétní matematiky. To proto, že umožňuje pohodlně dokazovat i složitá tvrzení po jednotlivých (malých a diskrétních) krocích od jednoduchých počátků. Uvažme tedy větu ve tvaru:
„Pro každé přirozené (celé) n > k0 platí T (n)."
Zde k0 je nějaké pevné přirozené číslo a T(n) je tvrzení parametrizované číslem n. Příkladem je třeba tvrzení:
Pro každé n > 0 platí, že n přímek dělí rovinu nejvýše na ^n(n + 1) + 1 oblastí.
Definice 4.5. Princip matematické indukce říká, že k důkazu věty
„Pro každé přirozené (celé) n > ko platíT(n)." stačí ověřit platnost těchto dvou tvrzení:
• T(k0) (tzv. báze neboli základ indukce)
• Pro každé k > ko; jestliže platí T(k), (indukční předpoklady pak platí také T(k + 1). (indukční krok)
Formálně řečeno, matematická indukce je axiomem aritmetiky přirozených čísel.
Opět jako v předešlém si tuto techniku ilustrujeme množstvím názorných příkladů.
Příklady důkazů indukcí
Příklad 4.6.  Velmi jednoduchá a přímočará indukce.
Věta. Pro každé přirozené, n > 1 je stejná pravděpodobnost, že při současném hodu n kostkami bude výsledný součet sudý, jako, že bude lichý.
Důkaz: Základ indukce je zde zřejmý: Na jedné kostce (poctivé!) jsou tři lichá a tři sudá čísla, takže obě skupiny padají se stejnou pravděpodobností.
Indukční krok pro k > 1: Nechť psk pravděpodobnost, že při hodu k kostkami bude výsledný součet sudý, a plk je pravděpodobnost lichého. Podle indukčního předpokladu je psk = plk = |. Hoďme navíc (k + l)-ní kostkou. Podle toho, zda na ní padne liché nebo sudé číslo, je pravděpodobnost celkového sudého součtu rovna
3 z 3 s _ 1 QPk + QPk ~ 2
28
a stejně pro pravděpodobnost celkového lichého součtu. □
Příklad 4.7.   Ukázka skutečné důkazové „síly" principu matematické indukce. Věta. Pro každé n > 0 platí, že n přímek dělí rovinu nejvýše na
1
-n(n + 1) + 1
oblastí.
Důkaz: Pro bázi indukce postačí, že n = 0 přímek dělí rovinu na jednu oblast. (Všimněte si také, že 1 přímka dělí rovinu na dvě oblasti, jen pro lepší pochopení důkazu.)
Mějme nyní rovinu rozdělenou n = k přímkami na nejvýše ^k(k + l) +1 oblastí. Další, (k + l)-ní přímka je rozdělena průsečíky s předchozími přímkami na nejvýše k + 1 úseků a každý z nich oddělí novou oblast roviny. Celkem tedy bude rovina rozdělena našimi přímkami na nejvýše tento počet oblastí:
h(k + l) + l + (fc + 1) = Ifc(fc + l) + I.2(fc + l) + 1 = i(fc + l)(fc + 2) + 1 A toto je přesně naše tvrzení pro n = k + 1, takže jsme hotovi.
□
Příklad 4.8. Další indukční důkaz rozepsaný v podrobných krocích. Věta. Pro každé n > 0 platí Yľj=oJ = n^n^ .
Důkaz indukcí vzhledem k n.
• Báze: Zde musíme dokázat platnost tvrzení pro n := 0, což je v tomto případě rovnost Y^°j=oJ = 0<"02hl'> ■ Tato rovnost (zjevně) platí.
• Indukční krok: Musíme dokázat, pro každé k > 0, že z platnosti tvrzení pro n := k vyplývá platnost pro n := k + 1, což konkrétně znamená:
Jestliže platí X^=o J = ki~k^, pak platí X^=o J = (fc+1^+1+1). Předpokládejme tedy, že "Y^=Qj = k(-k^^  a pokusme se dokázat, že pak také
k+l
. _  (fc+l)(fc+l + l)  _  (k+ l)(fc + 2)
j=0
To už plyne přímočarou úpravou: i=o j=0
Podle principu matematické indukce je celý důkaz hotov. □
29
4.4   Komentáře k matematické indukci
Pro správné a úspěšné použití indukce v dokazování je vhodné si zapamatovat několik cenných rad:
* Základní trik všech důkazů matematickou indukcí je vhodná reformulace tvrzení T(n + 1) tak, aby se „odvolávalo" na tvrzení T(n).
- Dobře se vždy podívejte, v čem se liší tvrzení T(n + 1) od tvrzení T(n). Tento „rozdíl" budete muset v důkaze zdůvodnit.
* Především dokud se matematickou indukci teprve učíte, důsledně používejte následující pomůcku. Zaveďte si další proměnnou k a formulujte svá tvrzení a úpravy stylem „platí-li naše tvrzení T(n) pro n := k, pak bude platit i pro n := k + 1". Elegantně se tak vyhnete nejasnostem a chybám vznikajícím popletením n a n + 1.
* Pozor, občas je potřeba zesílit tvrzení T(n), aby indukční krok správně „fungoval" (a jsou situace, kde tento trik velmi pomáhá).
- Velkým problémem bohužel je, že není možno podat přímočarý návod, jak vhodné zesílení nalézt (ani kdy jej vlastně hledat). Jedná se často spíše o pokusy a „hádání z křišťálové koule", kde ke správnému řešení dospějete až díky dostatečné zkušenosti s indukcí. Viz Příklady 4.9 a 4.10.
* Často se chybuje v důkazu indukčního kroku, neboť ten bývá většinou výrazně obtížnější než báze, ale o to zrádnější jsou chyby v samotné zdánlivě snadné bázi!
- Dejte si dobrý pozor, od které hodnoty n > ko je indukční krok univerzálně platný a jestli případně báze nezahrnuje více než jednu hodnotu...
Zesílení tvrzení v indukčním kroku
Zmíněný fakt, že v některých situacích je vhodné dané tvrzení nahradit něčím „silnějším" pro hladký průběh matematické indukce si ukážeme v následujících dvou příkladech. Jaké zesílení však máme na mysli? Především to musí být nějaké tvrzení T'(n), ze kterého původní tvrzení T(n) jednoduše vyplývá. Jak si tím ale v indukčním kroku pomůžeme? Je na jedné straně pravdou, že nově musíme dokazovat silnější závěr T'(n + 1), ale zároveň máme k dispozici silnější indukční předpoklad T'(n) a to právě může být klíčovou pomocí.
Příklad 4.9. Kdy je vhodné (a v zásadě také nutné) indukční tvrzení zesílit... Věta. Pro každé n > 1 platí
Co však indukční krok"? Předpoklad s(n) < 1 je sám o sobě „příliš slabý" na to, aby bylo možno tvrdit také s(n + 1) = s(n) + t^tt < 1-
Neznamená to ještě, že by celé tvrzení nebylo platné, jen je potřeba náš indukční předpoklad zesílit, zhruba řečeno aby přesněji vyjadřoval podstatu zadaného příkladu (sami si pro několik prvních členů spočítejte, „o kolik menší" je s(n) než pravá strana 1). Budeme raději dokazovat silnější
Tvrzení. Pro každé přirozené n > 1 platí s(n) < 1 — ^ < 1.
Důkaz: Báze indukce je zřejmá, neboť | < 1.
30
To platí pro bázi n = 1, neboť \ < \ — \ (nezapomeňte ověřit!), a dále už úpravou jen dokončíme zesílený indukční krok:
1               11 1 sin + 1) = s(n) H--- < 1---1--- = 1---
v       '       v '    2n+1 ~       2n    2n+1 2n+1 □
Komentář: Příklad 4.9 má co do činění i s klasickými Zenónovými paradoxy, konkrétně s paradoxem dichotomie. Představme si, že máme doběhnout do stanoveného cíle (tj. jednotku vzdálenosti, třeba přes celé hřiště). Když uběhneme půlku, stále nám půlka k uběhnutí zbývá. Když uběhneme další čtvrtinu, stále nám poslední čtvrtina zbývá. Když uběhneme další osminu, stále nám osmina zbývá. A tak dále... Doběhneme vůbec někdy do cíle?
Příklad 4.10. Další, už ne tak jednoduchá, ukázka, v níž je nutné pro indukční krok zesílit a nalezení toho správného zesílení vyžaduje zkušenost a cvik...
Věta. Pro každé n > 1 platí
,,111 1
t(n) =--1---1---1-----1--;-- < 1.
K J     1-22-33-4 n(n + l)
Důkaz: Báze indukce je zřejmá, neboť      < 1. Co však indukční krok"? Předpoklad t(n) < 1 je sám o sobě opět „příliš slabý" na to, aby bylo možno tvrdit t(n + 1) = t(n) + (n+1^n+2) < 1-
Znovu je tedy potřeba náš indukční předpoklad zesílit. Budeme třeba dokazovat
Tvrzení. Pro každé přirozené n > 1 platí t(n) < 1 — ^-j-j- < 1 .
To platí pro n = 1 (nezapomeňte ověřit!) a dále už úpravou jen dokončíme zesílený indukční krok:
■y i i
t(n + 1) = t(n) +----- < 1
(n + l)(n + 2) ~       n + 1     (n + l)(n + 2) -(n + 2) + 1   = x__1_
(n + l)(n + 2) n + 2 □
Rozšíření předpokladu; silná indukce
Mimo zesilování tvrzení indukčního kroku jsme někdy okolnostmi nuceni i k rozšiřování samotné báze indukce a s ní indukčního předpokladu na více než jednu hodnotu parametru n.
- Můžeme například předpokládat platnost (parametrizovaných) tvrzení T(n) iT(n + l) zároveň, a pak odvozovat platnost T(n + 2). Toto lze samozřejmě zobecnit na tři i více předpokládaných parametrů.
- Můžeme dokonce předpokládat platnost tvrzení T(j) pro všechna j = ko, ko + 1,..., n najednou a dokazovat T(n + 1) (vznešeně se této variantě indukce říká silná indukce). Toto typicky využijeme v případech, kdy indukční krok „rozdělí" problém T(n + 1) na dvě menší části a z nich pak odvodí platnost T(n + 1).
Fakt: Obě prezentovaná „rozšíření" jsou v konečném důsledku jen speciálními instancemi základní matematické indukce; nejsou o nic „silnější" ve striktním matematickém smyslu a použité rozšířené možnosti pouze zjednodušují formální zápis důkazu.
31
Příklad 4.11. Když je nutno rozšířit bázi a indukční předpoklad... Věta. Nechť funkce f pro každé n > O splňuje vztah
/(n + 2) = 2/(n + l)-/(n).
Pokud platí /(O) = 1 a zároveň /(l) = 2, tak platí f(n) = n + 1 pro všechna přirozená n > 0.
Důkaz: Už samotný pohled na daný vztah /(n + 2) = 2/(n + 1) — f(n) naznačuje, že bychom měli rozšířit indukční předpoklad (a krok) zhruba takto:
Pro každé přirozené k > 0; jestliže platí f(n) = n + 1 pro n := k a zároveň pro n := k + 1 (neboli f (k) = k + 1 a f {k + 1) = k + 2), pak f (n) = n + 1 plat/ taiíé pro n := A; + 2 (neboli f (k + 2) = k + 3).
Báze indukce - pozor, zde už musíme ověřit dvě hodnoty pro n := 0 a n := 1:
/(O) = 0 + 1 = 1,   /(l) = 1 + 1 = 2
Náš indukční krok tak nyní může využít celého rozšířeného předpokladu, znalosti hodnot f(k) i /(A; + 1), pro ověření požadovaného vztahu pro n := k + 2
/(n) = /(fc + 2) = 2/(fc + 1) - f (k) = 2-(fc + l + l)-(fc + l) = fc + 3 = n + l.
□
Komentář: Jak by tento důkaz měl být formulován v tradiční indukci? („Substitucí" nového tvrzení.)
Příklad 4.12. Ukázka s vhodným použitím silné indukce:
Věta. Každé přirozené číslo n > 2 lze zapsat jako součin prvočísel (může být jen jednoho a prvočísla nemusí být různá).
Důkaz: Báze indukce. Nechť n = 2, pak n je prvočíslem a součinem jednoho prvočísla. Indukční krok. Pokud nemá n vlastní dělitele, je n prvočíslem vzhledem k předpokladu n > 2, což je shodné s bází.
Jinak napíšeme n = a ■ b, kde platí a, b > 2 a zároveň a, b < n, a proto lze na obě čísla a, b použít indukční předpoklad. Tudíž každé z nich lze napsat jako součin prvočísel a jelikož ta nemusí být různá, prostě oba součiny sloučíme do jednoho, jehož výsledkem je a ■ b = n. □
Závěrem malý „problém"
Příklad 4.13. Aneb jak snadno lze v matematické indukci udělat chybu. Věta. („nevěta")
V každém stádu o n > 1 koních mají všichni koně stejnou barvu.
Důkaz indukcí vzhledem k n. Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.
Indukční krok: Nechť S = {Ki,..., Kn+i} je stádo o n + 1 koních. Dokážeme, že všichni koně mají stejnou barvu. Uvažme dvě
- S' = {KuK2,...,Kn}
- S" = {K2,..., Kn, Kn+i]
32
Podle indukčního předpokladu mají všichni koně ve stádu S' stejnou barvu B'. Podobně všichni koně ve stádu S" mají podle indukčního předpokladu stejnou barvu B". Dokážeme, že B' = B", tedy že všichni koně ve stádu S mají stejnou barvu. To ale plyne z toho, že koně K2,..., Kn patří jak do stáda S', tak i do stáda S". □
Komentář: Ale to už je podvod! Vidíte, kde?
Navazující studium
Jak jsme již řekli, matematické důkazy a jejich chápání jsou samozřejmě nezbytné ke studiu vysokoškolských matematických předmětů. Bez schopnosti přesného vyjadřování a chápání defínic a vět se ale informatik neobejde, ani pokud se zaměřuje čistě aplikovaným směrem; příkladem je třeba správné pochopení různých norem a specifíkací.
Na druhou stranu umění "tvořit" nové matematické důkazy je dosti obtížné a nedá se jemu jen tak snadno naučit - vyžaduje to mnoho tréninku a pokročilých matematických zkušeností. Jelikož je schopnost formálního matematického dokazování nezbytná (převážně jen) v teoretických informatických disciplínách, není tato část kritická v celém rozsahu našeho předmětu (a u zkoušek se objeví s menším důrazem), ale to neznamená, že byste se jí mohli zcela vyhýbat. Obzvláště techniku matematické indukce by měl každý informatik aspoň trochu ovládat, neboť s jejím použitím se zajisté ještě mnohokrát setkáte v budoucím studiu. Například znovu hned v Lekcích 5 a 6 tohoto textu.
33
5   Rekurze a induktivní definice
Úvod
Mimo „přímočarých" defínic množin a funkcí, jako výčtem prvků či explicitním zadáním, se obzvláště v informatice setkáváme s defínicemi nepřímými, které se odvolávají na sebe sama. Ostatně jde o problematiku velmi podobnou rekurentním programům, které jste už sami mohli potkat.
Odborně se taková situace nazývá rekurzí či induktivní definicí. My si celou problematiku probereme z matematického pohledu od jednoduchých rekurentních defínic posloupností po induktivní definice množin a funkcí a dokazování nad nimi, v čemž budeme pokračovat v příští lekci. Podstatnou technikou práce s takovými defínicemi je samozřejmě matematická indukce ve svých velmi rozmanitých podobách.
Cíle
Cílem našeho výkladu je jednak vysvětlit a procvičit základní rekurentní definice a vztahy pro posloupnosti a funkce s více parametry, za druhé připravit půdu pro nelehkou látku strukturální indukce nad induktivními defínicemi v příští lekci.
5.1   Posloupnosti a rekurentní vztahy
Pokud chceme obecně v matematice vyjádřit uspořádaný soubor objektů, používáme pojem posloupnost. Důležité je si uvědomit, že na rozdíl od množin je opakování prvků v posloupnosti povoleno(l). Uspořádané fc-tice (viz Oddíl 3.2) z daného oboru hodnot H jsou tak nazývány konečnými posloupnostmi délky k (nad H). Pojem posloupnosti zobecňuje toto pojetí na „nekonečnou délku" takto:
Definice 5.1. Posloupnost (nekonečná) je zobrazením z přirozených čísel N do oboru hodnot H, neboli
p : N H.
Místo „funkčního" zápisu n-tého členu posloupnosti jako p(n) častěji používáme „indexovou" formu jako pn, ve které se celá posloupnost zapíše (pn)neN-
Komentář: Oborem hodnot H posloupnosti obvykle bývá nějaká číselná množina, ale může to být i jakákoliv jiná množina.
Poznámka: Třebaže to není zcela formálně přesné, běžně se setkáme s posloupnostmi indexovanými od nuly nebo od jedničky, jak se to v aplikacích hodí (bez ohledu na to, zda nulu považujeme za přirozené číslo nebo ne). I my se budeme touto „uvolněnou" konvencí řídit a vždy si určíme počáteční index podle potřeby.
Pojem poslopupnosti si nejlépe ilustrujeme několika příklady:
• po = 0, pi = 2,... ,pi = 2i,... je posloupnost sudých nezáporných čísel,
• (3, 3.1, 3.14, 3.141,...) je posloupnost postupných dekadických rozvojů čísla 7r,
• třeba (jablko, hruška, švestka, hruška, hruška,...) je posloupnost nad druhy ovoce coby oborem hodnot.
• (1, —1, 1, — 1,...) je posloupnost určená vztahem pi = (—1)*, i > 0,
• avšak pokud bychom chtěli stejnou posloupnost (1, —1, 1, —1,...) určit indexy od jedné, tj. zadat ji jako qÍ7 i > 1, tak definiční vzorec bude vypadat (proč?) qri = (—l)l_1.
34
Definice: Posloupnost (pn)neN je
* rostoucí pokud pn+i > Pn a nerostoucí pokud pn+i < Pn,
* klesající pokud pn+i < Pn a neklesající pokud pn+i > Pn platí pro všechna n.
Rekurentní zadání posloupnosti
Když je naše posloupnost definována jako zobrazení z přirozených čísel, proč se jí věnujeme zvlášť, mimo běžné funkce? Asi hlavním důvodem pro tuto zvláštní péči je možnost definovat posloupnosti pomocí odkazů na sebe sama - tzv. rekurentně (což třeba pro reálné funkce možno není).
Definice: Říkáme, že posloupnost (pn)neN je zadána rekurentně, pokud je dán její počáteční člen po (či několik počátečních členů) a dále máme předpis, jak určit hodnotu členu Pn+i z hodnot pi pro nějaká i < n.
Komentář: Ukázky rekurentně zadaných posloupností:
• Zadáme-li posloupnost pn počátečním členem po = 1 a rekurentním vztahem pn+i = 2pn pro n > 0, pak platí pn = 2n pro všechna n.
• Funkce „faktoriál" (na přirozených číslech) je dána počáteční hodnotou 0! = 1 a rekurentním vztahem (n + 1)! = (n + 1) • n\ pro n > 0.
• Známá Fibonacciho posloupnost je zadaná počátečními členy f± = f2 = 1 a vztahem
fn+2 = fn+1 +/„prOtl>l.
Všimněte si v poslední ukázce, že není potřeba doslova dodržovat formu rekurentního vztahu vPn+i z hodnot pi\ ale vždy je třeba hodnotu následujícího členu posloupnosti odvozovat z předchozích (tj. už určených) členů, v tom případě „fn+2 z hodnot f i, i = n, n + 1".
Příklad 5.2. Posloupnost f : N —y Z je zadaná rekurentní defínicí
/(O) = 3    a    /(n + l) = 2-/(n) + l
pro všechna přirozená n. Určete hodnotu f(n) explicitním 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). Jakl Zkusíme vypočítat několik prvních hodnot a uvidíme...
/(I) = 2-/(0) + l=2-3 + l = 7
f (2) = 2-/(l) + l =2-7+1 = 15
/(3) = 2 • f (2) + 1 = 2 • 15 + 1 = 31
/(4) = 2-/(3) + l =2-31 + 1 =63
Nepřipomínají nám tato čísla něco? Co třeba výrazy 8 — 1, 16 — 1, 32 — 1, 64 — 1... ? Bystrým studentům se již asi podařilo uhodnout (a ostatním napovídáme), že jde o mocniny dvou snížené o 1. Přesněji, f(n) = 2n+2 — 1 (proč je exponent n + 2 ? inu proto, aby správně vyšlo /(O)).
Ve druhé fázi nesmíme ale zapomenout správnost našeho „věštění" dokázat, nejlépe matematickou indukcí podle n.
. Báze pro n := 0 říká /(O) = 20+2 -1 = 4-1 = 3 = /(O), což platí.
35
• Indukční krok využije indukční předpoklad platnosti vztahu f (n) = 2n+2 — 1 pro n := i (tj. f (i) = 2l+2 — 1), kde i je libovolné přirozené číslo, a pokračuje úpravou ze zadaného rekurentního vzorce
f (i + 1) = 2 • f [i) + 1 = 2- (2Í+2 - 1) + 1 = 2 • 2Í+2 - 2 + 1 = 2(m)+2 - 1,
což po dosazení pro n := i + 1 znamená opět požadovaný vztah f (n) = 2n+2 — 1.
Podle principu matematické indukce je nyní dokázáno, že pro zadanou rekurentní posloupnost / platí f (n) = 2n+2 — 1 pro všechna přirozená n. □
Příklad 5.3. Posloupnost (sn)neN je zadaná rekurentní defínicí
s0 = 0    a    sn = sn_i + n2
pro všechna n > 1. Dokažte, že sn =        + l)(2n + 1) pro všechna přirozená n. Řešení: Opět postupujeme matematickou indukcí podle n. . Báze n : = 0: s0 = \ • 0 • (0 + 1)(2 • 0 + 1) = 0, což platí.
• Indukční krok: za využití Sj_i = |(i — 1)(« — 1 + 1)(2« — 2 + 1) = — \)i{2i — 1), což je indukční předpoklad pro n := i — 1 a libovolné i > 1, upravujeme daný rekurentní vzorec jako
st =       + i2 = ^(i - l)i(2i - 1) + i2 = U (2i2 - 3i + 1) + i2
= \i (2i2 - 3i + 1 + 6i) = \i(i + \)(2i + 1), o o
což dokazuje požadovaný vztah sn = l)(2n+1) také pro n := i a podle principu
matematické indukce jsme hotovi. □
Poznámka: Výsledek Příkladu 5.3 je ukázkou tzv. sumačního vzorce pro řadu
l2 + 22 H-----h n2 = -n(n + l)(2n + 1).
6
Jinou podobnou ukázkou je už dříve zmíněný základní vztah 1 + 2 + • • • + n = ^n(n + 1). A podobně můžeme odvodit například
1 + 3 H-----h (2n - 3) + (2n - 1) = 1 + (2n - 1) + 3 + (2n - 3) H----= 2n • | = n2,
nebo už bez zdůvodnění l3 + 23 + • • • + n3 = (1 + 2 + • • • + n)2 = ^n2(n + l)2. Jakmile vztah tohoto typu „uhodneme", není těžké jej vždy dokázat indukcí. Jak ale dojdeme k tomu uhodnutí takového vztahu? Pomoci si můžeme jednoduchým trikem - součet prvních řekněme n polynomiálních členů lze vyjádřit nějakým polynomem v n stupně o jedna vyššího. Napišme si tedy třeba l2 + 22 + • • • + n2 = Ar? + Bn2 + Cn + D a postupným dosazením n = 0,1, 2, 3 získejme soustavu čtyř lineárních rovnic o čtyřech neznámých, které nám pomohou určit správné hodnoty A, B,C, D. Vyzkoušejte si sami.
Závěrem zopakujeme, že odvozování a práce s jednoduchými sumačními vzorci by měla náležet do výbavy každého schopného informatika. Princip matematické indukce je pro tuto práci klíčový.
36
5.2   Rekurze s více parametry a indukce
Kromě přímočarých ukázek rekurze na funkcích s jediným celočíselným parametrem (tj. na posloupnostech) se lze setkat, především v návrhu algoritmů, s rekurzí za přítomnosti více parametrů.
I pro takové obecnější případy je základním matematickým přístupem použít indukci, avšak nejprve je nutno vhodně zvolit či vytvořit jeden celočíselný parametr, podle nějž indukci můžeme vést. Zopakujme si základní požadavky, které parametr matematické indukce musí splňovat; musí být zdola ohraničený (třeba nezáporný) a pro každou rekurentně odkazovanou hodnotu musí být nižší než pro aktuálně určovanou hodnotu.
Možné přístupy k věci si uvedeme na několika typických ukázkách.
Přístup fixace parametru
První možností uplatnění matematické indukce nad několika parametry jsou případy, kdy sice rekurentně definovaná funkce má více (celočíselných) parametrů, ale při samotném rekurentním odkazu dochází ke změně jen jednoho z nich.
Příklad 5.4. Mějme funkci m : N x N —y N defínovanou rekurentně takto:
• m(0, 6) = 0 pro všechna b G N a
• m(a + 1,6) = m(a, b) + b pro všechna a, b G N. Co bude hodnotou m(a, b) pro obecné a, b G N ľ
Bližším pohledem na zadanou definici zjistíme, že hloubka zanoření rekurze pro vyčíslení m (a, b) je přesně a. Jelikož každé zanoření k výsledku přičte hodnotu b, odhadneme:
Věta. Pro každá a, b G N platí m(a, b) = a ■ b (součin daných parametrů).
Jaký je vhodný postup k důkazu tohoto tvrzení indukcí? Je snadno vidět, že rekurentní vyhodnocení na hodnotě parametru b nijak podstatně nezáleží (6 lze fíxovat) a důležité je sledovat měnící se hodnotu a. Tato úvaha nás dovede k následujícímu přístupu:
Důkaz: Budiž b G N libovolné ale pro další úvahy pevné. Dokazujeme tady, že pro každou hodnotu a := i G N platí m(i, b) = i ■ b. Podle principu matematické indukce uplatněné na parametr i dostáváme snadno:
* V bázi i = 0 je explicitně zadáno m(0, b) = 0 = 0 • b pro jakékoliv b G N.
* Indukční krok.
Nechť je tvrzení známo pro a = i G N a uvažme hodnotu parametru a := i + 1. Podle zadání pak platí m(i + 1,6) = m(i,b) + b. Podle indukčního předpokladu již víme, že m (i, b) = i ■ b. Zbývá jen uvedené poznatky správně zřetězit, abychom odvodili, že výslednou hodnotou m(a, b) skutečně bude
m(a, b) = m (i + 1,6) = m(i, b)+b = i- b + b= (i + 1) ■ b = a ■ b. Důkaz matematickou indukcí je tímto zdárně ukončen. □
37
Indukce k součtu parametrů
Druhou techniku je vhodné použít v případech, kdy se v rekurzi některý parametr zmenšuje, ale v různých místech je to jiný parametr, takže v indukci se nelze zaměřit jen na jeden z nich.
Příklad 5.5. Mějme funkci fc:NxN->N defínovanou rekurentně takto:
• k(c, 0) = k(0, c) = 1 pro všechna c G N a
• k (m, n) = k (m, n — 1) + k (m — 1, n) pro všechna m, n G N, m,n > 0. Co bude hodnotou k (m, n) pro obecné m, n G N ľ
My si zde správnou odpověď nejen ukážeme, ale i přesně dokážeme:
Věta. Pro každé m, n G N je hodnota k (m, n) rovna počtu všech m-prvkových podmnožin (m + n)-prvkové množiny, tedy jinými slovy roven známému kombinačnímu číslu k(m,n) = (™>^n)-
Poznámka: Všimněte si navíc, že náš důkaz vůbec nevyužije faktu, že dokazovaný počet podmnožin je vyjádřitelný uvedeným kombinačním číslem, naopak tento vztah počtu podmnožin ke kombinačnímu číslu (mí^n) a k Pascalovu trojúhelníku vyplyne jako „boční produkt" našeho elementárního důkazu.
Důkaz indukcí vzhledem k součtu parametrů i = m + n:
* Báze i = m + n = 0 pro m, n G N znamená, že m = n = 0. Zde však s výhodou využijeme tzv. „rozšíření báze" na všechny hraniční případy m = 0 nebo n = 0 naši rekurze. V obou rozšířených případech je přímo zadáno k (m, 0) = k(0,n) = 1. Je toto platná odpověď? To ověříme snadno.
Kolik je prázdných podmnožin (m = 0) jakékoliv množiny? Jedna, prázdná 0. Kolik je m-prvkových podmnožin m-prvkové (n = 0) množiny? Zase jedna, ta množina samotná. Tím je důkaz rozšířené báze indukce dokončen.
* Indukční krok přechází na součet i + 1 = m + n. Navíc díky předchozímu rozšíření báze se rovnou můžeme omezit na případy m,n > 0. Platí tedy podle zadání k(m,n) = k(m, n — 1) + k (m — l,n). Přitom oba rekurentní odkazy, k(m, n — 1) i k(m — 1, n) se vztahují na případy se součtem obou parametrů rovným m — l + n = m + n— 1 = i.
Podle indukčního předpokladu tudíž platí, že k(m,n — 1) je počtem m-prvkových podmnožin i-prvkové množiny a k(m — 1, n) je počtem (m — l)-prvkových podmnožin i-prvkové množiny, třeba množiny M = {1,2,...
Berouce do úvahy, že i + 1 = m+n, kolik nyní existuje m-prvkových podmnožin (i + 1)-prvkové množiny M' = MU{i + l}? Pokud ze všech těchto podmnožin odebereme prvek i+1, dostaneme právě m-prvkové podmnožiny (z těch neobsahujících prvek i+1) plus (m— l)-prvkové podmnožiny (z těch původně obsahujících i + 1). A to je v součtu rovno právě k(m — l,n) + k(m,n — 1) = k(m,n), jak jsme měli v indukčním kroku dokázat. □
Přístup se zesílením dokazovaného tvrzení
Poslední ukázka indukčního důkazu se zabývá situací, která je jistým způsobem opačná k první ukázce fixace parametru. V nynější situaci je nám přímo zadáním jeden z parametrů
38
zafixován na určitou hodnotu (b = 1), avšak sledování průběhu výpočtu vyžaduje tuto fixovanou hodnotu zpět „uvolnit" a uvažovat ji proměnnou. V kontextu Oddílu 4.4 pak vlastně dochází k zesílení požadovaného tvrzení y matematické indukci.
Příklad 5.6. Zjistěte, jakou hodnotu v závislosti na celočíselném parametru a nabývá funkce t(a, 1), která je rekurentně definována takto:
• í(0, b) = 0 pro všechna b G N a
• t(a, b) = t(a — 1, 2b) + b pro všechna a, b G N, a > 0.
Zkusíme-li si ručně vypočítat několik prvních požadovaných hodnot t(a, 1) pro a = 0,1, 2, 3,4 ..., postupně získáme výsledky rovné 0,1, 3, 7,15 ... (všimněte si také, jak se v rekurzivním rozvoji postupně sčítají mocniny dvou). Na základě toho již není obtížné uhodnout, že návratová hodnota patrně bude obecně určena vztahem 2a — 1. Toto tvrzení je však třeba také dokázat.
Komentář: Jak záhy zjistíme, matematická indukce na naše tvrzení přímo „nezabírá", ale mnohem lépe se nám povede s následujícím přirozeným zesílením dokazovaného tvrzení, které zobecňuje výsledek na proměnné hodnoty parametru b v návaznosti na zadaný rekurentní vztah. Jak k takovému zesílení dojdeme? Třeba neformálním „vytknutím" faktoru b z celého rekurentního předpisu.
Věta. Pro každé a, b G N platí t(a, b) = (2a - 1) • b. Důkaz: Postupujeme indukcí podle a := i G N.
* V bázi pro a = i = 0 je určena hodnota t(a, b) = 0 = (2° — 1) • b bez ohledu na vstup b.
* Indukční krok. Nechť je tvrzení známo pro a = i G N a uvažujme další hodnotu a := i + 1 > 0. V tom případě je rekurentní podmínkou dáno t(a, b) = t(a — 1, 2b) + b, přičemž hodnota t(a — 1,2b) = t(i,2b) vyplývá z dosazeného a = i + 1 a indukčního předpokladu. Celkově tedy
t(a, b) = t(i, 2b) + b = (T - 1) • 2b + b = 2i+1b - 2b + b = (2i+1 - 1) • b.
Poslední výraz je roven požadovanému (2a — 1) • b a důkaz matematickou indukcí je tímto ukončen. □
5.3   Induktivní definice množin
Rekurentně lze určit nejen hodnoty členů posloupnosti nebo funkce, ale mnohem siřeji lze určit i prvky nečíselných množiny a následně definovat obecnou funkci na nich. Koncept induktivních definic množin není zcela lehký, ale uvidíte, že v informatice je velmi přirozený a důležtý.
Definice 5.7. Induktivní definice množiny.
Jedná se obecně o popis (nějaké) množiny M v následujícím tvaru:
• Je dáno několik pevných (bazických) prvků a\, a2,..., dk G M.
• Je dán soubor induktivních pravidel typu
Jsou-li (libovolné prvky) x1}...,    G M, pak také y G M. V tomto případě je y typicky funkcí y = fi(xi,..., xe) (v pravidle číslo i).
39
Pak naše induktivně definovaná množina M je určena jako nejmenší (inkluzí) množina vyhovující všem těmto pravidlům.
Poznámka: O minimálních a nejmenších objektech v uspořádání se budeme učit až v Lekci 8. Pro účely Definice 5.7 znamená obrat „inkluzí nejmenší" množina M prostě fakt, že v M se nacházejí jen ty vynucené prvky a žádný jiný (tedy žádný, který by nebyl přímo určen některým bázickým nebo induktivním pravidlem).
Komentář: Několik jednoduchých ukázek... • Pro nejbližší příklad induktivní definice se obrátíme na množinu všech přirozených čísel, která je formálně zavedena následovně.
- 0 G N
• Pro každé y G N můžeme definovat jinou množinu My C N induktivně takto:
- y G My
- Jestliže x G My a x + 1 je liché, pak x + 2 G My. Pak například M3 = {3}, nebo M4 = {4 + 2i | i G N}.
• Dalším příkladem induktivní definice je už známé zavedení výrokových formulí z Oddílu 1.4. Uměli byste teď přesněji říci, co tam byly bázické prvky a jaká byla induktivní pravidla? A jaká byla v definici formulí role závorek? K výrokovým formulím se blíže vyjádříme ještě v příští lekce.
K Definici 5.7 a jednoduchým ukázkám přidáme poněkud složitější příklad ilustrující několik aspektů induktivně definovaných množin najednou.
Příklad 5.8. V Růžovém království mají zvláštní peníze - používají mince pouze dvou hodnot, tříkoruny a tňnáctikoruny.
a) Určete induktivní dennici množiny P všech celých kladných čísel, které lze jak peněžní částku složit z mincí v Růžovém království. (Uvažujte, že království má k dispozici neomezené množství mincí.)
b) Dokažte, že z mincí v Růžovém království lze složit jakoukoliv celou částku od 24 korun výše.
c) Chytrý Honza přijel do Růžového království a potřebuje si tam koupit jeden knoůík za korunu. Jak to může udělat a neprodělat?
a) Například takto: Bázickými prvky jsou 3 G P a 13 G P. K tomu přináleží dvě induktivní pravidla; je-li a G P, pak a + 3 G P a také a + 13 G P.
b) V řešení úkolu postačí dokázat toto tvrzení matematickou indukcí:
Věta. Platí-li pro nějaké n > 24, že 24, 25,..., n, n + l,n + 2 G P, pak také n + 3 E P.
Důkaz: V bázi indukce snadno vidíme, že částky 24 = 3 • 8, 25 = 13 + 3 • 4 a 26 = 13-2 náleží do P, a proto tvrzení platí pro n = 24.
V indukčním kroku z předpokladu n E P přímo odvodíme n + 3 G P (přidáme jednu tříkorunu) a jsme hotovi.
c) Honza zaplatí 1 třináctikorunu a nechá si vrátit 4 tříkoruny (12). □
Je-li i G N, pak také succ{i) G N (kde následník succ{i) odpovídá hodnotě i + 1).
40
Komentář: Zamyslete se sami, proč vlastně v Příkladu 5.8b) v dokazovaném tvrzení předpokládáme 24, 25,... ,n,n + l,n + 2 £ P? Pro platnost indukčního kroku přece stačí předpokládat n £ P, jak to ostatně děláme v uvedeném důkazu.
Na závěr přidáváme zájemcům jeden dobrovolný příklad k samostatnému procvičení.
Příklad 5.9. Jak byste dokázali jasně a srozumitelně (explicitně) popsat množinu D zadanou následující induktivní defínici?
• Bázickými prvky jsou 21 E D a 35 E D.
• Máme dvě induktivní pravidla:
* Jsou-li a, b E D (je možné a = b), pak také a + b E D.
* Jsou-li a, b E D a platí a > b, pak také a — b E D.
Pokud už máte odpověď, pak přemýšlejte, co se stane, když bázickými prvky bude jiná dvojice přirozených čísel. A co když v bázi zadáme trojici nebo čtveřici čísel? □
Rozšiřující studium
Rekurentními vztahy pro posloupnosti a funkce se zabývá do hloubky spíše čistá matematika než informatika, avšak pro informatiku jsou nesmírně důležité „strukturované" induktivní deňnice uvedené na konci této lekce a s pokračováním v příští lekci.
41
6   Strukturální indukce
Úvod
Nyní se naplno ponoříme do hlubin induktivních defínic a na ně navázané techniky strkturální matematické indukce. Na induktivní deňnice množin navážeme induktivními deňnicemi funkcí z nich a látku doprovodíme konkrétními ukázkami defínic i indukčních důkazů na nich. Výklad povedeme s ohledem na potřeby a podstatu informatiky, speciálně s uhledem na potřebu formálních popisů a specifikací (syntaxe, sémantiky, dat).
Cíle
Náplní našeho výkladu je vysvětlit nelehkou oblast induktivních (tj. na sebe se odvolávajících) defínic množin a funkcí, se kterými se hojně pracuje v prakticky všech oblastech informatiky. V návaznosti na předchozí látku čtenáře postupně uvedeme do nového formalismu strukturální matematické indukce.
6.1   Jednoznačnost induktivních definic
Před pokračováním našeho výkladu s induktivními definicemi funkcí potřebujeme ještě jednu technickou definici vztahující se k induktivně definovaným množinám.
Definice: Řekneme, že daná induktivní definice množiny M je jednoznačná, právě když každý prvek M lze odvodit z bázických prvků pomocí induktivních pravidel právě jedním způsobem.
Komentář: Induktivní definice množiny přirozených čísel N je jasně jednoznačná. Podobně je jednoznačná následující definice množiny M C N;
- 2,11 G M
- Jestliže x G M, pak také x + 2 G M.
Avšak jednoznačná už není tato induktivní definice množiny PCN;
- 2,11 G P
- Jestliže x G P, pak také x + 3 G P.
Proč? To proto, že například prvek 11 G P lze získat jednou jako bázický prvek definice a podruhé z bázického prvku 2 G P trojí iterací pravidla Ĺx + 3 G P' (a je mnoho jiných prvků majících více odvození v P).
V čem tedy spočívá důležitost jednoznačných induktivních definic množin? Je to především v dalším možném využití induktivní definice množiny jako „základny" pro odvozené vyšší definice, viz následující Definice 6.2 a třeba doplňková Věta 6.9. Stručně a neformálně řečeno, hlavní role jednoznačnosti induktivní definice je v možnosti pak přiřadit prvkům této induktivní množiny nějaký „jednoznačný význam".
Příklad 6.1. Jednoznačnost induktivní defínice 01-řetězců.
Nad binární abecedou E = {0,1} induktivně definujeme speciální množinu řetězců B C E* následujícím předpisem:
. '0', 'Olľ G B (bázické prvky).
• Jestliže x E B a řetězec x končí znakem 0, pak také x + 'Oľ G B, kde x + 'Oľ označuje řetězec vzniklý z x přidáním dvojice znaků 01 na konec.
• Jestliže x E B a řetězec x končí znakem 1, pak také x + '00' G B.
42
Dokážte, že uvedená definice množiny B je jednoznačná.
Jelikož pojednáváme o induktivně definované množině B, je přirozené pro důkaz aplikovat matematickou indukci. Avšak na rozdíl od dříve probíraných příkladů zde nevidíme žádný celočíselný „parametr nlí, a proto musíme nejprve za něj definovat vhodnou náhradu, neformálně řečenou jako „indukci podle délky odvození prvku x E BĹÍ, kterážto délka je definována jako počet aplikací induktivních pravidel potřebných k odvození x G B. Přesně řečeno, naši indukci povedeme podle struktury odvození prvků naší induktivní množiny a budeme tudíž mluvit o strukturální indukci.
Důkaz: Nejprve musíme ověřit jednoznačnost definice množiny B pro její bázické prvky, tj. je třeba zkontrolovat, že žádný z bázických prvků případně nelze odvodit i některým(i) z pravidel. Pro řetězec '0' G B je to jasné z jeho minimální délky, ale řetězec 'Olľ G B by případně mohl být odvozený z předchozího z hlediska své délky. Avšak žádné pravidlo nedává řetězec končící znaky 11. Báze indukci je tak hotova.
V indukčním kroku předpokládáme, že tvrzení platí pro všechny dříve odvozené prvky množiny B (formálně řečeno pro všechny bázické prvky a všechny prvky odvozené z nich použitím nejvýše l > 0 pravidel) a nahlédneme na prvek y E B dále odvozený jedním z daných pravidel (formálně tedy y E B odvozený použitím l + 1 pravidel).
Nechť y končí znakem 0; pak y E B určitě musel být odvozen použitím „x + '00' G BĹÍ jako posledního pravidla (druhé ze zadaných pravidel totiž tvoří řetězce končící znakem 1). Je tedy jednoznačně y = x + '00' a zároveň podle indukčního předpokladu byl řetězec x E -B odvozen jednoznačně. Tudíž y E -B je odvozen jednoznačně. Obdobně postupujeme, pokud y končí znakem 1; pak y E B určitě musel být odvozen použitím „x + '01' G BĹÍ jako posledního pravidla. Je tedy jednoznačně y = x + '01' a zase podle indukčního předpokladu byl řetězec x E B odvozen jednoznačně. Tudíž y E B je odvozen jednoznačně i v tomto případě.
Probrali jsme všechny možnosti vytvoření dalšího prvku množiny B a důkaz indukčního kroku je tak hotov. □
6.2   Induktivní definice funkcí
Induktivně definovaná množina povětšinou nemá valný význam sama o sobě, avšak poskytuje defíniční obor pro následnou induktivně definovanou funkci.
Komentář: Pro ilustraci z informatického světa si vezměte, že induktivní definice množiny mnohdy definuje prostě jen syntaxi, tedy správný způsob zápisu nějaké instrukce či programu, ale k tomu je nutno také podat definici sémantiky, tedy významu toho správně zapsaného - co se má vlasně provést nebo vykonat. K tomu právě slouží „nadstavbová" induktivní definice funkce nad induktivní množinou.
Definice 6.2. Induktivní definice funkce z induktivní množiny.
Nechť množina M je dána jednoznačnou induktivní definicí. Pak říkáme, že funkce ÍF :
M —> X je definována induktivně (vzhledem k induktivní definici M), pokud je řečeno:
• Pro každý z bázických prvků 01,02,... ,Ok G M je určeno ÍF(ai) = q, kde q je konstanta.
• Pro každé induktivní pravidlo typu
"Jsou-li (libovolné prvky) x\,...,xi E M, pak také f(x\,..., x i) E M" je definováno
f(xi,..., Xi)) na základě hodnot ÍF(xi),..., ÍF{xe).
43
Komentář: Ilustrujme si induktivní definici funkce dětskou hrou na „tichou poštu". Definičním oborem je řada sedících hráčů, kde ten první je bázickým prvkem a každý následující (mimo posledního) odvozuje hráče sedícího hned za ním (nebo vedle) jako další prvek hry. Hodnotou bázického prvku je první (vymyšlené) posílané slovo. Induktivní pravidlo pak následujícímu hráči přiřazuje slovo, které je odvozeno („zkomolením") ze slova předchozího hráče. Výsledkem hry pak je hodnota-slovo posledního hráče.
Pro další příklad se podívejme třeba do manuálových stránek unixového příkazu test EXPRESSION:
EXPRESSION is true or false and sets exit status.    It is one of:
( EXPRESSION ) EXPRESSION is true
! EXPRESSION EXPRESSION is false
EXPRESSI0N1 -a EXPRESSI0N2 both EXPRESSI0N1 and EXPRESSI0N2 are true
EXPRESSI0N1 -o EXPRESSI0N2 either EXPRESSI0N1 or EXPRESSI0N2 is true
[-n] STRING the length of STRING is nonzero
STRING1 = STRING2 the strings are equal
Vidíte, jak tato ukázka krásně koresponduje s Definicí 6.2 ? No, ne úplně, poněkud problematická je otázka jednoznačnosti této definice - jednoznačnost není vynucena (jen umožněna) syntaktickými pravidly, jinak je pak dána nepsanými konvencemi implementace příkazu. To je pochopitelně z matematického hlediska špatně, ale přesto jde o pěknou ukázku z praktického života informatika.
6.3   Použití strukturální indukce
Strukturální indukce je matematickou indukcí jako každá předchozí indukce, viz Definice 4.5. Hned je však vidět na první pohled zásadní rozdíl, nemáme zde žádný „parametr n", podle kterého bychom indukci přirozeně vedli. Místo explicitního parametru problému indukci pak vedeme podle délky odvození (počtu použitých induktivních pravidel) prvku induktivní množiny (té množiny, která je podstatou zkoumaného problému) Například bázické prvky jsou, jejichž délka odvození je 0.
Definice: Mějme induktivně definovanou množinu M a na jejích prvcích formulované tvrzení T(m), kde m G M. Tvrzení T (m) dokazujeme strukturální indukcí podle množiny M takto:
• Dokážeme platnost T(mo) pro každý bázický prvek mo G M.
• Pro každý nebázický prvek m G M vybereme induktivní pravidlo odvozující m G M z prvků mi,... ,rrik G M a předpokládáme platnost tvrzení T(rrii) pro všechna i = 1,..., k. Z těchto předpokladů pak dokážeme platnost tvrzení T(m).
Poznámka: Někdy může nastat (ale ne v jednoznačných definicích), že prvek m E M vyplývá z více induktivních pravidel určujících množinu M. Nemusíte dokazovat indukční krok pro každé pravidlo vedoucí k m G M, nýbrž vám stačí si vybrat jedno nejvhodnější.
Nyní si zopakujeme induktivní definici množiny a funkce z ní na primitivním příkladu, na který poté nasadíme strukturální indukci.
Příklad 6.3. Induktivní defínice na přirozených číslech následníkem.
Vzpomeňte si z Oddílu 5.3, že přirozená čísla lze definovat induktivně bázickým prvkem 0 G n a pravidlem následníka jíGN^ succ(n) G n. Pišme zkráceně s(n) místo succ(n). Na množině N definujme funkci f(n) takto
44
* /(o) = o,
* pokud n G N, tak f (s (n)) = s (s (f (n))). Dokážte, že f (n) = 2n pro každé n G N.
Důkaz: V bázi skutečně platí /(O) =0 = 2-0.
Pro jakékoliv n G N pak můžeme (viz induktivní pravidlo) předpokládat, že f(n) = 2n platí. Z tohoto předpokladu pak přímočaře odvozujeme hodnotu f(s(n)) takto/(s(n)) = s(s(f(n))) = s(s(2n)) = s(2n + 1) = 2n + 2 = 2(n + 1). A jelikož přirozeně f(s(n)) = f(n + 1), tvrzení f(n + 1) = 2(n + 1) platí a jsme s důkazem hotovi. □
Druhý ukázkový příklad induktivní definice funkce a důkazu strukturální indukcí je podobně přímočarý a až promitivní, ale už se v něm setkáme s jistou „strukturou" důkazu, spočívající ve zpracování více induktivních pravidel s více parametry.
Příklad 6.4. Jednoduché aritmetické výrazy a jejich význam.
Nechť je dána abeceda E = {0,1, 2, 3,4, 5, 6, 7, 8, 9, 0, ©, (,)}. Definujme množinu jednoduchých výrazů SExp C S* induktivně takto:
* Dekadický zápis každého přirozeného čísla n je prvkem SExp (bázické prvky).
* Jestliže x, y G SExp, pak také (x) 0 (y) a (x) © (y) jsou prvky SExp.
* Jak snadno nahlédneme, díky nucenému závorkování je tato induktivní definice jednoduchých výrazů SExp jednoznačná.
Tímto jsme jednoduchým aritmetickým výrazům přiřadili jejich „formu", tedy syntaxí.
Pro přiřazení „významu", tj. sémantiky aritmetického výrazu, následně definujme funkci vyhodnocení Val: SExp —> N induktivně takto:
* Pro bázické prvky: Val(n) = n, kde n je dekadický zápis přirozeného čísla n.
* První induktivní pravidlo: Val((x) © (y)) = Val(x) + Val(y).
* Druhé induktivní pravidlo: Val((x) ©(?/))= Val(x) ■ Val(y).
Co je pak „správným významem" (hodnotou) uvedených jednoduchých aritmetických výrazů? (Příklad 6.5) □
Příklad 6.5. Důkaz správnosti přiřazeného „významu" Val: SExp —> N.
Věta. Pro každý výraz a G SExp je hodnota Val(a) z Příkladu 6.4 číselně rovna výsledku vyhodnocení výrazu a podle běžných zvyklostí aritmetiky.
Důkaz: V bázi indukce ověříme vyhodnocení bázických prvků, kteréžto jsou zde dekadické zápisy přirozených čísel. Platí Val(n) = n, což skutečně odpovídá zvyklostem aritmetiky.
V indukčním kroku se podíváme na vyhodnocení Val((x) © (y)) = Val(x) + Val(y). Podle běžných zvyklostí aritmetiky by hodnota Val((x) © (y)) měla být rovna součtu vyhodnocení výrazu x, což je podle indukčního předpokladu rovno Val(x) (x má zřejmě kratší délku odvození), a vyhodnocení výrazu y, což je podle indukčního předpokladu rovno Val(y). Takže skutečně Val((x) © (y)) = Val(x) + Val(y).
Druhé pravidlo Val((x) 0 (y)) se zpracuje analogicky. Podle běžných zvyklostí aritmetiky by hodnota Val((x)Q(y)) měla být rovna součinu vyhodnocení výrazu x, což je podle indukčního předpokladu rovno Val(x), a vyhodnocení výrazu y, což je podle indukčního předpokladu rovno Val(y). Opět tedy správně platí Val((x) 0 (y)) = Val(x) ■ Val(y). □
45
6.4   Nazpět k matematické logice
Vybaveni aparátem induktivních definic, můžeme nyní podat matematicky přesnější definici formulí výrokové logiky z Oddílu 1.4 a jejich sémantiky.
Definice: Nechť V = {A,B,C,... } je (nekonečná spočetná) množina výrokových proměnných. Množina J7 výrokových formulí je dána těmito pravidly induktivní definice:
* Bázickými prvky J7 jsou výrokové proměnné V, tj. X E J7 pro každé X E V.
* (negace) Je-li ip G J7, pak také ~<((p) je prvkem J7.
* (implikace) Je-li íp,ip E J~, pak také (ip) =>- (ip) je prvkem J7.
Zároveň platí, že závorky okolo ip lze vynechat pouze pokud ip> E V nebo 99 bylo vytvořeno induktivním pravidlem negace. To stejné platí pro vynechávání závorek okolo ip.
Poznámka: Již nad rámec předchozí definice patří dříve uvedené syntaktické zkratky
* p V ip    (disjunkce/„nebo") je jiný zápis formule —np=^ip,
* p A ip    (konjunkce/„a") je jiný zápis formule    _,(_,V3 V _,V'))
* p 4^ V    (ekvivalence) je jiný zápis formule    (tp =ŕ ip) A (ip =ř tp).
Na základě jednoznačné induktivní definice množiny J7 výrokových formulí nyní můžeme podat přesnou induktivní definici funkce vyhodnocení (logické hodnoty formulí), kterou jsme doposud znali z Definice 1.8.
Nechť valuace (ohodnocení) je funkce v : V —> {0,1}.
Definice 6.6. Sémantika (význam) výrokové logiky. Pro každou valuaci v definujeme funkci
Převod formulí do normálního tvaru
V dalším se vrátíme k logickým formulím v normálním tvaru (viz Oddíl 2.2), tedy k formulím, ve kterých se operátor negace vztahuje pouze k výrokovým proměnným. Význam normálního tvaru pro lidské chápání významu formulí jsme si již zdůvodnili a nyní si formálně dokážeme, že vždy můžeme normálního tvaru dosáhnout.
Tvrzení 6.7. Každou výrokovou formuli lze převést do normálního tvaru, pokud k =^ povolíme i užívání odvozených spojek A a V.
Důkaz Tvrzení 6.7 pak přímo vyplývá z jednoduchého mechanického postupu převodu formulí do normálního tvaru popsaného v následující Metodě 6.8.
Sv : T -> {0,1}
zvanou vyhodnocení formule a vzhledek k v, induktivně takto: * SV(X) := v(X) pro každé X E V.
0   jestliže Sv(ip) = 1 a Sv(ip) = 0;
46
Metoda 6.8. Převod formule p do normálního tvaru F{p).
Pro převod použijeme funktory F a G s neformálním významem J7(X) jako „je pravda, že X" a Q (X) jako „není pravda, že X". Tyto funktory definujeme induktivními předpisy následovne:
F{A) =  A g{A) =  -n A
F{^p)     = G{^p)     = Hv)
F(p^^)  = F(p)^FW       G(p^^) = ^)A5W
f(pa^) = j^ajw G(ifA^) = g(v)vgw F(pv^) = j^vjw G(pv^) = e^AffW f(p^^) = f(p)^f(^)     g(p^^) = f(p)^gw
Pro predikátové formule toto rozšíříme ještě o pravidla:
Fi^x.p)   =  Vx.F(p) G^x.p)   = 3x.G(p)
F(3x.p)   =  3x. J7 (</?) G(3x.p)   = \/x.Q(ip)
Komentář: Uvažme formuli —<(A =4> ~^{B V -|(C => —iA))). Užitím uvedeného postupu Metody 6.8 získáme:
J7{-'{A => ->{B V -i(C => ->A))))   =   G (A    -i(B V -i(C => -*A))) = F {A) A G{->{B V -i(C => -^A)))    = AAJ(BVn(C^nA)) A A (J7(B) V Jr(-i(C => -iA)))      =   AA{BVG{C ^^A)) AA(5V(J(C)AgH))) =   A A {B V (C A F{A)))
A A {B V {C A A))
Formuli A A (B V (C A A)) lze dále zjednodušit na ekvivalentní formuli A A (B V C). To ale je již z našeho pohledu matematicky neformální (heuristicky) postup.
Důkaz pro normální tvar formule
Na závěr následuje další ilustrativní ukázka důkazu strukturální indukcí.
Věta 6.9. Pro libovolnou výrokovou formuli p platí (viz Metoda 6.8), že
a) F{p) je formule v normálním tvaru ekvivalentní k p
b) a G{p) je formule v normálním tvaru ekvivalentní negaci ->p.
Důkaz povedeme indukcí ke struktuře formule, neboli indukci povedeme podle „délky" l - počtu aplikací induktivních pravidel při sestavování formule p.
• Báze indukce [l = 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě platí, že F (A) = A je ekvivalentní A a G {A) = ->A je ekvivalentní —i A.
• V indukčním kroku předpokládejme, že a) i b) platí pro všechny formule p délky nejvýše l. Vezmeme si formuli ip délky £+1, která je utvořená jedním z následujících způsobů:
* ip = -op. Podle výše uvedeného induktivního předpisu je F(ip) = F(—np) = G{p)- Podle indukčního předpokladu pak je G{p) formule v normálním tvaru ekvivalentní ->p = ip. Obdobně pro funktor G vyjádříme G (ý) = G(~"f) = F (p). Podle indukčního předpokladu pak je F{p) formule v normálním tvaru ekvivalentní p a to je dále ekvivalentní -1-199 = -iifj podle Tvrzení 1.10.
47
* ip = (<pi =>- p2). Podle výše uvedeného induktivního předpisuje ťF{ip) = ÍF(pi =>• p2) = Fifi) =^ Jr(p>2)- Podle indukčního předpokladu jsou ťF{pi) i Jr{p2) formule v normálním tvaru ekvivalentní p\ a p2. Potom i ťF{pi) =>• Jr{p2) je v normálním tvaru dle definice a podle sémantiky =>- je ta ekvivalentní formuli
(<Pi    p2) = 4>-
Obdobně rozepíšeme G(4>) = G(pi =>• p2) = ^(pi) A G (^2)- Jelikož A je pro nás jen zkratka, výraz dále rozepíšeme G (ý) = ~^{F{pi) =>• -<G(p2))- Podle indukčního předpokladu (a dvojí negace) jsou ťF{pi) a ~<G(p2) P° řadě ekvivalentní formulím p\ a p2. Tudíž nakonec odvodíme, že G (ý) je ekvivalentní negaci formule pi =>- p2, což jsme zde měli dokázat.
* ip = (pi\/p2). Zde si musíme opět uvědomit, že spojka V je pro nás jen zkratka, a přepsat ip = (-<pi =>• p2). Potom podle předchozích dokázaných případů víme, že Fijp) = .T7(-i</?i =>• p2) = Fíp^pi) =>• J-'ip^ je ekvivalentní formuli (-><pi =>• p2) = ip, což bylo třeba dokázat. Stejně tak G (ý) = G(~"fi =>• f 2) = -^(""Pi) A ^(^2) je podle předchozích případů důkazu ekvivalentní (—upi A —1(^2) = ~^ip-
* ip = (pi A (^2) & ip = {pi ^ P2) už dokončíme analogicky.
Rozšiřující studium
Poslední částí látky o důkazech a množinách byla problematika induktivních definic, které ač ve formálním podání mohou nejprve vypadat těžko pochopitelné, jsou ve skutečnosti zcela přirozenou popisnou metodou v mnoha aplikačních sférách informatiky a jejich alespoň intuitivní ovládání pro vás bude v dalším studiu informatiky nezbytné. Schválně, zkuste se podívat do kterékoliv vaší oblíbené oblasti informatiky, kde všude induktivní dennice (tj. ty odvolávající se rekurzivně samy na sebe pro „menšípřípady"), najdete. Ať už přímo či nepřímo. V Lekci uvedený příklad příkazu 'test EXPRESS ION' je jen vybraným zrníčkem písku v hromadě dalších použití.
48
7   Relace a jejich vlastnosti
Úvod
Jak jsme si říkali v Lekci 3, relace a funkce patří mezi základní „datové typy" matematiky Zároveň na pojem (zcela obecné) relace velmi brzy narazí každý informatik při studiu dat a databází, které na něm staví. Není to však jen oblast relačních databází, ale i jiná místa informatiky, kde se abstraktní relace skrývají či přímo explicitně objevují. Nejčastěji se tak setkáte s binárními relacemi nad množinami, na něž se v textu hlouběji zaměříme.
Cíle
Rozšíříme látku závěru Lekce 3 o prezentace relací, zvláště v případě binárních relací. Ve vztahu k binárním relacím je zavedeno množství pojmů, které jsou používány v různých oblastech matematiky i informatiky. Ty zahrnují základní vlastnosti relací a jejich uzávěry. V látce pak plynule pokračujeme Lekcí 8.
7.1   Reprezentace konečných relací
Oblastí, kde informatici nejčastěji potkají obecné relace, je bezesporu ukládání dat. To proto, že shromažďovaná data, stejně jako relace, především sledují vztahy mezi objekty. Na druhou stranu je relační databáze zcela obecnou ukázkou reprezentace jakékoliv relace, kterou si ilustrujeme příkladem.
Příklad 7.1. Tabulka relační databáze prezentuje obecnou relaci. Definujme následující množiny („elementární typy")
* ZNAK = {a, ■ ■ ■ ,z,A,--- , Z, mezera},
* ČÍSLICE = {0,1, 2, 3,4, 5, 6, 7, 8, 9}.
Dále definujeme tyto množiny („odvozené typy")
* JMÉNO = ZNAK15,     PŘÍJMENÍ = ZNAK20,     VEK = ČÍSLICE3,
* ZAMESTNANEC  „G" JMÉNO x PŘÍJMENÍ x VEK. Relaci „typu" ZAMESTNANEC pak lze reprezentovat tabulkou:
JMÉNO	PŘÍJMENÍ	VEK
Jan	Novák	42
Petr	Vichr	28
Pavel	Zima	26
Stanislav	Novotný	52
□
Reprezentace binárních relací na množině
Jistě čtenáři uznají, že zadání relace výčtem jejích složek není pro člověka (na rozdíl od počítače) tím nej příjemnějším způsobem. Je tedy přirozené se ptát, jak co nejnázorněji takovou relaci, alespoň v její nejčastější binární podobě, ukázat.
Značení: Binární relaci i? C M x M lze jednoznačně znázornit jejím grafem:
• Prvky M znázorníme jako body v rovině (tj. na papíře).
• Prvek (a,b) G R znázorníme jako orientovanou hranu („šipku") z a do b. Je-li a = b, pak je touto hranou „smyčka" na a.
49
Komentář: Například mějme M = {a,b,c,d,e, /} a R = {(a,a), (a,b), (b,c), (b,d), (b, e), (b, /), (d, c), (e, c), (/, c), (e, <f), (e, /), (/, b)}, pak:
c
Pozor, nejedná se o „grafy funkcí" známé třeba z matematické analýzy.
V případě, že M je nekonečná nebo „velká", může být reprezentace R jejím grafem nepraktická (záleží také na míře „pravidelnosti" R).
Značení: Binární relaci R C M x M \ze jednoznačně zapsat také pomocí matice relace - matice A typu M x M s hodnotami z {0,1}, kde dij = 1 právě když (i, j) G R.
1 0  0  0 0\
0 1111
0 0   0   0 0
0 10   0 0
0 110 1
1 1   0   0 0/
7.2   Vlastnosti binárních relací
Pro začátek dalšího matematického výkladu relací si výčtem a doprovodnými schematickými obrázky uvedeme pět základních vlastností binárních relací na stejné množině, které nás typicky v matematické teorii zajímají. Je třeba si uvědomit, že se budeme zabývat velmi speciálním případem, neboť uvedené vlastnosti dávají dobrý smysl pouze pro uspořádané dvojice na téže množině, ale na druhou stranu se jedná o užitečný speciální případ.
Definice 7.2.   Nechť R C M x M. Binární relace R je
• reflexivní, právě když pro každé a G M platí (a, a) G R;
•Ô <í>
• ireflexivní, právě když pro každé a E M platí (a, a) ^ R;
• symetrická, právě když pro každé a, b G M platí, že jestliže (a, b)  G R, pak také (b, a) G R;
a
50
» antísymetrícká, právě když pro každé a, b G M platí, že jestliže (a, b), (6, a) G i?, pak a = b; V"
» tranzitívni, právě když pro každé a,b,c £ M platí, že jestliže (a, 6), (b,c) G i?, pak také (a, c) E R. n ^
Komentář: Pozor, může být relace symetrická i antisymetrická zároveň?
<í>   <í> <í>
Ano!
Vezměte si relaci i? = {(x,x) \ x £ M}, která obě jmenované vlastnosti splňuje. Neboli není pravda, že relace je antisymetrická, právě když není symetrická. Proto pokud jste třeba dotázáni, zda relace je symetrická, nestačí se v odpovědi odvolávat na fakt, že je antisymetrická (či naopak), neboť tyto vlastnosti se nevylučují.
Ukázkové binární relace
Příklad 7.3. Jak poznat vlastnosti relací z matice:
(\ 1   0 0\
0 111
0 0 10
\0 0   1 1/
(\ 1 1 0 0 1
\0 1
0 0\
1 1
0 1
1 0/
Které z vlastností z Defínice 7.2 mají binární relace reprezentované těmito maticemi?
Řešení: Ony vlastnosti si probereme (trochu neformálně) jednu po druhé.
* Podle definice je relace reflexivní, právě když každý prvek na hlavní diagonále je 1. Tudíž vlevo relace reflexivní je a vpravo není.
* Obdobně je relace ireflexivní, právě když je její hlavní diagonála vyplněna nulami. Tudíž ani jedna z našich relací ireflexivní není.
* Podle definice je relace symetrická, právě když je matice „stejná" v zrcadlovém obraze podle hlavní diagonálýTudíž vlevo symetrickou relaci nemáme a vpravo máme.
* Obdobně je relace antisymetrická, právě když po „přeložení" matice podle hlavní diagonály nebudou nikde mimo tuto diagonálu dvě jedničky „na sobě". Tudíž vlevo relace antisymetrická je a vpravo není.
* Zbývá posoudit tranzitivitu, což není úplně jednoduché... Pokusíme se velmi neformálně popsat názorný postup vycházející z definice tranzitivity.
Relace je tranzitivní, právě když vždy vyjde následující test. Najdeme v libovolném řádku 1, od ní ve svislém směru (nahoru nebo dolů) dojdeme na hlavní diagonálu (její prvek nás nezajímá) a z toho místa nakonec ve vodorovném směru dojdeme na jinou 1. Poté na průsečíku počátečního řádku a koncového sloupce musí také být 1.
51
□
Příklad 7.4. Několik příkladů relací defínovaných v přirozeném jazyce. Nechť M je množina všech studentů 1. ročníku FI. Uvažme postupně relace R C M x M definované takto
*	(x,	y)	e	R	právě	když	x a, y mají stejné rodné číslo;
*	(x,	y)	e	R	právě	když	x má stejnou výšku jako y (dejme tomu na celé mm
*	(x,	y)	e	R	právě	když	výška iaj/se neliší více jak o 2 mm;
*	(x,	y)	e	R	právě	když	x má alespoň takovou výšku jako y;
*	(x,	y)	e	R	právě	když	x má jinou výšku než y (dejme tomu na celé mm);
*	(x,	y)	e	R	právě	když	x je zamilován(a) do y.
Zamyslete se, které z definovaných vlastností tyto jednotlivé relace mají... □
Komentář: Co dělat v situaci, že naše relace některou z poptávaných vlastností nemá, ale nám by se ta vlastnost hodila? V některých případech lze chybějící vlastnost relaci „doplnit" pomocí takzvaného uzávěru, čemuž se budeme věnovat v dalším oddíle.
• Například reflexivní uzávěr jednoduše přidá do relace všechny dvojice (x, x) nad nosnou množinou relace.
• Nebo symetrický uzávěr zahrne do relace všechny obrácené dvojice k existujícím dvojicím, čili všechny chybějící (x, y) pokud (y, x) £ R.
7.3   Uzávěry relací
V předchozím jsme se krátce zmínili o postupu, jak danou relaci můžeme „obohatit" o zvolenou vlastnost. (To se v praxi může hodit například tehdy, když naše data o relaci jsou neúplná a potřebná vlastnost je tak poškozena.) Takové obohacení se pochopitelně může týkat pouze některých vlastností - těch, které lze jednoznačně zajistit prostým přidáním dvojic do existující relace. Podchytit uzavíratelné vlastnosti má za úkol následující definice.
Definice: Nechť V je libovolná vlastnost binárních relací. Řekneme, že V je uzavíratelné, pokud splňuje následující podmínky:
* Pro každou množinu M a každou relaci R C M x M existuje alespoň jedna relace S* C M x M, která má vlastnost V a pro kterou platí R C S.
* Nechť J je množina a nechť Ri C M x M je relace mající vlastnost V pro každé i E I. Pak relace f]ieI Rí má vlastnost V.
Fakt: Libovolná kombinace vlastností reňexivita, symetrie, tranzitivita je uzavíratelná vlastnost. To plyne přímo z toho, že úplná relace M x M na naší množině M má všechny uvedené vlastnosti zároveň. Ireŕfexivita a antisymetrie naopak nejsou uzavíratelné vlastnosti.
Věta 7.5. Nechť V je uzavíratelná vlastnost binárních relací. Buď M množina a R libovolná binární relace na M. Pak pro množinu všech relací S D R na M majících vlastnost
V existuje infímum Rv (vzhledem k množinové inkluzi), které samo má vlastnost V. Platí
Rv= f] S.
SDR, S má V na M
52
Definice: Tuto minimální relaci R   s vlastností V nazýváme V-uzávěrrelace R.
Srovnáme-li Větu 7.5 s Definicí 5.7, pohledem sběhlého matematika uvidíme, že V-uzávěr Rv relace je vlastně daný induktivní definicí, ve které bázickými prvky jsou dvojice původní relace R a induktivní pravidla odpovídají vlastnosti V. Tento konstruktivní pohled je podchycen případ od případu v následujícím tvrzení.
Tvrzení 7.6. Nechť R je binární relace na M. Pak platí následující poznatky.
* Reflexivní uzávěr R je přesně relace R U {(x, x) | x G M}.
* Symetrický uzávěr R je přesně relace R= {(x, y) | (x, y) G R nebo (y, x) G R}.
* Tranzitivní uzávěr R je přesně relace R+ = \^}°11T"I'(R), kde T je zobrazení, které pro každou binární relaci S vrátí relaci
ľ (S) := S U {(x, z) | existuje y takové, že (x, y), (y, z) G S}
a T%(S) = T(T■ . . (T(S)) ...) je i-krát iterovaná aplikace zobrazení T.
i
* Reflexivní a tranzitivní uzávěr R je přesně relace R* = Q+, kde Q je reflexivní uzávěr R.
* Reflexivní, symetrický a tranzitivní uzávěr R (tj. nejmenší ekvivalence obsahující R) je přesně relace (Q)+, kde Q je reflexivní uzávěr f?.
Poznámka: Na pořadí aplikování uzávěrů vlastností záleží! Zhruba řečeno, tranzitivní uzávěr obvykle aplikujeme coby poslední.
Závěrem se ještě pozastavíme nad případem tranzitivního uzávěru R+ = Tl(R), jehož definice se nezdá až tak „konstruktivní" - jak bychom počítali nekonečné sjednocení? To skutečně nepotřebujeme, neboť platí následující:
Tvrzení 7.7. Nechi R je relace na konečné množině. Pak existuje přirozené m takové, že tranzitivní uzávěr relace R lze zapsat R+ = IJíI!i Tl(R).
Důkaz: Pro něj si uvědomme zásadní fakt - pokud Tl+1(R) = Tl(R), tak už platí Tl+k(R) = Tl(R) pro všechna přirozená k. Neboli je potřeba sjednotit jen tolik prvních členů výrazu \^}°11T"I'(R), dokud se hodnota Tl(R) „zvětšuje", což může nastat jen konečně krát nad konečnou množinou. □
7.4   Tranzitivní relace
Mezi základními vlastnostmi relací popsanými Definicí 7.2 je jedna - tmnzitivita, jejíž uchopení a zvládnutí je výrazně těžší než u ostatních vlastností. Proč? Definice reflexivity, symetrie či antisymetrie nám ihned řeknou, které dvojice v relaci chybí nebo přebývají. Avšak vlastnost tranzitivity je fundamentálně induktivní - všimněte si předchozího tranzitivního uzávěru, kde po každém přidání dvojice do relace je nutno znovu podmínku tranzitivity kontrolovat, což „indukuje" nové dvojice k přidávání.
K hlubšímu pochopení tranzitivity pomůže (snad) následující poznatek.
53
Tvrzení 7.8. Mějme relací R na konečné množině M a nechť R+ je tranzitivním uzávěrem R. Pak pro každé x,y E M platí (x, y) G R+ právě tehdy, když existují zq, z\, ..., Zk G M takové, že zq = x, Zk = y a (zí-\,Zj) G R pro i = 1,..., k.
Komentář: Tvrzení 7.8 o tranzitivním uzávěru R+ je potřeba (neformálně) číst takto: Do tranzitivního uzávěru patří všechny ty dvojice (x,y), že v původní relaci R se lze „dostat po šipkách" z x do y. Pro velmi jednoduchou ilustraci:
•-5>—•-ž=—•-ž=—•
V rozšířeném příkladě buď i? C N x N definovaná takto: R = {(i,i + 1) | i G N}. Pak tranzitivní uzávěr R+ je běžné ostré lineární uspořádání < přirozených čísel.
Důkaz: Nezapomeňte, že tvrzení vyslovené jako ekvivalence se musí dokazovat ve dvou směrech implikace. Nejprve předpokládejme, že existují zq, z\, ..., Zk G M takové, že zq = x, Zk = y a (zi-i, Zi) G R pro i = 1,..., k. Indukcí podle i > 1 snadno dokážeme, že (z0,Zi) G R: zde platí (zq,z,i_i) G R z indukčního předpokladu a (z^,^) E R z předpokladu našeho tvrzení. Potom (z0,Zi) G R plyne z definice tranzitivity.
Naopak předpokládejme (x,y) G R+. Tento směr důkazu není lehký a pomůžeme si tímto trikem: Nechť D C M je množina těch prvků M, do kterých se lze „dostat po šipkách" z x (induktivní definice množiny). Potom x E D a, pokud také y E D, jsme s důkazem hotovi. Pro spor tedy předpokládáme, že y E1 D.
Z toho, jak jsme množinu D zavedli, plyne, že pro každé zEDatEM\D platí (z, t) E1 R (neformálně, z D nevede ven žádná šipka). Podle definice tranzitivního uzávěru pak ale nevede z D ven žádná šipka ani v uzávěru R+ a jelikož y E M \ D, dostáváme (x, y) E1 R+, což je spor. Důkaz opačného směru je hotov. □
S tranzitivními relacemi (mezi objekty) se nejčastěji setkáváme, pokud tyto objekty porovnáváme vztahy „je stejný jako" nebo „je větší/lepší než". Takové porovnání přímo vede k následujícím pojmům.
Definice 7.9.   Daná binární relace R je
* relace ekvivalence, právě když je i? reflexivní, symetrická a tranzitivní;
* částečné uspořádání, právě když je R reflexivní, antisymetrická a tranzitivní (často říkáme jen uspořádání).
Příklad 7.10. Jaké vlastnosti mají následující relace?
• Buď f? C N x N definovaná takto (x, y) E R právě když x dělí y. (Částečné uspořádání, ale ne každá dvě čísla jsou porovnatelná.)
• Buď i?CNxN definovaná takto (x, y) E R právě když x a, y mají stejný zbytek po dělení číslem 5. (Ekvivalence.)
• Nechť F = {f \ f : ¥S —^N}je množina funkcí. Buď R C F x F definovaná takto (f, g) E R právě když f (x) < g (x) pro všechna x. (Ireňexivní, antisymetrická a tranzitivní, ale ne reflexivní - striktně řečeno není uspořádáním.)
54
□
Příklad 7.11. Jak vypadá graf relace ekvivalence?
Poměrně příznačně, jak nám ukazuje následující obrázek (všimněte si absence šipek, která je dána symetrií relace).
8
8
Neformálně řečeno; ekvivalence je relace R C M x M, taková, že (x, y) G R právě když x a, y jsou v nějakém smyslu „stejné" (leží na stejné hromádce). Tyto hromádky pak nazýváme komponentami či třídami ekvivalence dané relace. Více se o vztahu ekvivalence k jejím třídám dozvíme v příští lekci. □
Zvídavým čtenářům ještě přidáme jeden obtížnější příklad, který se už trochu vztahuje k příští látce...
Příklad 7.12. Studenti předmětu IB000 sedí v lavicích v obdélníkové posluchárně (však to dobře znáte). Ne všechny sedačky jsou nutně obsazené. Defínujeme relaci R tak, že dvojice studentů (a, b) náleží do R, právě když b sedí ve stejné řadě vlevo od a nebo b sedí ve stejném sloupci před a.
a) Dokažte, že tranzitivní uzávěr R je antisymetrická relace.
b) Kolik nejméně a nejvíce tříd ekvivalence může defínovat reůexivní, symetrický a tranzitivní uzávěr relace R ?
Část (a) dokážeme sporem; nechť tedy platí (a, b), (b, a) G R+ kde a ^ b. Proč by toto nemělo nastat? Pro důkaz si pomůžeme jednoduchým trikem: pro studenta x definujeme hodnotu s(x) := i + j, kde i je řada a j sloupec, ve kterých x sedí, číslováno zleva a zepředu. Pak podle popisu relace R zřejmě platí s(x) > s(y) pokud (x,y) G R. Podle definice tranzitivního uzávěru pak s (a) > s(b) jakmile (a, b) G R+ a a ^ b, avšak také s (a) < s(b) jelikož (b,a) G R+. To je zřejmě spor.
Nyní přejdeme k části (b). Označme S reflexivní, symetrický a tranzitivní uzávěr relace R. Nejméně tříd, jednu, získáme při plném obsazení posluchárny, ať už má jakékoliv rozměry. Vezměme kterékoliv dva různé studenty a, b. Podle definice reflexivního a symetrického uzávěru existuje student c sedící ve stejné řadě jako a a ve stejném sloupci jako b (může to být i jeden z a,b), přičemž platí (a, c), (c, b) G S. Podle definice tranzitivního uzávěru pak (a, b) G S, a proto a, b leží ve stejné jedné třídě podle Věty 8.7.
Naopak nejvíce tříd získáme, pokud žádní dva studenti nesedí ve stejné řadě nebo stejném sloupci (třeba sedí jen na jedné úhlopříčce). Počet tříd pak je přesně l, kde l je rovno minimu z počtu řad a sloupců posluchárny. Předpokládejme pro spor, že by mohlo při nějakém obsazení posluchárny existovat více než l tříd ekvivalence uzávěru S. Zvolme z každé třídy jednoho studenta jako reprezentanta. Podle Dirichletova principu někteří dva a, b z vybraných studentů sedí ve stejné řadě či sloupci (neboť studentů je více, než minimum z počtu řad a sloupců). Podle definice naší relace R a symetrického uzávěru pak platí (a, b) G S. Avšak a, b pochází z různých tříd ekvivalence a to je ve sporu s Větou 8.7. □
55
Navazující studium
Mějte na paměti, že na pojmech množin, relací a funkcí jsou vystavěny prakticky všechny skutečné datové struktury používané v dnešní informatice. Explicitně toto můžete vidět na relačních databázích, ale i na mnoha jiných implicitních výskytech. Mnohem více si nejprve o relacích a jejich skládání a poté speciálně o funkcích vysvětlíme v dalších dvou lekcích. Dalším důležitým matematickým datovým typem odvozeným z binárních relací jsou pak grafy probírané od Lekce 10, na nichž v různé míře staví většina základních algoritmů, které se budete učit.
56
8   Ekvivalence, Uspořádané množiny
Úvod
V této lekci pokračujeme rozebíráním relací na množinách jako nástrojů vyjadřujících vztahy mezi objekty. Zaměříme se přitom pouze na relace binární, které nějakým způsobem srovnávají objekty podle jejich vlastností (obvykle ve smyslu „ stejný jako" nebo „ lepší/větší než"). Takto vágně opsané binární relace mívají jasné společné znaky, které se pak objevují ve zde uvedených formálních dennících relace ekvivalence a uspořádání.
Co se týče ekvivalencí, lze šije neformálně představit jako rozdělení prvků nosné množiny na „hromádky", přičemž prvky každé jednotlivé hromádky jsou si navzájem v jistém smyslu stejné. Naopak uspořádání nám již podle svého názvu udává srovnání prvků nosné množiny, neboli které prvky si „stojí lépe" než jiné.
Cíle
Defínujeme relace ekvivalence a uspořádání a mnohé další pojmy k nim se vztahující, například rozklady a Hasseovské diagramy. Studující by měli porozumět matematické problematice rozkladů množin a uspořádaných množin a naučit se je správně používat.
8.1   Relace ekvivalence a rozklady
Nyní se hlouběji podívejme na první specifický typ binární relace zmíněný v Lekci 7: Podle Definice 7.2 je relace R C M x M ekvivalence právě když f? je reflexivní, symetrická a tranzitivní. Tyto tři vlastnosti tedy musí být splněny a ověřeny k důkazu toho, že daná relace i? je ekvivalencí.
Značení. V případě relace ekvivalence se poměrně často lze setkat s označením jako ~ či    místo R. Místo (x, y) E R se pak píše x »2 y.
Příklad 8.1. Nechť M je množina všech studentů 1. ročníku FI. Uvažme postupně relace R C M x M defínované následovně a zkoumejme, zda se jedná o ekvivalence:
* (x, y) E R právě když x má stejnou výšku jako y;
* (x, y) E R právě když x má stejnou barvu vlasů jako y;
* (x, y) E R právě když x, y mají stejnou výšku a stejnou barvu vlasů;
* (x, y) E R právě když x, y mají stejnou výšku nebo stejnou barvu vlasů.
U kterého body se nejedná o relaci ekvivalence a proč? Je to poslední případ, kdy není splněna tranzitivita. □
Uvedený příklad ukazuje na následující univerzální poznatek, který může platit (a taky platí) pouze pro průnik a nikoliv pro sjednocení.
Tvrzení 8.2. Nechť R, S jsou dvě relace ekvivalence na stejné množině M. Pak jejích průnik R D S je opět relací ekvivalence.
Důkaz (náznak): Jelikož reflexivita a symetrie jsou zřejmé, stačí snadno ověřit platnost tranzitivity na R H S. Nechť (a, b), (b,c) E R f) S, pak podle tranzitivity každé jedné z R, S plyne (a, c) G R a zároveň (a, c) E S. □
Příklad 8.3. Nechť i? C N x N je binární relace definovaná takto: (x,y) E R právě když \x — y\ je dělitelné třemi. V jakém smyslu jsou zde x a y „stejné"?
57
Platí (x, y) e R právě když x, y dávají stejný zbytek po dělení třemi. Je to opět relace ekvivalence. □
Příklad 8.4. Buď R binární relace mezi všemi studenty na přednášce FP.IB000 defínovaná takto: (x, y) G R právě když x i y sedí v první lavici.
Už na první pohled jde o relaci symetrickou a tranzitivní. Proč se v tomto případě nejedná o relaci ekvivalence? Protože není reflexivní pro studenty sedící v dalších lavicích. (Takže si dávejte dobrý pozor na správné pochopení definic.) □
Rozklady a jejich vztah k ekvivalencím
Náplní následující části výkladu je ukázat jiný přirozený pohled na ekvivalence. Tento nový pohled nám matematicky formalizuje již nastíněnou představu ekvivalence jako rozdělení prvků nosné množiny M na „hromádky", přičemž prvky každé jednotlivé hromádky jsou si navzájem v jistém smyslu „stejné".
Definice 8.5. Rozklad množiny. Nechť M je množina.
Rozklad (na) M je množina podmnožin M C 2M splňující následující tři podmínky:
- 0 0 A/" (tj. každý prvek M je neprázdná podmnožina M);
- pokud A,B eN, pak buď A = B nebo A H B = 0;
Prvkům M se také říká třídy rozkladu. Komentář:
* Buď M = {a, b, c, d}. Pak N = {{a}, {b, c}, {d}} je rozklad na M.
* Nechť A0 = {k G N | k mod 3 = 0}, Ax = {k G N | k mod 3 = 1}, A2 = {k G N j k mod 3 = 2}. Pak J\í = {Aq,A±, A2} je rozklad všech přirozených čísel N podle zbytkových tříd.
Každý rozklad M na M jednoznačně určuje jistou ekvivalenci Rx na M:
Věta 8.6. Nechi M je množina a M rozklad na M. Nechi Rx C M x M je relace na M definovaná takto
(x, y) G Rjy právě když existuje A e M taková, že x, y e A.
Pak Rjy je ekvivalence na M.
Důkaz: Dokážeme, že R^ je reůexivní, symetrická a tranzitivní (Dennice 7.2).
• Reflexivita: Buď x e M libovolné. Jelikož M je rozklad na M, musí existovat A e M takové, že x e A (jinak spor se třetí podmínkou z Defínice 8.5). Proto (x,x) e Rj^, tedy Rx je reflexivní.
• Symetrie: Nechť (x,y) e R^. Podle definice R^ pak existuje A e M taková, že x, y e A. To ale znamená, že také (y,x) e R^ podle definice R^, tedy R^ je symetrická.
• Tranzitivita: Nechť (x,y), (y,z) e R^. Podle definice R^ existují A, B e M takové, že x,y e A a y, z e B. Jelikož A H B ^ 0, podle druhé podmínky z Defínice 8.5 platí A = B. Tedy x, z e A = B, proto (x, z) e R^ podle definice R^. n
Každá ekvivalence R na, M naopak jednoznačně určuje jistý rozklad M/R na M:
58
Věta 8.7. Nechť M je množina a R ekvivalence na M. Pro každé x E M definujeme množinu
[x] = {yeM\ (x,y)eR}. Pak {[x] | x G M} je rozklad na M, který značíme M/R a čteme „rozklad M podle R".
Důkaz: Dokážeme, že M/R splňuje podmínky Defínice 8.5.
• Pro každé [x] G M/R platí [x] 7^ 0, neboť x G [x].
• Nechť [x], [y] G M j R. Ukážeme, že pokud [x] H [y] 7^ 0, pak [x] = [y].
Jestliže [x] H [y] 7^ 0, existuje z E M takové, že z E [x] a z E [y]. Podle definice [x] a [y] to znamená, že (x, z), (y, z) G R. Jelikož R je symetrická a (y, z) G R, platí (z, y) G R. Jelikož (x, z), (z, y) G R a R je tranzitivní, platí (x, y) G R. Proto také (y, x) G R (opět ze symetrie R). Nyní dokážeme, že [y] = [x]:
* v[x] !í= [y] ": Nechť v G [x]. Pak (x, v) G i? podle definice [x]. Dále (y, x) G i? (viz výše), tedy (y, v) G R neboť R je tranzitivní. To podle definice [y] znamená, že v G [y].
* ,7[y] ^ M ": Nechť v G [y]. Pak (y, v) G R podle definice [y]. Dále (x, y) G i? (viz výše), tedy (x, v) G i? neboť R je tranzitivní. To podle definice [x] znamená, že v G [x].
• Platí U [x] e m/í? N = M, neboť x G [x] pro každé x G m. '-' 8.2   Uspořádané množiny
Přirozený vágní pojem porovnání/uspořádání objektů má také svou přesnou matematickou definici: Podle Definice 7.2 je relace R C M x M (částečné) uspořádání právě když f? je reflexivní, antisymetrická a tranzitivní. Tyto tři vlastnosti tedy musí být splněny a ověřeny k důkazu toho, že daná relace i? je uspořádáním.
Komentář: Neformálně řečeno: uspořádání je taková relace R C M x M, kde (x,y) G R právě když x je v nějakém smyslu „menší nebo rovno" než y. Mohou ovšem existovat taková x, y G M, kde neplatí (x, y) G i? ani (y, x) G R. (Pak říkáme, že x a y jsou nesrovnatelné.)
Jak názorně zobrazit (částečné) uspořádání? Příklad zjednodušeného zakreslení (jsou vynechány šipky vyplývající z reflexivity a tranzitivity, viz Oddíl 8.3) je zde:
8 12
dělitelnost:
59
Všimněte si, že je někdy zvykem „větší" prvky kreslit nad ty „menší".
Značení. Pro větší přehlednost se relace uspořádání často značí symboly jako C či ^ místo prostého R. I my tak často budeme psát třeba x -< y místo (x, y) E R.
Poznámka: Zajisté jste se již neformálně setkali s „neostrým" uspořádáním čísel < a „ostrým" uspořádáním < . Všimněte si dobře, že námi definované uspořádání je vždy neostré. Pokud byste naopak chtěli definovat ostré uspořádání, mělo by vlastnosti ireňexivní, antisymetrické a tranzitivní. (Příliš se však tato varianta nepoužívá.) Nadále budeme pracovat pouze s neostrým uspořádáním, ale smyčky vyplývající z reflexivity a případně i šipky z tranzitivity budeme pro větší přehlednost v obrázcích vynechávat.
Uspořádaná množina
Matematicky důležitějším pojmem než samotná relace uspořádání je uspořádaná množina, neboli soubor prvků s pevně zvoleným uspořádáním na nich.
Definice 8.8. Uspořádaná množina je dvojice (M, ^), kde M je množina a ^ je (částečné) uspořádání na M.
Definice: Uspořádání ^ na M je lineární (nebo také úplné), pokud každé dva prvky M jsou v -< srovnatelné.
Příklady
Příklad 8.9. Nechť M je množina všech studentů 1. ročníku FI. Uvažme postupně relace R C M x M defínované následovně (jedná se úplně vždy o uspořádání?):
* (x, y) E R právě když x má alespoň takovou výšku jako y;
* (x, y) E R právě když y má alespoň takovou výšku jako x.
Všimněte si dobře možného problému - pokud by dva studenti měli přesně stejnou výšku, nebyla by splněna podmínka antisymetrie. Prakticky však můžeme uvažovat, že toto nenastane (matematicky bychom řekli, že pravděpodobnost výskytu dvou studentů přesně stejné výšky bez omezení přesnosti měření je nula) a bude se jednat o uspořádání. □
Příklad 8.10. Nechť M je množina všech českých studentů 1. ročníku FI. Uvažme relaci R C M x M defínovanou tak, že (x, y) E R právě když x a y mají stejné rodné číslo. Je možné, aby R byla uspořádáním na M?
Ano, za zákonného předpokladu jedinečnosti rodného čísla. Dobře si promyslete proč (které dvojice jsou vůbec porovnatelné?). □
Příklad 8.11. Další ukázky uspořádaných množin následují zde:
* (N, <) je lineárně uspořádaná množina, kde < má „obvyklý" význam.
* (N, | ), kde a\b je relace dělitelnosti „a dělí 6" na přirozených číslech, je uspořádaná množina. Toto uspořádání není lineární.
60
* Buď M množina. Pak (2M, C) je uspořádaná množina (říkáme inkluzí). Které dvojice jsou v uspořádání inkluzí nesrovnatelné?
Komentář: Zamyslete se také, jak vypadá relace dělitelnosti na celých (tj. i záporných) číslech. Proč se už nejedná o uspořádání? Blíže viz konec Oddílu 8.3.
Multikriteriální uspořádání
Přirozenou ukázkou praktického problému, ve kterém potkáme problematiku netriviálně uspořádaných objektů, je výběr toho nejlepšího podle více nezávislých kritérií. Co třeba znamená požadavek na „nejlepší počítač"? I pokud se soustředíme jen na užitné / výkonové charakteristiky počítače, můžeme porovnávat nejen podle rychlosti procesoru, ale také třeba podle výkonu grafiky, velikosti paměti a disku, nebo i počtu na-koušlých jablek na víku. A jen málokdy se setkáme s dostupným počítačem, který by jasně dominoval ve všech kritériích najednou.
Takže jak lze objekty podle více kritérií seřadit?
• Pokud jsou všechna kritéria numerická, zkoumané objekty lze řadit podle jejich váženého průměru (či součtu). Avšak numerické hodnoty jsou ne vždy dostupné a především „průměrování" kritérií často dává velmi nepřirozené výsledky.
• Objekty můžeme uspořádat podle průniku seřazení jednotlivých kritérií (říká se po složkách). Výhodou je, že pokud objekt (počítač) P je lepší než Q, tak P v žádném kritériu nemůže zaostávat za Q. Avšak výsledkem bude typicky existence několika „nejlepších" objektů, které nebudeme umět vzájemně porovnat. (Podívejte se na pojem maximálního prvku v Definici 8.14.)
• Nakonec si můžeme pomoci slovníkovým uspořádáním: Kritéria seřadíme od nej důležitějšího a první odlišná hodnota kritéria rozhoduje. Například nás v prvé řadě zajímá rychlost procesoru, poté velikost paměti a až nakonec výkon grafiky či velikost disku... (Máme přece počítač na práci a ne na hraní her či sledování filmů.)
Předchozí vágní popisy uspořádání nyní formalizujeme matematicky. Formálně mějme několik kritérií označených indexovou množinou I (například uvažme čtyři kritéria vypsaná výše s I = {1,2,3,4}). Pro i E I nechť hodnoty nabývané i-tým kritériem tvoří uspořádanou množinu (Aí,<í). Ve výsledku nás pak zajímá „složené" uspořádání na kartézském součinu Xie/A, které definujeme následovně.
Definice 8.12. Uspořádání podle více kritérií.
Pro J C N mějme systém uspořádaných množin (Ai, <«) kde i E I. Na množině M := X iejAi definujeme binární relace C a ^ takto;
pro l,m E M kde £=(£«: i E I) a m = (rrii : i E I) platí * (po složkách)
{a. b, o}
□
£ \Zm    právě když    £i <j rrij pro všechna i E I,
61
* (lexikograficky)
l -< m   právě když     l = m , nebo
existuje j E I tak, že í j <j m j a
pro všechna i E I, i < j platí £j = m^.
Komentář: Lexikografické uspořádání z Definice 8.12 je staré známé uspořádání slov ve slovníku podle abecedy - kde / indexuje jednotlivá písmena slov zleva. Všimněte si, že pro definici lexikografického uspořádání je potřebné, aby také indexová množina / byla lineárně uspořádaná. Porovnejte si jej s detaily naší definice pro lepší porozumnění věci.
Tvrzení 8.13. Nechi C a -< jsou binární relace na množině M z Definice 8.12. Pak se v obou případech jedná o relace uspořádání. Navíc, pokud všechny (Ai} <j) jsou lineárně uspořádané množiny, tak lexikografické uspořádání (M, ^) nad nimi je taktéž lineární.
8.3   Pojmy uspořádaných množin
K tématu uspořádaných množin se vztahuje množství formálních pojmů, které potkáte v různých oblastech matematiky i informatiky.
Definice 8.14.   Nechť (M, ^) je uspořádaná množina.
• x E M je minimální právě když pro každé y E M platí, že z y ^ x vyplývá x <y, čili podle antisymetrie pro každé y -< x platí y = x.
• x G M je maximální právě když pro každé y E M platí, že z x ^ y vyplývá y ^ x, čili podle antisymetrie pro každé y >z x platí y = x. (Tj. x je maximální, právě když neexistuje žádný prvek ostře větší než x, a x je minimální, právě když neexistuje žádný prvek ostře menší než x.)
• x E M je nejmenšíprávě když pro každé y E M platí, že x ^ y.
• x E M je největší právě když pro každé y E M platí, že y ^ x.
• x E M pokrývá y E M právě když x / y, y -< x a neexistuje žádné z E M takové, že x/zÝya,y<z<x.
• x E M je dolní závora (mez) množiny ACM právě když x ^ y pro každé y E A.
x
x
y
X
62
• x G M je horní závora (mez) množiny ACM právě když y ^ x pro každé y G A.
• x G M je infimum množiny ACM právě když x je největší dolní závora (mez) množiny A. ___
• x G M je supremum množiny A C M, právě když x je nej menší horní závora (mez) množiny A.
• A C M je řetězec v uspořádání ^ právě když (A, ^) je lineárně uspořádaná množina.
Komentář: Tuto dlouhou definici se sluší poněkud neformálně okomentovat. Za prvé, s pojmy nejmenšího a největšího prvku jste se už intuitivně setkali mnohokrát, ale (matematicky slabší) pojmy minimálního a maximálního působí někdy problémy. Zapamatujte si proto dobře, že minimálních prvků může mít množina několik, jsou to prostě všechny ty "vespod", ale nejmenší prvek existuje nejvýše jeden a je to pouze ten unikátní minimální prvek množiny. Stejně pro maximální...
Další poznámka se vztahuje k infimu a supremu množiny. Jak jsme napsali (a asi totéž znáte z matematické analýzy), množina nemusí mít nejmenší ani největší prvek, ale v mnoha případech je lze "nahradit" po řadě infimem a supremem, které hrají v jistých ohledech podobnou roli. Avšak ani supremum a infimum nemusí vždy existovat.
Nakonec si dejte pozor, že některé uvedené definice mají „netriviální chování" na nekonečných množinách. Proto je budeme obvykle uvažovat jen nad konečnými množinami.
Příklad 8.15. Proč má každá uspořádaná množina nejvýše jeden největší prvek?
Tvrzení dokážeme sporem: Nechť m i n jsou největší prvky uspořádané množiny (M, ^). Pak podle Definice 8.14 platí n ^ m i m ^ n zároveň. Ovšem jelikož uspořádání musí být antisymetrické, pak platí m = n a největší prvek je jen jeden. □
Hasseovské diagramy
Motivací zavedení tzv. Hasseovských diagramů uspořádaných množin jsou přehlednější „obrázky" než u grafů relací. Například si srovnejte následující ukázky:
Zjednodušení a konvence přinesené následující definicí jsme ostatně měli možnost vidět už na některých z předchozích ilustračních obrázků uspořádání.
63
Definice: Hasseovský diagram konečné uspořádané množiny (M, ^) je její jednoznačné grafické znázornění definované takto:
* Prvky nosné množiny M jsou zakresleny body v rovině („puntíky").
* Mezi každou dvojicí prvků x ^ y vede hrana (tj. „čára", ale bez šipek), právě když prvek x pokrývá prvek y. V takovém případě x musí být zakreslen výše než y. Pojem pokrývání prvku najdete v Definici 8.14.
Komentář: Všimněte si, jak přímo z definic vyplývá, že původní relace uspořádání ^ je reflexivním a tranzitivním uzávěrem relace pokrývání z Hasseovského diagramu. To znamená, že samotné hrany tohoto diagramu spolu s podmínkou, které prvky hran jsou kresleny výše, už poskytují plnou informaci o naší uspořádané množině (M, ^).
Metoda 8.16. Zakreslení Hasseovského diagramu
Pro danou konečnou uspořádanou množinu (M, :^) jej jednoduše získáme takto:
* Do první horizontální vrstvy zakreslíme body odpovídající minimálním prvkům (M,^). (Tj. které nepokrývají nic.)
* Máme-li již zakreslenu vrstvu i, pak do vrstvy i + 1 (která je „nad" vrstvou i) zakreslíme všechny nezakreslené prvky, které pokrývají pouze prvky vrstev < i. Pokud prvek x vrstvy i + 1 pokrývá prvek y vrstvy < i, spojíme x a y neorientovanou hranou (tj. „čárou bez šipky").
Příklad 8.17. Relaci inkluze na čtyřprvkové množině {a,b,c,d} zakreslíme Hasse-ovským diagramem takto:
Komentář: Znovu jinými méně formálními slovy opakujeme, že v Hasseovském diagramu „vynecháváme" ty hrany relace ^, které vyplývají z reůexivity či tranzitivity. To celý obrázek výrazně zpřehlední, a přitom nedochází ke ztrátě informace. Lze vynechat i šipky na hranách, neboť dle definice všechny míří „vzhůru". Také pojem „vrstvy" v Metodě 8.16 je jen velmi neformální, důležité je, že větší (pokrývající) prvky jsou nad menšími (pokrývanými).
8.4   Relace předuspořádání
Mimo uspořádání chápaných striktně antisymetricky se v praxi často setkáme se „po-louspořádáními", ve kterých některé očividně různé prvky stojí na stejné úrovni naší preference. Co třeba dostaneme, když studenty na zkoušce „uspořádáme" podle výsledné známky A-F? Bude to vždy uspořádání ve smyslu Definice 7.2? Samozřejmě ne, obvykle více než jeden student bude mít třeba známku E, což zjevně porušuje antisymetrii. Přesto cítíme, že studenty podle známky tak nějak uspořádané máme. Z toho důvodu je užitečné zavést i následující obecnější pojem:
□
64
Definice: Relace R C M x M je předuspořádání (také kvaziuspořádání, nebo po-louspořádání) právě když f? je reůexivní a tranzitivní.
Komentář: Rozdíl mezi uspořádáním a předuspořádáním je (jen neformálně řečeno!) v tom, že u předuspořádání srovnáváme prvky podle kritéria, které není pro prvek jedinečné. V předuspořádání takto mohou vznikat „balíky" (třídy) se stejnou hodnotou kritéria, což schematicky ilustrujeme na následujícím obrázku.
Důležitým poznatkem je, že předuspořádání se „až tak moc" neliší od dřívějšího uspořádání - přirozeně totiž odvodíme následující:
Věta 8.18. Je-li c předuspořádání na M, můžeme definovat relaci ~ na M předpisem
x ~ y    právě když    x c y a y c x.
Pak ~ je ekvivalence na M, která se nazývá jádro předuspořádání c. Na rozkladu M/ ~ pak lze zavést relaci -< definovanou takto
[x] ^ [y]    právě když x c y.
Pak (Mj ~, -<) je uspořádaná množina indukovaná c.
Komentář: Pro ukázku si vezměme relaci dělitelnosti na TL. Pak třeba —2 ~ 2. Jádrem zde jsou dvojice čísel stejné absolutní hodnoty.
Důkaz (náznak): Tranzitivita a reflexivita relace ~ vyplývá z tranzitivity a reflexivity relace c. Symetrie ~ pak je přímým důsledkem její definice. Tudíž ~ skutečně je relací ekvivalence a M j ~ je platný rozklad nosné množiny.
Tranzitivita a reflexivita relace -< se opět dědí z relace c. Její antisymetrie vyplývá následující úvahou: Pokud [x] ^ [y] a [y] ^ [x], pak podle naší definice x c y a y c x, neboli i ~ i/ a [i] = [y] podle definice tříd rozkladu. Pozor, nej důležitější částí této větve důkazu je však ještě zdůvodnění, že naše podaná definice vztahu [x] ^ [y] je korektní, což znamená, že její platnost nezávisí na konkrétní volbě reprezentantů x z [x] a y z [y].
Poslední zmíněné tvrzení dokážeme sporem: Nechť x, x' G [x] a y, y' E [y] jsou (možná různí) reprezentanti dvou zkoumaných tříd rozkladu Mj ~, pro které však platí x c y a x1 □ í/. Podle definice třídy rozkladu je x ~ y a rr' ~ ?/' a z tranzitivity i c i/ c i/' c x' c x a tudíž [x] = [y] a na volbě reprezentanta skutečně nezáleží. □
Rozšiřující studium
S relacemi ekvivalence i jimi implicitně defínovanými rozklady množin se lze setkat všude tam, kde nějaké objekty "rozdělujeme do přihrádek" podle nějakých sdílených znaků nebo kritérií. Principy takových rozkladů vám zajisté byly intuitivně známy ještě dříve, než jste vůbec slyšeli o matematickém pojmu ekvivalence, v této lekci jsme si je jen zavedli
65
na pevných formálních základech. Toto formální pojetí relací ekvivalence a rozkladů budete porůznu potkávat i v dalších informatických předmětech, například u teorie automatů apod.
Druhá část lekce pojednává o látce, kterou opět určitě na intuitivní úrovni znáte (však schopnost si věci „uspořádat" je jednou ze základních lidských dovedností). Přesto správné matematické uchopení podstaty uspořádaných množin vyžaduje se prokousat několika nesnadnými formálními defínicemi, které byly v této lekci vysvětleny a okomentovány. Všimněte si, že hlavní těžkosti konceptu uspořádání se vztahují k částečným, tedy nelineárním uspořádáním, kdy běžnému lidskému uvažování není zcela intuitivně jasná práce s nesrovnatelnými dvojicemi. S trochou příslušného matematického formalismu se správné nakládání s konečnými částečnými uspořádáními stane snadnou rutinou.
66
9   Skládání relací a funkcí
Úvod
JVa závěr učiva o relacích se vracíme k základním defínicím abstraktní relace a funkce z Oddílu 3.5. Náplní výkladu bude to, jak relace obracet a jak je mezi sebou skládat, což si mimo obecných relací vysvětlíme i na speciálním případu funkcí (konrétně na tzv. permutacích). Mimochodem, kde jste se již přirozeně se skládáním funkcí setkali - jak například spočítáte na kalkulačce výsledek složitějšího vzorce? Obecné skládání relací je základním nástrojem práce v relačních databázích. A ke skládání funkcí se pak váže několik dalších základních matematických pojmů, jako jsou injektivní, surjektivní a bijektivní funkce.
Cíle
V této lekci defínujeme inverzi a skládání více relací a ukážeme na zásadní význam těchto operací pro relační databáze. Na to navážeme defínicí základních vlastností funkcí a diskusí souvisejících operací inverze a skládání funkcí. V rámci této diskuse si podrobně probereme problematiku cyklů permutací a skládání permutací.
9.1   Inverze a skládání relací
Ve výkladu se nyní vrátíme k obecnému pojetí relací mezi dvěma (třeba různými) množinami. K využitelné práci s relacemi v aplikacích se dostaneme, pokud budeme umět relace správně „převracet" a „skládat". To nám umožní následující definice.
Definice: Nechť R C A x B je binární relace mezi A a B. Inverzní relace k relaci R se značí R~ľ a je definována takto:
R-1 = {(b,a) | (a, b) G R}
R 1 je tedy relace mezi B a A.
Následuje klíčová definice, pro jejíž bližší ilustraci odkazujeme také na Příklad 9.3. Definice 9.1. Složení (kompozice) relací R a S.
Nechť RCAxB&SCBxC jsou binární relace. Složení relací R a S (v tomto pořadí!) je relace S o R G A x C definovaná takto:
S o R = {(a, c) I existuje b E B takové, že (a, b) G R, (b, c) G S}
Složení relací čteme „R složeno s SCÍ nebo (pozor na pořadí!) „S po RCÍ.
67
Komentář: Několik matematických příkladů skládání relací následuje zde.
* Je"h -A = {a,b},   B = {1,2},   C = {X,Y},
- R = {(a, 1), (6,1), (6, 2)},   S = {(1,X)}, pak složením vznikne relace
- SoR = {(a,X),(b,X)}.
* Složením funkcí h(x) = x2 a f(x) = x + 1 na R vznikne funkce
(foh)(x)=f(h(x)) = x2 + l.
* Složením těchže funkcí „naopak" ale vznikne funkce (h o /) (x) = h(f(x)) = (x + l)2.
Poznámka: Nepříjemné je, že v některých oblastech matematiky (například v algebře při skládání zobrazení) se setkáme s právě opačným zápisem skládání, kdy se místo S o R píše R ■ S nebo jen RS. Proto je si vždy dobré slovně ujasnit, které pořadí skládaných relací máme na mysli. My zde zásadně budeme používat pořadí S o R.
Tvrzení 9.2. Nechť R C A x B a S C B x C jsou binární relace. Pak inverzí složené relace S o R je relace (S o R)~ľ = R~ľ o S~ľ.
Důkaz: Zopakujme si, co nám říkají výše uvedené definice:
R-1   =   {(b,a) | (a, b) e R}
S-1 = {{c,b)\(b,c)eS}
(S o R)^1   =   {(c, a) | existuje b e B takové, že (a, b) G R, (b, c) G S} Dosazením z prvních dvou vztahů do třetího vzniká
(S o R)^1 = {(c, a) | existuje b e B takové, že (6, a) G R~ľ, (c, b) G S~ľ} a to již podle Definice 9.1 ihned implikuje požadovaný závěr
(S o R)'1 = R'1 o S'1.
9.2   Praktické použití skládání
Podívejme se nyní, jak se skládání relací přirozeně objevuje v práci s relačními databázemi. (Dá se zjednodušeně říci, že právě v operátoru skládání tabulkových relací tkví hlavní smysl relačních databází...)
Příklad 9.3. Skládání v relační databázi studentů, jejich předmětů a fakult.
Mějme dvě binární relace - jednu R přiřazující studentům MU kódy jejich zapsaných předmětů, druhou S přiřazující kódy předmětů jejich mateřským fakultám. Malý výsek z těchto relací může v tabulkové reprezentaci vypadat třeba následovně.
R :
student (učo)	předmět (kód)
121334	MA010
133935	M4135
133935	IA102
155878	M1050
155878	IB000
S :
předmět (kód)	fakulta MU
MA010	FI
IB000	FI
IA102	FI
M1050	PřF
M4135	PřF
68
Jak z těchto „tabulkových" relací zjistíme, kteří studenti mají zapsané předměty na kterých fakultách (třeba na FI)?
Jedná se jednoduše o složení relací S o R. V našem příkladě tabulkové reprezentace vyjde výsledek:
SoR:
student (učo)	fakulta MU
121334	FI
133935	FI
133935	PřF
155878	FI
155878	PřF
□
Zobecněné skládání relací
V praktických použitích relačních tabulek povětšinou nevystačíme jen s binárními relacemi, takže je přirozené se ptát, jestli lze podobně skládat i více-ární relace. Odpověď je snadná - lze to a ani nepotřebujeme novou definici, vystačíme s tou, kterou už máme výše uvedenou.
Definice: (skládání relací vyšší arity):
Mějme relace T C K\ x K2 x • • • x K\. a, U C L\ x L2 x • • • x Lg, přičemž pro nějaké m < min(k,£) platí L\ = Kk-m+i, L2 = Kk-m+2, ■ ■ ■ ,Lm = Kk- Pak relaci T lze složit s relací U na zvolených m složkách Li,..., Lm („překrytí") s použitím Defínice 9.1 takto:
* Položme A = Ki x ■ ■ ■ x Kk-m, B = L\ x ■ ■ ■ x Lm a C = Lm+i x ■ ■ ■ x Li.
* Příslušné relace pak jsou   R = {(čí, b) G A x B | (a±,... CLk-m, b±,... bm) G T} a S = {(b,č) G B x C | (b1,...bm,cm+1,...ce) G U}.
* Nakonec přirozeně položme U om T ~ S o R, takže vyjde
UomT = {(a, č) | ex. b G B, že (ai,... afc_m, h,... bm) G T a (&i,... bm, cm+1,... ce) G U} . Schematicky pro snadnější orientaci ve složkách našich relací:
T C    Kx x • • • x Kk_mx   Kk-m+1 x ■ ■ ■ x Kk U C                                   Li    x ■ ■ ■ x Lm   xLm+i x ■ ■ ■ x Lc U om T C    Kx x • • • x Kk_m x__x Lm+1 x ■ ■ ■ x Le
'-*-' -B- '-*-'
a b c
Opět je nejjednodušší si koncept skládání vícečetných relací ilustrovat příkladem.
Příklad 9.4. Skládání v relační databázi pasažérů a letů u leteckých společností.
Podívejme se na příklad hypotetické rezervace letů pro cestující, relace T. Jak známo (tzv. codeshare), letecké společnosti si mezi sebou „dělí" místa v letadlech, takže různé lety (podle kódů) jsou ve skutečnosti realizovány stejným letadlem jedné ze společností. To zase ukazuje relace U.
T :
pasažér	datum	let		datum	let	letadlo
Petr	5.11.	OK535		5.11.	OK535	CSA
Pavel	6.11.	OK535	U :	5.11.	AF2378	ČSA
Jan	5.11.	AF2378		5.11.	DL5457	ČSA
Josef	5.11.	DL5457		6.11.	OK535	AirFrance
Alena	6.11.	AF2378		6.11.	AF2378	AirFrance
69
Ptáme-li se nyní, setkají se Petr a Josef na palubě stejného letadla? Případně, čí letadlo to bude? Odpovědi nám dá složení relací U o2 T, jak je popsáno výše.
pasažér	letadlo
Petr Josef Pavel	CSA ČSA AirFrance
Zkuste se zamyslet, lze tyto dvě relace skládat ještě jinak? Co by pak bylo významem?
□
9.3   Vlastnosti funkcí
Funkce je intuitivně chápána jako předpis, který každé hodnotě (či hodnotám v případě více proměnných) levé strany přiřadí jednoznačně hodnotu pravé strany, tzv. funkční hodnotu neboli výsledek. Avšak v nejobecnější podobě pojem funkce nemusí být nijak svázaný s konkrétním předpisem jejího výpočtu; tento obecnější náhled je obzvláště potřebný v informatice, kdy se budete setkávat i s funkcemi, které nejsou algoritmicky vyčíslitelné.
Připomeňme si, že funkce je podle Definice 3.12 speciálním případem relace, mající pro každou hodnotu levé strany jedinou (funkční) hodnotu pravé strany. V tomto oddíle si uvedeme několik vlastností specifických pro funkce.
Definice 9.5. Funkce (případně parciální funkce) / : A —> B je * injektivní (nebo také prostá) právě když pro každé x,y e A, x ^ y platí f(x) ý f{v)'i
* surjektivní (nebo také „na") právě když pro každé y e B existuje x e A takové, že
* bíjektívní (vzáj. jednoznačná) právě když je injektivní a současně surjektivní.
		
		
	3K--	
Komentář: Následují jednoduché ukázky vlastností funkcí.
* Funkce plus : N x N —» N je surjektivní, ale není prostá.
* Funkce g : TL —> N daná předpisem
-2x — 1    jestliže x < 0,
</W = ^ 2
je bijektivní.
g{x) = . .. v '     1  2x jmak
70
* Funkce 0 : 0 —> 0 je bijektivní.
* Funkce 0 : 0 —?► {a, b} je injektivní, ale není surjektivní.
Příklad 9.6. Dokázali byste nalézt jednoduše (tj. „hezky") vypočitatelnou bijektivní funkci N->Nx Nľ
V řešení si problém nejprve zkusíme představit vhodným geometrickým modelem (není to nutné, ale velmi dobré pro pochopení). Množina N x N nechť je představována všemi jednotkovými čtverečky v prvním kvadrantu roviny. Celý tento kvadrant postupně vyplňujeme po krocích většími čtverci z levého dolní rohu, tj. postupně o rozměrech lxl, 2 x 2, 3 x 3, atd. Co nám v každém kroku i přibude (postupujeme od i = 0)? Bude to pásek 2i + l jednotkových čtverečků ve tvaru H. Pokud tyto pásky narovnáme a seřadíme za sebou, dostaneme jednostranně nekonečný pás jednotkových čtverečků, což znamená pro nás množinu N. Kýžená bijekce je na světě!
Nyní zbývá formální stránka věci - zapsat tuto bijekci předpisem, čili vzorcem. K tomu si připomeneme, že N = {0,1, 2, 3,... }. Jak si sami můžete snadno ověřit, předpis výpočtu hodnoty f(n), kde / : N -} N x N je výše geometricky popsaná bijekce, je následující:
* Nalezneme největší k takové, že k2 < n (k := Lv^J)-
* Pro n — k2 < k máme f(n) := (k,n — k2),
kdežto pro n — k2 > k je f (n) := (k2 + 2k — n, k). □
Příklad 9.7. Pro jaké hodnoty parametrů a, b je funkce f (x) = ax3 + 3x2 + bx + 1 z R do R injektivní či surjektivní?
Nejprve rozebereme případ a = 0, kdy platí /(O) = /(—6/3) = 1. Pro 6 ^ 0 je —6/3 ý 0? kdežto pro 6 = 0 zase platí /(l) = /(—1) = 4. Tudíž pro a = 0 funkce / nemůže být nikdy injektivní. Zároveň pro a = 0 nemůže být ani surjektivní, neboť pro každé x platí, že f(x) = 3x2 + bx + 1 > 1 — 62/12.
Nechť tedy a > 0. Potom lim:E^_00 f(x) = — oo a linx^oo f(x) = oo a vzhledem ke spojitosti funkce / musí nabývat všech reálných hodnot a je surjektivní. Totéž platí pro a < 0. Zodpovězení otázky, kdy je / injektivní, již vyžaduje některé základní poznatky matematické analýzy. Ze školní znalosti průběhu polynomické funkce plyne, že ta je prostá právě tehdy, když nemá žádný lokální extrém. V případě kubického polynomu to konkrétně znamená, že první derivace nesmí být nulová ve dvou různých reálných bodech. Vyjádřeno příslušnou kvadratickou rovnicí, f'(x) = 3ax2 + 6x + 6 = 0, dostáváme z jejího determinantu podmínku 36 — 12a6 < 0.
Závěr: Funkce / je surjektivní, právě když a / 0. Funkce / je injektivní, právě když a ý 0 a 36 - 12a6 < 0. □
Inverze funkce
Inverze funkce je dána definicí inverze relace z Oddílu 9.1. Komentář: Příklady inverzí pro běžné funkce:
* Inverzí bijektivní funkce f(x) = x + 1 na TL je funkce f^1(x) = x — 1.
* Inverzí prosté funkce f(x) = ex na R je parciální funkce f^1(x) = lux.
* Funkce g(x) = x mod 3 není prostá na N, a proto její inverzí je „jen" relace g^1 = {(a, b) \ a = b mod 3}. Konkrétně g'1 ={(0,0), (0,3), (0, 6),..., (1,1), (1,4), ...,(2, 2), (2, 5),... }.
71
K pojmu inverze funkce se vztahují následující základní a jednoduché poznatky:
Tvrzení 9.8. Mějme funkcí f : A —>• B. Pak její inverzní relace f^1 je
a) parciální funkce právě když f je prostá,
b) funkce právě když f je bijektivní.
Důkaz vyplývá přímo z definic funkce a inverze relace. Zkuste si sami. □
Tvrzení 9.9. Je-li inverzní relace f^1 funkce f taktéž parciální funkcí, tak platí f^1(f(x)) = x pro všechna x z definičního oboru.
Důkaz vyplývá přímo z definic funkce a inverze relace. □
9.4   Skládání funkcí, permutace
Obdobně jako u inverze, i skládání funkcí je dáno definicí skládání relací z Oddílu 9.1. Jelikož však definice skládání relací je poměrně složitá, je vhodné si uvést alternativní jednoduchou definici skládání pouze pro funkce.
Fakt: Mějme funkce (zobrazení) f: A^tB&g: B^tC. Pak jejich složením coby relací v tomto pořadí vznikne zobrazení (g o /) : A —> C definované
(9° f)(x) ■= g(f(x))-
Komentář:
* Jak například na běžné kalkulačce vypočteme hodnotu funkce sin2 x ? Složíme (v tomto pořadí) „elementární" funkce f(x) = sin x a g(x) = x2.
* Jak bychom na „elementární" funkce rozložili aritmetický výraz 21og(x2 + l)? Ve správném pořadí složíme funkce fi(x) = x2, f2(x) = x + 1, fz{x) = loga; a f&{x) = 2x.
* A jak bychom obdobně vyjádřili složením funkcí aritmetický výraz sin x + cos x? Opět je odpověď přímočará, vezmeme „elementární" funkce g\(x) = sin x a g2(x) = cosx, a pak je „složíme" další funkcí h(x, y) = x + y. Vidíme však, že takto pojaté „skládání" už nezapadá hladce do našeho zjednodušeného formalismu skládání relací.
Pro nedostatek prostoru si skládání funkcí s více parametry nedefinujeme, ale sami vidíte, že obdobné skládání se v programátorské praxi vyskytuje doslova „na každém rohu" a ani se nad tím nepozastavujeme.
Skládání permutací
Po zbytek tohoto oddílu se zaměříme na permutace coby speciální případ (bijektivních) zobrazení, neboť dobře ilustrují problematiku skládání bez zbytečných technických komplikací a zároveň se jedná o užitečnou oblast diskrétní matematiky.
Značení: Nechť permutace 7r množiny {1,2,... ,n} je určena seřazením jejích prvků jako (pi,p2,... ,pn)- Pak 7r je zároveň bijektivním zobrazením {1,...,n} —> {1,...,n} definovaným předpisem       = pi. Abychom postihli obě tyto podoby permutace zároveň,
( 1    2   ... n
budeme také jako pomůcku používat obvyklý rozšířený zápis
j>!  p2   ... p.
Permutace lze skládat jako relace (funkce) podle Definice 9.1 a platí následující:
72
Tvrzení 9.10. Mějme permutace n a a množiny {1,2,... ,n}. Pak jejich složeni a o 7r je opět permutaci množiny {1,2,... ,n}.
Důkaz vyplývá snadno aplikací definice bijektivní funkce. □
Poznámka: Všechny permutace množiny {1, 2,... , n} spolu s operací skládání tvoří grupu, zvanou symetrická grupa Sn. Permutační grupy (podgrupy symetrické grupy) jsou velice důležité v algebře, neboť každá konečná grupa je vlastně isomorfní některé permutační grupě.
Komentář: Příkladem permutace vyskytujícím se v programátorské praxi je třeba zobrazení i i—> (i + 1) mod n ("inkrement"). Často se třeba lze setkat (aniž si to mnohdy uvědomujeme) s permutacemi při indexaci prvků polí.
V kontextu pohledu na funkce a jejich skládání coby relací si zavedeme jiný, názornější, způsob zápisu permutací - pomocí jejich cyklů.
Definice: Nechť 7r je permutace na množině A. Cyklem v 7r rozumíme posloupnost (ai, a2, ■ ■ ■, a*:) různých prvků A takovou, že 7r(<2j) = ai+1 pro i = 1,2,..., k — 1 a 7r(afc) = d\.
Jak název napovídá, v zápise cyklu (a1; a2,..., a^) není důležité, kterým prvkem začneme, ale jen dodržení cyklického pořadí. Cyklus v permutaci může mít i jen jeden prvek (zobrazený na sebe).
Komentář: Nakreslete si (vámi zvolenou) permutaci tv obrázkem, ve kterém vedete šipku vždy od prvku i k prvku tt(í). Pak uvidíte, že cykly dle naší definice jsou právě cykly tvořené šipkami ve vašem obrázku. S tímto grafickým zobrazením pro vás nebude problém pochopit následující látku.
Reprezentace permutací jejich cykly
Věta 9.11. Každou permutaci tt na konečné množině A lze zapsat jako složení cyklů na disjunktních podmnožinách (rozkladu) A.
Důkaz: Vezmeme libovolný prvek aľ G A a iterujeme zobrazení a2 = 7r(<2i), 03 = 7r(a2), atd., až se dostaneme „zpět" k afc+1 = ir(ak) = aľ. Proč tento proces skončí? Protože A je konečná a tudíž ke zopakování některého prvku a^+i musí dojít. Nadto je 7r prostá, a proto nemůže nastat ir(ak) = clj pro j > 1. Takto získáme první cyklus (ai,..., a^).
Induktivně pokračujeme s hledáním dalších cyklů ve zbylé množině A' = A \ {ai,..., afc}, dokud nezůstane prázdná. V tomto indukčním kroku si musíme uvědomit, že 7T omezené na nosnou množinu A' je stále permutací podle definice (neboli žádná prvek z A' se nezobrazí do {a1;..., a^})- 1=1
73
Značení permutace jejími cykly: Nechť se permutace 7r podle Věty 9.11 skládá z cyklů (ai,..., dk), (bi,... ,bi) až třeba (zi,..., zm). Pak zapíšeme
7T = ((ai,..., ak) (61,..., bi)... {zu ..., zm)) .
Komentář: Primitivní pseudonáhodné generátory v počítačích iterují z náhodného počátku permutaci danou vztahem i 1—> (i + p) mod q. Je pochopitelné, že tato permutace nesmí obsahovat krátké cykly, lépe řečeno, měla by se skládat z jediného (dlouhého) cyklu. (Pro úplnost, jedná se o permutaci množiny {0,1,... , q — 1}).
Příklad 9.12. Ukázka skládání permutací daných svými cykly.
Vezměme 7-prvkovou permutaci zadanou seřazením 7r = (3,4,5,6,7,1,2), neboli rozšířeně zapsanou jako (3456712)' ^a se skládá z jediného cyklu (1,3,5,7,2,4,6). Jiná permutace daná seřazením a = (5,3,4,2,6,1,7), neboli Q \ \ \ \ \ J), se rozkládá na tři cykly (1, 5, 6), (2, 3,4) a (7). Nyní určíme složení o o 7r těchto dvou permutací (už přímo v zápisu cykly):
((1,5,6)(2,3,4)(7)) o ((1,3,5,7,2,4,6)) = ((1, 4)(2)(3, 6, 5, 7))
(Nezapomínejme, že první se ve složení aplikuje pravá permutace!)
Postup skládání jsme použili následovný: 1 se zobrazí v permutaci vpravo na 3 a pak vlevo na 4. Následně 4 se zobrazí na 6 a pak na 1. Tím „uzavřeme" první cyklus (1,4). Dále se 2 zobrazí na 4 a pak hned zpět na 2, tj. má samostatný cyklus. Zbylý cyklus (3, 6, 5, 7) určíme analogicky. □
Rozšiřující studium
Mějte na paměti, že na pojmech množin a relací jsou vystavěny prakticky všechny datové struktury používané v dnešní informatice. Explicitně toto můžete vidět na relačních databázích, ale i v mnoha jiných implicitních výskytech. A dalším důležitým matematickým datovým typem odvozeným z binárních relací jsou pak grafy probírané od Lekce 10, na nichž v různé míře staví většina základních algoritmů, které se budete učit.
S formalizací pojmu funkce a jejími vlastnostmi se zatím setkáváte spíše v matematice, avšak například na bijektivní funkce v informatice narazíte hned při zpracování dat při volbě klíče apod. Našim cílem bylo ukázat práci s funkcemi v jejich abstraktní podobě, tj. bez vazby na nějaký konkrétní analytické vzoreček jako v matematice. Takové abstraktní pojetí je bližší tomu, jak relace a funkce využívá informatika.
74
10   Pojem grafu
Úvod
Po relacích se náš výklad upře směrem k další základní struktuře diskrétní matematiky, grafu. Třebaže grafy (pozor, nepleťte si je s grafem funkce) jsou jen jedním z mnoha typů objektů v diskrétní matematice a vlastně pouze speciálním případem binárních relací, vydobyly si svou užitečností a názorností (a to především ve vztahu k informatice) důležité místo na slunci. Dá se tak bez nadsázky říci, že teorie grafů je asi nejvýznamnější součástí soudobé diskrétní matematiky, a proto se jí budeme věnovat po dvě následující lekce.
Neformálně řečeno, graf se skládá z vrcholů, které si představíme jako nakreslené „puntíky", a z hran, které spojují dvojice vrcholů mezi sebou. Své důležité místo si grafy získaly především dobře vyváženou kombinací vlastností - snadno pochopitelným názorným nakreslením a zároveň jednoduchým zpracováním na počítačích. Díky těmto vlastnostem se grafy prosadily jako vhodný matematický model pro popis různých vztahů mezi daty a objekty.
Cíle
Defínujeme, co je graf a jaké jsou nejzákladnější grafové pojmy (třeba hrany a stupně, podgrafy, souvislost). Klademe důraz na to, aby se čtenář naučil grafy uchopit a účelně s nimi pracovat a také aby správně viděl „stejnost" (isomorňsmus) grafů. Poté se věnujeme nej jednoduššímu druhu grafů, totiž stromům. Jedná se vesměs o pojmy, které se hojně vyskytují v informatických aplikacích grafů a především pak ve většině základních algoritmů, které se student informatiky učí.
10.1   Definice grafu
Hned na úvod přistoupíme k formální definici grafu. Bude se jednat o definici tzv. jednoduchého neorientovaného grafu, který budeme považovat za základní, pokud neřekneme jinak. Svým způsobem navazujeme na reprezentace relací v Oddíle 7.1.
Definice 10.1. Graf je uspořádaná dvojice G = (V, E),
kde V je konečná množina vrcholů a E ]e množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů; tj. E C .
Značení: Hranu mezi vrcholy uav píšeme jako {u, v}, nebo zkráceně uv. Vrcholy spojené hranou jsou sousední a hrana uv vychází z vrcholů u a. v. Na množinu vrcholů známého grafu G odkazujeme jako na V(G), na množinu hran E(G).
Komentář: Grafy se často zadávají přímo názorným obrázkem, jinak je lze formálně zadat výčtem vrcholů a výčtem hran. Například:
1 .
2 3 4
V = {1,2,3,4},    E = {{1,2}, {1,3}, {1,4}, {3,4}}
Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří právě dvojice prvků z této relace. Pro další výklad je žádoucí si uvědomit, že v základním podání jsou vrcholy grafu vždy „bezejmenné" (neformálně máme jen ty puntíky, které žádné jméno nemusí mít přiřazené). Jména vrcholům grafu přiřazujeme jen pro účely zápisu či popisu tohoto grafu a můžeme je volit libovolně.
75
Stupně vrcholů v grafu
Máme-li graf, často nás zajímá, kolik z kterého vrcholu vychází hran-spojnic, neboli kolik má vrchol „sousedů". Proto jedním z prvních definovaným pojmů bude stupeň vrcholu v grafu.
Definice 10.2. Stupněm vrcholu v v grafu G
rozumíme počet hran vycházejících z v. Stupeň v v grafu G značíme de (v).
Komentář: Slovo „vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí u neorientovaných grafů říkat, že hrana vychází z obou svých konců zároveň.
Například v nakreslené ukázce jsou stupně přímo zapsány u vrcholů. Definice: Graf je d-regulární, pokud všechny jeho vrcholy mají stejný stupeň d.
Značení: Nejvyššístupeň v grafu G značíme A(G) a nejnižší 8{G).
Věta 10.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran.
Důkaz. Při sčítání stupňů vrcholů v grafu započítáme každou hranu dvakrát - jednou za každý její konec. Proto také výsledek vyjde sudý. □
Příklad 10.4. Zodpovězme následující otázky:
a) Kolik hran má graf se 17 vrcholy stupňů 4ľ
b) Existují dva „různé" grafy se 6 vrcholy stupňů 2?
V otázce (a) je součet stupňů 17 • 4 = 68 a podle Věty 10.3 je počet hran 68/2 = 34.
V (b) existují dva velmi odlišné grafy uvedené vlastnosti, snadno je nakreslíme takto:
V dalším textu si zavedeme některé základní názvy, které nám umožní podobně jednoduché grafy snadno a stejně názorně popisovat slovy místo obrázků. □
Běžné typy grafů
Pro snadnější vyjadřování je zvykem některé běžné typy grafů nazývat popisnými jmény. Jde čistě o věc konvence a autoři se mohou v některých názvech lišit (i přicházet s novými názvy), avšak následujících pět názvů patří k všeobecným základům teorie grafů.
76
Kružnice délky n má n > 3 různých vrcholů spojených „do jednoho cyklu" n hranami:
3
c
n
Cesta délky n > 0 má n + 1 různých vrcholů spojených „za sebou" n hranami:
n
12     3 4
n   n + 1
Úplný graf na n > 1 vrcholech má n různých vrcholů spojených po všech dvojicích (tj. celkem (™) hran):
K
n
Úplný bipartitní graf na m > 1 a n > 1 vrcholech má m+n vrcholů ve dvou skupinách (partitách), přičemž hranami jsou spojeny všechny m ■ n dvojice z různých skupin:
1    2    3    4 .
m
Kr
V   2'   3' • • • rí
Hvězda s n > 1 rameny je zvláštní název pro úplný bipartitní graf KltTl:
3
Definice: Formálně nechť kružnice délky n > 3 je graf Cn, kde V(Cn) = {1,2,... ,n} a E(Cn) = {{i,i + 1} : 1 < i < n - 1} U {{n, 1}}. Nechť cesto délky n > 0 je graf Pn, kde F(Pn) = {1,2,... ,ra + 1} a £(P„) = {{«,« + 1} :1 <i<n}. Nechť típZny ^ra/na n > 1 vrcholech je ií,,, kde V(Kn) = {1, 2,..., n} a £(Ä„) = {{i, j} : 1 < i < j < n}. Nechť úplný bipartitní graf na, m> lan > 1 vrcholech je Km,n, kde V(Km,n) = {1,2,... ,m, m+ 1,... ,m + n} a E(Km^n) = {{i,j} '■ 1 < i < m, m + 1 < j < m + n}.
77
Příklad 10.5. Zodpovězte si sami následující snadné otázky:
* Pro jakou hodnotu n je úplný graf Kn zároveň cestou?
* Pro jakou hodnotu n je úplný graf Kn zároveň kružnicí?
* Pro jaké hodnoty m,n > 0 je úplný bipartitní graf Km,n zároveň kružnicí?
* Kolik hran musíte přidat do kružnice délky 6, aby vznikl úplný graf na 6 vrcholech?
* Pro jaké hodnoty m, n > 0 úplný bipartitní graf Km<n neobsahuje žádnou kružnici? □
Zmínka o zobecněných grafech
Komentář: Všimněme si, že v definici grafu (Def. 10.1) vůbec neuvažujeme možnosti vícenásobných hran (mezi stejnou dvojicí vrcholů) a tzv. „smyček" (hrana se stejným jedním koncem) - takovému zobecnění by se říkalo multigraf. Také prozatím nepřisuzujeme hranám žádný směr.
V Oddíle 10.4 si však ještě zavedeme orientované grafy, které každé hraně přiřazují jistý směr.
10.2   Podgrafy a isomorfismus
Dva základní nástroje pro práci s grafy jsou následující; možnost popisovat „část grafu" (podobně jako podmnožinu množiny, avšak je nutno se vyvarovat nekorektních situací) a poznávat „stejnost" dvou grafů.
Definice: Podgmfem grafu G rozumíme libovolný graf H na podmnožině vrcholů V(H) C V (G), který má za hrany libovolnou podmnožinu hran grafu G majících oba vrcholy ve V(H).
Píšeme H C G, tj. stejně jako množinová inkluze (ale význam je trochu jiný).
Komentář: Na následujícím obrázku vidíme zvýrazněné podmnožiny vrcholů hran. Proč se vlevo nejedná o podgraf? Obrázek vpravo už podgrafem je.
Definice: Indukovaným podgrafem je podgraf H C G takový, který obsahuje všechny hrany grafu G mezi dvojicemi vrcholů z V(H).
„Stejnost" grafů
Pozorný čtenář si možná již při čtení předchozího oddílu položil otázku: Co když vezmeme jeden graf (třeba kružnici délky 4) a nakreslíme nebo zapíšeme jej jednou tak, podruhé zase jinak - je to stále tentýž graf nebo ne? Viz obrázky dole.
78
Přísně formálně řečeno, každé další nakreslení jistého grafu, třeba této kružnice C4, je jiným grafem, ale přitom bychom rádi řekli, že různá nakreslení téhož grafu jsou „stále stejná". Pro tuto stejnost grafů se vžil pojem isomorfní grafy.
X : H : X
Definice 10.6. Isomorfismus ~ grafů G a H
je bijektivní (vzájemně jednoznačné) zobrazení / : V(G) —> V(H), pro které platí, že každá dvojice vrcholů u,v G V (G) je spojená hranou v G právě tehdy, když je dvojice f(u),f(v) spojená hranou v H.
Grafy G a H jsou isomorfní, pokud mezi nimi existuje isomorfismus. Píšeme G ~ H. Vlastnosti isomorfismu
Fakt: Mějme isomorfismus / grafů G a H. Pak platí následující
* G a H mají stejný počet hran,
* / zobrazuje na sebe vrcholy stejných stupňů, tj. de (v) = du(f(v)). Komentář:
U výše zakreslených dvou grafů objevíme isomorfismus velmi snadno - podíváme se, jak si odpovídají vrcholy stejných stupňů.
Naopak v této trojici grafů (se stejnými počty vrcholů i hran) žádné dva nejsou isomorfní. Proč? Ten vlevo má vrchol stupně 4, čímž se od obou zbylých liší. Prostřední graf pak má jediné dva vrcholy stupně 2 spojené hranou, kdežto v pravém takové dva vrcholy spojené nejsou (isomorfismus by je však i s hranou musel zachovat).
Příklad 10.7. Jsou následující dva grafy isomorfní?
79
Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Mají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Takže ani takto jsme mezi nimi nerozlíšili a mohou (nemusejí!) být isomorfní. Dále tedy nezbývá, než zkoušet všechny přípustné možnosti zobrazení isomorfismu z levého grafu do pravého.
Na levém grafu si pro ulehčení všimněme, že oba vrcholy stupně tři jsou si symetrické, proto si bez újmy na obecnosti můžeme vybrat, že nej levější vrchol prvního grafu, označme jej 1, se zobrazí na nejlevější vrchol ľ v druhém grafu (taky stupně tři). Očíslujme zbylé vrcholy prvního grafu 2,... ,6 v kladném smyslu, jak je ukázáno na následujícím obrázku. Druhý vrchol stupně tři, označený 4, se musí zobrazit na analogický vrchol druhého grafu (pravý spodní). Pak je již jasně vidět, že další sousedé 2, 6 vrcholu 1 se zobrazí na analogické sousedy 2', & vrcholu ľ v druhém grafu, a stejně je to i se zbylými vrcholy 3, 5. Výsledný isomorfismus vypadá v odpovídajícím značení vrcholů takto:
Abychom mohli s isomorfismem grafů přirozeně pracovat, je potřeba následující fakt: Věta 10.8. Relace „být isomorfní" ~ na třídě všech grafů je ekvivalencí.
Důkaz. Relace ~ je reflexivní, protože graf je isomorfní sám sobě identickým zobrazením. Relace je také symetrická, neboť bijektivní zobrazení lze jednoznačně obrátit. Tranzitivita ~ se snadno dokáže skládáním zobrazení-isomorfismů. □
Důsledkem je, že všechny možné grafy se rozpadnou na třídy isomorfismu. V praxi pak, pokud mluvíme o grafu, myslíme tím obvykle jeho celou třídu isomorfísmu, tj. nezáleží nám na konkrétní prezentaci grafu.
Komentář: Je uvedený přístup, tj. zaměňování konkrétního grafu za celou jeho třídu isomorfismu, v matematice neobvyklý? Ne, například už v geometrii jste říkali „čtverec o straně 2" či „jednotkový kruh" a podobně, aniž jste měli na mysli konkrétní obrázek, nýbrž celou třídu všech těchto shodných objektů.
Další (pod)grafové pojmy
Definice: Mějme libovolný graf G.
* Podgrafu H C G, který je isomorfní nějaké kružnici, říkáme kružnice v G.
* Speciálně říkáme trojúhelník kružnici délky 3.
* Podgrafu H C G, který je isomorfní nějaké cestě, říkáme cesta v G.
* Podgrafu H C G, který je isomorfní nějakému úplnému grafu, říkáme klika v G. (Někdy se za kliku považuje pouze takový úplný podgraf, který je maximální vzhledem k uspořádání inkluzí.)
* Podmnožině vrcholů X C V (G), mezi kterými nevedou v G vůbec žádné hrany, říkáme nezávislá množina X v G.
80
* Indukovanému podgrafu H C G, který je isomorfní nějaké kružnici, říkáme indukovaná kružnice v G.
Komentář: Uvažujme následující ukázky grafů:
První z ukázaných grafů například neobsahuje žádný trojúhelník, ale obsahuje kružnici délky 4, dokonce indukovanou. Druhý graf trojúhelník obsahuje a kružnici délky 4 taktéž. První graf obsahuje cestu délky 4 na vrcholech 1,2,3,4,5, ale ta není indukovaná. Indukovaná cesta délky 4 v něm je třeba 2,3,4,5,6. Druhý graf tyto cesty také obsahuje, ale naopak žádná z nich není indukovaná. První graf má největší kliku velikosti 2 - jedinou hranu, kdežto druhý graf má větší kliku na vrcholech 3,4, 5. Největší nezávislá množina u obou grafů má 3 vrcholy 2,4, 6.
Jak poznat neisomorfní grafy
Fakt: Mějme isomorfismus / grafů G a H. Pokud G obsahuje podgraf F, pak H také musí obsahovat podgraf isomorfní F. Obecněji lze tvrdit, že počet podgrafů v grafu G isomorfních zvolenému F je vždy roven takovému počtu v grafu H.
Příklad 10.9. Jsou následující dva grafy isomorfní?
Postupovat budeme jako v Příkladě 10.7, nejprve ověříme, že oba grafy mají stejně mnoho vrcholů i stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Pokud se však budeme snažit najít mezi nimi isomorfismus, něco stále nebude vycházet... Co nám tedy v nalezení isomorfismu brání? Podívejme se, že v druhém grafu oba vrcholy stupně tři mají svého společného souseda, tvoří s ním trojúhelník. V prvním grafu tomu tak není, první graf dokonce nemá žádný trojúhelník. Proto zadané dva grafy nejsou isomorfní. □
Příklad 10.10. Najděte všechny isomorfní dvojice grafů v následujících obrázcích tří 10-vrcholových grafů. Isomorfní dvojice odpovídajícím způsobem očíslujte, u neisomorfních toto zdůvodněte.
81
Postupujme systematicky: Všechny tři grafy mají po 10 vrcholech a všechny vrcholy stupňů 3. Takto jsme je tedy nijak nerozlíšili. Podívejme se třeba na trojúhelníky v grafech - opět si nepomůžeme, neboť žádný z nich trojúhelníky neobsahuje. Co se tedy podívat na obsažené kružnice délky 4? Graf C jich jasně obsahuje pět, graf A po chvíli zkoumání také, ale v grafu B najdeme i při vší snaze jen tři kružnice délky 4. (Obdobného rozdílu si můžeme všimnout, pokud se zaměříme na kružnice C5, zkuste si to sami.)
Takže co z dosavadního zkoumání plyne? Graf B nemůže být isomorfní žádnému z A,C. Nyní tedy zbývá najít (očekávaný) isomorfismus mezi grafy A a C. To se nám skutečně podaří poměrně snadno - stačí „prohozením" prostředních dvou vrcholů u grafu A získat lepší obrázek
	9		
			
	<	D	
9
c >
a odpovídající bijekce je na pohled zřejmá. Pro větší názornost jsme bijekci potvrzující isomorfismus zakreslených grafů explicitně vyznačili odpovídajícím číslováním vrcholů.
□
Poznámka: Výše uvedené příklady nám ukazují některé cesty, jak poznat (tj. najít nebo vyloučit) isomorfismus dvou grafů. Ty však ne vždy musí fungovat. Čtenář se může ptát, kde tedy najde nějaký univerzální postup pro nalezení isomorfismu? Bohužel vás musíme zklamat, žádný rozumný univerzální postup není znám a zatím platí, že jediná vždy fungující cesta pro nalezení či nenalezení isomorfismu mezi dvěma grafy je ve stylu vyzkoušejte všechny možnosti bijekci mezi vrcholy těchto grafů. (Těch je, jak známo, až n\.) Avšak heuristické algoritmické přístupy pracující se stupni vrcholů samotných a jejich sousedů a případně s malými podgrafy jsou v praxi velmi efektivní pro rozhodování isomorfismu.
10.3   Souvislost, komponenty a vzdálenost
Důležitou globální vlastností grafů je souvislost, tedy možnost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu. Tuto vlastnost si nyní upřesníme.
Tvrzení 10.11. Mějme relací ~ na množině vrcholů V(G) libovolného grafu G takovou, že pro dva vrcholy x ~ y právě když existuje v G cesta začínající v x a končící v y. Pak ~ je relací ekvivalence.
Důkaz. Relace ~ je reflexivní, neboť každý vrchol je spojený sám se sebou cestou délky 0. Symetrická je také, protože cestu z x do y snadno v neorientovaném grafu obrátíme na cestu z y do x. Důkaz tranzitivity však není takto triviální—pokud vezmeme cestu z x do y a cestu z y do z, tak se tyto dvě cesty mohou protínat i jinde než v y a nelze je prostě „navázat" na sebe.
82
Pro důkaz tranzitivity si označme P cestu z x do y a Q cestu z y do z. Pokud označíme P' C P tu část první cesty z x do prvního vrcholu p v průniku s Q (tj. p G V (P) H V (Q)) a označíme Q' ^ Q zbytek druhé cesty od p do z, tak P' U Q' vždy je cestou z x do z. □
Definice 10.12. Komponentami souvislosti  grafu G nazveme třídy ekvivalence výše popsané (Tvrz. 10.11) relace ~ na V(G).  Jinak se také komponentami souvislosti myslí podgrafy indukované na těchto třídách ekvivalence.
Komentář: Podívejte se, kolik komponent souvislosti má tento graf:
Vidíte v obrázku všechny tři komponenty? Jedna z nich je izolovaným vrcholem, druhá hranou (tj. grafem isomorfním K2) a třetí je to zbývající.
Definice: Graf G je souvislý pokud je G tvořený nejvýše jednou komponentou souvislosti, tj. pokud každé dva vrcholy G jsou spojené cestou.
Poznámka: Prázdný graf je souvislý a má 0 komponent.
Komentář: Který z těchto dvou grafů je souvislý?
Příklad 10.13. Dokažme si, že každý souvislý jednoduchý 2-regulární graf G je kružnicí (tj. isomorfní některé kružnici Cn z Oddílu 10.1).
Nechť e je hranou mezi vrcholy u,v grafu G a vezměme graf G' = G — e vzniklý odebráním hrany e. Pokud by u a v náležely v G' různým komponentám souvislosti, tyto komponenty by každá měla lichý součet stupňů, což nelze podle Věty 10.3. Proto nati jsou spojeny cestou v G', nechť vrcholy této cesty jsou po řadě značeny u\ = u, u2,... ,Uk = v. Toto značení nám nyní udává isomorfismus zobrazující vrchol Ui na vrchol i z definice kružnice C\.- Nyní už zbývá jen drobnost; dokázat, že jiné vrcholy než u1}..., v grafu G nejsou. Pokud bychom měli další vrchol x, pak x je spojen cestou Q do u a první vrchol z V(Q) H {ui,..., Uk} by měl stupeň větší než 2, spor. □
Grafová vzdálenost
Mimo předchozí otázku souvislosti grafu, tj. existence jakékoliv cesty mezi dvojicemi vrcholů, je častou úlohou se dostat z místa na místo tou nejkratší cestou. Ve zjednodušeném podání nás zajímá jen počet hran, neboli považujeme každou hranu grafu za jednotkově dlouhou, a definujeme následující.
83
Dennice 10.14. Vzdálenost dc(u,v) dvou vrcholu u, v v grafu G je dána
délkou nejkratší cesty mezi u a v v G.  Pokud cesta mezi u, v neexistuje, je vzdálenost
definována de (u, v) = oo.
Komentář: Neformálně řečeno, vzdálenost mezi u, v je rovna nejmenšímu počtu hran, které musíme překonat, pokud se chceme dostat z u do v. Speciálně vždy platí dc(u,u) = 0 a dále dc(u,v) = oo právě když u,v patří různým komponentám souvislosti.
Jaká je ve výše zakresleném grafu vzdálenost dc(u,v)? Ano, snadno určíme hodnotu dc(u,v) = 2, viz vyznačená cesta délky 2.
Najdete ale v temže grafu nějakou dvojici vrcholů se vzdáleností 3? Fakt: V neorientovaném grafu je vzdálenost symetrická, tj. dc(u,v) = dc(v,u).
Lema 10.15. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost:
Mu, v, w G V (G) :   dG(u, v) + dG(v, w) > dG(u, w).
Důkaz. Postupujeme podobně jako v důkaze Tvrzení 10.11 - pokud máme cesty P, P' mezi u,v a mezi v,w, tak existuje cesta Q C P U P' mezi u,w, jež má zřejmě délku nejvýše dG(u,v) + dc(v,w). Skutečná vzdálenost mezi u,w pak už může být jen menší.
□
Příklad 10.16. Proč každý 3-regulární graf na 12 vrcholech musí obsahovat dvojici vrcholů se vzdáleností 3 ľ
Dokažme požadované tvrzení sporem. Nechť v je libovolný vrchol našeho grafu G. Pak v má tři sousedy a, b, c (tj. ve vzdálenosti 1 od v). Podle definice vzdálenosti je každý vrchol ve vzdálenosti 2 od v sousedem některého z a, b, c. Avšak a má za jednoho souseda v a mimo něj má už jen dva další sousedy. Stejně tak b, c. Tudíž v G existuje nejvýše šest vrcholů mimo v, kteří jsou sousedé jednoho z a, b, c. Celkem tak napočítáme (od v) jen 1 + 3 + 6 = 10 vrcholů a některý z 12 vrcholů grafu G musí být ve větší vzdálenosti než 2, spor. Zakreslete si sami tuto úvahu obrázkem. □
Jednoduché zjištění vzdálenosti
Jak nejsnadněji určíme vzdálenost v grafu? Jednoduše postupujeme od prvního z vrcholů „do šířky" (jakoby v soustředných kruzích) a počítáme si kroky, až narazíme na druhý z vrcholů. Formalizovat tento postup můžeme následovně (a jak se později dozvíte, jedná se o obecné schéma prohledávání grafu do šířky).
Algoritmus 10.17. Určení vzdáleností z vrcholu u grafu G.
Pro daný souvislý graf G a jeho vrchol u určíme vzdáleností d(u, x) do každého vrcholu x G V (G) následujícím postupem.
1. Na začátku položíme d(u,u) := 0.
84
2. Pro i = 0,1, 2,..., přesněji dokud nejsou určeny všechny vzdálenosti, provádíme: Pro každou hranu xy G E(G) takovou, že d(u, CC^j — 1 db d(u,y) je dosud neurčená, položíme d(u,y) :=i + 1.
0 \
2
3
i
i + 1
Důkaz správnosti algoritmu: Cílem je dokázat, že pro hodnoty určené Algoritmem 10.17 platí d(u,v) = dc(u,v) podle Definice 10.14. Předně si uvědomíme, že v souvislém konečném grafu je vzdálenost vždy konečná, neboli existuje přirozené i takové, že dc(u,v) = i. Proto stačí dokázat indukcí podle i > 0, že pro každý vrchol x takový, že dc(u,x) < i, skutečně platí d(u,x) = dc(u,x).
Pro bázi indukce, tj. pro i = 0 cl X — U to je zřejmé. Necht nyní naše tvrzení platí pro nějaké přirozené i a vezměme libovolný vrchol y takový, že dc(u,y) < i + 1. Pokud dc(u, y) < i, jsme hotovi podle indukčního předpokladu. Jinak dc(u, y) = i + 1 a existuje cesta P C G s konci u a y délky i + Nechť x je sousedem y na cestě P. Pak dc(u, x) = i podle definice vzdálenosti a tudíž d(u, x) = i podle indukčního předpokladu. Tudíž v našem algoritmu určíme d(u,y) := i + 1 = dc(u,y). □
Poznámka: Vedle jednotkové grafové vzdálenosti podle Definice 10.14 nás často v praktických aplikacích zajímá zobecněné pojetí, ve kterém nemají všechny hrany stejnou délku. Formálně tak můžeme studovat obecnou vzdálenost v grafech, jejichž hrany jsou váženy nezápornými reálnými čísly (délkami). K výpočtu takto zobecněné vzdálenosti už nestačí jednoduchý postup Algoritmu 10.17, ale obracíme se k trochu sofistikovanějším algoritmům jako například k Dijkstrově algoritmu. To je už téma nad rámec tohoto matematického předmětu.
10.4   Základní pojmy orientovaných grafů
Ve většině aplikací grafů se v základu soustředíme na neorientované grafy, ale pro některé úlohy je vhodné či přímo nezbytné vědět, kterým „směrem" hrana grafu vede. Požadavek explicitně vyjádřit směr hrany přirozeně vede na následující definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů. (V obrázcích kreslíme orientované hrany se šipkami.)
Definice 10.18.    Orientovaný graf je uspořádaná dvojice D = (V, E), kde V je
množina vrcholů a E C V x V je množina hran - tj. podmnožina uspořádaných dvojic vrcholů.
Pojmy podgrafu a isomorfismu z Oddílu 10.2 se přirozeně přenášejí na orientované grafy.
85
Značení: Hrana (u, v) (zvaná také šípka) v orientovaném grafu D začíná ve vrcholu u a končí ve (míří do) vrcholu v. Opačná hrana (v, u) je různá od (u, v) . Speciálně hrana tvaru (u, u) se nazývá orientovaná smyčka.
Komentář: Orientované grafy odpovídají relacím, které nemusí být symetrické. Mezi stejnou dvojicí vrcholů mohou tudíž existovat dvě hrany v obou směrech, nebo jen kterákoliv jedna z nich nebo žádná. Všimněte si také, že orientované grafy implicitně odlišujeme od obyčejných použitím písmene D místo dřívějších G, H.
Například orientovaná cesta délky n > 0 je následujícím grafem na n + 1 vrcholech
6      ... n
Definice: Počet hran začínajících ve vrcholu u orientovaného grafu D nazveme výstupním stupněm d^^u) a počet hran končících v u nazveme vstupním stupněm dlg(u).
Komentář: Součet všech výstupních stupňů je přirozeně roven součtu všech vstupních stupňů orientovaného grafu. Důkaz viz Věta 10.3.
Definice: Symetrizací orientovaného grafu D rozumíme neorientovaný graf G vzniklý „zapomenutím směru hran" v D, přesněji V(G) = V(D) a md G E(G) právě když {(u,v),(v,u)}nE(D)^^.
Souvislost na orientovaných grafech
Pojem orientované souvislosti grafu D je natolik fundamentálně odlišný od neorientovaného případu (což je dáno právě jeho „směrovostí"), že si zaslouží samostatnou diskusi i v našem zběžném pohledu na orientované grafy. Uvedeme si odstupňovaně tři základní pohledy na orientovanou souvislost:
• Slabá souvislost. Jedná se o tradiční souvislost na symetrizaci grafu D
Komentář: Zjednodušeně a názorně se dá říci, že při cestování grafem „zapomeneme" směr šipek. Na obrázku:
®-2> •-5=-»-=í--•-3=-®
Dosažitelnost (směrem „ven"). Orientovaný graf D je dosažitelný směrem ven, pokud v něm existuje vrchol v G V (D) takový, že každý vrchol x G V (D) je dosažitelný orientovanou cestou z v.
86
Komentář: Podrobným zkoumáním následujícího obrázku zjistíme, že jeho graf není dosažitelný směrem ven, neboť chybí možnost dosáhnout vrchol b úplně vpravo. Na druhou stranu po vypuštění b je zbylý graf dosažitelný ven z vrcholu a vlevo.
Všimněte si, že definici dosažitelnosti lze snadno „obrátit", avšak touto další možností se v našem krátkém přehledu nebudeme zabývat.
• Silná souvislost.  V nejsilnější verzi vyžadujeme současnou existenci spojení (cest) v obou směrech mezi dvojicí vrcholů.
Tvrzení 10.19. Nechť »2 je binárni relace na vrcholové množině V(D) orientovaného grafu D taková, že u »2 v právě když existuje dvojice orientovaných cest - jedna z u do v a druhá z v do u v grafu D.  Pak »2 je relace ekvivalence.
Důkaz (náznak). Postupujeme podobně jako v důkaze Tvrzení 10.11. □
Definice 10.20. Silné komponenty orientovaného grafu D
jsou třídy ekvivalence relace »2 uvedené v Tvrzení 10.19. Orientovaný graf D je silně souvislý pokud má nejvýše jednu silnou komponentu.
Komentář: Pro ilustraci si mírně upravíme dříve prezentovaný orientovaný graf tak, že bude dosažitelný z nejlevějšího vrcholu. Je výsledek silně souvislý?
Ne, na obrázku jsou vyznačené jeho 4 silné komponenty. Vpravo zároveň uvádíme pro ilustraci obrázek kondenzace silných komponent tohoto grafu, což je acyklický orientovaný graf s vrcholy reprezentujícími zmíněné silné komponenty a směry hran mezi nimi.
Pro zvídavé čtenáře poznamenáváme, že si mohou definici silné komponenty porovnat s jádrem předuspořádání v Oddíle 8.3. Jde o hodně podobné koncepty, ale vidíte i jeden drobný (skutečně ne až tak podstatný) rozdíl?
87
10.5   Dodatek: 7 mostů jedním tahem
Pravděpodobně nejstarší zaznamenaný výsledek teorie grafů pochází od Leonharda Eu-lera - jedná se o slavný problém 7-mi mostů v Královci / Kônigsbergu / dnešním Ka-liningradě. Tento problém, či spíše matematickou hříčku, o kreslení grafů „jedním tahem" zařazujeme na závěr lekce především z důvodů historických. Eulerovo jednoduché řešení má některé zajímavé a užitečné důsledky v jiných oblastech kombinatoriky, ty však přesahují rámec našeho úvodního textu.
O jaký problém se 7-mi mosty se tehdy v Kônigsbergu 18-tého století jednalo?
Příklad 10.21. Je možné při jedné procházce suchou nohou přejít po každém ze sedmi vyznačených mostů v Kônigsbergu právě jednou?
Geniálně jednoduché řešení otázky představíme ve zbytku tohoto oddílu. □ Sled a tah v grafu
Pro přesnou formulaci řešení uvedeného příkladu využijeme následující nové pojmy.
Definice: Sledem délky n v grafu G rozumíme posloupnost vrcholů a hran
(vo,e1,v1,e2,v2,.. -,en,vn), ve které vždy hrana    má koncové vrcholy Ví_i,Ví.
Komentář: Všimněte si, že sled je vlastně jakákoliv procházka po hranách grafu z u do v. Příkladem sledu může být průchod IP paketu internetem (včetně cyklem).
Definice: Ta/z je sled v grafu bez opakování hran. Uzavřený tah]e tahem, který končí ve vrcholu, ve kterém začal. Otevřený tah je tahem, který končí v jiném vrcholu, než ve kterém začal.
Komentář: Jistě znáte dětskou hříčku s „kreslením domečku jedním tahem"... Ano, to je v podstatě totéž, co tah v grafu (kterým „kreslíme" hrany našeho grafu).
Fakt: Cesta je přesně otevřený tah bez opakování vrcholů. Kružnice je přesně uzavřený tah bez opakování vrcholů. (Srovnejte si toto s definicemi Oddílu 10.1.)
Eulerovské grafy
Slibované řešení Příkladu 10.21 od Leonharda Eulera zní takto:
Věta 10.22. Graf G lze pokrýt (nakreslit) jedním uzavřeným tahem právě když G je souvislý a všechny vrcholy v G jsou sudého stupně.
88
Komentář: Znění této věty lze velmi názorně ilustrovat následujícím obrázkem grafu a příslušného uzavřeného tahu pokrývajícího všechny hrany.
A jak je tomu v Příkladu 10.21? Zde nejprve nakreslíme příslušný (multi)graf, ve kterém vrcholy jsou jednotlivé kusy země oddělené vodou (tj. dva říční ostrovy a dva břehy):
Jaké jsou stupně vrcholů tohoto grafy? Je to 3, 3, 3, 5, neboli všech 7 hran-mostů města Kónigsbergu nelze dle Věty 10.22 pokrýt jedním uzavřeným tahem (ani otevřeným tahem, viz Důsledek 10.23).
Důsledek 10.23. Graf G lze pokrýt (nakreslit) jedním otevřeným tahem právě když G je souvislý a všechny vrcholy v G až na dva jsou sudého stupně.
Důkaz: Dokazujeme oba směry ekvivalence Věty 10.22. Pokud lze G pokrýt jedním uzavřeným tahem, tak je zřejmě G souvislý a navíc má každý stupeň sudý, neboť uzavřený tah každým průchodem vrcholem pokryje dvě hrany.
Naopak zvolíme mezi všemi uzavřenými tahy T obsaženými v G ten (jeden z) nejdelší. Tvrdíme, že T obsahuje všechny hrany grafu G.
- Pro spor vezměme graf G' = G — E (T), o kterém předpokládejme, že je neprázdný. Jelikož G' má taktéž všechny stupně sudé, je (z indukčního předpokladu) libovolná jeho hranově-neprázdná komponenta C C G' pokrytá jedním uzavřeným tahem Tq-
- Vzhledem k souvislosti grafu G každá komponenta C C G' protíná náš tah T v některém vrchole w, a tudíž lze oba tahy Tc a T „propojit přes wlí. To je spor s naším předpokladem nejdelšího možného T, neboť T U Tc je delším tahem v G. □
Důkaz důsledku: Nechť u,v jsou dva vrcholy grafu G mající lichý stupeň, neboli dva (předpokládané) konce otevřeného tahu pro G. Do G nyní přidáme nový vrchol w spojený hranami siiaw. Tím jsme náš případ převedli na předchozí případ grafu se všemi sudými stupni. □
Rozšiřující studium
Grafy můžeme v informatice potkat doslova na každém kroku, mimo jiné hojně už v základních kurzech algoritmizace. Nejen že grafy jsou základem mnoha programátorských datových struktur, ale představují i vhodný model pro mnoho praktických problémů, z nichž některé ochutnáte již v příští lekci. Celkově je zdejších pár lekcí teorie grafů jen lehkým
89
úvodem do celé rozsáhlé oblasti, přičemž na FI MU lze pokračovat v jejím cíleném studiu v předmětech MA010 a MA015.
Rozsáhlý matematický úvod do teorie grafů je zahrnut ve skvělé knize Kapitoly z diskrétní matematiky autorů Jiřího Matouška a Jaroslava Nešetřila. Vřeleji doporučujeme jako doplňkový studijní zdroj všem, kteří chtějí lépe pochopit grafy z jejich matematické stránky.
90
11    Stromy a kostry grafů
Úvod
JVa rozdíl od předchozí lekce, která se zabývala grafy z obecného a také trochu povrchního pohledu, se nyní soustředíme na jednu konkrétní nepříliš obtížnou oblast, které se budeme věnovat do větší hloubky Jde o problematiku stromů, neboli acyklických souvislých grafů, představujících nejjednoduššípodobu grafů. Na stromech si budeme ilustrovat argumentaci a důkazy o grafech a také jeden z historicky základních diskrétních optimalizačních problémů -problém minimální kostry (tj. minimálně ohodnoceného stromu na dané množině vrcholů).
Cíle
Rozebereme si různé charakteristické vlastnosti stromů a rozebereme si důkazy těchto vlastností. Zmíníme také kořenové stromy. Poté si defínujeme problém minimální kostry a ukážeme jeho efektivní řešení.
11.1    Stromy — grafy bez kružnic
Podrobné studium některých užitečných vlastností grafů si pro zjednodušení ukážeme na tom prakticky nej jednodušším typu grafu - na stromech, jež jsou mimo jiné základem mnoha datových typů používaných v informatice.
Komentář: Začněme ilustračními obrázky stromů. Povšimněte si přitom jedné zvláštnosti,
Definice 11.1. Strom je (jednoduchý) souvislý graf T bez kružnic.
Komentář: Obecněji les je pak graf bez kružnic (opět jednoduchý, ale nemusí být souvislý). Komponenty souvislosti lesa jsou stromy. Jeden vrchol bez hran a prázdný graf jsou také stromy. Grafy bez kružnic také obecně nazýváme acyklické.
Vlastnosti stromů
Přehled základních vlastností stromů je pro nás zároveň příležitostí si ukázat několik nových hezkých matematických důkazů a naučit se správně zdůvodňovat v oblasti grafů.
Tvrzení 11.2. Strom s více než jedním vrcholem obsahuje vrchol stupně 1.
Důkaz: Vezmeme libovolný strom Tav něm libovolný vrchol v. Jelikož souvislý graf s více než jedním vrcholem nemá vrchol stupně 0, zvolený vrchol v má incidentní hranu. Zvolme (sestrojme) nyní nejdelší možnou cestu S v T začínající ve v: S začne libovolnou hranou vycházející z v; v každém dalším vrcholu u cesty S, který má stupeň větší než 1, pokračuje S další hranou. Pokud by tomu tak nebylo, není S nejdelší možná nebo další
91
hrana vede do některého předchozího vrcholu cesty S. Tím bychom ale získali kružnici, což ve stromě nelze. ^
Proto cesta S nutně skončí v nějakém vrcholu stupně 1 v T. □
Komentář: Uvedený důkaz lze zapsat výrazně stručněji (ale poněkud tím utrpí jeho pochopitelnost): Rovnou na začátku lze zvolit S jako libovolnou nejdelší možnou cestu ve stromě T a podívat se, kam by případně vedly další hrany z koncového vrcholu S.
Zamyslete se navíc, proč v každém stromě s více než jedním vrcholem jsou alespoň dva vrcholy stupně 1 (odpověď je skrytá už v předchozím důkaze). Zároveň si odpovězte, jestli lze tvrdit, že každý strom s více než jedním vrcholem obsahuje tři vrcholy stupně 1.
Definice: Každý jeho vrchol stromu stupně 1 nazveme listem stromu.
Věta 11.3. Strom na n vrcholech má přesně n — 1 hran pro n > 1.
Důkaz: Toto tvrzení dokážeme indukcí podle n. Strom s jedním vrcholem má přesně 0 = n — 1 hran.
Předpokládejme platnost tvrzení pro libovolné přirozené n := i > 1. Nechť T je nyní libovolný strom nan :=i + l vrcholech. Podle Tvrzení 11.2 obsahuje T vrchol v stupně 1. Označme T' = T — v graf vzniklý z T odebráním vrcholu v a jedné jeho hrany. Pak T' je také souvislý graf bez kružnic, a tudíž strom na n — 1 = i vrcholech. Dle indukčního předpokladu T' má i — 1 = n — 2 hran, a proto T má n — 2 + 1 = n — 1 hran. □
Příklad 11.4. Les G má 2015 vrcholů a 4 souvislé komponenty. Kolik má hran?
Pokud počty vrcholů jednotlivých komponent lesa G po řadě označíme n\, n2, n^, n^, tak máme n\ + n2 + n% + = 2015. Každá komponenta G je strom podle definice lesa. Zároveň podle Věty 11.3 má i-tá komponenta přesně rti — 1 hran. V součtu má G celkem (ni - 1) + (n2 - 1) + (n3 - 1) + (n4 - 1) = 2015 - 4 = 2011 hran. □
Cesty ve stromech
Věta 11.5. Mezi každými dvěma vrcholy stromu vede právě jediná cesta.
Jelikož strom T je souvislý dle definice, mezi libovolnými dvěma vrcholy u,v vede nějaká cesta. Pokud by existovaly dvě různé cesty R±,R2 mezi u a, v, tak bychom vzali jejich symetrický rozdíl, podgraf H = RľAR2 s neprázdnou množinou hran, kde H zřejmě má všechny stupně sudé. Na druhou stranu se však podgraf stromu musí opět skládat z komponent stromů, a tudíž obsahovat vrchol stupně 1 podle Tvrzení 11.2, což je spor. Proto cesta mezi u a v existuje jen jedna. □
92
Komentář: Uvedený důkaz Věty 11.5 může působit poněkud „tajemně a neprůhledně" (ve srovnání s předchozími přímočařejšími důkazy). Vždyť to přeci vypadá docela jasně, že ze dvou cest mezi u a v složíme dohromady nějakou(?) kružnici. Avšak po hlubším zamyšlení můžete sami zjistit, že správně zapsat, kde ta kružnice v R\ U R2 je, není vůbec lehké a vedlo by to k delšímu a ne moc průhlednějšímu důkazu.
Důsledek 11.6. Přidáním jedné nové hrany do stromu vznikne právě jedna kružnice.
Důkaz: Nechť mezi vrcholy u,v ve stromu T není hrana. Přidáním hrany e = uv vznikne právě jedna kružnice z e a jediné cesty mezi u,v v T podle Věty 11.5. □
Alternativní charakterizace stromů
Z předchozích tvrzení vyplývá následující alternativní charakterizace stromů, která ukazuje důležitost jich samotných i jako tzv. koster obecných grafů (viz Oddíl 11.2).
Na dané množině vrcholů je (vzhledem k inkluzi množin hran) strom
• minimální souvislý graf (plyne z Věty 11.5)
• a zároveň maximální acyklický graf (plyne z Důsledku 11.6).
Komentář: Jen tak mimochodem, kolik dokážete nalézt neisomorfních stromů na 4 nebo 5 vrcholech? Vidíte, že jich není mnoho? Nakreslete si je všechny.
Kořenový strom
Mimo samotnou teorii grafů se častěji setkáte s poněkud odlišným pojetím stromu, ve kterém má význačné místo jeden speciálně vybraný vrchol stromu, zvaný kořen (viz třeba mnohé datové struktury v algoritmech).
Definice: Strom T s vyznačeným vrcholem r G V (T), zkráceně zapsaný dvojicí (T,r), nazýváme kořenovým stromem s kořenem r. Vrchol p nazveme následníkem vrcholu q, pokud (ta jediná) cesta z kořene r do p obsahuje (neboli vede přes) q. Dále p nazveme potomkem (synem) q, pokud p je následníkem q a zároveň {p, q] je hranou T. V kořenovém stromu nazveme listem každý vrchol, který nemá potomky.
Komentář: Každý vrchol kořenového stromu je následníkem kořene. V přirozeně přeneseném významu se u kořenových stromů používají pojmy rodič, prarodič, děti/synové, sourozenci, předchůdci, atd. Zběžná ilustrace použití těchto pojmů je na následujícím schématu stromu.
kořen
(celkově
Definice: Výška kořenového stromu je rovna největší vzdálenosti z jeho kořene do některého listu.
93
Poznámka: Všimněte si, že význam pojmu „list" se může lišit mezi stromem a kořenovým stromem. V extrémním případě stromu sestávajícího pouze z kořene je tento kořen (stupně 0) zároveň listem, ale jinak každý list kořenového stromu má nutně stupeň 1. V opačném směru zase platí, že kořen stupně 1, který je nazýván listem v obyčejném stromu, není listem příslušného kořenového stromu (má přece jednoho potomka).
11.2   Problém minimální kostry
V návaznosti na učivo o stromech se podíváme na tradiční a široce studovaný problém nalezení minimálního souvislého podgrafu (stromu) v daném grafu - této úloze se říká minimální kostra neboli MST (z anglického minimum spanning tree). V jakém smyslu však chápat slovo „minimální" u kostry? Na jedné straně to odkazuje na fakt, že kostra souvislého grafu je vždy strom, coby inkluzí minimální souvislý graf na daných vrcholech podle učiva Oddílu 11.1. Přesně definováno:
Definice: Podgraf T C G souvislého grafu G se nazývá kostrou, pokud
* T je stromem a
* V(T) = V(G), neboli T propojuje všechny vrcholy G.
Na druhou stranu navíc požadujeme, že nalezená kostra má mít v součtu co nejmenší celkovou délku. Co však toto znamená? Podle Věty 11.3 má každý strom na daných n vrcholech stejně hran, přesně n — 1. Tudíž aby úloha minimalizace délky (či váhy) kostry vůbec dávala smysl, budeme se věnovat grafům s „obecně dlouhými" hranami:
Definice: Vážený graf je graf G spolu s ohodnocením w hran reálnými čísly w : E(G) —> R. Váženému také někdy říkáme ohodnocený.
Vahou (celkovou délkou) kostry T C G váženého souvislého grafu (G, w) rozumíme
tj. součet vah všech hran této kostry.
Definice 11.7. Problém minimální kostry (MST) ve váženém souvislém grafu (G,w) hledá kostru T C G s nejmenší možnou vahou (přes všechny kostry grafu G).
Komentář: Problém minimálni kostry je ve skutečnosti historicky úzce svázán s jižní Moravou a Brnem, konkrétně s elektrifikací jihomoravských vesnic ve dvacátých letech! Právě na základě tohoto praktického optimalizačního problému brněnský matematik Otakar Borůvka jako první v matematické literatuře zformuloval a podal řešení problému minimální kostry v roce 1926.
Ve výzkumu minimálních koster pokračoval i velmi dobře známý český matematik Vojtěch Jarník, s publikací v roce 1930 (viz Algoritmus 11.10). První ne-českou publikací na toto téma je pak až Kruskalův hladový algoritmus z roku 1956 (viz Algoritmus 11.8).
94
Řešení minimální kostry
Následující postup tzv. hladového nalezení minimální kostry pochází od Kruskala. Sice nejde ani o nejstarší publikovaný postup (viz Borůvka a Jarník výše), ani o nejvhodnější algoritmus k praktické implementaci, má svou hlubokou teoretickou hodnotu, a proto jej uvádíme první a podrobně.
Algoritmus 11.8. Hladový postup pro minimální kostru grafu (G,w).
Mějme dán souvislý vážený graf G s ohodnocením hran w.
1. Seřadíme všechny hrany G jako E(G) = (ei, e2,..., em) tak, že w(ei) < w(e2) < • • • < w(em).
2. Inicializujeme prázdnou kostru T = (V(G),$).
3. Po řadě pro i = 1,2,... , m provedeme následující:
• Pokud T + e,i nevytváří kružnici, tak E(T) +- E(T) U {ej}.
(Neboli pokud    spojuje různé komponenty souvislosti dosavadního T.)
4. Na konci T obsahuje minimální kostru grafu G (případně jednu z několika takových).
Komentář: Pro ilustraci si ukážeme postup hladového algoritmu pro vyhledání kostry následujícího grafu:
Hrany si nejprve seřadíme podle jejich vah 1,1,1,1, 2, 2, 2, 2, 3, 3, 3,4,4.
V obrázku průběhu algoritmu používáme tlusté čáry pro vybrané hrany kostry a tečkované čáry pro „zahozené" hrany. Hrany teď postupně přidáváme do kostry či zahazujeme. ..
	M,
1 3	4 2 4 3
	7y4
Získáme tak minimální kostru velikosti 1 + 2 + 2 + 3 + 1 + 1 + 2 = 12, která je v tomto případě (náhodou) cestou, na posledním obrázku vpravo.
Poznamenáváme, že při jiném seřazení hran stejné váhy by kostra mohla vyjít jinak, ale vždy bude mít stejnou váhu 12.
Věta 11.9. Hladový postup korektně spočítá minimální kostru váženého grafu (G,w).
95
Důkaz (náznak): Pro spor předpokládejme, že Ti je kostra spočítaná Algoritmem 11.8 a T2 nějaká minimální kostra, kde <Í£(T2) < cř^(Ti) a rozdíl \E(Ti)AE(t2)\ je nejmenší. Nechť i je nejmenší index takový, že e« G E(Ti)AE(t2). Pak nutně e« G E (Ti) \ EiT?) (proč?), a tudíž T2 + podle Důsledku 11.6 obsahuje kružnici procházející také hranou e j pro j > i. Potom však T3 = (T2 + e^) \ {e,} je další kostrou mající váhu cř^(T2) + w(e,i) — w(ej) > g^(T2), a proto u>(ej) = w(ej). Tudíž T3 je minimální kostra „bližší" T\ ve smyslu symetrického rozdílu, což je spor s volbou T2. □
Jarníkův (Primův) algoritmus
Ač koncepčně velmi jednoduchý, má Algoritmus 11.8 některé problematické implementační detaily, pro které je mnohem častěji používán následující algoritmus (často je připisován Američanu Primoví, ale mnohem dříve publikován Vojtěchem Jarníkem v roce 1930), vycházející z prostého prohledávání do šířky (viz také Algoritmus 10.17).
Algoritmus 11.10. Hledání minimální kostry ve váženém grafu (G,w).
Opět mějme dán souvislý vážený graf G s ohodnocením hran w.
1. Na začátku zvolíme libovolný vrchol u G V (G) a podstrom T := ({u}, 0).
2. Dokud V (T) ý ^(G), provádíme: Nalezneme hranu / = uv G E (G) nejmenší váhy s jedním koncem u ve V(T) a druhým v ve V(G) \ V(T) a položíme T := T + v + /'.
Formálně přesněji tento krok popíšeme následovně.
* Nechť X = {uv G E (G) : u G V (T), v G V (G) \ V (T)} a zvolme / = uv G X minimalizující váhu w(f).
* Položme V (T) := V (T) U {v} a E(T) := E (T) U {/}.
3. Nyní je T minimálni kostrou grafu G.
Komentář: Následuje stručná ukázka průběhu Jarníkova algoritmu, kde kostru opět vyznačujeme tučnými čarami a zpracované vrcholy kroužky kolem.
	1 \ 1
	
	\ 3
2	1 i\
	
	1          \ 1
Již bez důkazu si na závěr našeho pojednání o kostrách uvedeme: Věta 11.11. Algoritmus 11.10 korektně spočítá minimální kostru váženého grafu (G,w).
96
11.3   Dodatek: Výběr různých reprezentantů
S grafy je úzce svázán i tento klasický kombinatorický problém, vybírající různé reprezentanty z daného systému množin (které typicky nejsou disjunktní a tudíž není jasné, zda reprezetanti dvou množin skutečně budou různí).
Definice: Nechť M1; M2,..., jsou neprázdné množiny. Systémem různých reprezentantů množin M . M2- ■ ■ ■, nazýváme posloupnost různých prvků (xi, x2,..., Xk) takových, že Xi G Mi pro i = 1, 2,..., k.
Teoretické řešení problému výběru různých reprezentantů je plně popsané následující charakterizací jeho existence (známou jako Hallova věta):
Věta 11.12. Nechť Mi, M2,..., Mk jsou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, právě když platí
neboli pokud sjednoceni libovolné skupiny z těchto množin má alespoň tolik prvků, kolik množin je sjednoceno.
Komentář: Všimněte si dobře, že v jednom směru je platnost Věty 11.12 zřejmá; neboli pokud systém různých reprezentantů existuje, tak podmínka (1) jasně musí platit.
Co nám tedy Věta 11.12 prakticky říká? Jednoduše, pokud systém různých reprezentantů existuje, stačí jej najít či uhodnout. A pokud neexistuje, stačí nalézt vhodnou množinu J porušující podmínku (1) Věty 11.12. Popisům jako tato věta se říká dobré charakterizace, neboť nám poskytují buď snadno ověřitelné řešení našeho problému, nebo snadno uvěřitelný důvod, proč řešení nemůže existovat.
Párování grafu a reprezentanti
Přiřazení reprezentantů množinám lze chápat jako hrany grafu, ve kterém na jedné straně jsou naše množiny M\,M2,... ,Mk z Věty 11.12 a na druhé straně jsou jejich všechny prvky. Takto vypadajícím grafům říkáme bipartitni (formálně je bipartitní graf libovolným podgrafem vhodného úplného bipartitního grafu Km<n).
Požadavek na jedinečnost a různost reprezentantů pak můžeme vyjádřit touto definicí:
Definice: Párovániv (nyní bipartitním) grafu G je podmnožina hran M C E (G) taková, že žádné dvě hrany z M nesdílejí koncový vrchol.
Uvažujme systém množin M1;..., Mk a označme p\,... ,pm všechny prvky ve sjednocení Mi U • • • U Mfc. Definujeme si bipartitní graf G na množině vrcholů {1,2,...,A;} U {pi,... ,pm}, který je tvořen hranami {i,Pj} pro všechny dvojice pro které pj G Mi. Pak platí:
Tvrzení 11.13. Množiny M1;...,M\. maji systém různých reprezentantů právě tehdy, když v grafu G existuje párování pokrývající všechny vrcholy {1,2,... ,k}.
Důkaz: Nechť (xi,..., Xk) je systém různých reprezentantů množin Mi,..., Mk- Pak M = {{i,Xi} : i = 1,..., k} je požadované párování v G. Naopak párování pokrývající všechny vrcholy {1,2,... ,k} v G přímo určuje jednoho reprezentanta každé množiny a tito reprezentanti jsou různí, neboť žádné dvě hrany párování nesdílejí koncový vrchol.
□
97
Poznámka: Pro nalezení nej většího párování v bipartitním grafu existují rychlé postupy (algoritmy), související s tzv. toky v sítích. Tyto postupy se také dají využít (podle uvedeného tvrzení) k hledání systémů různých reprezentantů.
11.4   Příklady použití grafů
Závěrem si v našem studijním textu nastíníme některé základní motivace pro zavedení a použití grafů při popisu a řešení problémů například v informatice.
Příklad 11.14. Ukázky některých problémů „ze života" popsatelných grafy. Podotýkáme, že tyto ukázky jsou často velmi zjednodušené (pro jejich lepší přístupnost širokému okruhu čtenářů), ale to neubírá jejich motivačnímu potenciálu.
• Vyjádření mezilidských vztahů - „mají se rádi", „kamarádí se", „nesnesou jeden druhého", apod:
Zde jednotlivé osoby tvoří vrcholy grafu a vztahy jsou hranami (často neorientované, ale i orientace je přípustná). Všimněme si coby zajímavosti, jak tento model přirozeně preferuje „párový" pohled na vztahy - hrany přece spojují jen dvojice vrcholů. Třebaže například vztah „kamarádí se" může být obecně platný pro větší skupinky lidí než dvojice, stejně se obvykle vyjadřuje klikou v grafu (každí dva v našem družstvu jsou dobří kamarádi...). Tato obecně pojímaná tendence vyjadřovat i složitější vztahy těmi párovými je vodou na mlýn použití teorie grafů jako téměř univerzálního vyjadřovacího prostředku v podobných případech.
Na druhou stranu i teorie grafů disponuje pojmem tzv. hypergrafu umožňujícího použití hran libovolné arity (počtu koncových vrcholů), ale rozsah výskytu hypergrafu v teorii i aplikacích je oproti grafům vskutku zanedbatelný.
• Vyjádření závislostí mezi objekty nebo procesy:
Představme si situace, ve kterých jednotlivé entity (modelované jako vrcholy) závisí na výstupech jiných entit a naopak poskytují výstupy další entitám. Typickým příkladem mohou být závislosti jednotlivých kroků výrobního nebo rozhodovacího procesu. Ty pak vedou k definici orientovaného grafu na dané množině vrcholů/entit, tj. použití hran „se šipkami". Všimněme si, že závislosti často bývají časového charakteru (přičemž směr závislosti je implicitně jasný) a pak je nezbytnou doplňkovou podmínkou vyloučení výskytu orientovaných cyklů v modelovém grafu. Na druhou stranu existují i situace, kdy cyklické závislosti jsou dovoleny a mají svůj význam.
Pro ještě jednu ukázku závislostí z běžného života informatika se podíváme na správu balíčků softwaru například v Linuxových distribucích. V tom případě jsou jednotlivé balíčky vrcholy grafu, jejich vyžadované závislosti popisují odchozí hrany a jejich poskytované vlastnosti jsou příchozími hranami grafu závislostí. Korektní instalace zvoleného balíčku pak řeší problém zahrnutí všech dalších vrcholů „dosažitelných" ze zvoleného. Vše je navíc komplikováno správou verzí balíčků a případným vzájemným vyloučením některých dvojic balíčků, ale to už je mimo rámec našeho úvodního slova.
• Modelování technických či dopravních sítí grafy:
V takových případech bývají vrcholy grafu jednotlivá technická zařízení jako třeba rozvodny, routery, křižovatky a podobně, kdežto hrany jsou tvořeny spojnicemi/vedením mezi vrcholy. Často se zde setkáváme s orientovanými grafy a obecně multigrafy.
98
• Vizualizace vztahů a závislostí pro lidského pozorovatele:
Nejen při řešení cvičných příkladů v naší učebnici, ale i v mnoha reálných aplikacích využívajících grafy jako modely, je velmi potřebné tyto grafy vizualizovat (tj. hezky nakreslit) pro lidského pozorovatele. Jedná se obecně o poměrně obtížný úkol, který přesahuje hranice našeho textu. ^
Zpracování grafu počítačem
Mějme jednoduchý graf G na n vrcholech a značme vrcholy jednoduše čísly V(G) = {0,1,..., n — 1}. Pro počítačovou implementaci grafu G se nabízejí dva základní způsoby, které budeme implicitně využívat i v některých algoritmech následujících lekcí.
• Implementace matici sousednosti G, tj. dvourozměrným polem, ve kterém hodnota G[i,j] = 1 reprezentuje hranu mezi vrcholy i a j.
• Implementace výčtem sousedů, tj. systémem množin, který každému vrcholu i grafu udává seznam jeho sousedů. Všimněte si, že pořadí sousedů může být jakékoliv.
Poznámka: Dávejte si pozor na symetrii hran v implementaci! To znamená, že pokud uložíte hranu G[i,j] = 1, tak musíte zároveň uložit i hranu G[j, i] = 1, jinak se dočkáte v algoritmech nepříjemných překvapení. Totéž se týká i seznamů sousedů, ať už jsou implementovány jakkoliv.
Komentář: Implementace maticí sousednosti je hezká svou jednoduchostí, avšak velmi nehezká svou paměťovou náročností. Druhá možnost se pak mnohem lépe hodí pro grafy s relativně malým počtem hran, což nastává ve většině praktických aplikací. (Navíc je implementace výčtem sousedů vhodná i pro multigrafy.) Ke grafům lze do zvláštních složek přidat také ohodnocení vrcholů a hran libovolnými čísly či značkami...
Rozšiřující studium
JVáš kurz poskytuje jen skutečně minimalistický úvod do informatický zaměřené teorie grafů. Mnohem více se o matematické stránce teorie grafů můžete dozvědět samostudiem, třeba knihy Kapitoly z diskrétní matematiky autorů Jiřího Matouška a Jaroslava Nešetřila, či v pozdějším navazujícím kurzu MA010 na FI MU.
Vedle toho, jak již bylo předesláno, se s informatickou stránkou grafů potkáte velmi široce v prakticky všech kurzech návrhu algoritmů, třeba na FI MU hned v druhém semestru vIB002. Mimo jiné se tak brzy dozvíte o základních postupech prohledávání grafu do šířky a do hloubky, o efektivním nalézání souvislých a silných komponent, o základních algoritmech pro problém hledání nejkratší cesty v ohodnoceném grafu a podobně.
99
12   Nekonečné množiny, Zastavení algoritmu
Úvod
Hloubavého čtenáře může snadno napadnout kacířská myšlenka, proč se vlastně zabýváme dokazováním správnosti algoritmů a programů, když by to přece (snad?) mohl za nás dělat automaticky počítač samotný. Bohužel to však nejde a je hlavním cílem této lekce ukázat matematické důvody proč tomu tak je.
Konkrétně si dokážeme, že nelze algoritmicky rozhodnout, ani zda se daný algoritmus na svém vstupu zastaví nebo ne. Hlavními nástroji, které použijeme, budou nekonečné množiny a důkazová technika tzv. Cantorovy diagonály, která se ve velké míře používá právě v teoretické informatice. Touto lekcí se tak krátce vymaníme ze zajetí naivní teorie množin, která v této oblasti má své nepřekonatelné limity. (Pro zvídavé - obdobně, ale mnohem složitěji, lze dokázat že ani matematické důkazy nelze obecně algoritmicky konstruovat...)
Cíle
Zavedeme si ve zjednodušeném (a stále „poněkud naivním") pohledu nekonečné množiny a na nich techniku důkazu Cantorovou diagonálou. Pak tuto klíčovou důkazovou techniku teoretické informatiky využijeme k důkazu algoritmické neřešitelnosti problému zastavení.
12.1    O nekonečných množinách a kardinalitě
Zatímco v naivní teorii jsme si velikost konečné množiny definovali jednoduše jako počet jejích prvků vyjádřený přirozeným číslem, pro nekonečné množiny je situace obtížná a mnohem méně intuitivní. Co nám třeba brání zavést pro velikost nekonečné množiny symbol oo? Ponejvíce závažný fakt, že není „nekonečno" jako „nekonečno" (Věta 12.2)!
Právě proto si pro určení mohutnosti nekonečných množin musíme vypomoci následujícím příměrem: Velikosti dvou hromádek jablek dokážeme i bez počítání porovnat tak, že budeme z obou hromádek po řadě odebírat dvojice jablek (z každé jedno), až dokud první hromádka nezůstane prázdná - druhá hromádka pak je větší (nebo nejvýše rovna) té první.
Definice: Množina A je „nejvýše tak velkálí jako množina B, právě když existuje injek-tivní funkce / : A —>• B. Množiny A a, B jsou „stejně velkélí právě když mezi nimi existuje bijekce. V případech nekonečných množin pak místo "velikosti" mluvíme formálně o jejich
						
		•				
Komentář: Uvedená definice kardinality množin funguje korektně i pro nekonečné množiny:
* Například N a TL mají stejnou kardinalitu (jsou „stejně velké", tzv. spočetně nekonečné).
* Lze snadno ukázat, že i (Q je spočetně nekonečná, tj. existuje bijekce / : N —> (Q, stejně
100
* Existují ale i nekonečné množiny, které jsou „striktně větší" než libovolná spočetná množina (příkladem je R ve Větě 12.2).
* Později dokážeme, že existuje nekonečná posloupnost nekonečných množin, z nichž každá je striktně větší než všechny předchozí.
Pro porovnávání velikostí množin někdy s výhodou využijeme následující přirozené, ale nelehké tvrzení (bez důkazu):
Věta 12.1. Pro libovolné dvě množiny A, B (i nekonečné) platí, že pokud existuje injekce A —>• B a zároveň i injekce B —>• A, pak existuje bijekce mezi A a B.
Cantorova diagonála, aneb kolik je reálných čísel
Prvním klíčovým poznatkem ukazujícím na neintuitivní chování nekonečných množin je následující důkaz, který dal historicky vzniknout metodě tzv. Cantorovy diagonály.
Věta 12.2. Neexistuje žádné surjektivní zobrazení g : N —y R.
Důsledek 12.3. Neexistuje žádné injektivní (tudíž ani bijektivní) zobrazení h : R —y N. Neformálně řečeno, reálnych čísel je striktně více než všech přirozených.
Důkaz (Věty 12.2 sporem): Nechť takové g existuje a pro zjednodušení se omezme jen na funkční hodnoty v intervalu (0,1) tj. ponechme z každé funkční hodnoty jen její nezápornou necelou část. Podle hodnot zobrazení g si takto můžeme „uspořádat"
101
dekadické zápisy všech reálných čísel v intervalu (0,1) po řádcích do tabulky:
9(0)
9(1) 9(2) 9(3) í? (4)
0. 15427578325 0. 4 0. 1 0. 3 0. 9
Nyní sestrojíme číslo a E (0,1) následovně; jeho i-tá číslice za desetinnou čárkou bude 1, pokud v i-tém řádku tabulky na diagonále není 1, jinak to bude 2. V našem příkladě a = 0.21211...
Kde se naše číslo a v tabulce nachází? Nezapomeňme, že g byla surjektivní, takže a někde musí být. Konstrukce však ukazuje, že a se od každého čísla v tabulce liší na aspoň jednom desetinném místě, a to je spor. (Až na drobný technický detail s rozvojem ... 9, který pro dosažení jednoznačnosti zápisu v naší tabulce preferujeme nad konečným rozvojem takového čísla. Neboli místo 0.125 budeme do tabulky psát 0.1249.) □
12.2    „Naivní" množinové paradoxy
Analogickým způsobem k Větě 12.2 lze dokázat následovné zobecnění vyjadřující se o jakékoliv množině a jí přiřazené striktně větší množině.
Věta 12.4. Nechi M je libovolná množina. Pak existuje injektivní zobrazení f : M —>• 2M, ale neexistuje žádné bijektivní zobrazení g : M —y 2M.
Důkaz: Dokážeme nejprve existenci /. Stačí ale položit f(x) = {x} pro každé x G M. Pak / : M —y 2M je zjevně injektivní.
Neexistenci g dokážeme sporem. Předpokládejme tedy naopak, že existuje bijekce g : M —>• 2M. Uvažme množinu K C M definovanou takto:
Jelikož g je bijektivní a K E 2M, musí existovat y E M takové, že g (y) = K. Nyní rozlišíme dvě možnosti:
- y E g(y). Tj. y E K. Pak ale y E1 g(y) z definice K, což je spor.
- y E1 g(y). To podle definice K znamená, že y E K, tj. y E g (y), spor. ^
Komentář: Dvě navazující poznámky. • Technika použitá v důkazech Vět 12.2 a 12.4 se nazývá Cantorova diagonální metoda, nebo také zkráceně diagonalizace.
Konstrukci množiny K lze znázornit pomocí následující tabulky:
K = {x E M \ x E~ g(x)}.
a     b     c d
g (a}
g(b)
9(c) g (d)
102
Symbol y7 resp. — říká, že prvek uvedený v záhlaví sloupce patří resp. nepatří do množiny uvedené v záhlaví řádku. Tedy např. d E g (b) a a 0 g (d). Množina K poté obsahuje ty diagonálni prvky označené —, tj. „převrací" význam diagonály.
• Z toho, že nekonečna mohou být „různě velká", lze lehce odvodit řadu dalších faktů. V jistém smyslu je např. množina všech problémů větší než množina všech algoritmů (obě množiny jsou nekonečné), a proto nutně existují problémy, které nejsou algoritmicky řešitelné.
Cantorův paradox
Naivní teorie množin, jak jsme si ji uvedli i v tomto předmětu, trpí mnoha neduhy a nepřesnostmi, které vyplynou na povrch především při „neopatrné manipulaci" s nekonečnými množinami. Abychom se těmto „neopatrnostem" vyhnuli bez přílišné formalizace, dva základní z těchto paradoxů si nyní ukážeme.
Příklad 12.5. Uvážíme-li nyní nekonečnou posloupnost množin
A1,A2,A3,A4,---
kde A\ = N a Ai+i = 2Ai pro každé i G N, je vidět, že všechny množiny jsou nekonečné a každá je striktně větší než libovolná předchozí.
Kde však v tomto řazení kardinalit bude „množina všech množin"? Na tuto otázku, jak sami asi cítíte, nelze podat odpověď. Co to však znamená? □
* Takto se koncem 19. století objevil první Cantorův paradox nově vznikající teorie množin.
* Dnešní moderní vysvětlení paradoxu je jednoduché, prostě „množinu všech množin" nelze definovat, taková v matematice neexistuje.
Brzy se však ukázalo, že je ještě mnohem hůř... Russelův paradox
Fakt: Není pravda, že každý soubor prvků lze považovat za množinu.
* Nechť X = {M | M je množina taková, že M £ M}. Platí X G X ?
- Ano. Tj. X G X. Pak ale X splňuje X g X.
- Ne. Pak X splňuje vlastnost X ^ X, tedy X je prvkem X, tj., X e X.
* Obě možné odpovědi vedou ke sporu. X tedy nelze prohlásit za množinu. Jak je ale něco takového vůbec možné?
Komentář: Vidíte u Russelova paradoxu podobnost přístupu s Cantorovou diagonalizací? Russelův paradox se objevil začátkem 20. století a jeho „jednoduchost" zasahující úplné základy matematiky (teorie množin) si vynutila hledání seriózního rozřešení a rozvoj formální matematické logiky.
Pro ilustraci tohoto paradoxu, slyšeli jste už, že „v malém městečku žije holič, který holí právě ty muže městečka, kteří se sami neholí"? Zmíněné paradoxy naivní teorie množin zatím v tomto kurzu nerozřešíme, ale zapamatujeme si, že většina matematických a informatických disciplín vystačí s „intuitivně bezpečnými" množinami.
103
12.3   Algoritmická neřešitelnost problému zastavení
Výše vysvětlené myšlenky diagonalizace a principů základních paradoxů naivní teorie množin sice vypadají „velmi matematicky". Přesto je však téměř beze změny lze aplikovat i na bytostně informatickou otázku, zda lze algoritmicky poznat, pro které vstupy se daný program vůbec zastaví. Negativní odpověď na tuto otázku je jedním z fundamentálních výsledků informatiky a přitom má překvapivě krátký a čistý důkaz diagonalizací.
Fakt: Uvědomme si (velmi neformálně) několik základních myšlenek.
* Program v každém programovacím jazyce je konečná posloupnost složená z konečně mnoha symbolů (písmena, číslice, mezery, speciální znaky, apod.) Nechť E je množina všech těchto symbolů. Množina všech programů je tedy jistě podmnožinou množiny UieN^1' která je spočetně nekonečná. Existuje tedy bijekce / mezi množinou N a množinou všech programů. Pro každé j G N označme symbolem Pj program f(j). Pro každý program P tedy existuje i G N takové, že P = Pí.
* Každý možný vstup každého možného programu lze zapsat jako konečnou posloupnost symbolů z konečné množiny T. Množina všech možných vstupů je tedy spočetně nekonečná a existuje bijekce g mezi množinou N a množinou všech vstupů. Pro každé j G N označme symbolem Vj vstup g(j).
* Předpokládejme, že existuje program H alt, který pro dané i, j G N zastaví s výstupem ano/ne podle toho, zda Pí pro vstup Vj zastaví, nebo ne.
* Tento předpoklad dále dovedeme ke sporu dokazujícímu, že problém zastavení nemá algoritmické řešení.
Věta 12.6. Neexistuje program Halt, který by pro vstup (Pi} Vj) správně rozhodl, zda se program Pí zastaví na vstupu Vj.
Důkaz: Sporem uvažme program Diag s následujícím kódem: input k;
if   iJa/r(k,k) =ano   then   while true do ; done
(Program Diag(k) má na rozdíl od Halt jen jeden vstup k, což bude důležité.) Fungování programu Diag lze znázornit za pomocí následující tabulky:
	.Po Pi	P2  p3 ...
		- v •••
v1		- v •••
v2	— ^4	
v3		
Symbol y/ resp. — říká, že program uvedený v záhlaví sloupce zastaví resp. nezastaví pro vstup uvedený v záhlaví řádku. Program Diag „zneguje" diagonálu této tabulky.
Podle našeho předpokladu (Diag je program a posloupnost Pj zahrnuje všechny programy) existuje j G N takové, že Diag = Pj. Zastaví Diag pro vstup Vj?
- Ano. Podle kódu Diag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví.
104
- Ne. Podle kódu Díag pak ale if test neuspěje, a tento program tedy zastaví. Předpoklad existence programu Halt tedy vede ke sporu. □
Komentář: Otázkami algoritmické (ne)řešitelnosti problémů se zabývá teorie vyčíslitelnosti. Metoda diagonalizace se také často využívá v teorii složitosti k důkazu toho, že dané dvě složitostní třídy jsou různé.
Rozšiřující studium
Látka této lekce zabrousila až do teoretických hlubin matematické logiky a teorie množin. Další studium v těchto oblastech se dá očekávat hlavně u studentů specifícky zaměřených teoretickým směrem (a mířících spíše do akademické než aplikační sféry), zajímajících se o matematiku samotnou nebo o teorii vyčíslitelnosti. Proto také uvedené pokročilé poznatky Lekce 12 nebudou vyžadovány u zkoušky tohoto předmětu.
105
Závěrem
Gratulujeme všem, kteří se naším nelehkým učebním textem „prokousali" až sem, a přejeme mnoho úspěchů v dalším studiu informatiky.
Nakonec znovu připomínáme, že nedílnou součástí našeho studijního textu je Interaktivní osnova předmětu IB000 v IS MU a v ní přiložené online odpovědníky určené k procvičování přednesené látky.
http://is.muni.cz/el/1433/podzim2024/IB000/index.qwarp
106