Úvod do informatiky • Přednášející: Petr Hliněný (hiineny@fi.muni.cz) • Konzultanti kurzu: Jan Holeček (hoiecek@fi.muni.cz) Jan Obdržálek (xobdrzal@fi.muni.cz) • Materiály a informace dostupné na http://www.fi.muni.cz/~hlineny/Vyuka/UINF.html Studenti jsou aktuální informace na tomto webu povinni pravidelně číst! Smysl a formát kurzu • Elementárně pojatý úvod do matematiky „vysokoškolského typu" s ohledem na potřeby studia informatiky. • Aplikace zapamatovaných vzorců a vět (SŠ) x styl definice-věta-důkaz (VŠ). • Úvodní pasáže jsou obsahově velmi podobné kurzu „Matematické základy I". • Cíl: příprava pro další studium, vyjasnění základních pojmů. • Evaluace: * 30% dvě písemky v semestru (2x 15%), * 70% zkoušková písemka, * až 5% bonus za řešení jednoho domácího projektu (nenárokové!), který bude zadaný příště. • K absolvování kurzu je třeba zhruba 50% z celkového počtu bodů. Úvod do formálního dokazovaní Uvažme matematickou větu 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. Sudé číslo je celé číslo dělitelné 2, tj. tvaru 2k. Liché číslo je celé číslo nedělitelné 2, tj. tvaru 2k + 1. Příklad 1. Věta: Jestliže x je součtem dvou lichých čísel, pak x je sudé. Důkaz. tvrzení zdůvodnění 1) a = 2k + 1, k celé předpoklad 2) b = 21 + 1, l celé předpoklad 3) x = a + b=2k + 2l + 1 +1 1,2) a komutativita sčítání (axiom) 4) x = 2(k + l)+2-1 3) a distributivnost násobení 5) x = 2(le + l+1) 4) a opět distributivnost násobení D 5 Příklad 2. 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. • Nechťz = ^=x + V=^-V- • Číslo zje racionální, neboť x au jsou racionální. • Platí z > x, neboť ^ > 0. • Dále platí z < y, opět neboť ^ > 0. • Celkem x < z< y. D Alternativní formulace Věty 2: • Pro každé xyy e Q, kde x < y, existuje z g Q takové, že x < z < y. • Množina racionálních čísel je hustá. Struktura matematických vět • První krok formálního důkazu je uvědomit si, co se má dokázat, tedy co je předpoklad a co závěr. • Příklady: * Věta: Konečná množina má konečně mnoho podmnožin. * Věta: sin2(a) + cos2(a) = 1. * Věta: Graf je rovinný jestliže neobsahuje podrozdělení K5 nebo K33. • Často pomůže pouhé rozepsání definic pojmů, které se v dané větě vyskytují. • Jak „moc formální" mají důkazy vlastně být? * 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á. Konstruktivní a existenční důkazy • Důkaz Věty 2 je konstruktivní. Dokázali jsme nejen, že číslo z existuje, ale podali jsme také návod, jak ho pro dané x a y sestrojit. • Existenční důkaz je takový, kde se prokáže existence nějakého objektu bez toho, aby byl podán návod na jeho konstrukci. Příklad 3. Věta: Existuje program, který vypíše na obrazovku čísla tažená v 25. tahu sportky v roce 2006. Důkaz. Existuje pouze konečně mnoho možných výsledků losování 25. tahu sportky v roce 2006. 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 v 25. tahu sportky v roce 2006 skutečně vylosován. D („Podvod", nebo ne? Je to prostě tak...) • Pro informatické disciplíny (teorie automatů, teorie složitosti, návrh algoritmů, apod.) je důležitá konstruktivnost důkazů vět, které se zde objevují. • V matematice jsou mnohé příklady užitečných existenčních důkazů, třeba tzv. pravděpodobnostní důkazy. Příklad 4. Věta: Na dané množině boduje 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 n2 21_n + + 21_n = —------>0 n2 Jelikož je toto číslo (pravděpodobnost) pro n > 7 menší než 1, bude existovat obarvení bez jednobarevných zvolených podmnožin. D Základní důkazové techniky Přímé odvození. To je to, o čem jsme se dosud bavili. Kontrapozice (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 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... Příklad důkazu kontrapozicí Prvočíslo v > 1 nemá jiné dělitele než 1 ap. Příklad 5. Věta: Jestliže p je prvočíslo větší než 2, pak p je liché. Důkaz. Kontrapozicí. (Budeme tedy dokazovat, že je-li p sudé, pak p buď není větší než 2, nebo p není prvočíslo.) Jsou dvě možnosti: • p < 2. Pak p není větší než 2. • p > 2. Pak p = 2.k pro nějaké celé k > 1, tedy p není prvočíslo. D 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", není pouhou intuicí snadné zjistit, co je vlastně jeho negací. Jak uvidíme, užitím jednoduché induktivní metody lze podobná tvrzení negovat zcela mechanicky. Příklady důkazu sporem Příklad 6. 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 Příklad 7. Věta: Číslo \fl není racionální. Důkaz. Sporem. Nechť tedy y/l je racionální, tj. nechť existují nesoudělná celá kladná čísla r, s taková, že y/l = r/s. 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, je r2 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á, spor. D „Nevíte-li, jak nějakou větu dokázat, zkuste důkaz sporem." Matematická indukce • Důkazová technika aplikovatelná na tvrzení tohoto typu: „Pro každé přirozené (celé) n > k0 platí T [n)." Zde k0 je nějaké pevné přir. číslo a T(n) je tvrzení parametrizované číslem n. • Příklad: Pro každé n > 0 platí, že n přímek dělí rovinu nejvýše na ^n(n+1) +1 oblastí. • Princip matematické indukce říká (coby axiom), že k důkazu věty „Pro každé přirozené n > k0 platí T [n)." stačí ověřit platnost těchto dvou tvrzení: * T(ko) (tzv. báze neboli základ indukce) * Pro každé n > k0; jestliže platí J{n), ("indukční předpoklady pak platí také T(n + 1). ("indukční krok,) Příklady důkazů indukcí Příklad 8. 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ť p^ pravděpodobnost, že při hodu n kostkami bude výsledný součet sudý, a vln je pravděpodobnost lichého. Podle indukčního předpokladu je vsn = Vn = \- Hoďme navíc (n+ 1)-ní kostkou. Podle toho, zda na ní padne liché nebo sudé číslo, je pravděpodobnost celkového sudého součtu rovna a stejně pro pravděpodobnost celkového lichého součtu. D 14 Příklad 9. Věta: Pro každé n > O platí, že n přímek dělí rovinu nejvýše na -n(n+1) + 1 oblastí Důkaz. Pro bázi indukce stačí, že 0 přímek dělí rovinu na jednu část. (Možná je lépe si ještě ověřit, ž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 + 1) + 1 čá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 tolik částí: n(n+1) + 1 + (n+1) = -n(n+1) + - • 2(n+1) + 1 = -(n+1)(n + 2) + 1 2 2 2 2 D Příklad 10. Věta: Pro každé u > 0 platí L"=o 5 - i Důkaz. Indukcí vzhledem krt. 15 n . __ n(n+1) Báze: Musíme dokázat tvrzení T(0), což je v tomto případě rovnost o . _ om ■i=o) — 1 Lľ=o J = 5^LU- Tat0 rovnost (zjevně) platí. Indukční krok: Musíme dokázat následující tvrzení: Jestliže platí Y_)=o) = i-^}1kdei>0, pak platili i = (í+1)2(í+2). Předpokládejme tedy, že H-=0j = x-^j^- a pokusme se dokázat, že pak také £i+i . = (i+iKi+2)_ To už p!yne úpravou: V1- V-^r-^n ííí±21^r-^n t(t + 1) + 2(1 + 1) (i+1)(i + 2) }_1 = 2_^ + í1+^ = —2— ^ ^ = ----------2---------- = -------2------- j=0 j=0 D Matematická indukce (pokračování) • Základní trik všech důkazů matematickou indukcí je vhodná reformulace tvrzení T(i + 1) tak, aby se „odvolávalo" na tvrzení T(i). * Dobře se vždy podívejte, v čem se liší tvrzení T(i + 1) od tvrzení T(i). Tento „rozdíl" budete muset zdůvodnit. • Pozor, občas je potřeba „zesílit" tvrzení T(n), aby indukční krok fungoval. • Č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 pozor, od které hodnoty n > k0 je indukční krok univerzálně platný... 17 Příklad 11. Věta: Pro každé n > 1 platí 111 1 1-2 2-3 3-4 n(n+ IJ Důkaz. Báze indukce je zřejmá, ^ < 1 ■ Co však indukční krok? Předpoklad s(n) < 1 je sám „příliš slabý" na to, aby bylo možno tvrdit s(n + 1) = s{n) + (n+1 )1(n+2) < 1. Neznamená to ještě, že by tvrzení nebylo platné, jen je potřeba náš indukční předpoklad zesílit. Budeme dokazovat „Pro každé přirozené n > 1 platís{n) < 1 — ^ < 1 ." To platí pro n = 1 a dále algebraickou úpravou dokončíme zesílený indukční krok: s(n + 1) = s{n) +-------—------— < 1---------- + (n+1)(n + 2) - n+1 (n+1)(n + 2) = 1 , -(n + 2) + 1 = ^_ 1 (n+1)(n + 2) n + 2 D 18 Příklad 12. 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 krt. • Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu. • Indukční krok: Nechť S = {Kí, • • •, Ki+i} je stádo o i + 1 koních. Dokážeme, že všichni koně mají stejnou barvu. Uvažme dvě menší stáda: * S^ÍKi,...,^} * S"={K2,.--,Ki+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) • • • ,Ki patří jak do stáda Sx, tak i do stáda S ". D (Ale to už je podvod! Vidíte, kde?) Věty typu „tehdy a jen tehdy" • Jde o 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: * 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ě když platí tvrzení B. • 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. Pojem množiny 20 Co je množina? * Naivní teorie množin: „Množina je soubor prvků a je svými prvky plně určena." * Množiny mohou být prvky jiných množin (!) * 0, {a,b}, {b,a}, {a,b,a}, {{a,b}}, {0,(0},{{0}}} * {x | x je liché přirozené číslo} Počet prvků (mohutnost) množiny |A|. * |0| = 0, |{0}| = 1, |{a, b, c}| = 3, |{{a, b}, c}| = 2 Množiny jsou „stejné" právě když mají stejné prvky. * x e M „x je prvkem množiny M" *ae{a,b}, a £ {{a, b}}, {a, b} G {{a, b}}, 0 G {0}, 0^0 * {a, b} = {b, a} = {a, b, a}, {a, b} ^ {{a, b}} • Množina A je podmnožinou množiny B, právě když každý prvek A je prvkem B. Píšeme A c B nebo také B d A; říkáme také, že se jedná o inkluzi. * {a} C {a} C {a, b} % {{a, b}}, 0 C {0} * A c B právě když ACBaA^B (A je vlastní podmnožinou B) • Podle definice jsou množiny A a B stejné, mají-li stejné prvky. * Platí tedy A = B právě když A c B a B c A. * Důkaz toho, že A = B, má obvykle dvě části. Odděleně se dokáží inkluze A c B a B c A. 22 v ■ Množinové operace Sjednocení AUB={x|xgA nebo xeB} * {a, b, c} U {a, d} = {a, b, c, d} * Uiei Ai = {x | x g Ai pro nějaké i g 1} * Nechť Ai = {2.i} pro každé i g N0. Pak UíGn0 Ai Je mn°žina všech sudých přirozených čísel. Průnik AnB={x|xGAa současně x g B} * {a, b, c} H {a, d} = {a} * Olei Ai = {x I x g Ai pro každé i g 1} * Nechť Ai = {x | x g N, x > i} pro každé i g N. Pak f|ieN At = 0 Rozdíl A\B={x|xeAa současně x ^ B} * {a,b,c}\{a,b,d} = {c} * ........ Doplněk Nechť ACM. Doplněk A vzhledem k M je množina A = M \ A. * Jedná se o poněkud specifickou operaci, která musí být vztažena vzhledem k nosné množině M ! 23 * Je-li M = {a, b, c}, pak {a, b} = {c}. * Je-li M = {a, b}, pak {a, b} = 0. • Kartézský součin Ax B ={(a,b) I QGA,b e B} * kde uspořádaná dvojice (a, b) je množina {{a}, {a, b}}. * Platí (a, b) = (c, d) právě když a = c a současně b = d. * Mnemotechnická pomůcka |A x B| = |A| • |B|. * {a,b}x{a} = {(a,a),(b,a)}. * 0 x M = 0 pro každou množinu M. * Co je podle definice (a, a)? (a, a) = {{a},{a, a}} = {{a},{a}} = {{a}} • Skládání součinu * Pro každé k g N definujeme uspořádanou k-tici (ai, • • •, ak) induktivně takto: - (Cli) = GLi - (a1r--,0^,01+0 = {{^ y - - - y di) y ai+]) * Platí (ai,---,aic) = (bi, - - •, bk) právě když at = bt pro každé i g N kde 1 < i < k. * Pro každé k g N definujeme Ai x • • • x Ak = {(gli , • • •, ak) | ol g At pro každé 1 < i < k}. * 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. * N3 = NxNxN = {(iJ,k) |i,j,kGN}. * Co je N°? {0} • Potenční množina (množina všech podmnožin) 2A = {B | B C A} * Platí |2A| =2lAL * 2Ía'bi = {0,{a},{b},{a,b}} * 20 ={0} * 2{«0» = {0,{0},{{0}},{0,{0}}} * 2WxWl = {(J,{(Q,Q)}){(Q)l))},{(a,a),(a,b)}} • Charakteristický vektor (pod)množiny * Používaný v případech, kdy všechny uvažované množiny jsou podmnožinami nějaké nosné množiny X. * Pro X = {xi } a A c X definujeme charakteristický vektor xa jako Xa = (ci , C2,..., cn), kde ct = 1 pro xt e A a ct = 0 jinak. Důkaz rovnosti množin Příklad 13. Věta: Pro každé tři množiny A, B, C platí A\(BnC) = (A\B)U(A\C). Důkaz. • A\(BnC) C (A\B)U(A\C): * Je-li x g A \ (B n C), pak x g A a zároveň x ^ (B n C), neboli x ^ B nebo x ^ C. * Pro první možnost máme x g (A \ B), pro druhou x g (A \ C). • A\(BnC) 2 (A\B)U(A\C): * Je-li x g (A \ B) U (A \ C), pak x g (A \ B) nebo x e (A \ C). * Pro první možnost máme x g A a zároveň x ^ B, z čehož plyne x g A a zároveň x ^ (B n C), a tudíž x g A \ (B n C). * Druhá možnost je analogická. D Relace mezi (nad) množinami 28 Nechť k g N. Relace mezi množinami Ai, • • •, Ak je podmnožina součinu Ai x • • • x Ak. Pokud Ai = • • • = Au = A, hovoříme o k-ární relaci na A. Příklady * {(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 +)) | ij g N} je ternární relace na N. * {3.11 i g N} je unární relace na N. 2a1x-xa]c je tedy množina všech relací mezi Ai,- • •, A k- Reprezentace konečných relací pomocí tabulek • 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 Petr Pavel Novák Vichr Zima 42 28 26 • 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. Funkce mezi množinami • (Totální) funkce z množiny A do množiny B je relace f mezi A a B taková, že pro každé x g A existuje právě jedno y g B takové, že (x,-y) g f. „Neformálně řečeno, ve funkci f je každé vstupní hodnotě x přiřazena jednoznačně výstupní hodnota y." (V obecné relaci počty „přiřazených" dvojic neomezujeme...) • Místo (x,y)ef píšeme obvykle f(x) =y. • Množina A se nazývá definiční obor a množina B obor hodnot funkce f. Zápis f : A —» B říká, že f je funkce s definičním oborem A a oborem hodnot B. • Parciální funkce. Pokud naší definici funkce upravíme tak, že požadujeme pro každé x g A nejvýše jedno y g B takové, že (x,-y) g f, obdržíme definici parciální funkce z A do B. V parciální funkci p nemusí být pro některé „vstupnľ hodnoty x funkční hodnota definována. Pro nedefinovanou hodnotu používáme znak _L Příklady funkcí 31 • Definujeme funkci f : N —» N předpisem f (x) = x + 8. Tj. f = {(x, x + 8) | x e N}. • Definujeme funkci plus : N0 x N0 —» N0 předpisem pZws(iJ) = i + j. Tj. p/ws = {(i,j,i + j) I i, j E N0}. • Definujeme parciální funkci f : Z —» N předpisem -, , í 3 + x jestliže x > O, f(x) = ( i. jinak. Tj. f = {(x,3 + x) | x G N0}. • Také funkce f : R —> R daná běžným analytickým předpisem f(x) = y/x je jen parciálni - není definována pro x < 0. • Co je relace, přiřazující lidem v ČR jejich rodná čísla? Funkcím se také říká zobrazení. Vlastnosti funkcí • Funkce f : A —» B je * injektivní (nebo také prostá) právě když pro každé x,-y g A, x ^-y platí, že f(x)=ŕf(u); * surjektivní (nebo také „na") právě když pro každé -y g B existuje x g A takové, že f (x) = y; * bijektivní (vzáj. jednoznačná) právě když je injektivní a současně surjektivní. • Příklady: * Funkce plus : N0 x N0 —» N0 je surjektivní, ale není prostá. * Funkce g : Z —» N0 daná předpisem , , _ í —2x - 1 jestliže x < 0, 91*1 — | 2x jinak je bijektivní. * Funkce 0 : 0 —» 0 je bijektivní. * Funkce 0 : 0 —»{a, b} je injektivní, ale není surjektivní. Princip inkluze a exkluze Někdy také nazýván „princip zapojenia vypojení". B Věta 1. Počet prvků ve sjednocení dvou či tří množin spočítáme: |AUB| = |A| + |B|-|AnB| |A U B U CI = lAl + IBI + ICI - |A n Bl - |A n CI - IB n CI + |A n B n CI Z 1000 televizí jich při první kontrole na výrobní lince má 5 vadnou obrazovku, 10 je poškrábaných a 12 má jinou závadu. Přitom 3 televize mají současně všechny tři vady a 4 jiné jsou poškrábané a mají jinou vadu. Kolik televizí je celkem vadných? 17 O mohutnosti a nekonečných množinách • Množiny A je „nejvýše tak velká" jako množina B, právě když existuje injektivní funkce f : A —» B. • Množiny A a B jsou „stejně velké" právě když mezi nimi existuje bijekce. • Tyto definice „fungují" i pro nekonečné množiny. Např. N a Z jsou „stejně velké" (tzv. spočetně nekonečné). • Lze snadno ukázat, že i Q je spočetně nekonečná, tj. existuje bijekce f : N —» Q. • Existují ale i nekonečné množiny, které jsou „striktně větší" než libovolná spočetná množina (příkladem je R). • 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í". Věta 2. Neexistuje žádné surjektivní (tudíž ani bijektivní) zobrazení g : N —» R. Neformálně řečeno, reálných čísel je striktně více než přirozených. Důkaz. Dokazujeme sporem. Nechť takové g existuje a pro zjednodušení se omezme jen na funkční hodnoty v intervalu (OJ). 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: 427578325 9(0) = 0. 1 5 9(D = 0. 2 9(2) = 0. 9(3) = 0. 9(4) = 0. Nyní sestrojíme číslo oce (0 J) následovně; jeho i-tá číslice za desetinnou čárkou bude 1, pokud v i-tém řádku tabulky na diagonále není 1, jinak to bude 2. V našem příkladě oc = 0.21211 ... Kde se naše číslo a v tabulce nachází? (Nezapomeňme, g byla surjektivní, takže tam oč 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.) D V obecnosti lze dokonce podobným způsobem dokázat následovné. Věta 3. Buď M libovolná množina. Pak existuje injektivní zobrazení í : M —» 2M, ale neexistuje žádné bijektivní zobrazení g : M —» 2M. Důkaz. Dokážeme nejprve existenci f. Stačí ale položit f(x) = {x} pro každé x e M. Pak f : M —» 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: K = {x G M | x ^ g(x)}. Jelikož g je bijektivní a K g 2m, musí existovat x g M takové, že g (x) = K. Nyní rozlišíme dvě možnosti: • x g g(x). Tj. x g K. Pak ale x ^ g(x) z definice K, spor. • x 4. g(x). To podle definice K znamená, že x g K, tj. x g g(x), spor. D Poznámky. • 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é), proto nutně existují problémy, které nejsou algoritmicky řešitelné. Musíme však být opatrní... • Technika použitá v důkazech Vět 2 a 3 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(a) V - - V ••• g(b) V - - V ••• g(c) - V - 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 4 g(d). „Naivní" množinové paradoxy • Uvážíme-li nyní nekonečnou posloupnost množin Ai,A2,--- kde Ai = N a Ai+i = 2Ai pro každé i e 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"? * Toto byl první Cantoruv paradox nově vznikající teorie množin. * Brzy se však ukázalo, že je ještě mnohem hůř... • Russeluv paradox: Není pravda, že každý soubor prvků lze považovat za množinu. * X = {M | M je množina taková, že M ^ M} * Platí X g X ? * Ano. Tj. X g X. Pak ale X splňuje X ^ 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. Vidíte zde podobnost přístupu s Cantorovou diagonalizací? • Pro ilustraci, znáte toho „holiče v malém městečku, který holí právě ty muže městečka, kteří se sami neholí"? • Tyto 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. Algoritmická neřešitelnost problému zastavení • 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ť I je množina všech těchto symbolů. Množina všech programů je tedy jistě podmnožinou množiny UieNX\ která je spočetně nekonečná. Existuje tedy bijekce f mezi množinou N a množinou všech programů. Pro každé i g N označme symbolem Pt program f (i). Pro každý program P tedy existuje ) e N takové, že? = ?j. • Každý možný vstup každého možného programu lze zapsat jako konečnou posloupnost symbolů z konečné mnočiny r. Množina všech možných vstupů je tedy spočetně nekonečná a existuje tedy bijekce g mezi množinou N a množinou všech vstupů. Pro každé i g N označme symbolem Vt vstup g (i). • Předpokládejme, že existuje program Halt, který pro dané i,j e N zastaví s výstupem ano/ne podle toho, zda Pt pro vstup Vj zastaví, nebo ne. • Uvažme program Diag s následujícím kódem: input(k); if {Halt{ky k) == ano) then while true do skip Program Diag[k) má na rozdíl od Halt\en jeden vstup k, což bude důležité. • Fungování programu Diag lze znázornit pomocí následující tabulky: Pí P2 P3 P4 ••• Ví V - - V ••• v2 V - - V -" v3 - V - V -" v4 - - V V -" Symbol y/ resp. - říká, že program uvedený v záhlaví sloupce zastaví resp. nezastaví pro vstup uvedený v záhlaví řádku. Program Diag „obrací" diagonálu této tabulky. • Podle dřivě uvedeného pozorování existuje j e N takové, že Diag = Pj. Zastaví Diag pro vstup Vj? * Ano. Podle kódu Diag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví. * Ne. Podle kódu Diag pak ale if test neuspěje, a tento program tedy zastaví. Předpoklad existence programu Halt tedy vede ke sporu. D • 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é. 43 Reprezentace binárních relaci na množine Danou binární relaci R c M x M na M lze znázornit jejím grafem: * Prvky M znázorníme jako body v rovině. * Prvek (a, b) e R znázorníme jako orientovanou hranu („šipku") z a do b. Je-li a = b, pak je touto hranou „smyčka" na a. Pozor, nejedná se o „grafy funkcí" známé z analýzy. Příklad: Nechť M = {a, b,c,d}aR = {(a, a), (a, b), (b, a), (a, c), (c, d)}. a 4 b K Z^° J L c d V případě, že R je nekonečná nebo „velká", může být reprezentace R jejím grafem nepraktická (záleží pak na míře „pravidelnosti" R). Inverzní relace a skládání relací 44 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 ={(b,a) | (a,b) G R} R-1 je tedy relace mezi B a A. Nechť RCAxBaSCBxC jsou binární relace. Kompozice (složení) relací R a S je relace SoRCAxC (čteme „S po R") definovaná takto: S o R = {(a, c) | existuje b g B takové, že (a, b) g R, (b, c) g S} * Příklad: Je-li -A = {a,b}, B ={1,2}, C = {X}, - R={(a,1),(b,1),(b,2)}, S={(1,X)}, pakSoR = {(a,X),(b,X)}. Příklady pro relace-funkce: • Inverzí bijektivní funkce f (x) = x +1 na Z je funkce r1 (x) = x -1. Inverzí prosté funkce f (x) = ex na R je parciální funkce f-1 (x) = In x. • Funkce g (x) = x mod 3 není prostá na N, a proto její inverzí je jen relace g-1 = {(a, b) I a = b mod 3}. Konkrétně g"1 ={(0,0), (0,3), (0,6),... ,(1,1), (1,4),... ,(2,2), (2,5),...}. • Složením funkcí f (x) = x + 1 a h(x) = x2 na R vznikne funkce f oh (x) =f(H(x)) = x2 + 1. Pozor! Složením „naopak" ale vznikne funkce Hof (x) =H(f(x)) = (x+1)2. Vlastnosti binárních relací na množině Nechť R c M x M. Relace R je • reflexivní, právě když pro každé a g M platí (a, a) g R; • symetrická, právě když pro každé a, b g M platí, že jestliže (a, b) g R, pak také (b, a) g R; • antisymetrická, právě když pro každé a, b g M platí, že jestliže (a, b), (b, a) g R, pak a = b; • tranzitivní, právě když pro každé a,b,c e M platí, že jestliže (a,b), (b,c) g R, pak také (a, c) g R; • ekvivalence, právě když je reflexivní, symetrická a tranzitivní; • (částečné) uspořádání, právě když je reflexivní, antisymetrická a tranzitivní. Vlastnosti binárních relaci na množine — príklady Bud M množina všech studentů 1. ročníku Fl. 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; * (x,u)eR právě když výška x a y se neliší více jak o 2 cm; * (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; * (x,-y) e R právě když x je zamilován(a) doy. Bud R c N x N definovaná takto (x,-y) e R právě když x dělí-y. Bud R c No x No definovaná takto (x,-y) e R právě když x a y mají stejný zbytek po dělení číslem 5. Nechť M = {a, b} a nechť F = {f | f : M -> M}. Buď R c F x F definovaná takto (f, g) e R právě když f o g = g o f. Jaké má tato relace vlastnosti? Ekvivalence R c M x M je ekvivalence právě když R je reflexivní, symetrická a tranzitivní. Tyto tři vlastnosti je tedy třeba ověřit k důkazu toho, že daná relace R je ekvivalence. Jak vypadá graf ekvivalence? 9 A č Neformálně řečeno: ekvivalence je relace R c M x M, taková, že (x,-y) e R právě když x a y jsou v nějakém smyslu „stejné". Příklady: • Bud M množina všech studentů 1. ročníku Fl. Uvažme postupně relace R c M x M definované takto * (x,-y) e R právě když x má stejnou výšku jako y; * (x,-y) e R právě když x má stejnou barvu vlasů jako y; * (x,-y) e R právě když x,-y mají stejnou výšku a stejnou barvu vlasů; * (x,-y) e R právě když x,-y mají buď stejnou výšku nebo stejnou barvu vlasů, (tato relace obecně není ekvivalence !) • Bud R c N0 x N0 definovaná takto: [xyy] e R právě když |x -y\ je dělitelné třemi. (V jakém smyslu jsou x a y „stejné" ?) Rozklady a jejich vztah k ekvivalencím Definice 4. BuďM množina. Rozklad (na) M je množina Áí c 2M taková, že platí následující tři podmínky: • 0 ^ Áí (tj. každý prvek Áí je neprázdná podmnožina M); • pokud A, B e AT, pak buď A = B nebo A n B = 0; • Uagata = m- Prvkům Áí se také říká rř/c/y rozkladu. Příklady: • Bud M = {a, b, c, d}. Pak AT = {{a}, {b, c}, {d}} je rozklad na M. • Nechť A0 = {k g No | k mod 3 = 0}, Ai = {k g No I k mod 3 = 1}, A2 = {k e No I k mod 3 = 2}. Pak Áí = {A0) Ai, A2} je rozklad na N0. Každý rozklad AT na M jednoznačně určuje jistou ekvivalenci Rat na M. Věta 5. Buď M množina a Áí rozklad na M. Nechť R^r CMxMje relace na M definovaná takto [xyy) g Rat právě když existuje A eÁÍ taková, žexyy g A. Pak Rat je ekvivalence na M. Důkaz. Dokážeme, že Rat je reflexivní, symetrická a tranzitivní. • Reflexivita: Buď x e M libovolné. Jelikož Áí je rozklad na M, musí existovat A e Áí takové, že x g A (jinak spor se třetí podmínkou z Definice 4). Proto (x,x) G Rat, tedy Rat je reflexivní. • Symetrie: Nechť [xyy] g Rat- Podle definice Rat pak existuje A e Áí taková, že xyy g A. To ale znamená, že také [yyx] g Rat podle definice Rat, tedy Rat je symetrická. • Tranzitivita: Nechť [xyy)y[yyz) g Rat- Podle definice Rat existují A,B g AT takové, že xyy g A aij,z g B. Jelikož A n B ^0, podle druhé podmínky z Definice 4 platí A = B. Tedy xyz g A = B, proto (x,z) g Rat podle definice Rat- □ Každá ekvivalence R na M jednoznačně určuje jistý rozklad M/R na M. Věta 6. Buď M množina a R ekvivalence na M. Pro každé x e M definujeme množinu [x] ={y e M | (x,y) G R}. Pak M/R = {[x] | x g M} je rozklad na M. Důkaz. Dokážeme, že M/R splňuje podmínky Definice 4. • Pro každé [x] g M/R platí [x] ^ 0, neboť x g [x]. • Nechť [x], [y] g M/R. Ukážeme, že pokud [x] n [y] =£ 0, pak [x] = [y]. Jestliže [x] n [y] =£ 0, existuje z g M takové, že z g [x] a z g [y]. Podle definice [x] a [y] to znamená, že (x, z), [yyz] g R. Jelikož R je symetrická a (-y, z) e R, platí [zyy] g R. Jelikož [xyz)y[zyy) g R a R je tranzitivní, platí (x,-y) g R. Proto také (y,x) e R (opět ze symetrie R). Nyní dokážeme, že [x] c [y] a [y] c [x]. * „[x] c [y]-" Nechť v g [x]. Pak (x, v) g R podle definice [x]. Dále (-y, x) e R (viz výše), tedy (-y, v) e R neboť R je tranzitivní. To podle definice [y] znamená, že v E [y]. * »[yl c [x]:" Nechť v e [y]. Pak (-y, v) e R podle definice [y]. Dále (x,-y) e R (viz výše), tedy (x, v) e R neboť R je tranzitivní. To podle definice [x] znamená, že v E [x]. • Platí U m g m/r M = M> neboť x e [x] pro každé x e M. D Relace mezi (nad) množinami - zopakování • Nechť k g N. Relace mezi množinami Ai,---,Aic je libovolná podmnožina kartézského součinu Ai x • • • x Aic. Pokud k = 2 a Ai = A2 = M, hovoříme o binární relaci na M. • Znovu krátce vlastnosti binárních relací * reflexivní, platí (a, a) g R; * symetrická, jestliže (a,b) g R, pak také (b, a) g R; * antisymetrická, jestliže (a, b), (b, a) g R, pak a = b; * tranzitivní, jestliže (a,b), (b,c) g R, pak také (a,c) g R. Uspořádání a pŕeduspoŕádání • R c M x M je uspořádání právě když R je reflexivní, antisymetrická a tranzitivní. • R c M x M je předuspořádání (také kvaziuspořádání, nebo polouspořádání) právě když R je reflexivní a tranzitivní. • (Před)uspořádaná množina je dvojice (M,Q, kde M je množina a c je (před)uspořádání na M. • Neformálně řečeno: uspořádání je taková relace R c M x M, kde (x,-y) e 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) e R ani (-y,x) e R (pak říkáme, že x a y jsou nesrovnatelné). • Uspořádání R na M je lineární (také úplné) pokud každé dva prvky M jsou vzhledem k R srovnatelné. • 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 takového kritéria, které není pro daný prvek jedinečné. Uspořádání a předuspořádání - příklady • Bud M množina všech studentů 1. ročníku Fl. 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á alespoň takovou výšku jako y; * (x,-y) e R právě když y má alespoň takovou výšku jako x. • (No, <) je lineárně uspořádaná množina (kde < má „obvyklý" význam). • (N, |), kde | je relace dělitelnosti, je uspořádaná množina. Toto uspořádání není lineární. • Bud M množina. Pak (2M, c) je uspořádaná množina. • Nechť M je množina a (A, 2, pak množinu Ai x • • • x An lze uspořádat po složkách nebo lexikograficky. * Všimněte si, že lexikograficky se řadí slova ve slovníku... • Je-li c předuspořádání na M, můžeme definovat relaci - na M předpisem x - y právě když x n. y a y Q x. Pak - je ekvivalence na M, která se nazývá jádro předuspořádání c. Na rozkladu M/ - pak lze zavést relaci ^ definovanou takto M ^ [y] právě když xQy. Pak (M./ -, ^) je uspořádaná množina. * Pro příklad si vezměme relaci dělitelnosti na Z. Zde třeba —2 - 2. Jádrem tedy jsou dvojice čísel stejné absolutní hodnoty. Další pojmy související s uspořádáním Buď (M, Q uspořádaná množina. • x g M je minimální právě když pro každé y g M platí, že jestliže y Q x, pak xQy. (Tj. x je minimální právě když neexistuje žádný prvek ostře menší než x.) • x g M je maximální právě když pro každé y g M platí, že jestliže xCy, pak y Cx. (Tj. x je maximální právě když neexistuje žádný prvek ostře větší než x.) • x g M je nejmenší právě když pro každé y g M platí, žexc-y. • x g M je největší právě když pro každé y g M platí, že y c x. • x g M pokrývá y g M právě když x ^ y, y c x a neexistuje žádné z g M takové, žex^z^ijaij c z c x. • x g M je horní závora (mez) množiny A c M právě když y n. x pro každé y g A. • x e M je dolní závora (mez) množiny A c M právě když x c y pro každé y g A. • x g M je supremum množiny A c M, právě když x je nejmenší horní závora množiny A. • x g M je infimum množiny A c M právě když x je největší dolní závora množiny A. t A c M je řetězec v uspořádání c právě když (A, Q je lineárně uspořádaná množina. 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... Hasseovske diagramy 61 Hasseovske diagramy uspořádaných množin jsou přehlednější než grafy relací. Hasseovský diagram konečné uspořádané množiny (M, n.) vznikne takto * do první „horizontální vrstvy" zakreslíme body odpovídající mininálním prvkům (M, Q (tj. které nepokrývají nic); * máme-li již zakreslenu „vrstvu" i, pak do „vrstvy" i + 1 (která je „nad" vrstvou i) zakreslíme všechny nezakreslené prvky, které pokrývají pouze prvky „vrstev" < i. Pokud prvek x „vrstvy" i + 1 pokrývá prvek y „vrstvy" < i, spojíme x a y neorientovanou hranou (tj. „čárou"). Příklad: e Q / O O A d O a O b • Pozor! Původní popis Hasseova diagramu měl problém, který je vidět na obrázku: Ve skutečnosti se nelze odvolávat na prvky pokrávající jen některý prvek předchozí vrstvy, ale zařadit prvky do další vrstvy až tehdy, když všechny jím pokrývané prvky jsou v předchozích vrstvách. Také pojem „vrstvy" je jen velmi neformální, důležité je, že větší (pokrývající) prvky jsou nad menšími (pokrývanými). • Další příklad 8 4 dělitelnost: j 2 12 1 Uzávěry relací Buď V (nějaká) vlastnost binárních relací. Řekneme, že V je vhodně definovaná, 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ť I je množina a nechť Rt c M x M je relace mající vlastnost V pro každé i g I. Pak relace f|iGl Rt má vlastnost V. Příklady: • Reflexivita, symetrie, tranzitivita. Libovolná kombinace těchto tří vlastností je vhodně definovaná vlastnost. • Antisymetrie není vhodně definovaná vlastnost. Definice 7. Nechť V je vhodně definovaná vlastnost binárních relací. Buď M množina a R binární relace na M. Pak existuje nejmenší (vzhledem k inkluzi!) relace obsahujícím, která má vlastnostV. Tuto relaci nazýváme V uzávěr relace R. , 64 Příklady: Bud R binární relace na M • 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}. • Bud T funkce, která pro každou binární relaci S vrátí relaci T(S) = S U {(x,z) I existuje -y takové, že (x,-y), [yyz] G S}. • Tranzitivní uzávěr R je přesně relace R+ = U£i Tl(R), kde T{ = Jo • • • oTy. i • Reflexivní a tranzitivní uzávěr R je přesně relace R* = U£i ^(QL 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. • Bud RCNxN definovaná takto: R = {(i, i + 1) | i g N}. Pak R* je běžné <. Výroky a jejich struktura v „přirozené" podobě • Výrok je tvrzení, o kterém má smysl prohlásit, že je buď pravdivé nebo nepravdivé. * Dnes v Brně pršelo. * 2 + 3 = 6 * To je bez problémů. * x > 3 * Pro každé celé číslo x platí, že x > 3. • Z jednoduchých výroků můžeme vytvářet výroky složitější pomocí logických spojek. * Kateřina přijede ve 12:00 a půjdeme spolu do kina. * Množina {a, b} má více než jeden prvek a není nekonečná. * Jestliže má Karel přes 90 kilo váhy, nepojedu s ním výtahem. * Jestliže má kráva 10 nohou, mají všechny domy modrou střechu. • Schopnost porozumět takovýmto větám je součást lidského způsobu uvažování a z tohoto hlediska nemá přímou souvislost s matematikou („přirozená logika"). • Formální logika definuje jazyk matematiky a odstraňuje nejednoznačnosti přirozeného jazyka. (Formální) výroková logika Syntaxe: • Bud At = {A, B, C,...} spočetně nekonečná množina výrokových proměnných. • Množina výrokových formulí O je definována induktivně následujícími pravidly: (1) Ate O. (2) Jestliže cp,\p e ®, pak také --(cp) GOa((p)4 (ip) g O. (3) Každý prvek O vznikne konečně mnoha aplikacemi pravidel (1) a (2). • Příklady: * A, (A) =* (B), ((A) =* HB))) =* (HB)) =* (C)) *A^B, A^B^C, --A => B (nejsou správně výrokové formule) • Úmluva 1: Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to nepovede k nejednoznačnostem za předpokladu, že negace -■ má „vyšší prioritu" než =>. Touto úmluvou se nemění množina O; mění se způsob reprezentace jejích prvků. • Úmluva 2: * (pVip je jiný zápis formule —-cp => i|> * cpAip je jiný zápis formule -■(-■(p V-^) * (p <=> i|j je jiný zápis formule (cp => ip) A (ip => cp) Sémantika: • Valuace (ohodnocení) je funkce -v : At —» {truejalse}. • Pro každou valuaci y definujeme funkci Sy : O —»{truejalse} induktivně takto: * ip) = true právě když platí jedna z následujících podmínek — Sv((p) = rn/č a současně Sy{ty) = frwe, — 5v(cp) = false a současně Sv(ip) = false. • Formule cp e O je pravdivá (také výroková tautologie), psáno N (p, pokud pro každou valuaci -v platí, že 5v(cp) = true. * AV-A * - -A ^> A * (AA(A^B)) ^>B * (-B=^-A)=^(A=^B) * hA=> (BA-B)) ^ A • Řekneme, že formule (p,i|)GO jsou ekvivalentní, právě když N (p <=> ip. Důkazy indukcí ke struktuře formule • Důkazová technika aplikovatelná na tvrzení typu „Pro každou formuli cp e O p/aí/T(cp)". • Princip strukturální indukce říká, že k důkazu věty Pro každou formuli cp e O platí J {q)) stačí ověřit platnost těchto tří tvrzení: * Pro každé AeAí platí T(A). * Jestliže platí T(cp), pak platí také T(--(p). * Jestliže platí T(cp) a T(ip), pak platí také T(cp => ip). (Dokazujeme tak vlastně indukcí podle „délky" zápisu formule.) Věta 8. Buď J7: O —» O funkce definovaná induktivně takto: • .F(A) = --A (A e A*; Pak pro každé 6 e ® p/ar/, že 6 a J^(6) ysoi/ ekvivalentní. Důkaz. Indukcí ke struktuře 6. (= je „definiční rovnítko" pro formule.) • 9 = A. Formule Aa- --A jsou ekvivalentní. • 6 = --cp. Potřebujeme dokázat, že ^(p a J^(^(p) jsou ekvivaletní. Podle definice .F platí ^(--(p) = -,Jľ(cp), stačí tedy ověřit ekvivalenci --cp a -^(cp). Podle indukčního předpokladu jsou cp a F((p) ekvivalentní, proto jsou ekvivalentní také --cp a-^cp). • 9 = (p => ip. Musíme dokázat ekvivalenci formulí cp => ip a T{<$ => ip). Podle definice .F to znamená dokázat, že pro každou valuaci y platí Můžeme přitom předpokládat, že cp je ekvivalentní F((p), a že \p je ekvivalentní jf(i|;). Buď t valuace. Rozlišíme tři možnosti: * S-v(cp) = true a Sy[i\)) = false. Pak také S-y(F((p)) = řrwe a SyiJ7^)) = false. Tedy S^cp => ip) = false a S^(^J^*(\p) => -^(cp)) = false, což znamená, že platí (*). * S-v(cp) = frwe a S-v(ip) = frwe. Pak také S-y(F((p)) = frwe a SyiJ7^)) = frwe. Tedy S^(cp => ip) = frw a S^F^) => -^(cp)) = frw, což znamená, že platí (*)■ * S^(cp) = false. Pak také S^(JF((p)) = false, Tedy S^(cp => ip) = frwe a S^(^J^(\p) => -^(cp)) = frw, což znamená, že platí (*). D Co znamená „znegovat 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říct, že není pravda, že tě nemám nerad." • Výrokové formule se proto obvykle prezentují v normálním tvaru, kde se negace vyskytují pouze u výrokových proměnných. • Každou výrokou formuli lze převést do normálního tvaru, pokud povolíme užívání odvozených spojek A a V. * Pro ilustraci --(A => B) je ekvivalentní AA-B, * -(C A (-A => B)) je ekvivalentní -C V (-A A-B). • „Znegováním formule" se obvykle myslí převod --cp do normálního tvaru. Formální postup negace 74 Induktivně definujeme funkce T a Q předpisy (A) = A 0(A) = -A h) = = ^(cp)AJ^) ö() (cp^xl>) = = .F( .F(t|>) Q(v^A>) = = f((p)A6W (

))V(ö()) Pro libovolnou formuli cp platí, že JT((p) je jí ekvivalentní formule v normálním tvaru a (/(cp) je formule v normálním tvaru ekvivalentní negaci --cp. Uvedené formální předpisy takto vyjadřují „intuitivní postup negace" v matematicky přesném tvaru. 9617 Příklad: • Uvažme formuli -(A => -(B V -(B => -A))). Platí ^HA^iBViB^-A)))) = ö(A^iBViB^-A))) = ^■(A)A6HBViB4-A))) = AAf(BViB4-A)) AA(f(B)VfHB4-A))) = AA(BVg(B^-A)) AA(BV(^(B)AöhA))) = AA(BV(BAf(A))) A A (B V (BA A)) • Formuli AA (B V (B AA)) lze dále zjednodušit na (ekvivalentní) formuli A AB. To ale je již matematicky neformální (heuristický) postup. Problém splnitelnosti výrokových formulí Definice 9. Formule (p g O y e splnitelná, právě když existuje valuace y taková, žeSy[(p) = true. Problém: Splnitelnost výrokových formulí (SAT) Instance: cp g O Otázka: Je cp splnitelná? Je problém splnitelnosti algoritmicky řešitelný? • Ano. Obsahuje-li daná cp g O právě n výrokových proměnných, stačí vyzkoušet všechny možné valuace těchto proměnných, kterých je 2n. • Výše uvedený algoritmus není příliš praktický. Předpokládejme, že jednu valuaci lze vyzkoušet za 1 nanosekundu. Uvažme formuli, které má 100 výrokových proměnných. Pak všechny valuace vyzkoušíme zhruba za 1047 let. • Počet „časových jednotek", které počítač potřebuje k realizaci uvedeného algoritmu řešení SAT pro formuli s n proměnnými, je exponenciální v n. Otázka, zda existuje nějaký „lepší" algoritmus, který vyžaduje pouze p(n) časových jednotek (kde p je nějaký polynom v proměnné n), je ekvivalentní otázce zda V = AfV, což je nejslavnější otevřený problém teoretické informatiky. • Pomocí „rychlého" algoritmu pro problém SAT by bylo možné „rychle" řešit celou řadu dalších problémů, dá se říci že skoro všechny „praktické" problémy. (Např. rozložit dané přirozené číslo na součin prvočinitelů, tedy „definitivně" prolomit RSA šifru. Stejně tak pro DSA šifry.) • Pro zajímavost, existuje matematický model hypotetického výpočetního zařízení (kvantový počítač), na němž je možné prvočíselný rozklad spočítat „rychle". Princip fungování kvantového počítače je značně komplikovaný a není jasné, zda a kdy se ho technicky podaří sestrojit. Pro rychlejší řešení problému SAT však, zdá se, ani kvantový počítač nepomůže. Neformální zmínka o predikátové logice • 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 bud pravdivé nebo nepravdivé pro každou konkrétní volbu parametrů. Výrokové proměnné lze chápat jako predikáty bez parametrů. * x > 3 * R je ekvivalence na M * čísla x a y jsou nesoudělná • Z predikátů lze vytvářet komplikovanější formule pomocí výrokových spojek a kvantifikátorů. * Vx. cp „pro každou volbu parametru x platí formule cp" * 3x. cp „existuje alespoň jedna volba parametru x, pro kterou platí cp" • Poukud není z kontextu jasné, co lze za daný parametr dosazovat, užívá se notace Vx e M. (p a 3x e M.. cp (jen pokud je daný parametr prvkem nějaké 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 Vxi. Vx2. • • • Vxn. cp se někdy krátce píše Vxi, X2, • • •, xn. cp. Podobně u existenčního kvantifikátoru. • Příklady: * Každé prvočíslo větší než 2 je liché. VxgN. (P(x)Ax>2) => L(x) * Každé číslo n, které není prvočíslem, je dělitelné nějakým číslem y kde n =£ y ay > 1- Vn. (--P(n) => 3y .{y\nA n^kj A y >])) * Jsou-li R a S ekvivalence na M, je také RUS ekvivalence na M. VMVR,S : (E(M,R)AE(M,S)) => E(M,RUS) 80 Je-li každá proměnná v dané formuli kvantifikovaná (tj. formule je uzavřená), pak je celá formule buď pravdivá nebo nepravdivá. Jak negovat formule predikátové logiky? Jr{?{x])...)xn)) = Píxi,...,^) Q{?{x])...)xn)) = -,P(xi,...,xn) •F(Vx.cp) = Vx..F((p) ö(Vx.cp) = 3x.£/((p) jF(3x.(p) = 3x.JF((p) £/(3x.(p) = Vx.ö(cp) Uvažme například formuli -(VMVR,S : (E(M,R)AE(M,S)) =^> E(M,RUS)). Pak ^h(VMVR,S : (E(M,R)AE(M,S)) => E(M,RUS))) = £(VMVR,S : (E(M,R)AE(M,S)) => E(M,RUS)) 3M3R,S.e((E(M,R)AE(M,S)) => E(M,RUS)) 3M3R,S. (E(M,R) A E(M,S) A HE(M,RUS)) Induktivní definice množin Buď N množina. Induktivní definice (nějaké) množiny M c N má obecně tento tvar: • Vymezení bázových prvků M. (Každý bázový prvek musí být prvkem N.) • Vymezení konečně mnoha induktivních pravidel (neboli uzáverových vlastností) množiny M. Induktivní pravidlo je určeno funkcí f : NT —» N, kde n e N, a je tohoto tvaru: Jestliže xi, • • •, Xn e M, pak také f (xi, • • •, xn) e M. (Říkáme také, že M je uzavřená na f). • Posledním bodem induktivní definice, který se často vynechává, je požadavek, že každý prvek M vznikne z bázových prvků konečně mnoha aplikacemi induktivních pravidel. Definice 10. Řekneme, že daná induktivní definice množiny M je jednoznačná, právě když každý prvek M lze odvodit z bázových prvků pomocí induktivních pravidel právě jedním způsobem. Příklady: • Definujme množinu M c N induktivně takto: * 3 G M. * Jestliže x g M, pak x + 2 g M. Pak M je přesně množina všech lichých čísel větších než 1. • Pro každé y e N definujme množinu Mv c N induktivně takto: * y G Mv. * Jestliže x g My a x + 1 je liché, pak x + 2 g M. Pak např. M3 = {3}, M4 = {4 + 2i | i g N0}. • Definujme množinu M c N induktivně takto: * 3,11 G M * Jestliže x, y, z g M, pak také (x + y )z, x.y, xx/yz jsou prvky M. Pro každou množinu I označíme symbolem I* množinu všech konečných posloupností složených z prvků I. Např. ababab e {a, b}*, (3)©(2)e{(,),©,2,3}*5 apod. • Nechť I = At u {-■,=>, (,)}. Množina OCX* všech výrokových formulí byla definována induktivně. • Nechť I = {0,1,2,3,4,5,6,7,8,9,0,©, (,)} Definujme množinu jednoduchých výrazů SExp c I* induktivně takto: * Dekadický zápis každého přirozeného čísla je prvek SExp. * Jestliže x,y e SExp, pak také (x) 0 [y) a (x) © [y) jsou prvky SExp. Strukturální indukce • Důkazová technika aplikovatelná na tvrzení typu pro každé x g M platí T(x), kde M c N je definovaná induktivně. • Princip strukturální indukce říká, že k důkazu věty Pro každé x g M platí T(x) stačí ověřit platnost těchto tvrzení: * Pro každý bázový prvek x množiny M platí T(x). * Pro každé induktivní pravidlo zadané funkcí f:NMNa každá xi, • • •, xn e M platí, že jestliže T(xi), • • •, T(xn) jsou pravdivá, pak T(f (xi, • • •, xn)) je také pravdivé. (Postupuje se vlastně indukcí podle „hloubky odvození" každého prvku M.) Induktivně definované funkce z induktivně definovaných množin Nechť M c N je induktivně definovaná, a nechť je tato definice jednoznačná. Induktivní definice funkcí T\ : M —» Kí, • • • , Ty : M —» Kk má obecně tento tvar: • Pro každé 1 < i < k a každý bázový prvek x množiny M se definuje hodnota Ti{x). • Pro každé induktivní pravidlo a každé 10 && b>0) { while (a<=b) b = b-a; x = a; a = b; b = x; } printf("Výsledek je %d.\n",a+b); Nejprve se zamyslete, proč tato smyčka vždy skončí pro jakákoliv celá a, b. (Kód vypočítá největšího společného dělitele čísel a,b.) Jak vidíme, není vždy na první pohled zřejmé, co i krátký programový kód „dělá". Pokud chceme mít naprostou jistotu, co daný program dělá, musíme podat matematický důkaz správnosti. Jednoduchý deklarativní programovací jazyk • Nechť Var = {x,-y,z,.. .}je spočetná množina proměnných. • Nechť Num = {0,1,52,397,...} je množina všech dekadických zápisů přirozených čísel. • NechťFVar = {f, g, h,...} je spočetná množina funkčních symbolů. Ke každému f g FVar 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 f g FVar 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 * E2 | Ei - E2 | ( Ei ) I fíE!,---^) | if Ei then E2 else E3 V uvedené rovnici je x g Var, n g Num, f g FVar a a g N je arita daného f. • Takováto specifikace syntaxe je abstraktní v tom smyslu, že se nezabývá tím, jak výrazy jednoznačně zapsat do řádku jako posloupnost symbolů. Je na nás, abychom napsali dostatečně mnoho závorek a případně stanovili prioritu operátorů tak, aby bylo zcela jasné, jak daný výraz podle uvedené rovnice vznikl. • Příklady: * 2 + 3*4 * f(2 + x,g(y,3*y)) * if x —lthen (2 + f(-y)) else g(x,x) (Vyhodnocení podmínky v „if" testuje ne nulovost argumentu.) • Deklarace je konečný systém rovnic tvaru f i (xi, • • •, xQl) = Ei kde pro každé 1 < i < n platí, že ft e FVar, at je arita ft, xi, • • • ,Xq. g Var a Et je výraz, v němž se mohou vyskytovat pouze proměnné xi, • • •, xQí a funkční symboly f i,---,fn. • Příklady: * f (x) = if x then x*f(x —1) else 1 ^ f (x) = g(x-l,x) g (x,-y) = if x then f [y) else 3 (Jak uvidíme formálně později, konvencí našich výpočtů je neužívat záporná čísla, místo toho O - 1 „="0.) * f(x) = f(x) (Nezapisuje toto náhodou „nekonečnou smyčku"?) Formalizace pojmů „výpočetní krok" a „výpočet" • Bud A deklarace. Symbolem Exp{A) označíme množinu všech výrazů E, které splňují tyto dvě podmínky: * E neobsahuje žádnou proměnnou; * jestliže E obsahuje funkční symbol f, pak f byl v A deklarován. • Množinu Exp{A) lze definovat také induktivně: E ::= n | E] + E2 | E] - E2 | E] * E2 | E] ^- E2 | f(Ei, • • • , Ea) I if E] then E2 else E3 V uvedené rovnici je n g Num, f je funkční symbol deklarovaný v A a a g N je arita daného f. • Induktivně definujeme funkci „krok výpočtu" i-> : Exp{A) —» Exp{A)\ místo i-»(E) = F budeme psát E i-> F. * n i-» n pro každé n e Num. * Pro E = Et + E2 definujeme krok výpočtu takto: — Jestliže Ei,E2 e Num, pak Ei + E2 i-> z kde z je dekadický zápis čísla Ei + E2. — Jestliže Ei ^ Num, pak Ei + E2 m> F + E2 kde Ei i-> F. — Jestliže Ei e Num a E2 ^ Num, pak Ei + E2 ^ Ei + F kde E21-> F. * Pro E = Et — E2 definujeme krok výpočtu takto: — Jestliže Ei,E2 e Num, pak Ei - E2 ^ z kde z je dekadický zápis čísla max{0,Ei -E2} (nezápornost výsledku!). — Jestliže Ei ^ Num, pak Ei — E2 ^ F — E2 kde Ei i-> F. — Jestliže Ei e Num a E2 ^ Num, pak Ei — E2 ^ Ei — F kde E21-> F. * Pro E = Et * E2 definujeme krok výpočtu takto: — Jestliže Ei,E2 e Num, pak Ei * E2 i-> z kde z je dekadický zápis čísla Ei * E2. — Jestliže Ei ^ Num, pak Ei * E21-> F * E2 kde Ei i-> F. — Jestliže Ei e Num a E2 4. Num, pak Ei * E2 m> Ei * F kde E2 i-> F. * Pro E = Et t E2 definujeme krok výpočtu takto: - Jestliže Ei, E2 e Num, pak Ei -=- E2 i-> z kde z je dekadický zápis celé části čísla Ei/E2. Pokud E2 = 0, je z = 0. - Jestliže Ei ^ Num, pak Ei -=- E2 i-> F -=- E2 kde Ei i-> F. - Jestliže Ei e Num a E2 ^ Num, pak Ei -=- E2 i-> Ei -=- F kde E21-> F. * Pro E = if Et then E2 else E3 definujeme krok výpočtu takto: - Jestliže Ei e Num a Ei =0, pak if Ei then E2 else E31-> E3. - Jestliže Ei e Num a Ei ^ 0, pak if Ei then E2 else E3 ^ E2. - Jestliže Ei ^ Num, pak if Ei then E2 else E3 ^ if F then E2 else E3 kde Ei ^F. * Pro E = f (Et , • • •, Ek) definujeme krok výpočtu takto: - Jestliže Ei, • • •, Ek e Num, pak f (Ei, • • •, Ek) i-> E(xi \ Ei, • • •, xk \ Ek) - Jinak fíEi, • • •, Ek) i-> f(E1r • •, E^, F, Ei+1, • • • ,Ek), kde i je nejmenší index pro který platí Et ^ Num a Et h F. • Reflexivní a tranzitivní uzávěr relace i-> značíme i->* („výpočet"). Příklady výpočtů • Uvažme deklaraci f (x) = if x then x * f (x - 1) else 1. Pak např. f (3) ^* 6, neboť f (3) ^ if 3 then 3 * f (3 - 1) else 1 ^ 3 * f (3 - 1) ^ 3*f(2) ^ 3* (if 2then2*f(2-l) elsel) ^ 3* (2* f(2-1)) ^ 3*(2*f(l)) ^ 3* (2* (if lthenl * f (1 - 1) elsel)) ^ 3 * (2 * (1 * f(l-l))) ^ 3* (2* (1 *f(0))) ^ 3* (2* (1 * if 0 then 0 * f (0 - 1) elsel)) ^ 3* (2* (1*1)) ^ 3 * (2*1) ^3*2 ^6 • Uvažme deklaraci f (x) = g(x —l,x), g (x,-y) = if x then f (-y) else 3. Pak např. f(3) ^*f(3), neboť f (3) i-> g(3 - 1,3) i-> g(2,3) i-Hf 2 then f (3) else 3 i-> f (3) • Uvažme deklaraci f (x) = f (x). Pak pro každé n e Num platí f (n) i-> f (n) a podobně f (f (n)) i-> f (f (n)). Ale f (f (2 + 3)) i-> f (f (5)) i-> f (f (5)). Důkaz správnosti programu Příklad 14. Věta: Uvažme deklaraci A obsahující pouze rovnici f (x) = if x then x * f (x -1) else 1 Pak pro každé n e N0 platíí{n) i->* m, /cde m = n!. Důkaz. Indukcí vzhledem krt. • u = 0. Platí f (0) i-> if 0 then o*f(0-l) elsel i-> 1. • Indukční krok. Nechť n + 1 = k. Pak f (k) h-> if kthenk*f(k-l) elsel i-> k*f(k-l) i-> k*f(w) kde w = n. Podle I.P. platí f (w) i->* u, kdeu = n!. Proto k*f(w) i->* k*u i-> v, kde v= (n+1) -n! = (n+ 1)!. D Důkazy „neukončenosti" výpočtů Věta 11. Buď A deklarace. Pro každé i e N definujeme relaci i-»1 c Exp [A) x Exp [A) předpisem \-r = h- o - • o h,. Dále definitoricky klademe m>° = {(E,E) | E e Exp{A)}. Pa/c^* = \X=0 ^- Podle předchozí věty platí, že E ^* F právě když E i-»1 F pro nějaké i e N0. Navíc musí existovat nejmenší i s touto vlastností. Toto pozorování může být užitečné v důkazech „neukončenosti" výpočtů. Příklad 15. Věta: Uvažme deklaraci f(x) = f(x). Pro každé n e Num platí, že neexistuje žádné m e Num takové, ze f (n) i->* m. Důkaz. Sporem. Předpokládejme, že existují 11,111 e Num takové, že f(n) 1-»* m. Pak existuje nejmenší i e N0 takové, že f (n) \->l m. Jelikož výrazy f (n) a m jsou různé, platí i > 0. Jelikož i-»1 = m^-1 o \-> a f (n) 1-» f (n), platí f (n) m^-1 m, což je spor s minimalitou i. D Další příklady I („fixace parametru") Příklad 16. Věta: Uvažme deklaraci A obsahující pouze rovnici g(x,-y) = ifx theny + g(x —1,-y) elseO Pak pro každé m, n g No platí g (m, n) i->* z, /cc/e z = m • n. Důkaz. Buď n g No libovolné ale pro další úvahy pevné. Dokážeme, že pro každé m g N0 platí g(m, n) i->* z, kde z = m • n. Indukcí vzhledem k m. • m = 0. Platí g(0,n) i-> if 0 then n+g(0-l,n) else 0 i-> 0. • Indukční krok. Nechť m + 1 = k. Pak g(k,n) •-> if kthen n + g(k- l,n) else 0 i-> n + g(k-l,n) h-> n + g(w,n) kde w = m. Podle I.P platí g(w,n) i->* u, kde u = m- n. Dále n + g(w,n) i->* n + u i—» v, kde v = n + (tu • n) = (tu + 1) • n. D Další příklady II („indukce k součtu parametrů") Příklad 17. Věta: 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) elseO) elseO Pak pro každé m, n e No platí g (m, n) ^* 0. Důkaz. Tvrzení Pro každé m,neN0 platí g (m, n) i->* 0 nelze dokázat indukcí vzhledem k m ani indukcí vzhledem k n. Důkaz lze ovšem vést indukcí k „součtu" m a n. To znamená, že výše uvedené tvrzení nejprve přeformulujeme do následující (ekvivalentní) podoby: Pro každé i e N0 platí, že jestliže i = m+n, kde m, n e N0, pak g (m, n) m>* 0 Toto tvrzení nyní dokážeme indukcí vzhledem k i: 101 • i = 0. Jestliže i = m + n, kde m, n e N0, pak m = n = 0. Dokážeme, že g(0,0) ^*0. Platí g(0,0) •-> if 0 then (if 0 then g(0- 1,0) + g(0,0-1) else 0) else 0 •-> 0 • Indukční krok. Nechť i + 1 = m + n, kde m, n e N0. Nyní rozlišíme tři možnosti: * m = 0. Pak platí g(0,n) •-> if Othen (if n then g(0-l,n) + g(0,n-l) else 0) else 0 •-> 0 * m > 0, n = 0. Pak platí g (m, 0) •-> if m then (if 0 then g (m - 1,0) + g (m, 0-1) else 0) else 0 •-> if Othen g (m- 1,0) + g (m, 0-1) else 0 •-> 0 * m > 0, n > 0. Pak platí g (m, n) \-> if m then (if n then g (m - 1, n) + g (m, n - 1) else 0) else 0 i-> if n then g (m - 1, n) + g (m, n - 1) else 0 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 — l,n) + g(m,n — 1) \->* 0 + g(m,n —1) \->* 0 + 0 \->* 0. Tím jsme s důkazem matematickou indukcí hotovi. D * 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 18. Věta: 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) elsel) elsel Pak pro každé m, n e No platí g (m, n) ^* k, kde k = (m^n) (kombinační číslo). Důkaz. Toto tvrzení opět dokážeme 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 (:::)-(.;,)-©■ Nepřipomíná to trochu naši deklaraci? Je však třeba správně „nastavit" význam parametrů a,b. • i = 0. Jestliže i = m + n, kde m,n e N0, pak m = n = 0. Dokážeme, že g(0,0) i->*1. Platí g(0,0) ■-> if 0then (if 0then g(0- 1,0) + g(0,0-1) elsel) elsel ^ 1 103 Indukční krok. Nechť i + 1 = m + n, kde m,n e N0. Nyní rozlišíme tři možnosti: * m = 0. Pak platí g(0,n) h-> if Othen (if nthen g(0-l,n) + g(o, n - 1) else 1) else 1 •-> 1 * m > 0, n = 0. Pak platí g (m, 0) h-> if m then (if 0 then g (m - 1,0) + g (m, 0-1) else 1) else 1 •-> if Othen g (m- 1,0) + g (m, 0-1) else 1 •-> 1 * m > 0, n > 0. Pak platí g (m, n) •-> if m then (if n then g (m - 1, n) + g (m, n - 1) else 1) else 1 i-> if n then g (m - 1, n) + g (m, n - 1) else 1 i-> g (m - 1, n) + g (m, n - 1) Podle I.P platí g(m-l,n) ^* (^V) a současně g(m,n-l) ^* (m+^_1). Přitom z Pascalova trojúhelníka plyne /m + n—K /m + n—K /m + n—1+1\ /m + n\ Vra—1/ V m / V m / Vra/' a proto g(m-l,n) + g(m,n-l) •->* ( ). V m / D Další příklady III („zesílení dokazovaného tvrzení") Příklad 19. Věta: Uvažme deklaraci A obsahující tyto rovnice: f (x) = if x then h(x) else 1 h(x) = if x then f (x -1) + h(x -1) else 1 Pak pro každé n e N0 platí í (n) i->* m, /cde m = 2n. Důkaz. Tvrzení Pro každé n e N0 platí f (n) i->* m kde m = 2n nelze dokázat indukcí vzhledem k n. Řešením je přeformulování dokazovaného tvrzení do silnější podoby, kterou již indukcí dokázat lze: Pro každé n e N0 platí f (n) ^* m a h(n) i->* m, kde m = 2n. Toto tvrzení již poměrně snadno dokážeme indukcí vzhledem k n: • n = 0. Platí f (0) i-> if 0 then h(0) else 1^1 h(0) i-> if 0 then f(o-l)+h(0 -1) else 1 i-> 1 • Indukční krok. Nechť n + 1 = k. Platí f (k) i-> if k then h(k) else 1 i-> h(k) i-> if k then f (k- 1) + h(k - 1) else 1 i-> f(k - 1) + h(k - 1) i-> f(w)+h(w) kde w = k— 1 = n. Podle I.P. platí f (w) i->* m, kde m = 2n. Zároveň také (naše „zesílení") platí i h(w) ^* m, a proto f(w)+h(w) i—»* m + m i—» 2m i—» q, kde q =m+m = 2-2n = 2n+1 = 2k. Proto f (k) nqa 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-> if kthenf(k-l)+h(k-l) elsel i-> f (k - 1) + h(k - 1) i-> f (w) + h(w) kde w = k— 1 = n. Podle I.P. platí f (w) i->* m, kde m = 2n, a také h(w) i->* m, a proto f(w)+h(w) i—»* m + m i—» q, kde q =m + m = 2-2n = 2n+1 = 2k. Proto h(k) h qai druhá část našeho tvrzení platí pro n +1 = k. D Euklidův algoritmus Příklad 20. Věta: Uvažme deklaraci A obsahující pouze rovnici 9 (x, y) = /rx — -y then g (x — y, y) else [if y — x then g (x, y — x) else x) Pak pro každé nenulové m, n g N platí g (m, n) ^* 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 e N, pak z je největší společný dělitel čísel m, n.) • i = 2. Pak m, n = 1 a platí g(l, 1) ■-> if 1 - 1 then g(l - 1,1) else (if 1 - 1 then g(l, 1-1) else 1) ■-> if 0 then g(l - 1,1) else (if 1 - 1 then g(i, 1-1) else 1) ■-> if 1-lthen g(l,l-l) elsel ■-> if 0 then g(i,i - 1) else 1 ■-> 1 • Indukční krok. Nechť i + 1 = m + n kde m, n e N. Jsou 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) i—» if 0 then g (m - n, n) else (if n - m then g (m, n - m) else m) i-> if n — m then g (m, n — m) else m i—» if 0 then g (m, n — m) else m i—» m * 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) i—» if 0 then g (m - n, n) else (if n - m then g (m, n - m) else m) i-> if n — m then g (m, n — m) else m i—» if z then g (m, n — m) else m i—» g(m,n-m) i-> g(m,k) kde k = n —m. Platí m + k = m+(n —m) = n < i, takže podle I.P 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, platí d < z. * m > n. Pak g (m, n) ^* g(m-n,n) i-> g(k,n) kde k = m —n. Podle I.P 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 největší společný dělitel čísel man. D 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? 109 Ještě příklad Vraťme se k předchozí ukázce (velmi „hutného") C kódu, který inkrementuje dekadický zápis čísla D uloženého po číslicích v poli. for (i=0; i? D[i-1]==0: 1; i++) D[i] = (D[i]+l)%10; Zapišme tento kód naší formální deklarací. • Jelikož nejsou k dispozici proměnné typu pole, „pomůžeme si" funkcí v(i) udávající i-tou dekadickou číslici výstupu. • Obdobně pro zadání číslic vstupu použijeme funkční deklarace z[i) = .... • Cyklus for nahradíme rekurzí (běžný postup). • Nakonec „trikově" nahradíme řídící podmínku našeho cyklu zavedením nové funkce p (i), která vyjadřuje „přenos" do i-tého řádu. (p(i) g {0,1}, na počátku p(0) = 1.) • Dohodneme se, že číslice jsou indexovány od nejnižšího řádu i = 0,1,2,.... Celá (formální) deklarace A bude vypadat následovně. Příklad 21. Věta: Uvažme deklaraci A obsahující tyto rovnice: v(i) = (z(i)+p(i))%10 p (i) = if i then (#7z(i — 1) + p(i — 1) — 9 řften 1 e/se 0) e/se 1 Pak pro každé i e N0 p/ar/, ze v(i) i/cfává dekadickou číslici i-tého řádu zprava čísla m + 1, /tete m má dekadický zápis po číslicích (z[i) z(i — 1)... z(1) z(0)) 10. Dokažte si toto sami za domácí úkol (diskutujte na IS). Je potřeba použít matematickou indukci se zesíleným předpokladem, který se bude vhodně vyjadřovat i o významu hodnoty p (i) („přenos"). Pochopitelně je třeba pro úplnou správnost řešení rozepsat operaci „modulo" % pomocí povolených aritmetických operací, což si také za úkol vyzkoušejte.