Fakulta Informatiky Masarykova Univerzita Úvod do Informatiky (FI: IBOOO) Doc. RNDr. Petr Hliněný, Ph.D. hlineny@f i.muni.cz 22. listopadu 2011 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 IB000 na FI MU od roku 2006, navazující na původní přednáškové slidy prof. Antonína Kučery z roku 2005. Verze 1.32 (2011) © 2006-2011 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 Úvodu do 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 navazuje na původní slidy předmětu IB000 sepsané A. Kučerou do roku 2005, je však výrazně rozšířený o volný text a komentáře. 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. 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. Interaktivní osnova http://is.muni.cz/el/1433/podzim2011/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č texto text obsahuje jen velmi málo příkladů k probírané látce; od každého studenta očekáváme, že si látku bude procvičovat online na zmíněných odpovědnících, obsahujících až tisíce příkladů desítek typů. (K praktickému pochopení přednesených znalostí i k jejich budoucím aplikacím je takové procvičení nezbytné!) V návaznosti na tyto odpovědníky doporučujeme studentům diskutovat o probírané látce a svých (ne)úspěších s cvičícími předmětu na předmětovém diskuzním fóru v IS. ii Obsah 0.1 O tomto textu a jeho studiu......................... ii 1 Základní formalismy: Důkaz a Algoritmus 1 1.1 Úvod do matematického dokazování..................... 1 1.2 Význam matematických vět......................... 2 1.3 Struktura matematických vět a důkazů................... 3 1.4 Formální popis algoritmu........................... 5 2 Důkazové techniky, Indukce 8 2.1 Přehled základních důkazových technik................... 8 2.2 Věty typu „tehdy a jen tehdy"........................ 10 2.3 Matematická indukce............................. 10 2.4 Komentáře k matematické indukci...................... 12 3 Množiny a jejich Prvky 15 3.1 Pojem množiny................................ 15 3.2 Množinové operace.............................. 16 3.3 Porovnávání a určení množin ........................ 19 3.4 Posloupnosti a rekurentní vztahy ...................... 20 4 Relace a funkce, Ekvivalence 23 4.1 Relace a funkce nad množinami....................... 23 4.2 Reprezentace konečných relací........................ 25 4.3 Vlastnosti binárních relací.......................... 26 4.4 Relace ekvivalence .............................. 27 4.5 Rozklady a jejich vztah k ekvivalencím................... 28 5 Uspořádané množiny, Uzávěry 31 5.1 Uspořádání a uspořádané množiny ..................... 31 5.2 Další pojmy uspořádaných množin ..................... 33 5.3 Hasseovské diagramy............................. 35 5.4 Uzávěry relací................................. 36 6 Skládání relací a funkcí 38 6.1 Vlastnosti funkcí............................... 38 6.2 Inverzní relace a skládání relací....................... 39 6.3 Skládání relací „v praxi"........................... 40 6.4 Skládání funkcí, permutace.......................... 42 6.5 Induktivní definice množin a funkcí..................... 44 7 Jemný úvod do Logiky 47 7.1 Výroky v přirozené podobě.......................... 47 7.2 Formální výroková logika........................... 48 7.3 Jak správně znegovat formuli?........................ 50 7.4 Predikátová logika, kvantifikace....................... 52 iii 8 Dokazování vlastností algoritmů 55 8.1 Jednoduché indukční dokazování ...................... 55 8.2 Algoritmy pro relace............................. 57 8.3 Dokazování konečnosti algoritmu ...................... 58 8.4 Zajímavé algoritmy aritmetiky........................ 59 9 Jednoduchý deklarativní jazyk 61 9.1 Popis jednoduchého deklarativního jazyka ................. 61 9.2 Formalizace pojmu „výpočet"........................ 63 9.3 Příklady výpočtů a důkazů.......................... 65 10 Důkazové postupy pro algoritmy 68 10.1 Technika „fixace parametru"......................... 68 10.2 Technika „indukce k součtu parametrů"................... 68 10.3 Technika „zesílení dokazovaného tvrzení".................. 70 10.4 Dva dobře známé školní algoritmy...................... 71 11 Nekonečné množiny a Zastavení algoritmu 74 11.1 O nekonečných množinách a kardinalitě................... 74 11.2 „Naivní" množinové paradoxy........................ 75 11.3 Algoritmická neřešitelnost problému zastavení............... 77 12 Délka výpočtu algoritmu 79 12.1 O významu délky výpočtu algoritmu.................... 79 12.2 Asymptotické značení a odhady funkcí................... 80 12.3 Rekurentní odhady.............................. 8f i v 1 Základní formalismy: Důkaz a Algoritmus Úvod Začněme 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 matematicko-teoretické (formální) základy moderní informatiky Právě odborný nadhled nad celou informatikou včetně nezbytné formální teorie nejspíše odliší „řadového programátora", kterých jsou dnes spousty i bez VS vzdělání, od skutečného a mnohem lépe placeného počítačového experta. A na tomto místě nyní přichází náš předmět Úvod do Informatiky, který (i přes svůj nepříliš obsažný název) vás právě na studium těchto formálních základů moderní informatiky připraví. Tak se do toho studia s chutí dejte... Cíle Prvním cílem této lekce je formálně rozebrat struktury matematických tvrzení (vět) a jejich formálních důkazů. V druhém sledu se naučíme obdobným způsobem formálně přesně zapisovat postupy, čili algoritmy. 1.1 Úvod do matematického dokazování Matematika (a tudíž i teoretická informatika jako její součást) se vyznačuje velmi přísnými formálními požadavky na korektnost argumentace. Takto korektně postavená argumentace vede 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.1. 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ď * 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 této a příští lekci. Nyní si jen celou problematiku uvedeme názornými příklady. Příklad 1.2. 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é. 1 Poznámka pro připomenutí: - Sudé číslo je celé číslo dělitelné 2, tj. tvaru 2k. - Liché číslo je celé číslo nedělitelné 2, tj. tvaru 2k + 1. 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 + 1 + 1 1,2) a komutativita sčítání (axiom) 4) x = 2(k + /) + 2 • 1 3) a distributivnost násobení 5) x = 2(k + / + 1) 4) a opět distributivnost násobení 6) x = 2m, m celé 5) a m = k + / + 1 je celé číslo (axiom) Příklad 1.3. 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 = =x + ^ =y- 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. Jak čtenář vidí, tento strohý formální zápis (i když matematicky kompletní) si zaslouží aspoň 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. Konkrétně je zde velmi vhodné poznamenat, že klíčový krok (1) popisuje námi vymyšlenou 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í formulace Věty z Příkladu 1.3 mohou znít: - Pro každé x, y G Q, kde x < y, existuje z G Q takové, že x < z < y. - Množina racionálních čísel je hustá. 1.2 Význam matematických vět První krok formálního důkazu je uvědomit si, co říká věta, která se má dokázat; tedy co je předpoklad a co závěr dokazovaného tvrzení. Pravdivost takového tvrzení pak je třeba 2 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í. Komentář: Příklady běžné formulace matematických vět: * Konečná množina má konečně mnoho podmnožin. * sin2(a) + cos2(a) = 1. * Graf je rovinný, jestliže neobsahuje podrozdělení K5 nebo 1^3,3. Co přesně nám uvedené matematické věty říkají? Č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í. O pravdivosti implikace Všimněte si také, jaký je správný logický význam matematického tvrzení vysloveného touto formou implikace („jestliže ..., pak ... "). Především, pokud předpoklady nejsou splněny nebo jsou sporné, tak celé tvrzení je platné bez ohledu na pravdivost závěru! Příklad 1.4. 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.5. 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í v druhé řadě lavic. Opět je třeba se hluboce zamyslet nad významem předpokladů a závěru, ale ten-tkrát není situace předpokladů tak triviálně sporná, jako v Příkladu 1.4. Kdy tedy nastávají oba předpoklady 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. Důkaz je hotov. □ 1.3 Struktura matematických vět a důkazů Jak „moc formálníCÍ mají správné matematické důkazy vlastně být? 3 • Záleží na tom, 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. 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 vyžaduje od vás přímo „umělecké" vlohy. Přesto se jí alespoň trochu musíte přiučit. Dokazovat či vyvracet tvrzení? Představme si, že našim úkolem je rozhodnout platnost matematického tvrzení. Jak matematicky správně zdůvodníme svou odpověď? • Záleží na odpovědi samotné... Pokud je to ANO, 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 pak je matematická věta T, která tvrdí nějaký závěr pro širokou oblast vstupních možností. Potom platí následující: • Pokud T je pravdivá, nezbývá než podat vyčerpávající důkaz platnosti pro všechny vstupy. • Avšak pokud T je nepravdivá, stačí „uhodnout" vhodný vstupní protipříklad a jen pro něj dokázat, že závěr tvrzení není platný. Komentář: A nyní se znovu vraťte na začátek Oddílu 1.2 a srovnejte si výše uvedené se základními poznatky o významu matematických vět... Příklad 1.6. 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 z něj vyplývá? 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 x = — | (není nutno zdůvodňovat, jak jsme jej „uhodli"!) a následně dokázat úpravou x2+ 3x + 2 = (x + l).(x + 2) = (-| + l).(-|+2) = (-!)•(+!) = ~<0. Dané tvrzení není platné. □ Konstruktivní a existenční důkazy Z hlediska praktické využitelnosti je potřeba rozlišit tyto dvě kategorie důkazů (třebaže z formálně-matematického pohledu mezi nimi kvalitativní rozdíl není). • Důkaz Věty 1.3 je konstruktivní. Dokázali jsme nejen, že číslo z existuje, ale podali jsme také návod, jak ho pro dané x a y sestrojit. 4 • Existenční důkaz je takový, kde se prokáže existence nějakého objektu bez toho, aby byl podán návod na jeho konstrukci. Příklad 1.7. čistě existenčního důkazu. Věta. Existuje program, který vypíše na obrazovku čísla tažená ve 45. tahu sportky v roce 2011. Důkaz: Existuje pouze konečně mnoho možných výsledků losování 45. tahu sportky v roce 2011. 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ě ten, který vypíše právě ten výsledek, který bude ve 45. tahu sportky v roce 2011 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 (2011: tedy dokud nám to pan Husák všechno nepokazí, že?). Fakt. Pro informatické i další aplikované disciplíny je důležitá konstruktivnost důkazů vět, které se zde objevují. V matematice ale jsou mnohé příklady užitečných a nenahraditelných existenčních důkazů, třeba tzv. pravděpodobnostní důkazy. Příklad 1.8. „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á množ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 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 Ti2 2l-n + • • • + 2l-n =-- ->0. s-v-' 2n_1 Jelikož je toto číslo (pravděpodobnost) pro n > 7 menší než 1, bude existovat obarvení bez jednobarevných zvolených podmnožin. □ 1.4 Formální popis algoritmu Nakonec si položme otázku, co je vlastně algoritmus? Když se na tím zamyslíte, asi zjistíte, že to není tak jednoduché přesně říci. Dokonce je to natolik obtížná otázka, že si zde podáme jen zjednodušenou odpověď. Poznámka: Za definici algoritmu je obecně přijímána tzv. Church-Turingova teze tvrdící, že všechny algoritmy lze „simulovat" na Turingově stroji. Jedná se sice o přesnou, ale značně nepraktickou definici. Mimo Tůringova stroje existují i jiné matematické modely výpočtů, jako třeba stroj RAM, který je abstrakcí skutečného strojového kódu, nebo také třeba Definice 9.2 v našem textu. 5 Konvence 1.9. Zjednodušeně zde algoritmem rozumíme konečnou posloupnost elementárních výpočetních kroků, ve které každý další krok vhodně1 využívá (neboli závisí na) vstupní údaje či hodnoty vypočtené v předchozích krocích. Tuto závislost přitom pojímáme zcela obecně nejen na operandy, ale i na vykonávané instrukce v krocích. Pro zápis algoritmu a jeho zpřehlednění a zkrácení využíváme řídící konstrukce -podmíněná větvení a cykly. Komentář: Vidíte, jak blízké si jsou konstruktivní matematické důkazy a algoritmy v našem pojetí? Jedná se nakonec o jeden ze záměrů našeho přístupu... Příklad 1.10. Zápis algoritmu pro výpočet průměru z daného pole a[] s n prvky. Algoritmus. • Inicializujeme sum 0 : • postupně pro i=0,l,2, . . . ,n-l provedeme * sum sum+a[i] : • vypíšeme podíl (sum/n) . □ Ve „vyšší úrovni" formálnosti (s jasnějším vyznačením řídících struktur algoritmu) se totéž dá zapsat jako: Algoritmus 1.11. Průměr z daného pole a[] s n prvky. sum 0; foreach i 0,1,2,...,n-l do sum sum+a[i]; done res sum/n; output res; Symbolický zápis algoritmů Značení. Pro potřeby symbolického formálního zápisu algoritmů v předmětu FI: IB000 si zavedeme následovnou konvenci: * Proměnné nebudeme deklarovat ani typovat, pole odlišíme závorkami p[]. * Přiřazení hodnoty zapisujeme a^—b, případně a := b, ale nikdy ne a=b. * Jako elementární operace je možné použít jakékoliv aritmetické výrazy v běžném matematickém zápise. Rozsahem a přesností čísel se zde nezabýváme. * Podmíněné větvení uvedeme klíčovými slovy if ... then . . . else ... f i , kde eis e větev lze vynechat (a někdy, na jednom řádku, i f i). * Pevný cyklus uvedeme klíčovými slovy foreach ... do ... done, kde část za foreach musí obsahovat předem danou množinu hodnot pro přiřazování do řídící proměnné. 1Zvídaví studenti si mohou na tomto místě uvědomit, že ve slůvku „vhodně" se skrývá celá hloubka Church-Turingovy teze. V žádném případě tak nelze uvedené obracet, že by každá posloupnost kroků atd ... byla algoritmem ve smyslu této teze (viz také Lekce 11). 6 * Podmíněný cyklus uvedeme klíčovými slovy while ... do ... done . Zde se může za while vyskytovat jakákoliv logická podmínka. * V zápise používáme jasné odsazování (zleva) podle úrovně zanoření řídících struktur (což jsou if, foreach, while). * Pokud je to dostatečně jasné, elementární operace nebo podmínky můžeme i ve formálním zápise popsat běžným jazykem. Malé srovnání závěrem Jak to tedy je s vhodnou a únosnou mírou formalizace u matematických důkazů i u zápisu algoritmů? Odpověď může naznačit tato tabulka: zcela formální běžná úroveň matematika formální rozepsání všech elem. kroků (Příklad 1.2) strukturovaný a matem, přesný text v běžném jazyce algoritmy rozepsání všech elem. kroků ve výpočetním modelu strukturovaný rozpis kroků (Algoritmus 1.11), i s využitím běžného jazyka programování assembler / strojový kód (kde se s ním dnes běžně setkáte?) „vyšší" (strukturované) programovací jazyky, například Java Komentář: Pochopitelně se ve všech třech bodech obvykle držíme druhého přístupu, tedy běžné úrovně formality, pokud si specifické podmínky výslovně nevyžadují přístup nejvyšší formality... 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 asi i ve všech dalších matematických předmětech, které zároveň studujete či budete studovat, a principy budou stále stejné. Taktéž schopnost formálně rozepisovat a správně chápat algoritmy je nezbytná pro celé příští studium informatiky. Blíže se formálním zápisům algoritmů a jejich dokazování budeme věnovat i v Lekcích 8,9,10. 7 2 Důkazové techniky, Indukce Úvod Náš hlubší úvod do matematických formalismů pro informatiku pokračujeme základním přehledem technik matematických důkazů. Třebaže matematické dokazování a příslušné techniky mohou někomu připadat neprůhledné (a 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šek), že vlastně vše, 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 „naučit se navrhovat správné algoritmy a být si i svými programy naprosto jisti". Z důkazových postupů je pro nás informatiky asi nej důležitější technika důkazů matematickou indukcí, která je svou podstatou velmi blízká počítačovým programům (coby iterace cyklů). V dalším výkladu budeme indukci hojně využívat, především v Lekcích 8 a 10. 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 pochopit. (Pro vysvětlení, z Lekce 1 víme, že matematický důkaz má „jednotnou formu" Deňnice 1.1, ale nyní se věnujeme takříkajíc šablonám, podle nichž takový korektní důkaz sestavíme.) 2.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í nalézt 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í.) Tyto techniky si v bodech shrneme zde: • Přímé odvozeni. To je způsob, o kterém jsme se dosud bavili. Postupujeme přímo od předpokladů k závěru, ale sami poznáte, že taková „přímá" cesta je obtížně k nalezení. • Kontmpozíce (také 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ů." • 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í opak jednoho z předpokladů (nebo platí jiné zjevně nepravdivé tvrzení)." • Matematická indukce. Pokročilá technika, kterou zde popíšeme později... 8 Tyto techniky jsou asi nejlépe ilustrovány následovnými příklady důkazů. Příklad důkazu kontrapozicí Definice: Prvočíslo p > 1 nemá jiné dělitele než lap. Příklad 2.1. na důkaz kontrapozicí (obrácením). Věta. Jestliže p je prvočíslo větší než 2, pak p je liché. Důkaz: Obráceného tvrzení - budeme tedy dokazovat, že je-li p sudé, pak p buď 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 dvě možnosti: • k < 1. Pak p = 2k 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ěr komplikované tvrzení tvaru „z toho, že z A a B plyne C, vyplývá, že z A nebo C plyne A a Bíl. není pouhou intuicí snadné zjistit, co je vlastně jeho negací. Jak uvidíme v pozdějších lekcích, užitím jednoduché induktivní metody lze podobná tvrzení negovat zcela mechanicky. Příklady důkazu sporem Příklad 2.2. Jiný přístup k Důkazu 2.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í opak jednoho z předpokladů, nebo platí jiné zjevně nepravdivé tvrzení." odvodíme k některému předpokladu jeho spor, nebo případně jiné tvrzení, které odporuje všeobecně přijatým faktů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 2.3. Věta. Číslo y/2 není racionální. Důkaz sporem: Nechť tedy \f2 je racionální, tj. nechť existují nesoudělná celá kladná čísla r, s taková, že \f2 = r/s. 9 - 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č?). - Jelikož r je dělitelné dvěma, jer2 dělitelné dokonce čtyřmi, tedy r2 = 4 • m pro nějaké 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 i s jsou dělitelné dvěma, jsou tedy soudělná a to je spor (s definicí racionálního čísla). □ Komentář: „Nevíte-li, jak nějakou větu dokázat, zkuste důkaz sporem... " 2.2 Věty typu „tehdy a jen tehdy" Uvažujme nyní (v matematice poměrně hojné) věty tvaru „Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy, platí-li tvrzení B." Příklady jiných formulací téže věty jsou: * 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. * Nechť platí předpoklady P. Pak tvrzení A platí právě tehdy když platí tvrzení B. Fakt: 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. 2.3 Matematická indukce Pokud se souhrnně podíváme na důkazové techniky v matematice, všimneme si, že matematická indukce je skoro „dvorní" důkazovou technikou diskrétní matematiky. To proto, že umožňuje pohodlně dokazovat i složitá tvrzení po jednotlivých (diskrétních) krocích od počátečního. Uvažme tedy větu ve tvaru: „Pro každé přirozené (celé) n > k0 platíT(n).u Zde k0 je nějaké pevné přir. číslo a T(n) je tvrzení parametrizované čís. 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 2.4. Princip matematické indukce říká, že k důkazu věty „Pro každé přirozené (celé) n > k$ platíT(n).u stačí ověřit platnost těchto dvou tvrzení: * T (ktý) (tzv. báze neboli základ indukce) 10 • Pro každé n > k0; jestliže platí T(n), (indukční předpoklad) pak platí také T(n + 1). (indukční krok) Formálně řečeno, matematická indukce je axiomem aritmetiky přirozených čísel. Poznámka: Pozor, v tomto předmětu počítáme 0 za přirozené číslo! 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 2.5. Velmi jednoduchá a přímočará indukce. Věta. Pro každé 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 n > 1: Nechť psn pravděpodobnost, že při hodu n kostkami bude výsledný součet sudý, a pln je pravděpodobnost lichého. Podle indukčního předpokladu Je Pn = Pn = \- Hoďme navíc (n + l)-ní kostkou. Podle toho, zda na ní padne liché nebo sudé číslo, je pravděpodobnost celkového sudého součtu rovna 3, 3 8 1 6Pn + 6Pn ~ 2 a stejně pro pravděpodobnost celkového lichého součtu. □ Příklad 2.6. Ukázka 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 stačí, že 0 přímek dělí rovinu na jednu část. (Všimněte si také, že 1 přímka dělí rovinu na dvě části, jen pro lepší pochopení důkazu.) Mějme nyní rovinu rozdělenou n přímkami na nejvýše |n(n+l) + l částí. Další, (n+1)-ní přímka je rozdělena průsečíky s předchozími přímkami na nejvýše n + 1 úseků a každý z nich oddělí novou část roviny. Celkem tedy bude rovina rozdělena našimi přímkami na nejvýše tento počet oblastí: 1 111 -n(n + l) + l + (n + 1) = -n(n + 1) + - • 2(n + 1) + 1 = -(n + l)(n + 2) + 1 □ Příklad 2.7. Další indukční důkaz rozepsaný v podrobných krocích. 11 Věta. Pro každé n > O platí Y^j=o J Důkaz indukcí vzhledem k n. n(n+l) * Báze: Musíme dokázat tvrzení T(0), což je v tomto případě rovnost V_\=Q j -Tato rovnost (zjevně) platí. * Indukční krok: Musíme dokázat následující tvrzení: Jestliže platí Yľj=oJ = '^X^ kde i > 0, pai piat/ ^*=g j = (t+1)fo+2), Předpokládejme tedy, že ^*=0J = a pokusme se dokázat, že pak také Y^jt^oJ = (j + l)(í + l + l) (Í + l)(í + 2) rp - , -—^- = —2— uz Plyne úpravou: E j = Eí+o+d = ^ + <« + i) = i(i + 1)t2"+1) = £±i^ i=o i=0 Podle principu matematické indukce je celý důkaz hotov. □ Poznámka: Výsledek Příkladu 2.7 je ukázkou tzv. sumačního vzorce pro posloupnost přirozených čísel. Jinou ukázkou je třeba vztah 1 + 3 H-----h (2n - 3) + (2n - 1) = 1 + (2n - 1) + 3 + (2n - 3) H----= 2n • ^ = n2, nebo 12+22H-----\-n2 = \n{n + l){2n + l) a 13+23H-----\-n3 = (1 + 2H-----hn)2 = in2(n + l)2. Odvozování a práce s jednoduchými sumačními vzorci by také měla náležet do výbavy schopného informatika, princip matematické indukce je zde klíčový. 2.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. * Pozor, občas je potřeba „zesílit" tvrzení T(n), aby indukční krok správně „fungoval". - Velkým problémem bohužel je, že není možno podat návod, jak vhodné „zesílení" nalézt (ani kdy jej vůbec hledat). Jedná se vlastně o pokusy a „hádání z křišťálové koule". * Č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 > k0 je indukční krok univerzálně platný... 12 Zesílení indukčního kroku Příklad 2.8. Když je nutno indukční krok zesílit... Věta. Pro každé n > 1 platí ,,111 1 s(n) =--1---1---1-----1--z-r < 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 s(n) < 1 je sám o sobě „příliš slabý" na to, aby bylo možno tvrdit s(n + 1) = s(n) + , ,, w < 1. \ ' / v / (n+l)(n+2) Neznamená to ještě, že by tvrzení nebylo platné, jen je potřeba náš indukční předpoklad zesílit. Budeme dokazovat Tvrzení. Pro každé přirozené n > 1 platí s(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: s(n + l) = s(n) + ---ŕ-r < 1 (n + l)(n + 2) ~ n + 1 (n + l)(n + 2) -(n + 2) + 1 _ x J_ (n + l)(n + 2) ' n+ 2 □ Rozšíření báze a předpokladu 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 jakýkoliv počet předpokládaných parametrů. - Můžeme dokonce předpokládat platnost tvrzení T(j) pro všechna j = k0, k0 + 1,..., n najednou a dokazovat T(n + 1). 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; použité rozšířené možnosti pouze zjednodušují formální zápis důkazu. Příklad 2.9. Když je nutno rozšířit bázi a indukční předpoklad... Věta. Nectí funkce f pro každé n > 0 splňuje vztah f(n + 2) = 2f(n + 1) — f(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 f(n + 2) = 2f(n + 1) — f(n) naznačuje, že bychom měli rozšířit indukční předpoklad (a krok) zhruba takto: 13 Pro každé n > 0; jestliže platí T (n); neboli f (n) = n + 1, a zároveň platíT (n + 1); f (n + 1) = n + 2, pak platí také T (n + 2); /(n + 2) = n + 3. 5a,ze indukce - pozor, zde už musíme ověřit dvě hodnoty /(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(n) i f(n + 1), pro ověření f(n + 2) = 2/(n + 1) - f{n) = 2-(n + l + l)-(n + l)=n + 3 = n + 2 + l. □ Komentář: Jak by tento důkaz měl být formulován v „tradiční" indukci? („Substitucí" nového tvrzení.) Závěrem malý „problém" Příklad 2.10. 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 = {K1}... ,Kn+1} je stádo o n + 1 koních. Dokážeme, že všichni koně mají stejnou barvu. Uvažme dvě IIlGIlŠl St cldcll - S' = {KuK2,...,Kn} - S" = {K2,..., Kn, Kn+i) 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 nezbytné ke studiu vysokoškolských matematických předmětů. Bez schopnosti přesného vyjadřování a chápání deňnic a vět se informatik neobejde, ani pokud se zaměřuje čistě aplikovaným směrem; viz třeba správné pochopení různých norem a speciň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 pokročilé praxe. 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 předmětu (a u zkoušek se objevíš 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áte setkáte v budoucím studiu. 14 3 Množiny a jejich Prvky Úvod V přehledu matematických formalismů informatiky se v této lekci zaměříme na základní datové typy matematiky, tj. na množiny, relace a funkce. Netradiční sousloví „datové typy" matematiky zde volíme záměrně, abychom zdůraznili jejich fundamentálnost pro výstavbu navazující 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 aspektech nekonečných množin se krátce zmíníme až v Lekci 11). 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, shrnutím běžných vlastností množin a uvedeme si příklady rekurzivně deňnovaných posloupností. 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}. Pozor, pojem prvku sám o sobě nemá matematický význam, svého významu totiž nabývá pouze ve spojení „být prvkem množiny". Prvky množiny tak může být cokoliv, mimo jiné i dalším množiny. Komentář: Relativitu významu vztahu „prvek-množina" si můžeme přiblížit třeba na vztahu „podřízený—nadřízený11 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ů. Značení množin a jejich prvků: • x G M „x je prvkem množiny M", • 0 je prázdná množina {}. Komentář: Některé vlastnosti vztahu „být prvkem" jsou * at{a,b}, a^{{a,b}}, {a, b} £ {{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} ^ {{a, &}}. Značení: Počet prvků (mohutnost) množiny A zapisujeme \A\. Komentář: |0| = 0, |{0}| = 1, \{a,b,c}\=3, \{{a, b}, c}\ = 2. 15 Jednoduché srovnání množin Vztah „být prvkem množiny" přirozeně nám podává i způsob porovnávání množin mezi sebou. Jedná se o klíčovou část teorie množin. Definice: Množina A je podmnožinou množiny B, právě když každý prvek 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 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ě 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. 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 bylo s ním spojeno několik paradoxů ukazujících, že naivní pohled na teorii množin pro nekonečné množiny nedostačuje. My se k problematice nekonečných množin, Kantorově větě a Russelově paradoxu vrátíme v závěru našeho předmětu v Lekci 11. 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. Definice 3.1. 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 E A a současně x G B} . AU B 16 * Příklady {a, b, c} U {a, d} = {a, b, c, d}, {a, b, c} H {a, d} = {a}. * Vždy platí „distributivita" A f] (B U C) = (A f] B) U (A f] C) a A U (B D C) = (AU B) (1 (AU C). Definice: Pro libovolný počet množin indexovaných pomocí I rozšířeně definujeme ^ Ai = {x | x E A-i pro nějaké i E 1} , ^ Ai = {x | x E Ai pro každé i E 1} . Komentář: Nechť Ai = {2 • i} pro každé i £ N. Pak UieNJe ninožina všech sudých přirozených čísel. Nechť Bi = {x \ x G N, x > i} pro každé i G N. Pak HíeN ^ = ^, Definice 3.2. Rozdíl \ a symetrický rozdíl A dvou množin A, B definujeme A\B = {x \ x E A a současně x ^ B} , AAB = (A\B) U (B\ A) . A\B V^ixC^ AAB * 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 n C) = (A \ B) U (A \ C) apod. Definice: Nechť A C M. Doplněk 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 = ÄnB a A(lB = ÄUB. (Viz Vennovy diagramy.) Uspořádané dvojice a 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á dvojíce (a,b) je zadána množinou {{a}, {a, b}}. Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d. Uměli byste toto sami dokázat přímo z podané definice? * Co je podle definice (a, a)l Je to (a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}. 17 Definice 3.3. Kartézský součin dvou množin A, B definujeme jako množinu všech uspořádaných dvojic ze složek z A a B A x B = {(a, b) | a G A, b G B} . * Příklady {a, b} x {a} = {(a, a), (b, 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á |Ax5| = |A|-|5|. Definice: Pro každé k G N, k > 0 definujeme uspořádanou k-tící (a1; • • • , a^) induktivně - (oi) = au - (a1; • • • , aj, <2j+i) = ((«1, • • • , Oj), Oj+i). Všimněte si, že definice používá tzv. rekurentní vztah, blíže viz Oddíl 3.4. 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 • • • x Ak = {{dl-, ■ ■ ■ , cbk) \ di £ Ai pro každé 1 < i < k} . * Například Z3 = ZxZxZ = k) \ k G Z}. * Co je A°7 {0}, neboť jediná uspořádaná 0-tice je právě prázdná 0. Poznámka: Podle uvedené definice není součin asociativní, tj. obecně nemusí platit, že A x (B x C) = (A x B) x 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. Potenční množina Definice 3.4. Potenční množina množiny A, neboli množina všech podmnožin, je definovaná vztahem 1A = {B | B C A} . * Platí například 2^ = {0, {a}, {b}, {a, &}}, * 2» = {0}, 2»W} = {0,{0},{{0}},{0,{0}}}, * 2Mx = {0; {(a> a)h {(a> b)h {(a> a); (a> Věta 3.5. Počet prvků potenční množiny splňuje \2A\ = 2'^'. Důkaz: Stručně indukcí podle \A\: Pro A = 0 platí |2^| = |{0}| = 1. Pro každý další prvek b G" A rozdělíme všechny podmnožiny A U {b} „napolovic" na ty neobsahující b a na ty obsahující b, tudíž 2A\ = 2\A\ + 1 = 2\Au{b}\ _ 2 i J 18 3.3 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.6. Pro každé dvě množiny A, B C M platí AU B = A C\ B. Důkaz v obou směrech rovnosti. . A U B C A n B: Pro x E M platí x E A U B, právě když x g AU B, neboli když zároveň x ^ A a x ^ B. To znamená x E A a zároveň x E B, z čehož vyplývá požadované x E A H B. • AU B D A C\ B: Pro x E M platí x G A H B, právě když x E A a, zároveň x E B, neboli když zároveň x ^ A a x ^ B. To znamená x AU B, z čehož vyplývá požadované x E A U B. Věta 3.7. Pro každé tři množiny A, B, C platí A\(BHC) = (A\B) \J(A\C). Důkaz (viz ilustrační obrázek). . A\(BílC) C (A \ B) \J(A\C): Je-li x E A \ (B H C), pak x E A a zároveň x (jL (B C\ C), neboli x £ B nebo x £ C. Pro první možnost máme x E (A\ B), pro druhou x E (A\C). . Naopak A \ (B n 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 £ B, z čehož plyne x E A a zároveň x £ {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 = (ci, C2,..., cn), kde q = 1 pro Xi E A a q = 0 jinak. Užitečnost této reprezentace je ilustrována také následovnými fakty. • Platí A = B právě když Xa = Xb- • Množinové operace jsou realizovány „bitovými funkcemi" sjednocení ~ OR, průnik ~ AND, symetrický rozdíl ~ XOR. 19 Princip inkluze a exkluze Tento důležitý a zajímavý kombinatorický princip je někdy také nazýván „princip zapojeni a vypojeni''. Používá se ke zjišťování počtů prvků množin s neprázdnými průniky. Věta 3.8. Počet prvků ve sjednoceni dvou čí tři množin spočítáme: \Al)B\ = \A\ + \B\ -\AC\B\ \AUBUC\ = \A\ + \B\ + \C\ -\Ar\B\ - \AnC\ - \BnC\ + \AnBnC\ 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 x ^ 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 £ 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.8 lze stejně tak využít k výpočtu počtu prvků v průniku množin... Příklad 3.9. Z 1000 televizí jich při první kontrole na výrobní lince má 5 vadnou obrazovku, 10 je poškrábaných a 12 má jinou vadu. Přitom 3 televize mají současně všechny tři vady a 4 jiné jsou poškrábané a mají jinou vadu. Kolik televizí je celkem vadných ? Řešení: Dosazením \A\ = 5, \B\ = 10, \C\ = 12, \A H B n C\ = 3, (zde pozor) \A n B\ = 3 + 0, \A n C\ = 3 + 0, \B n C\ = 3 + 4 do Věty 3.8 zjistíme výsledek 17. □ Poznámka. Jen stručně, bez důkazu a bližšího vysvětlení, si uvedeme obecnou formu principu inkluze a exkluze: E ( 0^7C{l,...,n} n * iei (Jeho znalost nebude v předmětu vyžadována. 3.4 Posloupnosti a rekurentní vztahy Uspořádané fc-tice (Oddíl 3.2) jsou také nazývány konečnými posloupnostmi délky k, neboli seřazeními prvků z dané neprázdné množiny hodnot (opakování prvků je povoleno). Tento pohled lze přirozeně zobecnit na nekonečné posloupnosti, avšak musíme sáhnout k trochu pokročilejším pojmům (viz také Oddíl 4.1 o funkcích): Definice: Nekonečná posloupnost p je funkcí z N do svého oboru hodnot H, neboli p : N —y H. Mimo „funkčního" zápisu p (n) často používáme „indexovou" formu zápisu funkční hodnoty pn. 20 Poznámka: Oborem hodnot posloupnosti obvykle bývá nějaká číselná množina, ale může to být i jakákoliv jiná množina. Také definiční obor posloupnosti může začínat od nuly nebo i od jedničky, jak je v aplikacích potřeba. • Příklady posloupností: * Po = 0, pi = 2,... ,pi = 2i,... je posloupnost sudých nezáporných čísel. * 3, 3.1, 3.14, 3.141,... je posloupnost postupných dekadických rozvojů tt. * 1, —1, 1, —1,... je posloupnost určená vztahem pi = (—1)*, i > 0. * Pokud chceme stejnou posloupnost 1, —1, 1, —1,... zadat jako qÍ7 i > 1, tak ji určíme vzorcem qri = (— • Posloupnost je rostoucí (či klesající), pokud pn+± > pn (pn+i < Pn) Pro všechna n. Rekurentní definice posloupnosti Slovem rekurentní označujeme takové definice (či popisy), které se v jistých bodech odvolávají samy na sebe. (Už jste se setkali s „rekurzí" při programování? A víte, co znamená?) Místo nepřehledných formálních definic si rekurentní vztahy uvedeme několika názornými ukázkami. • Zadáme-li posloupnost pn vztahy p0 = 1 a pn = 2pn_1 pro n > 0, pak platí pn = 2" pro všechna n. • Obdobně můžeme zadat posloupnost qn vztahy qľ = 1 a qn = qn-\ + n pro n > 1. Potom platí qn = ^n(n + 1) pro všechna n. Uměli byste toto dokázat indukcí? Viz Příklad 2.7. • Známá Fibonacciho posloupnost je zadaná vztahy f\ = f'2 = 1 a fn = fn-\ + fn-2 Pro n > 2. Příklad 3.10. Posloupnost f 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). Jak? Zkusíme vypočítat několik prvních hodnot a uvidíme... f{\) = 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 posloupnost 8 — 1, 16 — 1, 32 — 1, 64 — 1... ? Bystrému čtenáři se již asi podařilo uhodnout, že půjde o mocniny dvou snížené o 1. Přesněji, f(n) = 2n+2 — 1 (proč je exponent n + 2? inu proto, aby správně vyšlo /(O)). Ve druhé nesmíme ale zapomenout správnost našeho „věštění" dokázat, nejlépe matematickou indukcí podle n. . Báze: /(O) = 20+2 -1 = 4-1 = 3 platí. 21 • Indukční krok: za využití indukčního předpokladu f (n + 1) = 2 • f (n) + 1 = 2- (2n+2 - 1) + 1 = 2 • 2n+2 - 2 + 1 = 2(n+1)+2 - 1. což také platí. 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. □ Navazující studium I když jste se s "množinami" setkávali už od základní školy, do matematické teorie množin asi nahlédnete na VS poprvé. Nezalekněte se na úvod formality vyjadřování, která je bohužel nezbytná, a naučte se s množinami a relacemi dobře pracovat aspoň na zde ukázané naivní úrovni konečné teorie množin. (Lehký náhled na obecně nekonečné množiny a jejich zdánlivé paradoxy i informatické aplikace si ukážeme později v Lekci 11...) Dále si srovnejte pojem posloupnosti s pojmem funkce v Oddílu 4.1 a také si později povšimněte blízké koncepční podobnosti rekurentních deňnic s induktivními deňnicemi množin a funkcí v Oddíle 6.5. 22 4 Relace a funkce, Ekvivalence Úvod V návaznosti na předchozí lekci si podrobně rozebereme matematické formalismy relací a funkcí. Na rozdíl od množin, které se v jisté velmi naivní formě objevují už na základní škole, se relacím v jejich abstraktní podobě moc pozornosti ve výuce nevěnuje. Stejně tak s pojmem funkce jste se již setkali na nižších stupních škol, ale povětšinou jen ve spojení s aritmetickými a analytickými funkcemi tvaru x + 1, x2 — y, či sin x, 1 + cos x2, atd. Jak uvidíte nyní, pojmy relace i funkce jsou zcela abstraktní a neváže se ně žádný analytický vzorec výpočtu či podobné. Přitom na pojem (zcela obecné) relace velmi brzo narazí každý informatik při studiu dat a databází. Není to však jen oblast relačních databází, ale i jiná místa informatiky, kde se obecné funkce a relace skrývají či přímo explicitně objevují. Nejčastěji se setkáte s binárními relacemi, například vždy, když rozdělujete objekty podle „shodných" znaků (relace ekvivalence), nebo když objekty mezi sebou „porovnáváte" (relace uspořádání). Na tyto dvě základní oblasti se dále zaměříme. Cíle Úkolem této lekce je vybudovat matematický aparát (konečných) relací, s primárním zaměřením na funkce a binární relace typu ekvivalence a uspořádání. Ve vztahu k binárním relacím je zavedeno množství pojmů, které jsou později užitečné v různých oblastech matematiky i informatiky. Látka pak plynule pokračuje Lekcí 5. 4.1 Relace a funkce nad množinami Vedle množin dalším důležitým základním „datovým typem" matematiky jsou relace, kterým vzhledem k jejich rozsáhlému použití v informatice věnujeme významnou pozornost v této i dvou příštích lekcích. Definice 4.1. Relace mezi množinami A\, ■ ■ ■ ,Ak, pro k G N, je libovolná podmnožina kartézského součinu R C Ai x • • • x Ak . Pokud A\ = ■ ■ ■ = Ak = A, hovoříme o k-ární relaci R na A. Komentář: Příklady relací. * {(1, a), (2, a)} je relace mezi {1, 2, 3} a {a, b}. * {(i, 2 • i) | i G N} je binární relace na N. * {(i,j,i + j) \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... 23 Funkce mezi množinami Za první setkání s instancemi relací se většinou dá považovat pojem funkce. Přitom 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í. Definice 4.2. (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) E /. Množina A se nazývá definiční obor a množina B obor hodnot funkce /. Komentář: Neformálně řečeno, ve funkci / je každé „vstupní" hodnotě x přiřazena jednoznačně „výstupní" hodnota y. (V obecné relaci počty „přiřazených" dvojic neomezujeme. ..) A ^ >—B AxB fcAxB Značení: 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 B. Funkcím se také říká zobrazení. Komentář: Příklady funkcí jsou třeba následující. * Definujeme funkci / : N —> N předpisem f (x) = x + 8. Pak / = {(x, x + * Definujeme funkci plus :NxN-íN předpisem plus (i, j) = i + j. Pak plus = {(i, j, i + j) \i,j G N}. x G N}. Definice: Pokud naši Definici 4.2 upravíme tak, že požadujeme pro každé x E A nejvýše jedno y E B takové, že (x, y) E f, obdržíme definici parciální funkce z A do B. Komentář: AxB f e AxB 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? 24 4.2 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. Příklad 4.3. Tabulky relační databáze. 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 ~ 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 □ Poznámka: Relační databáze je konečná množina tabulek. Schéma databáze je (zjednodušeně řečeno) množina „typů" jednotlivých tabulek. 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ě. • Prvek (a, b) G R znázorníme jako orientovanou hranu („šipku") z a do b. Jedi a = b, pak je touto hranou „smyčka" na a. Komentář: Pozor, nejedná se o „grafy funkcí" známé z matematické analýzy. 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, d), (e, /), (/, b)}, pak: c 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). 25 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 aitj = 1 právě když (i, j) G R. d a (l 1 0 0 0 o\ b 0 0 1 1 1 1 c 0 0 0 0 0 0 d 0 0 1 0 0 0 e 0 0 1 1 0 1 f V> 1 1 0 0 oy1 4.3 Vlastnosti binárních relací Pro začátek si výčtem a doprovodnými schematickými obrázky uvedeme pět základních vlastností binárních relací, které nás typicky v matematice zajímají. Definice 4.4. Nechť R C M x M. Binární relace R je • reflexivní, právě když pro každé a E M platí (a, a) G i?: <£> <í> • ireflexivní, právě když pro každé a E M platí (a, a) ^ i?: • symetrická, právě když pro každé a, b G M platí, že jestliže (a, 6) G i?, pak také (b, a) G R; a • antisymetrická, právě když pro každé a,b G M platí, že jestliže (a, b), (b, a) G i?, pak • tranzitivní, právě když pro každé a,b,c G M platí, že jestliže (a,b), (b,c) G R, pak také (a, c) E R. , •v-2> Následují dva základní typy binárních relací; kde i? 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í). Komentář: Pozor, může být relace symetrická i antisymetrická zároveň? Ano! Vezměte si relaci R = {(x, x) \ x G M}, která obě jmenované vlastnosti splňuje. Proto pokud jste třeba dotázáni, zda relace je symetrická, nestačí se v odpovědi odvolávat na fakt, že je antisymetrická(!), neboť tyto vlastnosti se nevylučují. 26 Příklad 4.5. 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 x a y 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 podrobně, které z definovaných vlastností tyto jednotlivé relace mají. Které z nich tedy jsou ekvivalencí nebo uspořádáním? □ Příklad 4.6. 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.) □ 4.4 Relace ekvivalence Podle Definice 4.4 je relace R C M x M ekvivalence právě když i? 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 ekvivalence. Komentář: 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 Neformálně řečeno; ekvivalence je relace i? C M x M, taková, že (x, y) G i? právě když x a y jsou v nějakém smyslu „stejné". Značení. V případě relace ekvivalence se někdy lze setkat s pojmenováním jako ~ či « místo R. Místo {x, y) E R se pak píše x »2 y. Příklad 4.7. Nectí 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: 27 * (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) G R právě když x, y mají stejnou výšku a stejnou barvu vlasů: * (x, y) G 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áaledující univerzální poznatek, který může platit (a taky platí) pouze pro průnik a nikoliv pro sjednocení. Tvrzení 4.8. Nechť R, S jsou dvě relace ekvivalence na stejné množině M. Pak jejich průnik R C\ S je opět relací ekvivalence. Důkaz (náznak): Jelikož reflexivita a symetrie je zřejmá, stačí snadno ověřit platnost tranzitivity na RílS. Nechť (a, b), (b, c) G RílS, pak podle tranzitivity každé samostatné z R, S plyne (a, c) G R a zároveň (a, c) G S. □ Příklad 4.9. Nechť i? C N x N je binární relace defínovaná takto: (x,y) G R právě když \x — y\ je dělitelné třemi. V jakém smyslu jsou zde x a, y „stejné"? Dávají stejný zbytek po dělení třemi. □ Příklad 4.10. Buď R binární relace mezi všemi studenty na přednášce FP.IBOOO 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.) □ 4.5 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 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 4.11. 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 G" M (tj. každý prvek M je neprázdná podmnožina M): - pokud A,B eN, pak buď A = B nebo A H B = 0: - UAeMA = M- Prvkům M se také říká třídy rozkladu. Komentář: * Buď M = {a, b, c, d}. Pak M = {{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\í = {^0,^1,^2} 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 R^f na M: 28 Věta 4.12. Nechť M je množina a M rozklad na M. Nechť Rjy C M x M je relace na M definovaná takto (x, y) E -R/v právě když existuje A E M taková, že x, y E A. Pak Rfj- je ekvivalence na M. Důkaz: Dokážeme, že Rjy je reůexivní, symetrická a tranzitivní (Deňnice 4.4). • 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 4.11). Proto (x,x) E Rjy, tedy Rfj- je reflexivní. • Symetrie: Nechť (x,y) E Rjy. Podle definice Rjy pak existuje A E M taková, že x, y E A. To ale znamená, že také (y,x) E Rjy podle definice R^f, tedy Rjy je symetrická. • Tranzitivita: Nechť (x,y), (y,z) E Rjy. Podle definice Rj^ existují A, B E M takové, žex,yEAay,zEB. Jelikož A H B ^ 0, podle druhé podmínky z Defínice 4.11 platí A = B. Tedy x, z E A = B, proto (x, z) E Rjy podle definice Rj^. □ Každá ekvivalence R na, M naopak jednoznačně určuje jistý rozklad M/R na M: Věta 4.13. Nechť M je množina a R ekvivalence na M. Pro každé x E M definujeme množinu Pak {[x] | x E 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 4.11. • Pro každé [x] E M/R platí [x] ^ 0, neboť x E [x]. • Nechť [x], [y] E M/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) E R. Jelikož R je symetrická a (y, z) E R, platí (z, y) E R. Jelikož (x, z), (z, y) E R a R je tranzitivní, platí (x, y) E R. Proto také (y, x) E R (opět ze symetrie R). Nyní dokážeme, že [y] = [x]: * v[x] — [y] ": Nechť v G [x]. Pak (x, v) G R podle definice [x]. Dále (y, x) G R (viz výše), tedy (y, v) G R neboť R je tranzitivní. To podle definice [y] znamená, že v G [y]. * »[y] - [x] ": Nechť v G [y]. Pak (y, v) G R podle definice [y]. Dále (x, y) G R (viz výše), tedy (x, v) G R neboť R je tranzitivní. To podle definice [x] znamená, že v G [x]. • Platí |JyeM,R[x] = M, neboť x E [x] pro každé x E M. [x] = {yEM\ (x,y)ER}. M 29 □ 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, což můžete vidět na relačních databázích (viz také Lekce 6) a na často se vyskytujících induktivních dennících (Oddíl 6.5). S relacemi ekvivalence i jimi implicitně deňnovanými rozklady množin se lze setkat tam, kde nějaké objekty "rozdělujeme do přihrádek" podle nějakých sdílených znaků nebo jiných 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 uvedli na formálních základech. Toto formální pojetí relací ekvivalence a rozkladů budete potřebovat v různých navazujících předmětech, například u teorie automatů. 30 5 Uspořádané množiny, Uzávěry Úvod V této lekci dále pokračujeme probíráním binárních relací na množinách jako nástrojů vyjadřujících vztahy mezi objekty. Zaměřujeme se nyní především na relace „ srovnávající" objekty podle jejich vlastností. Takto vágně opsané relace mívají jasné společné znaky, které se objevují ve zde uvedené formální deňnici relace uspořádání. Následně se také zabýváme způsobem, jak libovolnou relaci „obohatit" o nějakou vlastnost. Tento úkol vede na rozšiřování naší relace (tj. přidávání dvojic) do vzniku jejího takzvaného uzávěru. Cíle Deňnujeme relace uspořádání a mnohé další pojmy k nim se vztahující, například Hasseovy diagramy. Studující by měli porozumět matematické problematice uspořádaných množin a naučit se je správně používat. Závěrem si ukážeme operátory uzávěrů relací. 5.1 Uspořádání a uspořádané množiny Podle Definice 4.4 je relace R C M x M (částečné) uspořádání právě když R 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 R je uspořádáním. Komentář: Neformálně řečeno: uspořádání je taková relace i? 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 R 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 5.3) je zde: 8 12 dělitelnost: 2 3 5 7 11 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) G 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 budeme pro větší přehlednost v obrázcích vynechávat. 31 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 5.1. 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 uspořádaných množin Příklad 5.2. Necht! M je množina všech studentů 1. ročníku FI. Uvažme postupně relace uspořádání R C M x M defínované následovně (jedná se 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: * (x, y) E R právě když x a y mají stejné rodné číslo. Ano, i v posledním bodě se jedná o uspořádání! (Dobře si promyslete, proč. Které dvojice jsou vůbec porovnatelné?) □ Příklad 5.3. 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í. * Buď M množina. Pak (2M, C) je uspořádaná množina (říkáme inkluzí). Které dvojice jsou v uspořádání inkluzí nesrovnatelné! la b, c} □ 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 5.2. Užitečnou dovedností je umět popsat uspořádání „větší množiny" pomocí „malých" složek. Neformálně lze toto uvést následujícími příklady: Příklad 5.4. Uspořádání „po složkách". Nechť (A, 2, pak množinu Ai x • • • x An lze uspořádat třeba po složkách nebo lexikografícky. Všimněte si, že lexikograficky se například řadí slova ve slovníku... 5.2 Další pojmy uspořádaných množin K tématu uspořádaných množin se vztahuje množství drobných pojmů, které potkáte v různých oblastech matematiky i informatiky. Definice 5.6. Nechť (M, ^) je uspořádaná množina. • x E M je minimální právě když pro každé y E M platí, že jestliže y ^ x, pak x ^ y. (Tj. x je minimální právě když neexistuje žádný prvek ostře menší než x.) x • x G M je maximální právě když pro každé y E M platí, že jestliže x ^ y, pak y ^ x. (Tj. x je maximální právě když neexistuje žádný prvek ostře větší než x.) • x E M je nejmenší právě když pro každé y E M platí, že x -< y. x > 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 G M takové, že x^z^yay^z^x. x x E M je do/m' závora (mez) množiny ACM právě když x ^ y pro každé y E A. y e A A A x G M je horní závora (mez) množiny ACM právě když y ^ x pro každé y E A. 33 • x G M je ínfimum množiny ACM právě když x je největší dolní závora množiny A. » x G M je supremum množiny A C M, právě když x je nejmenší horní závora 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 inŕlmu 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ě inrlmem a supremem, které hrají v jistých ohledech podobnou roli. Avšak ani supremum a inŕlmum nemusí vždy existovat. Pozor! Některé uvedené definice mají dosti „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 5.7. 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 5.6 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. □ Relace předuspořádání Mimo uspořádání chápaných striktně antisymetricky se v praxi často setkáme s „sko-rouspořádáními", ve kterých některé očividně různé prvky stojí na stejné úrovni naší preference. Jak třeba uspořádáte různé počítače podle výkonu nebo studenty podle známek A-E? To matematicky podchytí následující pojem. Definice: Relace R C M x M je předuspořádání (také kvazíuspořádání, nebo polouspořádání) právě když R je reůexivní a tranzitivní. Komentář: Rozdíl mezi uspořádáním a předuspořádáním je (neformálně řečeno!) v tom, že u předuspořádání srovnáváme prvky podle kritéria, které není pro daný prvek jedinečné. V předuspořádání takto mohou vznikat „balíky" (třídy) se stejnou hodnotou kritéria, což 34 schematicky ilustrujeme na následujícím obrázku. ©-l|J<^>e 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 5.8. 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 j ~ 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. 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] ^ [rr], 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]. □ 5.3 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: a b c a e f Definice: Hasseovský diagram konečné uspořádané množiny (M, ^) je jeho (jednoznačné) grafické znázornění získané takto: * Do první „horizontální vrstvy" zakreslíme body odpovídající mininálním prvkům {M, ^). (Tj. které nepokrývají nic. Pojem pokrývání prvku najdete v Definici 5.6.) 35 * 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"). Příklad 5.9. Relaci inkluze na čtyřprvkové množině {a,b,c,d} zakreslíme Has-seovským diagramem takto: □ Komentář: Jak vidíme, 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 definici je jen velmi neformální, důležité je, že větší (pokrývající) prvky jsou nad menšími (pokrývanými). 5.4 Uzávěry relací Posledním bodem našeho výkladu je postup, jak danou relaci můžeme „obohatit" o zvolenou vlastnost (například proto, že naše data o relaci jsou neúplná a vlastnost je tak poškozena). Definice: Buď V (nějaká) 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. Antisymetrie není uzavíratelná vlastnost. Věta 5.10. 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 Ry (vzhledem k množinové inkluzi), které samo má vlastnost V. Definice: Tuto „nejmenší" relaci Ry s vlastností V nazýváme V-uzávěrrelace R. Tvrzení 5.11. Nechť f? 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}. 36 * Tranzitívni uzávěr R je přesně relace R+ = T1 (R), kde T je funkce, která pro každou binární relaci S vrátí relaci T(S) = S U {(x, z) | existuje y takové, že (x, y), (y, z) G S} a T1 = X ° '"" ° 7~y Je *-krát iterovaná aplikace funkce T. i * Reflexivní a tranzitivní uzávěr f? 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 R. * Na pořadí aplikování uzávěrů vlastností záleží! Komentář: Význam reflexivních a symetrických uzávěrů je z předchozího docela zřejmý. Význam tranzitivního uzávěru R+ je následovný: Do R+ přidáme všechny ty dvojice (x, z) takové, že v i? se lze „dostat po šipkách" z x do z. Nakreslete si to na papír pro nějakou jednoduchou relaci, abyste význam tranzitivního uzávěru lépe pochopili. A jak bylo dříve řečeno, antisymetrický uzávěr relace prostě nemá smysl. Například buď fiCNxN definovaná takto: R = {(i, i +1) | i G N}. Pak R* je běžné lineární uspořádání < přirozených čísel. Příklad 5.12. Proč při výpočtu tranzitivního uzávěru relace na konečné množině podle vzorce R+ = IJ^i^í-^) yždy stačí uvažovat konečně mnoho členů tohoto sjednocení? Pro odpověď si uvědomme zásadní fakt — pokud 7~í+1 = T\ tak už platí 7~í+fc = T% pro všechna přirozená k. Neboli je potřeba sjednotit jen tolik prvních členů, dokud se ony „zvětšují", což může nastat jen konečně krát nad konečnou množinou. Mimo jiné tak vidíme, že uvedený popis tranzitivního uzávěru je konstruktivní. □ Rozšiřující studium I v této lekci se pojednává o látce, kterou určitě čtenáři na inuitivní úrovni znají (vždy umění si věci „uspořádat" je jednou ze základních lidských dovedností). Přesto správné matematické uchopení podstaty uspořádání vyžaduje se prokousat několika nesnadnými formálními deňnicemi. Všimněte si, že hlavní těžkosti pojmu uspořádané množiny se vztahují k částečným, tedy ne-lineárním, uspořádáním, kdy běžnému lidskému uvažování není zcela intuitivně jasné nakládání s nesrovnatelnými dvojicemi. Jmenovitě dále upozorňujeme na pojmy uzávěrů relace; co se týče praktického určení symetrického nebo tranzitivního uzávěru relace, odkazujeme na budoucí Algoritmy 8.5 a 8.6. 37 6 Skládání relací a funkcí Úvod Vraťme se nyní k látce Lekce 3. Z jejího pokročilého obsahu jsme doposud velmi detailně probírali relace a jejich jednotlivé vlastnosti. Nyní se podívejme, jak lze relace mezi sebou „ skládat", což je například základní technika práce s relačními databázemi. Je však i jiné místo, kde jste se zajisté se skládáním relací setkali - jedná se o skládání funkcí. Jak například spočítáte na kalkulačce výsledek složitějšího vzorce? Mimo to se ještě zobecněně vrátíme k problematice „postupných" (induktivních a rekurentních) deňnic a vztahů. Jedná se vlastně o matematické analogie rekurzivních programů a jejich správné formální pochopení oceníme mimo jiné i při programování samotném. Cíle V této lekci deňnujeme základní vlastnosti funkcí a především popíšeme a podrobně rozebereme skládání relací a návazně skládání funkcí jako relací (jako model nám poslouží permutace). Na závěr se stručně podíváme na problematiku induktivních deňnic funkcí, coby na rozšíření rekurentních vztahů z Oddílu 3.4. 6.1 Vlastnosti funkcí Funkce je podle Definice 4.2 speciálním případem (obvykle binární) relace, majícím pro každou hodnotu levé strany jedinou (funkční) hodnotu pravé strany. Více o funkcích řekne následující definice. Definice 6.1. Funkce (případně parciální funkce) / : A —> B je * ínjektívní (nebo také prostá) právě když pro každé x,y G A, x ^ y platí f(x) ^ f(y)\ * surjektívní (nebo také „na") právě když pro každé y E B existuje x E A takové, že f (x) = y, "V—i (7) Y * bíjektívní (vzáj. jednoznačná) právě když je injektivní a současně surjektivní. Funkce nás coby speciální případ relací budou provázet i ve zbytku lekce. Komentář: Následují jiné ukázky vlastností funkcí. * Funkce plus : N x N —> N je surjektivní, ale není prostá. 38 * Funkce g : Z je bijektivní. * Funkce 0:0- * Funkce 0:0- N daná předpisem —2x — 1 jestliže x < O, 2x jinak 0 je bijektivní. {a, b} je injektivní, ale není surjektivní. * Dokázali byste nalézt bijektivní funkci NxN-> N? 6.2 Inverzní relace a skládání relací K použitelné práci s relacemi v aplikacích se dostaneme, pokud budeme umět relace správně „skládat" a „převracet". K tomu nás přivedou zase 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^1 a je definována takto: R-1 R. {{b,a) | (a, b) G R} S7\ R -i. píí R 1 je tedy relace mezi B a A! Komentář: Příklady inverzí pro relace-funkce. * Inverzí bijektivní funkce f(x) = x + 1 na TL je funkce f^1(x) = x — 1. * Inverzí prosté funkce f(x) = e1 na R je parciální funkce = lnx. * Funkce g(x) = x mod 3 není prostá na N, a proto její inverzí je „jen" relace g^1 = {(a, 6) a = 6 mod 3}. Konkr. í^1 = {(0, 0), (0, 3), (0, 6),... , (1,1), (1,4),... , (2, 2), (2, 5),... }. Tvrzení 6.2. 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. □ Následuje klíčová definice, pro jejiž bližší ilustraci odkazujeme také na Příklad 6.4. Definice 6.3. 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) | existuje b G B takové, že (a, b) G R, (b, c) G S} 39 Složení relací čteme „R složeno s S" nebo (pozor na pořadí!) „S po R". Komentář: Několik matematických příkladů skládání relací následuje zde. Jg~li - A = {a,b}, 5 = {1,2}, C = {X,Y}, - R = {(a,l),(b,l),(b,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. 6.3 Skládání relací „v praxi" 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 6.4. 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) předmět (kód) fakulta MU 121334 MA010 MA010 FI 133935 M4135 S : IB000 FI 133935 IA102 IA102 FI 155878 M1050 M1050 PřF 155878 IB000 M4135 PřF 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)? 40 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 _řr2 x • • • x Kk a U C L\ x L2 x • • • x Lp, přičemž pro nějaké m < min(A;, í) 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 L1;..., Lm („překrytí") s použitím Defínice 6.3 takto: Položme A = Kľ x ■ ■ ■ x Kk_m, B = Li x ■ ■ ■ x Lm a C = L m+l x Lp. * Příslušné relace pak jsou R = {(a, b) G A x B | (a±,... ak-m, &i,... bm) G T} a S = {(b,č) G B x C | (b1,...bm,cm+1,...ce) e U}. * Nakonec přirozeně položme U om T ~ S o R, takže vyjde UomT = {(a, č) | ex. b G B, že (ai,... ak-m, h,... bm) G T a (6i,... 6m, cm+i,... q) G r/} . Schematicky pro snažší orientaci ve složkách našich relací: T C Kľx U C f/oJC iři x x Kk-m x Kk-m+1 x ■ ■ ■ x Kk L\ x ''' x Lm xL^yi^Y x ''' x Lp] x Kk-m x ._ _. x Lm+i x ■ ■ ■ x Lp a * c Opět je nejjednodušší si koncept skládání vícečetných relací ilustrovat příkladem. Příklad 6.5. 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 41 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 posá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? □ 6.4 Skládání funkcí, permutace Soustřeďme se nyní na další oblast, kde běžně a přirozeně používáme skládání relací, aniž si to uvědomujeme. Fakt: Mějme zobrazení (funkce) 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 + 1)? Ve správném pořadí složíme funkce }\(x) = x2, f2(3;) = x + 1, fs(x) = log x 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 §2{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í. Definice: Nechť permutace 7r množiny {1,2,... ,12} je určena seřazením jejích prvků (pi,... ,pn)- Pak 7T je zároveň bijektivním zobrazením {1,... ,12} —> {1,... ,12} definovaným předpisem tt(í) = Pí. Tudíž lze permutace skládat jako relace podle Definice 6.3. 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á grupa je vlastně isomorfní některé permutační grupě. 42 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, . . ., Ofc) 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 (ai, a2,..., ak) 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. Například permutaci (5, 3,4, 8, 6,1, 7, 2) si lze obrázkem nakreslit takto: Reprezentace permutací jejich cykly Věta 6.6. Každou permutací 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 = ^(^í)? a3 = 7r(a2)! atd., až se dostaneme „zpět" k a^+i = ^(a^) = d\- 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±,..., a^}, dokud nezůstane prázdná. □ Značení permutace jejími cykly: Nechť se permutace 7r podle Věty 6.6 skládá z cyklů (ai,..., Ofc), (bi,... ,bi) až třeba (z1}..., zm). Pak zapíšeme 7T = ((ai,..., ak) ..., bi) ... (Z!, ...,zm)). Komentář: Primitivní pseudonáhodné generátory v počítačích iterují z náhodného počátku permutaci danou vztahem i \—> (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 6.7. Ukázka skládání permutací daných svými cykly. Vezměme 7-prvkovou permutaci 7r = (3,4, 5, 6, 7,1, 2). Ta se skládá z jediného cyklu (1, 3, 5, 7, 2,4, 6). Jiná permutace a = (5, 3,4, 2, 6,1, 7) se rozkládá na tři cykly (1, 5, 6), 43 (2, 3,4} a (7). Nyní určíme složení a on těchto dvou permutací (už přímo v zápisu cykly): (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 6.5 Induktivní definice množin a funkcí Vzpomeňme si na definici posloupnosti rekurentním vztahem z Oddílu 3.4. Přímým zobecněním dřívějších rekurentních definic je následující koncept. Definice 6.8. 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,..., ak G M. • Je dán soubor induktivních pravidel typu V tomto případě je y typicky funkcí y = fi(xi,..., xe). Pak naše induktivně definovaná množina M je určena jako nejmenší (inkluzí) množina vyhovující těmto pravidlům. Poznámka: Vidíte podobnost této definice s uzávěrem relace? (Věta 5.10.) Komentář: • 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 - Je-li i G N, pak také i + 1 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}. Jednoznačnost induktivních definic 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ář: Definujme například množinu M C N induktivně takto: - 2,3 G M - Jestliže x, y G M a x < y, pak také x2 + y2 a x ■ y jsou prvky M. ((1, 5, 6)(2, 3,4}(7}) o ((1, 3, 5, 7, 2,4, 6}) = ((1,4}(2}(3, 6, 5, 7}) (3, 6, 5, 7} určíme analogicky. □ Jsoudi (libovolné prvky) x\,..., x i G M, pak také y E M. 44 Proč tato induktivní definice není jednoznačná? Například číslo 8 G M lze odvodit způsobem 8 = 2 • (2 • 2), ale zároveň zcela jinak 8 = 22 + 22. 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.9. Induktivní definice funkce z induktivní množiny. Nechť množina M je dána jednoznačnou induktivní definicí. Pak říkáme, že funkce J7 : M —> X je definována induktivně (vzhledem k induktivní definici M), pokud je řečeno: • Pro každý z bázických prvků a1,a2,...G M je určeno J7^) = Ci, kde q je konstanta. • Pro každé induktivní pravidlo typu :'Jsou-li (libovolné prvky) x\,... ,xt G M, pak také f(x\,..., x i) G M" je definováno Komentář: Pro příklad se podívejme třeba do manuálových stránek unixového příkazu test EXPRESSION: EXPRESSION is true or falše and sets exit status. It is one of: Vidíte, jak tato ukázka koresponduje s Definicí 6.9? Induktivní definice se „strukturální" indukcí Závěrem ještě doplňkově zařazujeme malou ukázku, kterak přirozeně zkombinovat induktivní definice s pokročilou formou matematické indukce v dokazování, s tzv. strukturální indukcí. Příklad 6.10. 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 prvek SExp. - Jestliže x, y G SExp, pak také (x) 0 (y) a (x) © (y) jsou prvky SExp. (Jak vidíme, díky nucenému závorkování je tato induktivní definice jednoznačná.) Tímto jsme aritmetickým výrazům přiřadili jejich „formu", tedy syntaxi. Pro přiřazení „významu", tj. sémantiky aritmetického výrazu, následně definujme funkci Val: SExp —> N induktivně takto: - 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). Jr(f(x1,...,xi)) na základě hodnot ^(xi),..., ^(x^). ! EXPRESSION EXPRESSI0N1 -a EXPRESSI0N2 EXPRESSI0N1 -o EXPRESSI0N2 [-n] STRING STRING1 = STRING2 EXPRESSION is false both EXPRESSI0N1 and EXPRESSI0N2 are true either EXPRESSI0N1 or EXPRESSI0N2 is true the length of STRING is nonzero the strings are equal 45 Co je tedy správným významem uvedených aritmetických výrazů? (Příklad 6.11) □ Příklad 6.11. Důkaz správnosti přiřazeného „významu" Val: SExp —> N. Věta. Pro každý výraz s G SExp je hodnota Val(s) z Příkladu 6.10 číselně rovna výsledku vyhodnocení výrazu s podle běžných zvyklostí aritmetiky. Jelikož pojednáváme o induktivně definované funkci Val, je přirozené pro důkaz jejích vlastností aplikovat matematickou indukci. Na rozdíl od dříve probíraných příkladů zde nevidíme žádný celočíselný „parametr n", a proto si jej budeme muset nejprve definovat. Naši indukci tedy povedeme podle „délky l odvození výrazu s" definované jako počet aplikací induktivních pravidel potřebných k odvození s G SExp. 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 dořeší analogicky. □ Rozšiřující studium S formalizací pojmu funkce a jejími vlastnostmi se setkáváte především v matematice, avšak například na bijektivní funkce narazíte při ukládání dat při volbě klíče apod. Pro informatiku jsou spíše důležitější relace a jejich skládání, na nichž je založena mimo jiné práce s relačními databázemi. Poslední částí lekce je problematika induktivních deňnic, které ač ve formálním podání mohou nejprve vypadat nepochopitelně, jsou ve skutečnosti zcela přirozenou popisnou metodou v mnoha aplikačních sférách informatiky a jejich alespoň intuitivní chápání pro vás bude v dalším studiu nezbytné. Schválně, zkuste se podívat zrovna do vaší oblíbené oblasti informatiky, kde všude induktivní definice (třebaže nepřímo) najdete. 46 7 Jemný úvod do Logiky Úvod Základem přesného matematického vyjadřování (viz Lekce 1) je správné používání matematické logiky a logických úsudků. Logika jako ňlozoňcká disciplína se intenzivně vyvíjí už od dob antiky, avšak ke skutečnému rozmachu formální logiky coby součásti matematiky došlo až začátkem 20. století. (S přispěním třeba Russelova paradoxu a převratných Góde-lových prací.) Dnes se základní logický kalkulus používá nejen v čisté matematice, ale „ stojí" na něm veškeré logické obvody a počítače. Proto se studenti informatiky s logikou setkávají záhy při svém studiu a mnohokrát se k tématu také vracejí. Cíle Následující lekce přináší (skutečně velmi jemný a tak trochu i povrchní) úvod do moderní matematické logiky, která je solidním základem matematiky a nakonec i celé informatiky. Zavedeme si základy výrokové logiky a výrokového počtu a velmi stručně si uvedeme problematiku predikátové logiky a kvantiňkace. 7.1 Výroky v přirozené podobě Prvním úkolem našeho výukového materiálu je vytvořit pevný „most" mezi přirozenou lidskou mluvou a formálním jazykem matematiky. To napomůže pochopení významu matematických výroků a práci s nimi. Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém má smysl 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ů. * Kateřina přijela ve 12:00 a šli jsme spolu do kina. * Množina {a, b} má více než jeden prvek a není nekonečná. * Jestliže má Karel přes 90 kg váhy, nejedu s ním výtahem. * Jestliže má tato kráva 10 nohou, 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? Tuto problematiku jsme již neformálně nakousli v Lekci 1 a přesnou odpověď poskytne Definice 7.3. (Ano, výrok je pravdivý.) 47 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ální (matematická) logika pak v podobném duchu definuje jazyk matematiky a přitom odstraňuje nejednoznačnosti přirozeného jazyka. 7.2 Formální výroková logika Pro dokončení přechodu z přirozené mluvy do formálního matematického jazyka je nutno dát druhému rigorózní náplň. Tato náplň formálního jazyka se skládá ze syntaxe („jak to zapíšeme") a sémantiky („co to znamená"). Definice 7.1. Syntaxe výrokové logiky. Buď AT = {A, B,C,...} spočetně nekonečná množina výrokových proměnných (tzv. atomů). Množina výrokových formulí $ je defínována induktivně následujícími pravidly: (1) AT C $. (2) Jestliže ip>,ip E <3>, pak také -1(99) G $ a (ip>) =>• (ip) E <3>. (3) Každý prvek $ vznikne konečně mnoha aplikacemi pravidel (1) a (2). Značení: Symbol -1 je zván negací a, =>- je nazýván implikací. Komentář: Příklady několika správně utvořených formulí: A, (A) => (B), ((A) => Hfl))) => (Hfl)) => (C)) A také příklady několika ne zcela správně utvořených formulí: A^B, A^B^C, -iA => B Z těchto nesprávných ukázek je „nejhorší" ta prostřední, neboť daný zápis neumožňuje ani odhadnout, která z implikací se má vyhodnotit jako první. Abychom si ujasnili, která zjednodušení formálního zápisu formule jsou ještě přijatelná beze ztráty smyslu, přistoupíme k následující dohodě. Konvence 7.2. Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to nepovede k nejednoznačnostem za předpokladu, že negace -1 má „vyšší prioritu" než (Touto úmluvou se nemění množina $; mění se jen způsob reprezentace jejích prvků.) Dále si zavedeme, že * ip\/ ip (disjunkce) je jiný zápis formule ~np =>- ip, *

A ip (konjunkce) je jiný zápis formule ~l(~"f V - <=ř ip (ekvivalence) je jiný zápis formule (ip =>- ip) A (ip =>• ip). Komentář: Například formule (-i((A) =4> (B))) =4> ((-<(B)) =4> (C)) se dá s naší konvencí zapsat jako (A=>B)VBVC. Definice 7.3. Sémantika výrokové logiky. Valuace (ohodnocení) je funkce v : AT —> {true, falše}. Pro každou valuaci v definujeme funkci Sv : $ —> {true, falše} (vyhodnocení) induktivně takto: * SU(A) = v (A) pro každé A E AT. true jestliže Sv(ip) = falše: 4Í false jinak. falše jestliže Sv(íp) = true a Sv(ip) = falše: true jinak. Poznámka: Tento předpis podává nejen deňnici funkce Sv, ale také návod na to, jak ji pro daný argument vypočítat. Tvrzení 7.4. Důsledkem Definice 7.3 je následovné: * Sv(ip V ip) = true právě když Sv(íp) = true nebo Sv(ip) = true. * Sv(ip A ip) = true právě když Sv(íp) = true a současně Sv(ip) = true. * Sv(ip <=ř ip) = true právě když platí jedna z následujících podmínek - Sv(íp) = true a současně Sv(ip) = true, - Sv(íp) = falše a současně Sv(ip) = falše. Pravdivostní tabulky V praxi často vyhodnocení Sv logické výrokové formule zapisujeme do tzv. pravdivostní tabulky. Tato tabulka typicky má sloupce pro jednotlivé proměnné, případné „mezifor-mule" (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. Místo true, falše píšeme 1,0. Pro naše účely postačí uvést pravdivostní tabulku instruktážním příkladem. Čtenáři nechť si vyplní podle Definice 7.3 vlastní pravdivostní tabulky dalších výrokových formulí, viz také příslušné cvičící odpovědníky IS MU. Příklad 7.5. Jaká je pravdivostní tabulka pro formuli (A =^ B)\/ B V C? A B c A ^B (A B) V B V C 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 □ Definice: Formule ip G $ je splnitelná, pokud pro některou valuaci v platí, že Sv(íp) = true. Formule ip G $ je vždy pravdivá, neboli výroková tautologii , psáno |= ip, pokud pro každou valuaci v platí, že Sv(íp) = true. Řekneme, že dvě formule B)) B * |= (-,# -,A) ^(A^ B) 49 * |= {-^A 4 (5 A -.5)) =>• 4 Komentář: Kde jsme se s užitím takových tautologií už setkali? A jak poznáme tautologii v pravdivostní tabulce? 7.3 Jak správně znegovať formuli? Přesný význam formulí se zanořenými negacemi je někdy obtížné zjistit (podobně jako v běžné řeči). „ Není pravda, že nemohu neříci, že není pravda, že tě nemám nerad." Výrokové formule se proto obvykle prezentují v tzv. normálním tvaru, kde se negace vyskytují pouze u výrokových proměnných, formálně: Definice: Formule ip G $ je v normálním tvaru, pokud se v ní operátor negace aplikuje pouze na výrokové proměnné. Komentář: Například, pokud přijmeme pravidlo „dvojí negace" (—i—iA 4^ A), tak výše napsanou větu si převedeme na lépe srozumitelný tvar: „Nemusím říct, že tě mám nerad." Tvrzení 7.7. Každou výrokou formuli lze převést do normálního tvaru, pokud k =>- povolíme i užívání odvozených spojek A a V. Komentář: Pro ilustraci k -<(A =4> B) je ekvivalentní A A - B)) je ekvivalentní ->C V (->A A ->B) a k ->((A B) C) je ekvivalentní (A B) A ->C). Poznámka: Při dalším studiu logiky či logického programování se setkáte s různými jinými „normálními formami" výrokových formulí, například s konjunktivní či disjunktivní normální formou. S naší definicí mají všechny důležitý styčný bod - použití negací jen u proměnných. Normální tvar (formální postup) „Znegováním formule iplí se obvykle myslí převod její negace ~np do normálního tvaru. Jak jsme již demonstrovali na příkladě, normální tvar formule je „výrazně čitelnější" než formule používající zanořené negace. Proto následující formální postup induktivně definuje právě způsob převodu libovolné výrokové formule do našeho normálního tvaru. Metoda 7.8. Převod formule ip do normálního tvaru ^(p). Definujeme funktory T a Q pro náš převod induktivními předpisy F{A) = A G{A) = ^A HfVý) = J^VJW G(pv^) = G(p)aGW 50 Komentář: Uvažme formuli -i(A =4> -i(73 V -|(C =4> -A))). Užitím postupu 7.8 získáme: F(->(A => ->(B V -i(C => - -A))) = F (A) A G{^{B V -i(C => -^A))) = AAF{B V ^(C ^A)) A A (F(B) V Jr(-i(C => -iA))) = A A (73 V Q(C => -A)) A A (73 y(T(C) AG(-^A))) = A A (73 V (C A T(A))) A A (73 V (CA A)) Formuli A A (73 V (C A A)) lze dále zjednodušit na (ekvivalentní) formuli A A (73 V C). To ale je již z našeho pohledu matematicky neformální (heuristický) postup. Uvedené formální předpisy takto vyjadřují „intuitivnípostup negace" v matematicky přesném tvaru. Důkaz tohoto tvrzení je zároveň velmi hezkou ukázkou použití strukturální matematické indukce. Věta 7.9. Pro libovolnou výrokovou formuli p platí, že a) ÍF{p) je ekvivalentní formule k p v normálním tvaru b) a G{p) je formule v normálním tvaru ekvivalentní negaci ->p. Důkaz povedeme tzv. „indukcí ke struktuře formule", tedy indukci povedeme podle „délky" l - počtu aplikací induktivních pravidel (Definice 7.1) 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) = -p (= je „definiční rovnítko" pro formule). Podle výše uvedeného induktivního předpisu je ÍF(ip) = ÍF{-^p) = G{p)- Podle indukčního předpokladu pak je G{p) formule v normálním tvaru ekvivalentní ->p = ip. Obdobně pro funktor Q vyjádříme Q{ip) = G{~^p) = 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 = —iip podle Tvrzení 7.6. * ifj = (pi =>- p2). Podle výše uvedeného induktivního předpisuje ÍF(ip) = F{pi =>• P2) = ÍF{pi) =>• ÍF{p2)- Podle indukčního předpokladu jsou ÍF{pi) i ÍF{p2) formule v normálním tvaru ekvivalentní p\ a p2- Potom i ÍF{pi) =>• ÍF{p2) je v normálním tvaru dle definice a podle sémantiky =>- je ta ekvivalentní formuli {• P2) = Jr(pi) A G(p2)- Jelikož A je pro nás jen zkratka, výraz dále rozepíšeme G{ip) = ~^{F{pi) =>• -- P2, což jsme zde měli dokázat. * ifj = (p1\Zp2). Zde si musíme opět uvědomit, že spojka V je pro nás jen zkratka, a přepsat ip = (-1^1 =>• P2)- Potom podle předchozích dokázaných případů víme, že Fijp) = ÍFip^pi =>• P2) = ÍFip^pi) =>• Jr(p2) je ekvivalentní formuli (->• P2) = ífj, což bylo třeba dokázat. Stejně tak G{ip) = G(~"fi =>• f 2) = -F^-ipi) A G{p2) je podle předchozích případů důkazu ekvivalentní (—upi A -1^2) = * ifj = (pi A P2) a ip = (pi P2) už dokončíme analogicky. 51 7.4 Predikátová logika, kvantifikace Výše popsaná výroková logika je velmi omezená faktem, že každý výrok musí být („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. • Predikátová logika je obecnější než logika výroková; každá formule výrokové logiky je i formulí predikátové logiky, ale ne obráceně. • Predikátová logika pracuje s predikáty. Predikáty jsou „parametrizované výroky", 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ů. Komentář: Pro neformální přiblížení si uvedeme několik ukázek predikátů: * x > 3 (parameterem je zde x G R), * R je ekvivalence na M (parametr R C M x M). * čísla x a y jsou nesoudělná (parametry x, y G N), * obecně jsou predikáty psány P(x,y), kde x, y jsou libovolné parametry. Dennice 7.10. Syntaxe i sémantika predikátové logiky. Z predikátů lze vytvářet predikátové formule pomocí už známých (viz Definice 7.1) výrokových spojek a následujících tzv. kvantifikátorů: * \/x. ip „pro každou volbu parametru x platí formule ip", * 3x . ip „existuje alespoň jedna volba parametru x, pro kterou platí 99". 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á. Konvence 7.11. Pro lepší srozumitelnost zápisu formulí predikátové logiky se domluvíme na následujícím. * „Neuzavřené" proměnné vyskytující se v predikátech ve formuli

někdy pro referenci vypisujeme jako „parametry" samotné formule >p>(x,y,...). * Poukud není z kontextu jasné, co lze za daný parametr dosazovat, užívá se notace \/x G M. ip a 3x G M.

. (Platí, jen pokud je kvantifikovaný parametr prvkem nějaké fixní množiny!). * Tečka za symbolem kvantifikátoru se někdy vynechává (při vhodném uzávorkování formule), nebo se používá symbol „ : ". * Místo \/xi. \/x2 ■ ■ ■ ■ \/xn . ip se někdy krátce píše \/xi,x2, • • • ,xn (ip). Podobně u existenčního kvantifikátoru 3x1}x2, ■ ■ ■ ,xn (ip). Příklad 7.12. Ukažme si vyjádření následujících slovních výroků v predikátové logice: • Každé prvočíslo větší než 2 je liché: Vn G N . (Pr(n) An>2) Li(n). • Každé číslo n > 1, které není prvočíslem, je dělitelné nějakým číslem y kde n/i/a y > i; 52 Vn G N. (n > 1 A -iPr(n)) =>- 3y(y\n A n^y A y>l). • Jsou-li R a, S ekvivalence na M, je také RU S ekvivalence na M. Zde například můžeme mít dva pohledy na toto tvrzení - v jednom bereme množinu M za pevnou VR,S : (EqM(R) AEqM(S)) ^ EqM(RUS), kdežto ve druhém je i množina M parametrem VMVR,S : (Eq(M, R) A Eq(M, S)) Eq(M,RUS). □ Příklad 7.13. V pytlíku máme různobarevné kuličky. Vytáhneme libovolné tři z nich. Zamyslete se, proč je pak matematicky pravdivé následující tvrzení: • Je-li první kulička (z vytažených) větší než druhá a zároveň je druhá kulička větší než první, tak je třetí kulička červená. Řešení: Tento příklad je podobný Příkladu 1.4. Opět lze „selským rozumem" namítat, že je to přece úplná blbost - nemůže být první kulička větší než druhá a zároveň naopak, také nemůže být pravda, že třetí vytažená kulička je vždy červená. Jenže je potřeba se na uvedené tvrzení podívat matematicky. V prvé řadě, slova „libovolné tři" (z kuliček) vyjadřují všeobecnou kvantifikaci (V). Neboli uvedené tvrzení má být pravdivé pro každou trojici kuliček. Tvrzení samo je vysloveno jako implikace, takže je pravdivé vždy s výjimkou případů, kdy jsou splněny předpoklady a nepravdivý závěr. Jenže předpoklady (první kulička větší než druhá a zároveň naopak) nejsou splněny pro žádnou trojici kuliček a tudíž je naše tvrzení univerzálně platné. □ Jak „negovat" formule predikátové logiky? Na závěr jen stručně rozšíříme výše uvedenou metodu formálního negování. Metoda 7.14. Převod predikátové formule ip do normálního tvaru ÍF((p). Dřívčjší Metodu 7.8 rozšíříme o následující indukční pravidla: Jr(P(x1,...,xn)) = P(x1,...,xn) g(P(x1,...,xn)) = ->P(x1,... ,xn) F(yx.v) = vx.F(p) G(yx.v) = 3x.g(v) Jr(3x.ip) = 3x.Jr(ip) Q(3x.(p) = \/x.Q(ip) Komentář: Uvažme například negaci výše uvedené formule --(VMVÄ,5 : (Eq(M, R) A Eq(M, S)) Eq(M,RUS)). Pak F(^(VMVR,S : (Eq(M, R) A Eq(M, S)) Eq(M,RUS))) = g{\JM\JR,S : (Eq(M, R) A Eq(M, S)) Eq(M,RUS)) 3M3R,S : G((Eq(M, R) A Eq(M, S)) Eq(M,RUS)) 3M3R,S : (Eq(M, R) A Eq(M,S) A ^Eq(M,RUS)). 53 Rozšiřující studium Základem každého počítače jsou logické obvody, které jsou jen praktickou funkční implementací vhodných formulí výrokové logiky Tudíž se dá směle říci, že bez výrokové logiky by nebylo ani počítačů, ani informatiky Nadto se informatici setkávají po teoretické stránce s výrokovou i predikátovou logikou nejen v matematice, ale i v logickém programování a nakonec i při psaní obyčejných složených podmínek v příkazu „ if "... Na druhou stranu zájemce o studium matematických hlubin logiky a třeba slavných Gódelových poznatků můžeme později odkázat na předmět Matematická logika MA007. 54 8 Dokazování vlastností algoritmů Úvod Po předchozí převážně matematické látce se náš výklad obrací zase k informatice a navazuje na druhý pilíř celého předmětu z Lekce 1 - algoritmy a jejich formální zápis. Jak jste asi již (i v našem předmětu) poznali, umění programovat není zdaleka jen o tom naučit se syntaxi programovacího jazyka, ale především o schopnosti vytvářet a správně formálně zapisovat algoritmy. Přitom situace, kdy programátorem zapsaný kód ve skutečnosti počítá něco trochu jiného, než si programátor představuje, je snad nejčastější programátorskou chybou - o to zákeřnější, že ji žádný „chytrý" překladač nemůže odhalit. Proto již na počátku (seriózního) studia informatiky je dobré klást důraz na správné chápání zápisu algoritmů i na důkazy jejich vlastností a správnosti. A to je téma, kterému se tedy budeme věnovat po převážný zbytek předmětu FI:IB000. Cíle Na podkladě formálního zápisu algoritmů z Oddílu 1.4 si ukážeme, jak využít předchozí nabyté matematické znalosti při dokazování vlastností a správnosti různých jednoduchých algoritmů. Nejčastějším nástrojem nám při tom bude matematická indukce. Neformálně o „správnosti" programů Jak se máme přesvědčit, že je daný program „správný"? * Co třeba ladění programů? Jelikož počet možných vstupních hodnot je (v principu) neohraničený, nelze otestovat všechna možná vstupní data. * Situace je zvláště komplikovaná v případě paralelních, randomizovaných, interaktivních a nekončících programů (operační systémy, systémy řízení provozu apod.). Takové systémy mají nedeterministické chovám a opakované experimenty vedou k různým výsledkům. (Nelze je tudíž ani rozumně ladit, respektive ladění poskytne jen velmi nedostatečnou záruku správného chování za jiných okolností...) * V některých případech je však třeba mít naprostou jistotu, že program funguje tak jak má, případně že splňuje základní bezpečnostní požadavky. - Pro „malé" algoritmy je možné podat přesný matematický důkaz správnosti. - Narůstající složitosti programových systémů a požadavky na jejich bezpečnost si pak vynucují vývoj jiných „spolehlivých" formálních verifíkačních metod. 8.1 Jednoduché indukční dokazování Pro svezení znalostí se nejprve podívejte zpět na naše konvence formálního zápisu algoritmů do Oddílu 1.4. Náš výklad začneme s několika zcela jednoduchými algoritmy, jejichž jediný účel je v demonstraci využití matematické indukce pro dokazování vlastností. Příklad 8.1. Zjistěte, kolik znaků 'x' v závislosti na celočíselné hodnotě n vstupního parametru n vypíše následující algoritmus. Algoritmus 8.2. foreach i«—1,2,3,...,n-l,n do 55 foreach j 1,2,3,...,i-l,i do vytiskni ' x' ; done done Nejprve si uvědomíme, že druhý (vnořený) cyklus vždy vytiskne celkem i znaků 'x'. Proto iterací prvního cyklu (nejspíše) dostaneme postupně 1 + 2 + • • • + n znaků ;x; na výstupu, což již víme (Příklad 2.7), že je celkem ^n(n + 1). Budeme tedy dokazovat následující tvrzení: Věta. Pro každé přirozené n Algoritmus 8.2 vypíše právě \n(n + 1) znaků 'x'. Důkaz: Postupujeme indukcí podle n. Báze pro n = 0 je zřejmá, neprovede se ani jedna iterace cyklu a tudíž bude vytištěno 0 znaků 'x', což je správně. Nechť tedy tvrzení platí pro jakékoliv n0 a položme n = n0 + 1. Prvních n0 iterací vnějšího cyklu podle indukčního předpokladu vypíše (ve vnitřním cyklu) celkem |n0(n0 + 1) znaků 'x'. Pak již následuje jen jedna poslední iterace vnějšího cyklu s i ^—n=no+l a v ní se vnitřní cyklus j ^— 1,2,... ,i=n iteruje celkem n = uq + 1 -krát. Celkem tedy bude vytištěn tento počet znaků ' x': 1 1 1 -n0(n0 + 1) + n0 + 1 = -(n0 + 1 + l)(n0 + 1) = ^n(n + 1) Důkaz indukčního kroku je hotov. □ Příklad 8.3. Zjistěte, kolik znaků 'z' v závislosti na celočíselné hodnotě n vstupního parametru n vypíše následující algoritmus. Algoritmus 8.4. st ^ "z" ; foreach i^—1,2,3,...,n-l,n do vytiskni řetězec st; st ^— st . st ; (zřetězení dvou kopií st za sebou) done Zkusíme-li si výpočet simulovat pro n = 0,1,2,3,4..., postupně dostaneme počty 'z' jako 0,1,3,7,15.... Na základě toho již není obtížné „uhodnout", že počet 'z' bude (asi) obecně určen vztahem 2n — 1. Toto je však třeba 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í: Věta. Pro každé přirozené n Algoritmus 8.4 vypíše právě 2n — 1 znaků 'z' a proměnná st bude na konci výpočtu obsahovat řetězec 2n znaků ' z'. Důkaz: Postupujeme indukcí podle n. Báze pro n = 0 je zřejmá, neprovede se ani jedna iterace cyklu a tudíž bude vytištěno 0 = 2° — 1 znaků 'z', což bylo třeba dokázat. Mimo to proměnná st iniciálně obsahuje 1=2° znak 'z'. Nechť tedy tvrzení platí pro jakékoliv uq a položme n = uq + 1. Podle indukčního předpokladu po prvních n0 iteracích bude vytištěno 2n° — 1 znaků ' z' a proměnná st bude obsahovat řetězec 2n° znaků 'z' .v poslední iteraci cyklu (pro i ^—n=n0+l) vytiskneme dalších 2n° znaků 'z' (z proměnné st) a dále řetězec st „zdvojnásobíme". Proto po n iteracích bude vytištěno celkem 2n° — 1 + 2n° = 2no+1 — 1 = 2n — 1 znaků 'z' a v st bude uloženo 2 • 2n° = 2no+1 = 2n znaků 'z'. □ 56 8.2 Algoritmy pro relace V dalších pokročilejších ukázkách volíme algoritmy pro relace, které představují velice vhodnou strukturou pro algoritmické zpracování. (Pilní studenti si zajisté dokážou navrhnout sami i další podobné algoritmy.) Algoritmus 8.5. Symetrický uzávěr. Pro danou relací R na n-prvkové množině A = {a±, cl2,..., an} vytvoříme její symetrický uzávěr R takto: R 0 iteracích vnějšího cyklu Algoritmu 8.6 aktuální hodnota relace R+ udává fc-částečně tranzitivní uzávěr relace R na A. 57 Důkaz: Báze indukce pro k = 0 jasně platí, neboť věta v tom případě nic neříká. Předpokládejme nyní, že tvrzení platí pro nějaké k0 > 0 a dokažme jej i pro k = k0 + l. Zřejmě stačí uvažovat případ k0 < n. Každá dvojice (a^a,) přidaná do R+ uvnitř cyklů musí náležet do fc-částečně tranzitivního uzávěru podle definice. Zbývá zdůvodnit, proč každá dvojice (a^a,) náležející do fc-částečně tranzitivního uzávěru, ale ne do fco-částečně tranzitivního uzávěru, bude do R+ v k-té iteraci přidána. Není těžké ověřit, že (a^a,) náleží do fc-částečně tranzitivního uzávěru, právě když v relaci R nalezneme takovou cestu „po šipkách" z a,i do a,-, která přechází pouze přes prvky de kde l < k. V naší situaci vyplývá, že taková cesta musí použít i prvek (jen jednou!), a proto (di,ak) i (a^a,) náleží do fco-částečně tranzitivního uzávěru R. V A;-té iteraci tudíž bude příslušná if podmínka splněná a (a^a,) bude přidána do R+. □ 8.3 Dokazování konečnosti algoritmu Komentář: Všimněte si, že jsme se zatím v důkazech vůbec nezamýšleli nad tím, zda náš algoritmus vůbec skončí. (To není samozřejmé a důkaz konečnosti je nutno v obecnosti podávat!) Prozatím jsme však ukazovali algoritmy využívající jen f oreach cykly, přitom podle naší konvence obsahuje f oreach cyklus předem danou konečnou množinu hodnot pro řídící proměnnou, neboli náš f oreach cyklus vždy musí skončit. Ale už v příštím algoritmu využijeme while cyklus, u kterého vůbec není jasné kdy a jestli skončí, a tudíž bude potřebný i důkaz konečnosti. Metoda 8.7. Důkaz konečnosti. Máme-li za úkol dokázat, že algoritmus skončí, vhodný postup je následující: * Sledujeme zvolený celočíselný a zdola ohraničený parametr algoritmu (třeba přirozené číslo) a dokážeme, že se jeho hodnota v průběhu algoritmu neustále ostře zmenšuje. * Případně předchozí přístup rozšíříme na zvolenou k-tící přirozených parametrů a dokážeme, že se jejich hodnoty v průběhu algoritmu lexikograficky ostře zmenšují. Pozor, naše „parametry" vůbec nemusejí být proměnnými v programu. Algoritmus 8.8. Cykly permutace. Pro danou permutací tt na n-prvkové neprázdné množině A = {1,2,... ,n} vypíšeme její cykly (víz Oddíl 6.4) takto: U 1 cyklů. Po první iteraci while cyklu zbude v restrikci permutace 7T na množinu U celkem l — 1 cyklů. Podle indukčního předpokladu pak tyto zbylé cykly budou správně vypsány a algoritmus skončí. □ Komentář: Vidíte, že v tomto důkaze indukcí je indukční krok zcela triviální a důležitý je zde především základ indukce? Věta. Pokud 7r je permutace, tak vnitřní while cyklus vždy skončí a nalezne v 7T cyklus obsahující libovolný počáteční prvek x G U. Navíc všechny prvky nalezeného cyklu odebere z množiny U. Důkaz: Zde přímo zopakujeme argument důkazu Věty 6.6: Vezmeme libovolný prvek x = X\ G U a iterujeme zobrazení xi+1 = tv(xí) pro i = 1, 2..., až dojde ke zopakování prvku Xk = Xj pro k > j > 1. (To musí nastat, neboť A je konečná.) Jelikož prvek Xj byl již odebrán z U, v kroku x = Xk dojde k ukončení našeho while cyklu. Nadto je 7r prostá, a proto nemůže nastat Xk = x j = tt(xj_i) pro j > 1. Takto byl nalezen a odebrán z U cyklus (a1;..., a^-i) a důkaz je hotov. □ 8.4 Zajímavé algoritmy aritmetiky Pro další ukázky důkazových technik pro algoritmy se podíváme na některé méně známé krátké algoritmy z oblasti aritmetiky. Například „zbytkové" umocňování na velmi vysoké exponenty je podkladem známé RSA šifry: Algoritmus 8.9. Binární postup umocňování. Pro daná číslo a, b vypočteme jejích celočíselnou mocninu (omezenou na zbytkové třídy modulo m kvůli prevenci přetečení rozsahu celých čísel v počítači), tj. c = ab mod m. c 0 do if b mod 2 > 0 then c 1 a uvažme l = £q + 1. Pak zřejmě 6 > 2 a vykonají se alespoň dvě iterace cyklu. Po první iteraci bude a' = a2, b' = [b/2\ a d = (ab mod 2) mod m. Tudíž délka binárního zápisu b' bude jen £0 a podle indukčního předpokladu zbylé iterace algoritmu skončí s výsledkem c = d ■a'b' mod m = (ab mod 2 • a2[b/2i) mod m = ab mod m. □ Na závěr lekce si ukážeme jeden netradiční krátký algoritmus a jeho analýzu a důkaz ponecháme zde otevřené. Dokážete popsat, na čem je algoritmus založen? Algoritmus 8.10. Celočíselná odmocnina. Pro dané přirozené číslo x vypočteme dolní celou část jeho odmocniny r = [^/x\. p ^— x; r ^— 0; while p > 0 do while (r + p)2 < x do r f- r+p ; p <- Lp/2J ; done výsledek r ; Poznámka: Zamysleli jste se, jaký mají algoritmy v tomto oddíle vlastně význam? Vždyť stejné úlohy jistě sami vyřešíte každý jednou jednoduchou f oreach smyčkou. Podívejte se však (alespoň velmi zhruba) na počet kroků, které zde uvedené algoritmy potřebují vykonat k získání výsledku, a srovnejte si to s počty kroků oněch „jednoduchých" algoritmů. Pro skutečně velká vstupní čísla zjistíte propastný rozdíl - s takovým „jednoduchým" algoritmem, třeba 'f oreach i i— 1, . . .b do c <— c-a mod m done', se pro obrovské hodnoty b výsledku nikdy nedočkáte, kdežto Algoritmus 8.9 stále poběží velmi rychle. (Spočítáte, jak rychle?) Obdobně je tomu u Algoritmu 8.10. Rozšiřující studium Smyslem této lekce bylo především ukázat, že u jednoduchých algoritmů lze (a je vhodné) matematicky dokazovat jejich správnost. Samozřejmě je iluzorní předpokládat, že obdobné důkazy správnosti podáme i pro velké softwarové projekty čítající až milióny řádků, ale postupy a techniky naučené při ověřování jednoduchých algoritmů s úspěchem využijete i při kontrole a ladění jednotlivých částí velkých projektů. Mimoto jsme se na příkladech pokusili ukázat několik zajímavých myšlenek a triků návrhu algoritmů, z nichž zvláště binární umocňování či centrální myšlenka „dynamického" Algoritmu 8.6 pro tranzitivní uzávěr se opakují v mnoha jiných algoritmech. O mnoha různých pokročilých technikách tzv. formální verifikace programů se v případě zájmu dozvíte v pokračujícím studiu. Tyto techniky jsou schopny na vhodném „modelu" rutinně a matematicky přesně ověřovat (ne)existenci různých běžných programátorských chyb. 60 9 Jednoduchý deklarativní jazyk Úvod Nyní se vracíme a pokračujeme dále v tématu předchozí lekce, tj. budeme se zabývat matematickým dokazováním vlastností a správnosti algoritmů. Třebaže mnohým mohla přijít už Lekce 8 více než dost formální, není tomu úplně tak; v následujícím si ukážeme (ještě) přesnější přístup založený na myšlenkách funkcionálního programování. Zároveň si tak i procvičíme správné chápání a používání matematických deňnic. Cíle Prvořadě jde o podání matematicky přesné deňnice jednoduchého deklarativního „programovacího" jazyka pro potřeby formálního dokazování příslušně zapsaných algoritmů. Na tomto základě pak v příští lekci postavíme přehled důkazových technik pro algoritmy. O „správnosti" programů, podruhé Vraťme se zpět k fundamentální otázce - jak se máme přesvědčit, že program funguje „správně"? * V případech, kdy je třeba mít naprostou jistotu správné funkce, je jedinou „dostatečně spolehlivou" možností podat formální matematický důkaz chování algoritmu. - Úplné matematické důkazy pro svou složitost dokáží obsáhnout pouze „malé" algoritmy. Přesto je jejich přesné dokazování důležité, neboť právě malé algoritmy obvykle tvoří stavební kameny rozsáhlejších systémů (kde již pak nastupují jiné metody verifíkace). * A co tedy důkazy vlastností symbolicky zapsaných (procedurálních) algoritmů z Lekce 8? Všimli jste si, co v nich bylo problematickým bodem? - Náš procedurální zápis algoritmu totiž přesně nedefinuje, co je to „elementární krokCÍ výpočtu - to je sice většinou docela zřejmé, někdy však může hlavní problém nastat právě zde. Sice by bylo možné použít k definici některý z přesných teoretických modelů výpočtu jako je Turingův stroj (nebo třeba i některý vhodný z reálných programovacích jazyků), avšak pak by se formální důkazy staly velmi složitými. * Vhodnějším řešením (pro potřeby formálního dokazování) se jeví příklon k „funkcionálnímu" zápisu algoritmů pomocí matematicky zcela přesných deklarací. 9.1 Popis jednoduchého deklarativního jazyka Z těchto výše popsaných důvodů se nyní soustředíme na podání matematicky zcela přesné definice jednoduchého deklarativního „programovacího" jazyka. Začneme jeho syntaxí (Definice 9.1) a poté přejdeme k jeho sémantice (Definice 9.2) - tedy k formalizaci takto zapsaných pojmů „výpočetního kroku" a „výpočtu". Definice 9.1. Deklarativní programovací jazyk (pro přednášky FI: IB000). * Nechť Var = {x,y, z,... } je spočetná množina proměnných. 61 * Nechť Num = {0,1,... 52,... 397,... } je množina všech dekadických zápisů přirozených čísel. * Nechť Fun = {/, g,h,...} je spočetná množina funkčních symbolů. Ke každému / G Fun je přiřazeno číslo a G N, které nazýváme arita f. Dále předpokládáme, že pro každé a G N existuje nekonečně mnoho / G Fun s aritou a. * Množina výrazů Exp je (induktivně) definována následující abstraktní syntaktickou rovnicí: E ::= x | n Ei + E2 | Ei — E2 | Ei * £/2 | Ei -ŕ- E2 | (Ei) f(Ei,---,Ea) if Ei then ^ else ^ fi V uvedené rovnici je x G Var, n G Num, Ei G -Erp jsou výrazy, / G Fnn a a G N je arita funkce /. Poznámka: Dobře si povšimněte, že ve smyslu Lekce 6 tato induktivní Definice 9.1 není jednoznačná. Neboli jeden výraz, jako třeba a + 1 — 2 * 3 lze odvodit několika různými způsoby. Praktickým důsledkem pak je, že není zřejmá „priorita operací", což lze na druhou stranu ale vždy snadno napravit přidáním dostatečného počtu závorek. Tuto abstraktní volnost syntaxe ponecháváme z čistě pragmatického důvodu snadnějšího méně formálního zápisu výrazů. Nakonec bude priorita operací přesně určena následující Definicí 9.2. Komentář: Pro lepší pochopení uvádíme několik příkladů výrazů (Exp) z definice. 254 - 2 + 3*4 - /(2)-5(5) - f(2+x,g(y,3*y)) - if x — 1 then (2 + f(y)) else g(x, x) fi (čtěme „if i-l/O...") Definice: Deklarace (v jazyce Definice 9.1) je konečný systém rovnic tvaru fi(xi,--- ,xai) = Efl fn(xi,--- ,XaJ = Efn kde pro každé 1 < i < n platí, že fi G Fun je funkce arity G Var jsou proměnné a Ei je výraz, v němž se mohou vyskytovat pouze proměnné Xi,..., xai a funkční symboly fi,...,fn. Komentář: Opět uvádíme pro osvětení několik příkladů deklarací z naší definice. • f(x) = if x then x * f (x — 1) else 1 fi f (x) = g(x-l,x) g(x,y) = if x then f(y) else 3 fi Později uvidíme, proč a jak je konvencí našich výpočtů tvrdit 0 — 1 "=" 0. • g(x, y) = if x — y then x else y fi • f(x) = f(x) (Nezapisuje toto náhodou „nekonečnou smyčku1'?) 62 Deklarace nám udává „soubor pravidel", podle kterých budeme vyhodnocovat (Definice 9.2) daný výraz. Jinak také lze deklaraci chápat jako zobecnění rekurentních deňnic funkcí. Neformálně řečeno, deklarace je tedy souborem pravidel pro určení hodnot funkcí s argumenty stojících na levé straně. Hodnoty jsou určeny běžnými aritmetickými výrazy používajícími číselné konstanty, argumenty funkce a hodnoty jiných zde deklarovaných funkcí. Tento poslední aspekt zavádí do deklarací „rekurzivnost" a dává tak deklaracím jejich „výpočetní sílu". Nedívejte se na deklarace v žádném případě pohledem procedurálního programování (tedy nejsou to žádná přiřazení hodnot proměnným), lépe na ně nahlédněte pohledem funkcionálního programování. 9.2 Formalizace pojmu „výpočet" Za výpočet (nad A) budeme považovat posloupnost úprav výrazů, které jsou „postaveny" na naší uvažované deklaraci A. To je formálně podchyceno v následujících dvou definicích. Srovnejte si Definici 9.2 také s neformálním pojetím algoritmů jako konečných posloupností elementárních kroků v Oddíle 1.4. Definice: Nechť A je deklarace. Symbolem Exp(A) označíme množinu všech výrazů E, které splňují zároveň tyto dvě podmínky: - E neobsahuje žádnou proměnnou. - Jestliže E obsahuje funkční symbol /, pak / byl v A deklarován (tj. na levé straně některé rovnice A). Komentář: Dívejte se na množinu Exp(A) jako na soubor „platných vstupů" (jako u programu) pro deklaraci A, nad kterými bude prováděn výpočet. Fakt: Množinu Exp(A) lze podle Definice 9.1 zadat také induktivně: E '.'.= n | (-Ei) | Ei + E2 I ei — e2 \ Ei * e2 \ Ei -G e2 f (Ei, ■■■ ,Ea) I if Ei then E2 else E3 fi V uvedené zápise je n G Num, f G Fun je funkční symbol deklarovaný v A a a G N je arita tohoto /. Jednotlivý krok výpočtu Definice 9.2. Výpočet a krok výpočtu v našem deklarativním jazyce. Relaci „krok výpočtu" 1—>■ C Exp(A) x Exp(A) definujeme induktivně; místo (E,F) G 1—>■ budeme psát E 1—>■ F, neboť se pro naše potřeby bude zhusta jednat o funkci. i) n i—)- n pro každé n G Num. ii) Pro E = (Ex) definujeme krok výpočtu takto: . Jestliže Ei i->- F G Num, pak (Ei) i->- F. . Jestliže Ei i->- F g Num, pak (Ei) i->- (F). iii) Pro E = Ex + E2 definujeme krok výpočtu takto: • Jestliže Ei,E2 G Num, pak Ei + E2 1—>■ z, kde z je dekadický zápis čísla Ei + E2. . Jestliže Ei G7 Num a Ex i->- F, pak Ex + E2 i->- F + E2. 63 . Jestliže Ei G Num a E2 Num a E2 >->■ F, pak Fx + E2 >->■ Fx + F. iv) Pro E = Ei — E2 definujeme krok výpočtu takto: • Jestliže F1;F2 G Num, pak Ei — E2 1—>■ z, kde z je dekadický zápis čísla max{0, Fx — F2}. (Pozor na nezápornost výsledku odčítání!) . Jestliže Ei g Num a Ex i->- F, pak Fx - F2 i->- F - F2. • Jestliže Fx G iVura a E2 ^ Num a £2 H- F, pak Fx — F2 1—>■ Ei — F. v) Pro E = Ex * E2 definujeme krok výpočtu takto: • Jestliže Ei,E2 G Num, pak Ei * E2 1—>■ z, kde z je dekadický zápis čísla Ei * E2. • Jestliže Ei g Num a Ex 1—> F, pak Fx * F2 1—>- F * F2. • Jestliže Fx G Ära a E2 £ Num a F2 1—>- F, pak Fx * F2 1—>- Fx * F. vi) Pro E = E\ -^r E2 definujeme krok výpočtu takto: • Jestliže E\,E2 G Num, pak E\ 4- F2 1—>- z, kde z je dekadický zápis (celé části) čísla [-El/-£_._!• Pokud E2 = 0, je z = 0 (dělení nulou!). • Jestliže Ei g Num a kde E\ 1—>■ F, pak E\ 4- F2 1—>■ F 4 F2. • Jestliže Fx G iVura a E2 ^ Num a E2 \—)• F, pak Fx 4 F2 1—>■ Ex 4 F. vii) Pro E = if íľi then i?2 else .E3 fi definujeme krok výpočtu takto: • Jestliže Fx G Ära a Eľ = 0, pak if Eľ then F2 else F3 fi 1—>■ (F3). • Jestliže Ei G Ära a Fx ^ 0, pak if Eľ then F2 else F3 fi 1—>■ (F2). • Jestliže Fx ^ iVm a E\ \—> F, pak if E\ then F2 else F3 f i 1—)• if F then F2 else F3 f i. viii) Pro E = f (Ei, • • • , Ek) definujeme krok výpočtu takto: . Jestliže F1; • • • ,Ek G ÍWíto, pak /(Fx, • • • , Ek) 1-4 (F/(xx fFx, • • • fFfc)). (V tomto formálním zápise se jedná o prosté „textové" dosazení hodnot F« za proměnné x i v deklaraci E f funkce f v A.) . Jinak /(Fx, • • • , Ffc) 1-4 f(E1, ■■■ , E^, F, Ei+1, ■ ■ ■ , Ek), kde i je nejmenší index pro který platí Fj G" iVm a Fj 1—)• F. V zápise jednotlivých bodů vždy platí, že E\,E2,--- G Exp (A). Znak = zde znamená „textovou" rovnost na množině výrazů Exp. Při nejednoznačnosti vždy aplikujeme první použitelné pravidlo naší definice na prvním použitelném místě zleva. Definice: Reflexívní a tranzitivní uzávěr relace 1—>■ značíme 1—>■* („výpočet"). Poznámky ke kroku výpočtu Tato rozsáhlá a důležitá definice si zaslouží několik podstatných připomínek. Za prvé si dobře povšimněte některých „aritmetických" aspektů výpočtu. - Výsledek odečítání je vždy nezáporný - všechna záporná čísla jsou nahrazena nulou. - Výsledek dělení je vždy celočíselný, počítáme jeho dolní celou část. 64 - Dělení nulou je definováno (není chybou), výsledkem je opět nula. Další připomínka se týká pořadí vyhodnocování ve výrazu - - to je přesně dáno pořadím pravidel v Definici 9.2, neboli vždy aplikujeme první pravidlo, které aktuálně lze použít na výraz a to na prvním možném místě zleva. Mimo jiné je takto „definována" nejvyšší priorita vyhodnocení uzávorkovaného výrazu. Uvědomte si dobře, že definice výpočetního kroku i—y je (poněkud skrytě) rekurzivní. Třeba krok (2*1) i—)• 2 je ve skutečnosti jediným krokem, přestože „vyvolá" použití dvou pravidel v sobě - vyhodnocení součinu i odstranění závorek. Poznámka: Ještě si uveďme, že naše definice připouští jistý nedeterminismus (poznámka jen pro čtenáře, kteří o nedeterminismu už slyšeli): Je možné mít v deklaraci A zadaných více rovnic pro tutéž funkci /(), pak však i—> přestává být funkcí. My se touto možností nebudeme zabývat. 9.3 Příklady výpočtů a důkazů Po suchém formálním vysvětlení si na příkladech ukážeme, jak dopadá „výpočet" nad našimi deklaracemi. Definice 9.2 popisuje jediný krok výpočtu, ale kdy má vlastně celý výpočet (tj. iterace jednotlivých elementárních kroků podle této definice) skončit? Jak uvidíme i v příkladech, ukončením výpočtu budeme rozumnět stav, kdy aktuální výraz je numerickou konstantou (podle Definice 9.2.i už pak k další změně stejně nedojde.) Příklad 9.3. Ukážeme si několik ilustrativních „výpočtů" nad různými deklaracemi. Všimněte si, že při úpravách výrazů si dovolujeme (oproti formální dennici) pro zpřehlednění vynechávat zdvojené a vnější závorky. • Uvažme deklaraci f(x) = if x then x * f (x — 1) else 1 fi. Pak třeba /(3) i—>■* 6, neboť /(3) i-4 if 3 then 3 * /(3 - 1) else 1 fi i-4 3 * /(3 - 1) i-4 3*/(2) i-4 3 * (if 2 then 2 */(2 - 1) else 1 fi) i-4 3 * (2 */(2 - 1)) i-4 3*(2*/(l)) i-4 3 * (2 * (if 1 then 1 */(l - 1) else 1 fi)) i-4 3*(2*(1*/(l-l))) i-4 3*(2*(l*/(0))) i-4 3*(2*(l*(if0 then 0*/(0-l) else 1 fi))) i-4 3 * (2 * (1 * 1)) i-4 3 * (2*1) 1-4-3*2 1-4-6. • Uvažme deklaraci f(x) = g(x — l,x) a g(x,y) = if x then f(y) else 3 fi. Pak například/(3) i—>■* /(3), neboť /(3) i—>• 0(3 -1,3)^ g(2, 3) i->- if 2 then /(3) else 3 fi i—>• /(3). • Uvažme deklaraci f(x) = f(x). Pak pro každé n G Num platí /(n) /(n) a podobně /(/(n)) /(/(n)). Ale /(/(2 + 3)) ^ /(/(5)) ^ /(/(5)). □ Příklad 9.4. Jak bude přesně vyhodnocen následující výraz? 1+2-3+4-5 Řešení: Klíčem k řešení tohoto je správné pochopení Definice 9.2. Prvním použitelným pravidlem našeho deklarativního jazyka je to pro E = E\ + E2. Je použito 65 na prvním místě zleva, tj. pro E\ = 1 a, E2 = 2 — 3 + 4 — 5. Podle definice je tedy nutno upravit Ei G N um i E2 Num, neboli definici aplikovat (rekurzivně) na výraz E2. Při vyhodnocování E2 = E' = 2 — 3 + 4 — 5je prvním použitelným pravidlem opět to pro E' = E[ + E'2, přičemž E[ = 2 — 3 a E2 = 4 — 5. Podle definice je nutno v tomto místě vyhodnotit výraz E[ \—y 0. Celkem v prvním kroce 1 + 2- 3 + 4- 5 i—>• 1+0+4-5. Nakonec stejným postupem získáme: 1 + 0 + 4-5^1 + 0 + 0^1+0^1 □ Důkaz správnosti programu Celá naše formalizace deklarativního jazyka směřuje k přesným matematickým důkazům algoritmů, takže si takové hned názorně ukážeme. Příklad 9.5. Pro ukázku uvažme deklaraci A obsahující pouze rovnici f(x) = if x then x * f (x — 1) else 1 fi. Věta. Pro každé n G N platí /(n) i—y* m, kde m = n\. Důkaz povedeme indukcí podle n: . Báze n = 0. Platí /(O) ^ if 0 then 0 * /(O - 1) else 1 f i i—>■ 1 a také 0! = 1. • Indukční krok. Nechť n + 1 = k. Pak /(k) ^ if k then k * /(k - 1) else 1 fi ■->■ k * /(k - 1) ■->■ k * /(w), kde w = k — 1 = n. Podle LP. platí /(w) i—>■* u, kde u = n\. Proto k * /(w) i—y* k * u i—)- v, kde v = (n + 1) • n\ = (n + 1)!. ^ Komentář: Vidíte, jak „hutný" a přitom formálně zcela přesný zápis důkazu naše formalizace umožňuje? Promyslete si podrobně všechny jeho kroky ještě jednou a dobře si uvědomte, co z čeho vyplývá a jak na sebe navazují. Důkazy „neukončenosti" výpočtů Jinou častou otázkou je, jak zdůvodnit, že některý výpočet neskončí. K tomu využijeme následující tvrzení navazující na látku o uzávěrech relací: Fakt: Nechť A je deklarace. Pro každé i G N definujeme relaci i—y 1 C Exp(A) x Exp(A) předpisem i—y 1 = vi—y o ■ ■ ■ o i—yy Dále definitoricky klademe i—y 0 = {(E, E) | E G s-v-' i Exp(A)}. Pak pro tranzitivní uzávěr (relaci „výpočet") platí i—y* = |J^0 i—y 1. Podle předchozího faktu platí, že E \—y* F právě když E i—>■1 F pro nějaké i G N. Navíc musí existovat nejmenší i s touto vlastností. Toto pozorování bývá velmi užitečné v důkazech „neukončenosti" výpočtů. 66 Příklad 9.6. Uvažme deklaraci f(x) = f(x). Pak pro každé n G Num platí, že neexistuje žádné m G Num takové, že /(n) i—>■* m. Důkaz sporem: Předpokládejme, že existují n, m G Num takové, že /(n) i—>■* m. Pak existuje nejmenší i G N takové, že /(n) i—y 1 m. Jelikož výrazy /(n) a m jsou různé, platí z > 0. Jelikož !—)•*= i—)•o i—)• a /(n) i—>■ /(n), platí /(n) i—>■m, což je spor s minimalitou i. □ Rozšiřující studium Místo suchého studia si pro lepší seznámení s naším deklarativním jazykem mohou čtenáři pohrát s jeho online interpretem poskytnutým Vaškem Brožkem na http://arran.fi.muni.cz/ibOOO/web_vyhodnot.cgi nebo s obdobným klientským (javaskriptovým) udělátkem vyvinutým Martinem Jurčou http://arran.fi.rnuni.cz/ibOOO/js-jurca/. Také je velmi vhodné si srovnat zde předloženou látku s předměty vyučujícími tzv. funkcionální programování (na FI třeba IB015). K samotnému pokročilému dokazování vlastností deklarativních algoritmů přistoupíme v příští lekci. 67 10 Důkazové postupy pro algoritmy Úvod Nakonec si ukážeme, jak formální deklarativní jazyk z Lekce 9 využít k formálně přesným induktivním důkazům vybraných algoritmů. Celý text tak bude sestávat jen a jen z ukázek takových důkazů. Dá se říci, že tato lekce je „vrcholem" v naší snaze o matematické dokazování algoritmů v informatice. Soustřeďte se v ukázkách důkazů na pochopení, jak jednotlivé formální matematické kroky korespondují s průběhem algoritmů. Cíle Na podkladu jednotlivých variant důkazů matematickou indukcí z Lekce 2 si ukážeme přehled formálních indukčních důkazových technik aplikovaných na vybrané algoritmy (v zápisech deklarativního jazyka). 10.1 Technika „fixace parametru" Na první pohled při snaze dokazovat vlastnosti algoritmů indukcí asi budou mít čtenáři nej větší komplikace tam, kde se v algoritmu vyskytuje najednou více parametrů. S kterým z nich potom můžeme indukci vést? Odpovědi nám poskytnou následující dvě techniky. První technika důkazu prostě dopředu za některé parametry dosazuje (obecně zvolené) konstanty. Tato technika je vhodná pro případy, kdy je sice v algoritmu více parametrů, ale „zjevně" dochází ke změně jen jednoho (nebo části) z nich a chování algoritmu ke zbylým „neměnným" parametrům je dobře předvídatelné. Příklad 10.1. Uvažme deklaraci A obsahující pouze rovnici g(x, y) = if x then y + g(x — 1, y) else 0 fi. Věta. Pro každé m, n G N platí g(m, n) i—>■* z, kde z = m ■ n. Důkaz: Budiž n G N libovolné ale pro další úvahy pevné. Dokážeme, že pro každé m G N platí g(m, n) i—>■* z, kde z = m ■ n, indukcí vzhledem k m. * Báze m = 0. Platí g(0, n) i->- if 0 then n + g(0 - 1, n) else 0 fi i—>- 0. * Indukční krok. Nechť m + 1 = k. Pak g(k, n) i—> if k then n + g(k — 1, n) else 0 fi i—> n + g(k — l,n) i—> n + g(w,n), kde je w = m. Podle I.P. platí g(w, n) i—>* u pro u = m ■ n. Dále n + g(w, n) i—>* n + u i—> v, kde v = n + (m • n) = (m + 1) • n = k ■ n, a tím jsme dohromady hotovi s důkazem g(k, n) v. □ 10.2 Technika „indukce k součtu parametrů" Druhou techniku je vhodné použít především v případech, kdy se v průběhu algoritmu vždy některý parametr zmenšuje, ale pokaždé je to některý jiný parametr, takže v indukci se nelze zaměřit jen na jeden z nich. Příklad 10.2. Uvažme deklaraci A obsahující pouze rovnici g(x, y) = if x then (if y then g(x — 1, y) + g(x, y — 1) else 0 fi) else 0 fi. 68 Věta. Pro každé m, n G N platí g (m, n) i—>■* 0. Tvrzení této věty přímo nelze dokázat indukcí vzhledem k m, ani indukcí vzhledem k n, neboť u žádného z m, n nemáme zaručeno, že se vždy zmenší. Důkaz lze ovšem postavit na faktu, že se vždy zmenší alespoň jeden z m, n, neboli se vždy zmenší součet m a n. To znamená, že výše uvedené tvrzení nejprve přeformulujeme do následující (matematicky ekvivalentní) podoby: Věta. Pro každé i G N platí, že jestliže i = m + n pro kterákoliv m,n G N, pak g (m, n) i—>■* 0. Důkaz indukcí vzhledem k i: Báze i = 0 znamená, že 0 = m + n pro m, n G N, neboli m = n = 0. Dokazujeme tedy, že g(0, 0) i—>■* 0. Platí 0(0, 0) i->- if 0 then (if 0 then g(0 -1,0)+ g(0, 0-1) else 0 fi) else 0 fi ■->■ 0 . Indukční krok. Nechť i + 1 = m + n, kde m, n G N. Nyní rozlišíme tři možnosti (z nichž první dvě jsou svým způsobem jen rozšířeními předchozí báze indukce): * Pro m = 0 platí g(0, n) (->• if 0 then (if n then g(0 - 1, n) + g(0, n - 1) else 0 fi) else 0 fi (->• 0 . * Pro m > 0, n = 0 platí if m then (if 0 then g(m -1,0)+ g(m, 0-1) else 0 fi) else 0 fi i—>-ifO then g(m - 1,0) + g(m,0 - 1) else 0 fi (->• 0. * Pro m > 0, n > 0 platí g(m, n) i—> if m then (if n then g(m — 1, n) + g(m, n — 1) else 0 fi) else 0 f i i—>-i—> if n then g(m — 1, n) + g(m, n — 1) else 0 fi i—> g(m — 1, n) + g(m, n — 1). Podle I.P. platí g(m — l,n) i—>* 0 a současně g(m,n — 1) i—>* 0, proto g(m — 1, n) + g(m, n - 1) i—>* 0 + g(m,n — l) \—>* 0 + 0 i—> 0. Tím jsme s důkazem matematickou indukcí hotovi. □ Zajímavější verze Udělejme si předchozí nudný příklad trochu zajímavějším (ale co se týče důkazu stále v podstatě stejným...). Příklad 10.3. Uvažme deklaraci A obsahující pouze rovnici g(x, y) = if x then (if y then g{x — 1, y) + g(x, y — 1) else 1 fi) else 1 fi. Věta. Pro každé m, n G N platí g (m, n) i—>■* k, kde k = (m^n) (kombinační číslo). 69 Toto tvrzení opět budeme dokazovat indukcí vzhledem k i = m + n. Vzpomeňte si nejprve na známý Pascalův trojúhelník kombinačních čísel, který je definovaný rekurentním vztahem a + 1\ / a \ fa b+l) = \b+l) + \b Nepřipomíná to trochu naši deklaraci? Je však třeba správně „nastavit" význam parametrů a, b. Důkaz indukcí vzhledem k i: Báze i = 0 znamená, že 0 = m + n pro m, n G N, neboli m = n = 0. Dokazujeme tedy, že g(0, 0) i—>■* 1. Platí 0(0, 0) i-+ if 0 then (if 0 then g(0 -1,0)+ g(0, 0-1) else 1 fi) else 1 fi i-+ 1. Indukční krok. Nechť i + 1 = m + n, kde m, n G N. Opět rozlišíme stejné tři možnosti: * Pro m = 0 platí Q = 1 a g(0, n) (->• if 0 then (if n then g(0 - 1, n) + g(0, n - 1) else 1 fi) else 1 fi (->• 1. * Pro m > 0, n = 0 platí (™) = 1 a • if m then (if 0 then g(m -1,0)+ g(m, 0-1) else 1 fi) else 1 f í i—>-if 0 then g(m - 1,0) + g(m,0 - 1) else 1 fi (->• 1. * Pro m > 0, n > 0 platí g(m, n) i—>■ if m then (if n then g(m — 1, n) + g(m, n — 1) else 1 fi) else 1 fi i—> \—> if n then g(m — 1, n) + g(m, n — 1) else 1 fi i—>■ p(m — 1, n) + g(m, n — 1). Podle I.P. platí g(m — l,n) i—>■* ki, kde ki = (mmÍ^n), a současně p(m, n — 1) i—>* k2, kde k2 = (m^ 1)- Přitom z Pascalova trojúhelníka plyne m + n — l\ /m + n— l\ /(m + n — 1) + l\ /m + n m — 1 y \ m J \ m J \ m a proto g(m — 1, n) + g(m, n — 1) i—ki + k2 i—k m □ 10.3 Technika „zesílení dokazovaného tvrzení" Velmi častou situací při dokazování algoritmu je, že se zajímáme o hodnoty některých proměnných nebo „výstupy" některé funkce, ale ke správnému matematickému důkazu musíme „postihnout" i chování jiných funkcí a proměnných v algoritmu. Taková situace pak typicky vede na potřebu zesílení požadovaného tvrzení v matematické indukci. Příklad 10.4. Uvažme deklaraci A obsahující tyto rovnice: f(x) = if x then h(x) else 1 fi h(x) = if x then f{x — 1) + h(x — 1) else 1 fi 70 Věta. Pro každé n G N platí /(n) i—>■* m, kde m = 2n. Požadované tvrzení bohužel nelze přímo dokázat indukcí podle n. Řešením je přeformulování dokazovaného tvrzení do silnější podoby, kterou již indukcí dokázat lze: Věta. Pro každé n G N platí /(n) i—>■* m a h(n) i—>■* m, kde m = 2n. Důkaz, již poměrně snadno indukcí vzhledem k n: * Báze n = 0. Platí /(O) ^ if 0 then h(0) else 1 fi ■->■ 1, kde 2° = 1, h(0) ^ if 0 then /(O - 1) + h(0 - 1) else 1 fi i->- 1. * Indukční krok: Nechť n + 1 = k, pak platí /(k) i-)- if k then h(k) else 1 f i i—>- h(k) \-> i—)• ifkthen /(k - 1) + h(k - 1) else 1 fi i—>• f(k-l) + h(k-l) i—>• /(w) + /i(k-l), kde w = A; — 1 = n. Podle I.P. platí /(w) i—>■* m, kde m = 2n. Zároveň také (naše „zesílení") platí i /i(w) i—>■* m, a proto /(w) + h(k — 1) i—)-* m + /?,(k—1) i—)-* m + /i(w) i—>■* m + m i—y q, kde q = m + m = 2m = 2 • 2n = 2n+1 = 2fc. Proto tranzitivně f(k) \—y q a první část našeho tvrzení platí i pro n + 1 = k. Podobně je třeba ještě dokončit druhou část tvrzení. h(k) i->- ifkthen/(k-l) + fc(k-l) else lfi ^ /(k-l) + Mk-l) ^* /(w) + Mk-l), kde w = k — 1 = n. Podle I.P. platí /(w) i—>■* m, kde m = 2n, a také /i(w) i—>■* m, tudíž opět f(w) + h(k—l) i—)-* m + h(k — 1) \—>* m + h(w) i—>■* m + m i—>■ q, kde g = m + m = 2 • 2n = 2n+1 = 2k. Proto h(k) \—y q a i druhá část našeho tvrzení platí pro n + 1 = k. □ 10.4 Dva dobře známé školní algoritmy Následuje příklad, který zajisté každý, kdo přičichl k programování, už v nějaké podobě pozná. My si jej uvádíme především z výukových důvodů. Číslice dekadického zápisu Příklad 10.5. Mějme přirozené číslo x. Jednotlivé číslice i-tého řádu jeho dekadického zápisu získáme deklarací c(x, i) = if i then c(x 4-10, i — 1) else x — 10 * (x 4-10) fi. Dokažte: 71 Věta. Pro každá m,i G N platí c(m, i) i—>■* s, kde s je číslice řádu i (počítáno od nultého zprava) v dekadickém zápise čísla m, nebo s = 0 v případě, že dekadický zápis čísla m má méně než i + 1 číslic. Důkaz: Použijeme techniku fixace parametru m při indukci podle i. * Báze i = 0. Platí c(m, 0) i—>■* m — 10 * (m -G 10) i—>■* t, kde t = m mod 10 . V tomto výsledku mod znamená známou funkci modulo definovanou vztahem x = [x/y\ ■ y + (x mod y). Tudíž t je poslední číslicí dekadického zápisu m. * Indukční krok: Nechť i + 1 = j, pak platí c(m, j) i—>■ if j then c(m -G10, j — 1) else m — 10 * (m -G10) fi i—> i->- c(m 4 10, j - 1) ■->■* c(p, w), kde p = L^i/10j a w = j — 1 = i. Podle I.P. platí c(p, w) i—>■* t a t je číslice i-tého řádu dekadického zápisu čísla p. Jelikož m = 10p + (m mod 10) a násobení deseti v dekadické soustavě znamená posun číslic v zápise „o jedno doleva", je t zároveň číslice i + 1 = j-tého řádu dekadického zápisu čísla m. To je přesně co bylo třeba dokázat.n Euklidův algoritmus Již z dávných dob antiky pochází následující zajímavý a koneckonců velmi jednoduchý algoritmus teorie čísel. (Víte, pro zajímavost, jestli se tehdy vůbec mluvilo o algoritmech a programech, nebo jako to bylo?) Věta 10.6. Uvažme deklaraci A obsahující pouze rovnici g(x, y) = if x — y then g(x — y, y) else (if y — x then g(x, y — x) else x fi) fi. Pak pro každé nenulové m, n G N platí g (m, n) i—>■* z, kde z je nejvčtší společný dělitel čísel m, n. Důkaz indukcí k i = m + n. (Tj. dokazujeme následující tvrzení: Pro každé i > 2 platí, že jestliže i > m + n, kde m, n G N, m, n > 0, pak z je největší společný dělitel čísel m, n.) V bázi pro i = 2 je m, n = 1 a platí 0(1,1) i—y if 1 - 1 then g(l - 1,1) else (if 1 - 1 then g(l, 1-1) else 1 fi) fi ■->• i—^ if 0 then g(l - 1,1) else (if 1 - 1 then g(l, 1-1) else 1 fi) fi (->• if 1 - 1 then g{l, 1-1) else 1 fi (->• if 0 then g{l, 1-1) else 1 fi (->• 1. Indukční krok. Nechť i + 1 = m + n kde m, n G N. Probereme tři možnosti: * m = n. Pak g (m, n) i—> if m — n then g (m — n, n) else (if n — m then g (m, n — m) else m fi) fi i—> if 0 then g (m — n, n) else (if n — m then g(m, n — m) else m fi) fi i—> if n — m then g (m, n — m) else m fi i—> if 0 then g(m, n — m) else m fi i—> m . 72 * m < n. Pak g (m, n) i—> if m — n then g (m — n, n) else (if n — m then g (m, n — m) else m fi) fi i—> if O then g (m — n, n) else (if n — m then g(m, n — m) else m fi) fi i—> if n — m then g (m, n — m) else m fi i—> if z then g(m, n — m) else m fi i—> g(m, n — m) i—> g(m, k), kde k = n —m. Platí m + k = m + (n — m) = n < i, takže podle LP. také platí g(m, k) i—>* z, kde z je největší společný dělitel čísel m a n — m. Ověříme, že z je největší společný dělitel čísel man. - Jelikož číslo z dělí čísla m a n — m, dělí i jejich součet (n — m) + m = n. Celkem z je společným dělitelem man. - Buď d nějaký společný dělitel čísel man. Pak d dělí také rozdíl n — m. Tedy d je společný dělitel čísel m a n — m. Jelikož z je největší společný dělitel čísel m a n — m, nutně d dělí z a závěr platí. * m > n. Pak g(m,n) h^* #(m-n,n) #(k,n), kde k = m — n. Podle LP. platí g(k, n) i—>* z, kde z je největší společný dělitel čísel m — n a n. Podobně jako výše ověříme, že z je také největší společný dělitel čísel man. □ Poznámka: Jak byste výše uvedený zápis Euklidova algoritmu vylepšili, aby správně „počítal" největšího společného dělitele i v případech, že m = 0 nebo n = 0? Co v takových případech selže při současném zápise? 73 11 Nekonečné množiny a Zastavení algoritmu Úvod Bystrého čtenáře může snadno napadnout 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, 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á právě 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í. 11.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 11.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á" jako množina B, právě když existuje injek-tivní funkce / : A —>• B. Množiny A a, B jsou „stejné velké" 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" velmi dobře 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. * 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ě 11.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í. 74 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 11.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 11.2. Neexistuje žádné surjektivní zobrazení g : N —y R. Důsledek 11.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 11.2 sporem): Nechť takové g existuje a pro zjednodušení se omezme jen na funkční hodnoty v intervalu (0,1). Podle hodnot zobrazení g si takto můžeme „uspořádat" dekadické zápisy všech reálných čísel v intervalu (0,1) po řádcích do tabulky: Nyní sestrojíme číslo a G (0,1) následovně; jeho i-tá číslice za desetinnou čárkou bude I, pokud v 2-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, g byla surjektivní, takže tam a musí být!) Kostrukce však ukazuje, že a se od každého čísla v tabulce liší na aspoň jednom desetinném místě, to je spor. (Až na drobný technický detail s rozvojem .. .9.) □ II. 2 „Naivní" množinové paradoxy Analogickým způsobem k Větě 11.2 lze dokázat následovně zobecnění. Věta 11.4. Nechť M je libovolná množina. Pak existuje injektivní zobrazení f : M —y 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 G 2M, musí existovat y G M takové, že g(y) = K. Nyní rozlišíme dvě možnosti: 9(0) 9(1) 9(2) 9(3) 2(4) 0. 15427578325 0. 4 0. 1 0. 3 0. 9 K = {x G M I x g g (x)}. 75 - y G g (y). Tj. y G K. Pak ale y £ g (y) z definice Ä", spor. - y g (y)- To podle definice Ä" znamená, že y E K, tj. y G spor. ^ Komentář: Dvě navazující poznámky. • Technika použitá v důkazech Vět 11.2 a 11.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: a b c d g(o) V - - v ■■■ 9(b) — 9{c) - - v ••■ g(d) v v ••• Symbol y/ resp. — říká, že prvek uvedený v záhlaví sloupce patří resp. nepatří do množiny uvedené v záhlaví řádku. Tedy např. d G g (b) a a 0 g (ď). 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 11.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í mohutností 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ůř... 76 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 E X ? - Ano. Tj. X E X. Pak ale X splňuje X g X. - Ne. Pak X splňuje vlastnost X ^ X, tedy X je prvkem X, tj., X G 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. 11.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ý algoritmus 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é i G N označme symbolem Pí program f (i). Pro každý program P tedy existuje j G N takové, že P = Pj. * 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é z G N označme symbolem Ví vstup g (i). * 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 11.6. Neexistuje program Halt, který by pro vstup (Pí, 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: 77 input k; if iJa/£(k,k) =ano then while true do ; done (Program Díag(k) má na rozdíl od Halt jen jeden vstup k, což bude důležité.) Fungování programu Díag lze znázornit za pomocí následující tabulky: Po Pi P2 p3 ... V — — v ••• v1 — - v ••■ v2 — v7 — v ••■ v3 v7 v ••■ Symbol resp. — říká, že program uvedený v záhlaví sloupce zastaví resp. nezastaví pro vstup uvedený v záhlaví řádku. Program Díag „zneguje" diagonálu této tabulky. Podle našeho předpokladu (Díag je program a posloupnost Pí zahrnuje všechny programy) existuje j G N takové, že Díag = Pj. Zastaví Díag pro vstup Vp. - Ano. Podle kódu Díag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví. - 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ů speciň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 nebudou vyžadovány u zkoušky tohoto předmětu. 78 12 Délka výpočtu algoritmu Úvod Mimo samotné správnosti výsledku vypočteného zapsaným algoritmem je ještě jedno neméně důležité hledisko k posouzení vhodnosti algoritmu k řešení zadané úlohy Jedná se o čas, který algoritmus stráví výpočtem. Asi netřeba argumentovat, že přehnaně dlouhá doba odezvy programu je každému uživateli nepříjemná. A co třeba v real-time systémech, kde si zdržení prostě nemůžeme dovolit. Obligátní odpověď „kupme si rychlejší počítač" bohužel není vždy řešením, jak při pokročilém studiu složitosti algoritmů sami poznáte. Mnohem větší potenciál zrychlení se skrývá v algoritmech samotných a jejich efektivním návrhu. Cíle V této lekci deňnujeme délku výpočtu algoritmu, přičemž deňnici postavíme na deklarativním jazyce z Lekce 9. Poté si ukážeme, jak se matematicky popisuje asymptotické chování funkcí, což se využívá především pro zjednodušené studium složitosti výpočtu algoritmu. 12.1 O významu délky výpočtu algoritmu Uvažme deklarativní jazyk Definice 9.1. Definice: Délkou výpočtu výrazu F nad deklarací A rozumíme nejmenší přirozené k takové, že pro něj existuje m G Num pro něž F \—> k m. (Když takové m neexistuje, klademe k = oo.) Komentář: Jaká je délka výpočtu následujících výrazů? * 3 + 4- 5*6; tři kroky 3 + 4- 5*6 3 + 4-30 3 + 0 3. * 3 + (5 - 4) * (6 4- 2); tentokrát čtyři kroky 3 + (5 - 4) * (6 4- 2) 3 + 1 * (6 4 2) 3 + 1*3 3 + 3 6. * 2011 ; žádný krok, tj. k = 0. Příklad 12.1. Pro ukázku uvažme deklaraci A obsahující pouze rovnici f(x) = if x then x * f{x — 1) else 1 fi. Věta. Pro každé n G N je délka výpočtu výrazu /(n) rovna An + 2. Důkaz povedeme indukcí podle n: • Báze n = 0. Platí /(0) i—>■ if 0 then 0 * /(0 — 1) else 1 fi i—>■ 1, což jsou přesně 2 kroky, tj. 4 • 0 + 2. • Indukční krok. Nechť n + 1 = k. Pak /(k) i—>• ifk then k*/(k- 1) else 1 fi ■->■ k*/(k-l) i—>• k*/(w). kde w = k — 1 = n. To jsou přesně 3 kroky. Podle I.P. je délka výpočtu výrazu /(w) rovna An + 2. Poté následuje ještě jeden poslední krok vynásobení k. Celkem se provedlo 3 + An + 2 + 1 = 4(n + 1) + 2 = Ak + 2 kroků. n 79 Počítat přesně nebo raději ne? Komentář: Jaký má smysl určení přesného počtu kroků algoritmu při dnešních CPU? Copak jsme dnes schopni jednoznačně říci, jak dlouho jedna instrukce CPU trvá? Z druh strany, i když víme, že algoritmus A třeba potřebuje 2n kroků výpočtu a algoritmus B třeba potřebuje 3n kroků, je mezi nimi až takový rozdíl? Stačí, když B spustíme na dvakrát rychlejším počítači a poměr se hned obrátí. Obě tyto prakticky motivované úvahy nás povedou k poznání, že aditivní a multiplikativní faktory funkce počtu kroků algoritmu jsou vlastně zanedbatelné. 12.2 Asymptotické značení a odhady funkcí Zajímá-li nás jen rychlost růstu funkce f(n) v závislosti na n, zaměřujeme se především na tzv. asymptotické chováni f při velkých hodnotách n. V popisu / nás tedy nezajímají ani různé přičtené "drobné členy", které se významněji projevují jen pro malá n, ani konstanty, kterými je / násobena a které jen ovlivňují číselnou hodnotu f(n), ale ne rychlost růstu. Komentář: Tak například funkce f(n) = n2 roste (zhruba) stejně rychle jako f'(n) = lOOOOOOOOn2 i jako f"(n) = O.OOOOOOOln2 - lOOOOOOOOn - 1000000. Naopak h(n) = O.OOOOOOOOOOln3 roste mnohem rychleji než f(n) = lOOOOOOOOn2. Pro porovnávání rychlostí růstů funkcí nám slouží následující terminologie. Definice: Nechť g : R —y R je daná funkce. Pro funkci / : R —y R píšeme /eO(9) pokud existují konstanty A, B > 0 takové, že Vn G R+ : f (n) < A ■ g (n) + B . V praxi se obvykle (i když matematicky méně přesně) píše místo f E 0[g) výraz f(n) = 0(g(n)). Znamená to, slovně řečeno, že funkce / neroste rychleji než funkce g. (I když pro malá n třeba může být f (n) mnohem větší než g (n).) Poznámka: Kromě vlastnosti / G O (g) se někdy setkáte i s vlastností / G o(g), která znamená limn^oo = 0 (funkce / roste striktně pomaleji než g). Definice: Píšeme / G Q(g), neboli f{n) = f2(g(n)), pokud g E O(f). Dále píšeme / G ©((?), neboli f{n) = 0(g(n)), pokud / G O (g) a zároveň / G neboli g E O(f). Výraz f{n) = 0(p(n)) pak čteme jako "funkce / roste stejné rychle jako funkce g". Značení: O funkci f(n) říkáme: * f{n) = je lineární funkce, * f{n) = ©(^2) je kvadratická funkce, * f{n) = 0(log n) je logaritmická funkce, 80 * f{n) = 0(nc) pro nějaké c > 0 je polynomiální funkce, * f(n) = íl(cn) pro nějaké c > 1 je exponenciální funkce. Příklad 12.2. Příklady růstů různých funkcí. Funkce f(n) = @(n): pokud n vzroste na dvojnásobek, tak hodnota f(n) taktéž vzroste (zhruba) na dvojnásobek. To platí jak pro funkci f(n) = n, tak i pro lOOOOOOOOOrz nebo n + y/n, atd. Funkce f(n) = @(n2): pokud n vzroste na dvojnásobek, tak hodnota f(n) vzroste (zhruba) na čtyřnásobek. To platí jak pro funkci f(n) = n2, tak i pro lOOOn2 + lOOOrř nebo n2 - 99999999n - 99999999, atd. Naopak pro funkci f(n) = @(2n): pokud n vzroste byť jen o 1, tak hodnota f(n) už vzroste (zhruba) na dvojnásobek. To je obrovský rozdíl exponenciálních proti polynomiálním funkcím. Pokud vám třeba funkce 999999n2 připadá velká, jak stojí ve srovnání s 2n? Zvolme třeba n = 1000, kdy 999999n2 = 999999000000 je ještě rozumně zapsatelné číslo, ale 21000 ^ iq300 byg^e uz na řádek nenapsali. Pro n = 10000 je rozdíl ještě mnohem výraznější! □ Příklad 12.3. (opakovaný) Zjistěte, kolik znaků 'x' v závislosti na celočíselné hodnotě n vstupního parametru n vypíše následující algoritmus. Algoritmus 12.4. foreach i«—1,2,3,...,n-l,n do foreach j ^— 1,2,3,...,i-l,i do vytiskni ' x' ; done done Zatímco v Lekci 8 jsme trochu zdlouhavě indukcí dokazovali, že výsledkem je + 1) 'x', nyní si mnohem snadněji odvodíme, že počet 'x' je Q(n2), což je dostačující asymptotická odpověď ve většině informatických aplikací. Důkaz: Shora hned odhadneme, že každá z n iterací vnějšího cyklu vytiskne po i < n znaků 'x', takže celkem je nejvýše n2 'x'. Naopak zdola hned vidíme, že posledních n/2 iterací vnějšího cyklu vytiskne i > n/2 znaků 'x', takže celkem je alespoň (n/2) ■ (n/2) = n2/A 'x'. Z toho podle definice hned vyjde asymptotický odhad Q(n2). □ 12.3 Rekurentní odhady V tomto oddíle si uvedeme krátký přehled některých rekurentních vzorců, se kterými se můžete setkat při řešení časové složitosti (převážně rekurzivních) algoritmů. Lema 12.5. Nechť a1;..., a*., c > 0 jsou kladné konstanty takové, že aľ + • • • + < 1, a funkce T : N —y N splňuje nerovnost T (n) < T( \aľn]) + T( \a2n\ ) + ••• + T( \akn\) + cn . PakT(n) = O (n). 81 Důkaz: Zvolme e > 0 takové, že a\ + • • • + ak < 1 — 1e. Pak pro dostatečně velká n platí (i se zaokrouhlením nahoru) \ain\ + • • • + [a^n] < (1 — ^)n, řekněme pro všechna n > n0. Dále zvolme dostatečně velké d > 0 tak, že ed > c a zároveň d > max j^T(n) : n = 1,... ,n0}. Dále už snadno indukcí podle n dokážeme T(n) < dn pro všechna n > 1: • Pro n < no je T(n) < dn podle naší volby d. • Předpokládejme, že T(n) < dn platí pro všechna n < n±, kde n\ > n$ je libovolné. Nyní dokážeme i pro n\ T(nľ) < T( [ai^i]) H-----h T( [afc«il) + c™i < < d • [aini] + • • • + d • [afc^i] + cni ^ < d • (1 — e)ni + cni < dni — (sd — c)ni < dni ■ □ Lema 12.6. Nechť k > 2 a a1}..., a*., c > 0 json kladné konstanty takové, že aľ + • • • + ňfc = 1, a funkce T : N —y N splňuje nerovnost T (n) < T( [am]) + T( [a2n] ) + ••• + T( [afcn]) + cn . (1) PaÄ: T (n) = O (n ■ log n). Důkaz (poněkud nematematický náznak): Bylo by možno postupovat obdobně jako v předchozím důkaze, ale výpočty by byly složitější. Místo formálního důkazu indukcí nyní předestřeme poměrně jednoduchou úvahu zdůvodňující řešení T(n) = 0(n ■ logn). Představme si, že upravujeme pravou stranu výrazu (1) v následujících krocích: V každém kroku rozepíšeme každý člen T(m) s dostatečně velkým argumentem ni rekurzivní aplikací výrazu (1) (s T(m) na levé straně). Jelikož aľ + • • • + = 1, součet hodnot argumentů všech T(-) ve zpracovávaném výrazu bude stále zhruba n. Navíc po zhruba t = 0(log n) krocích už budou hodnoty argumentů všech T(-) "malé" (nebude dále co rozepisovat), neboť 0 < a« < 1 a tudíž a\-n < 1 pro všechna i. Při každém z kroků našeho rozpisu se ve výrazu (1) přičte hodnota cn = 0(n), takže po t krocích bude výsledná hodnota T{n) = t ■ O (n) + O (n) = O (n ■ logn). Vyzkoušejte si tento postup sami na konkrétním příkladě T'(n) < 2T' (|) + n. □ V obecnosti je známo: Lema 12.7. Nechť a > 1, b > 1 jsou konstanty, f : N —y N je funkce a pro funkci T : N —y N platí rekurentní vztah T{n) < a ■ T Q + f (n) . b. Pak platí: * Je-li f(n) = 0(nc) a c < log6a; pak T(n) = O(nlogi>íl) * Je-li f(n) = 0(nlog"a); pak T(n) = O(nlog"a • logn). * Je-li f(n) = 0(nc) a O log6a; pak T(n) = 0(nc). 82 Důkaz tohoto obecného tvrzení přesahuje rozsah našeho předmětu. Všimněte si, že nikde ve výše uvedených řešeních nevystupují počáteční podmínky, tj. hodnoty T(0), T(l), T(2),... - ty jsou "skryté" v naší OQ-notaci. Dále v zápise pro zjednodušení zanedbáváme i necelé části argumentů, které mohou být zaokrouhlené. Příklad 12.8. Algoritmus merge-sort pro třídění čísel pracuje zhruba následovně: * Danou posloupnost n čísel rozdělí na dvě (skoro) poloviny. * Každou polovinu setřídí zvlášť za použití rekurentní aplikace merge-sort. * Tyto dvě už setříděné poloviny "slije" (anglicky merge) do jedné setříděné výsledné posloupnosti. Jaký je celkový počet jeho kroků? Nechť na vstupu je n čísel. Při rozdělení na poloviny nám vzniknou podproblémy o velikostech \n/2] a [n/2\ (pozor na necelé poloviny). Pokud počet kroků výpočtu označíme T(n), pak rekurzivní volání trvají celkem T(\n/2]) + T([n/2\). Dále potřebujeme c-n kroků (kde c je vhodná konstanta) na slití obou částí do výsledného setříděného pole. Celkem tedy vyjde T{n) = T( \n/2]) + T( [n/2\ ) + cn 1 a t(n) = o(nlog23) ~ 0(nL585), což je výrazně rychlejší Rozšiřující studium Poslední lekce našeho učiva nás dovedla do zajímavé a užitečné oblasti výpočetní složitosti. S problematikou zjišťování délky výpočtu („rychlosti") algoritmu se studenti určitě setkají v předmětech zabývajících se návrhem algoritmů. Alespoň základní znalost problematiky složitosti by měl mít každý programátor, aby dokázal psát rozumně efektivní programy. Na otázky rychlosti algoritmů pokročile navazuje teorie výpočetní složitosti, která se dále zabývá otázkami, proč pro mnohé problémy efektivní algoritmy neexistují (a existovat nejspíše ani nemohou). Později se tak studenti setkají třeba s pojmem NP-úplnosti -základním kritériem „efektivníneřešitelnosti" problému. □ 84 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. Konečně 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/podzim2011/IB000/index.qwarp 85