Drsná matematika Martin Panák, Jan Slovák Pokus o učební text pro začínající studenty informatiky přibližující podstatnou část matematiky v rozsahu čtyř semestrálních přednášek. Prozatím jsou zaznamenány první tři semestry přibližně v odpředneseném rozsahu. Poslední semestr je zapisován průběžně. i Obsah Kapitola 1. Úvod a motivace 1 1. Čísla a funkce 1 2. Kombinatorické formule 3 3. Diferenční rovnice 7 4. Pravděpodobnost 14 5. Geometrie v rovině 23 6. Relace a zobrazení 31 Kapitola 2. Elementární lineární algebra 37 1. Vektory a matice 37 2. Determinanty 45 3. Vektorové prostory a lineární zobrazení 51 4. Vlastnosti lineárních zobrazení 62 Kapitola 3. Linární modely 73 1. Lineární rovnice a procesy 73 2. Lineární diferenční rovnice a filtry 76 3. Markovovy procesy 81 4. Více maticového počtu 83 5. Rozklady matic a pseudoinverze 88 Kapitola 4. Analytická geometrie 95 1. Afinní geometrie 95 2. Euklidovská geometrie 105 3. Projektivní geometrie 120 Kapitola 5. Zřízení ZOO 125 1. Interpolace polynomy 125 2. Spojité funkce 133 3. Derivace 146 4. Mocninné řady 155 Kapitola 6. Diferenciální a integrální počet 167 1. Derivování 167 2. Integrování 179 3. Nekonečné řady 195 Kapitola 7. Spojité modely 201 1. Aproximace pomocí Fourierových řad 201 2. Integrální operátory 207 iii iv OBSAH Kapitola 8. Spojité modely s více proměnnými 213 1. Funkce a zobrazení na Rn 213 2. Integrování podruhé 242 3. Diferenciální operátory 250 4. Poznámky o numerických metodách 259 Kapitola 9. Kombinatorické metody 261 1. Grafy a algoritmy 261 2. Aplikace kombinatorických postupů 282 Kapitola 10. Algebraické struktury a techniky 303 1. Grupy 303 2. Okruhy polynomů a tělesa 314 3. Uspořádané množiny a Booleovská algebra 322 4. Kódy (a šifry?) 329 Kapitola 11. Statistické metody 333 1. Pravděpodobnost 334 2. Popisná statistika 346 3. Matematická statistika 346 Literatura 347 KAPITOLA 10 Algebraické struktury a techniky čím větší abstrakce, tím větší zmatek? ­ ne, často to bývá naopak ... Nyní se vrátíme k docela formálnímu studiu pojmů, jejichž na první pohled zcela abstraktní definice ve skutečnosti odráží velmi širokou třídu reálných vlast- ností věcí kolem nás. Určitě bude užitečné si před dalším čtením připomenout první a šestou část první kapitoly, kde jsme podobně abstraktně pohlíželi na čísla, se kte- rými počítáme, a obecněji na vztahy mezi objekty, které jsme abstrahovali do tzv. relací. 1. Grupy Budeme si pohrávat s objekty a se situacemi, ve kterých je možné rovnice a x = b vždy jednoznačně řešit (tak jako u lineárních rovnic jsou objekty a a b jsou dány, zatímco x hledáme). Půjde o tzv. teorii grup. Všimněme si, že zatím nic nevíme o povaze objektů, ani co znamená ta tečka. Nejprve si zavedeme malý slovníček pojmů. Následně projdeme příklady, ve kterých se s takovými objekty potkáváme. A pak už budeme moci ,,budovat teo- rii... 10.1 10.1. Definice. Pro libovolnou množinu A: ˇ binární operace na A je zobrazení A × A A, které budeme zpravidla značit (a, b) a b, množina s binární operací je grupoid ˇ binární operace je asociativní, jestliže pro všechny prvky v A platí a (b c) = (a b) c ˇ binární operace je komutativní, jestliže pro všechny prvky v A platí a b = b a ˇ levá jednotka v A je takový prvek e A, že pro všechny prvky v A platí ea = a; obdobně pro pravou jednotku musí platit pro všechny prvky a e = a ˇ jednotka binární operace je prvek e, který je pravou i levou jednotkou zároveň ˇ pologrupa (A, ) je grupoid s binární operací, která je asociativní ˇ prvek a-1 je levou inverzí k prvku a v pologrupě (A, ) s jednotkou e, jestliže platí a-1 a = e; obdobně je pravou inverzí a-1 takový prvek, pro který je a a-1 = e ˇ prvek a-1 je inverzní k a v pologrupě s jednotkou, jestliže je levou i pravou inverzí zároveň ˇ grupa (G, ) je pologrupa s jednotkou, ve které má každý prvek inverzi ˇ komutativní grupa, resp. komutativní pologrupa, je taková, kde je operace komutativní. 303 304 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY ˇ Je-li (A, ) grupa (případně pologrupa), pak její podmnožinu B A, která je uzavřená vůči zúžení operace a zároveň je spolu s touto operací grupou, nazýváme podgrupa. 10.2 10.2. Příklad. (1) Přirozená čísla N = {0, 1, 2, . . . }, spolu s kteroukoliv z ope- rací sčítání a násobení jsou asociativní a komutativní pologrupa s jednotkou, neexistují v ní ale inverzní prvky. (2) Celá čísla Z = {. . . , -2, -1, 0, 1, 2, . . . } jsou grupoid vůči kterékoliv z operací sčítání, odčítání, násobení. Jsou dokonce komutativní grupou vzhledem ke sčí- tání, jsou však jen komutativní pologrupou vůči násobení (neexistují inverze k prvkům a = 1). Operace odčítání není ani asociativní (např. (5 - 3) - 2 = 0 = 5 - (3 - 2) = 4). Všimněte si také, že pro odečítání je nula pravý neutrální prvek, ne však levý. Dokonce v tomto případě levý neutrální prvek neexistuje. (3) Racionální čísla Q jsou komutativní grupou vzhledem ke sčítání a nenulová racionální čísla jsou grupou vůči násobení. Celá čísla spolu se sčítáním jsou jejich podgrupou. (4) Pro k N, množina všech k-tých odmocnin z jedničky, tj. množina {z C; zk = 1} je konečná grupa vůči násobení komplexních čísel. Např. pro k = 2 dosta- neme grupu {-1, 1} se dvěma prvky, které jsou oba samy sobě inverzí, zatímco pro k = 4 dostáváme grupu G = {1, i, -1, -i}. (5) Množina Matn všech čtvercových matic je (nekomutativní) pologrupa vzhledem k násobení matic a komutativní grupa vzhledem ke sčítání matic (viz odstavce 2.2­2.5). (6) Množina všech lineárních zobrazení Hom(V, V ) na vektorovém prostoru je polo- grupa vzhledem ke skládání zobrazení a komutativní grupa vzhledem ke sčítání zobrazení (viz odstavec 2.31). (7) v obou předchozích příkladech, podmnožina invertibilních objektů uvažované pologrupy tvoří grupu. V případě (5) jde o tzv. grupu invertibilních matic, ve druhém o grupu lineárních transformací vektorového prostoru. 10.3 10.3. Grupy permutací. Zpravidla grupy a pologrupy potkáváme jako množiny zobrazení na pevně dané množině M, které jsou uzavřeny vůči skládání zobrazení. Často si ale tuto skutečnost přímo neuvědomujeme. Nejsnáze je tato souvislost vidět na konečných množinách M. Na každé takové množině o m = |M| N prvcích (prázdná množina má 0 prvků) máme k dispozici mm možných definic zobrazení (každý z m prvků můžeme zobrazit na kterýkoliv v M) a všechna taková zobrazení umíme skládat. Pokud chceme, aby existovala k zobrazení : M M jeho inverze -1 , musí být bijekcí. Složením dvou bijekcí vznikne opět bijekce a proto podmnožina m všech bijekcí na množině M o m prvcích je grupa. Říkáme jí grupa permutací (na m prvcích). Sám název přitom uvádí jinou souvislost, kdy místo bijekcí na konečné množině vnímáme permutace jako přerovnání rozlišitelných prvků. Potkávali jsme se s ní např. při studiu determinantů, 2.14. Promysleme si podrobněji, jak vlastně násobení v takové grupě vypadá. U (malé) konečné grupy si můžeme snadno sestavit úplnou tabulku všech operací. Jestliže v grupě permutací 3 na číslech {1, 2, 3} označíme jednotlivá pořadí a = (1, 2, 3), b = (2, 3, 1), c = (3, 1, 2), d = (1, 3, 2), e = (3, 2, 1), f = (2, 1, 3), 1. GRUPY 305 pak skládání našich permutací je zadáno tabulkou a b c d e f a a b c d e f b b c a f d e c c a b e f d d d e f a b c e e f d c a b f f d e b c a Všimněme si podstatného rozdílu mezi permutacemi a, b a c a dalšími třemi. Ty první tři tvoří tzv. cyklus generovaný prvkem b nebo prvkem c: b2 = c, b3 = a, c2 = b, c3 = a a samy o sobě jsou tyto tři prvky komutativní podgrupou. V ní a je jednotka, a b s c jsou vzájemně inverzní. Je tedy tato podgrupa stejná jako je grupa Z3 zbytkových tříd celých čísel modulo 3, resp. jako grupa třetích odmocnin z jedničky v 10.2(4). Další tři prvky jsou samy sobě inverzí a každý z nich je tedy společně s jednotkou a podgrupou stejnou jako je Z2. Říkáme, že b a c jsou prvky řádu 3, zatímco prvky d, e a f jsou řádu 2. Obdobně se chovají všechny grupy permutací m konečných množin o m prv- cích. Každá permutace rozkládá množinu M na disjunktní sjednocení maximál- ních invariantních podmnožin, které dostaneme tak, že postupně vybíráme dosud nezpracované prvky x M a do třídy rozkladu Mx přidáváme všechny akce iterací k (x), k = 1, 2, . . . , dokud není k (x) = x. Každou permutaci tak dostáváme jako složení jednodušších permutací, tzv. cyklů, které se chovají jako identická permu- tace vně Mx a tak jako na Mx. Pokud přitom očíslujeme prvky v Mx jako pořadí (1, 2, . . . , |Mx|) tak aby i odpovídalo i (x), pak je naše permutace prostým posunu- tím o jednu pozici v cyklu (tj. poslední prvek je zobrazen zpátky na první). Odtud název cyklus. Zjevně přitom tyto cykly komutují, takže je jedno, v jakém pořadí z nich permutaci složíme. Nejjednodušší cykly jsou jednoprvkové pevné body permutace a dvouprvkové (x, (x)), kde ((x)) = x. Těm se říká transpozice. Protože každý cyklus zjevně můžeme poskládat z permutací sousedních prvků (necháme ,,probublat první prvek nakonec), lze každou permutaci napsat jako složení transpozic sousedních prvků. Můžeme samozřejmě vyjádřit pomocí transpozic i jinak, ale skutečnost, jestli po- třebujeme sudý nebo lichý počet permutací je na volbách nezávislá. Máme tedy definováno dobře zobrazení sgn : m Z2 = {1}, tzv. paritu. Dokázali jsme si znovu tvrzení, která jsme již využívali při studiu determinantů (viz 2.14 a dále): Věta. Každá permutace konečné množiny je složením cyklů. Cyklus délky lze vyjádřit jako složení -1 transpozic. Parita cyklu délky je (-1) -1 . Parita složení permutací je součinem parit jednotlivých z nich, tzn. že zobrazení sgn převádí složení permutací na součin sgn sgn v komutativní grupě Z2. 10.4 10.4. Symetrie ohraničených rovinných útvarů. V páté části první kapitoly jsme podrobně a elementárně rozebrali souvislosti invertibilních matic se dvěma řádky a dvěma sloupci a lineárními transformacemi v rovině. Viděli jsme také, že matice zadávají lineární zobrazení R2 R2 , které zachovávají standardní vzdá- lenosti právě, když jsou jejich sloupce ortonormální bazí R2 (což je jednoduchá podmínka na souřadnice matice, viz 1.43). Ve skutečnosti není obtížné dokázat (ale nebudeme to tu dělat), že každé zobrazení roviny do sebe, které zachovává velikosti 306 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY je affinní, tj. je složením lineárního a vhodné translace. 1 Jak jsme již připomněli, lineární část takového zobrazení přitom musí navíc být ortogonální. Všechna taková zobrazení tedy tvoří grupu všech ortogonálních transformací (nebo také euklidov- ských transformací) v rovině. Navíc jsme ukazovali, že kromě translací Ta o vektor a jde pouze o rotace R o jakýkoliv úhel kolem počátku a zrcadlení Z vůči ja- kékoliv přímce procházející počátkem (povšimněme si, že středová souměrnost je totéž jako rotace o ). Uvažme nyní nějaký rovinný obrazec, pro začátek třeba úsečku a rovnostranný trojúhelník. Ptáme se, jak moc jsou symetrické, tzn. vůči kterým trasformacím (zachovávajícím velikost) jsou invariantní. Jinak řečeno, chceme aby obraz našeho obrazce byl od původního k nerozeznání, dokud si nepopíšeme nějaké význačné body, třeba vrcholy trojúhelníka A, B a C a konce úseček. Zároveň je předem jasné, že všechny symetrie pevně zvoleného útvaru budou vždy tvořit grupu (většinou pouze s jediným prvkem, identickým zobrazením). U úsečky je situace obzvlášť jednoduchá ­ na první pohled je zřejmé, že jedinými jejími netriviálními symetriemi jsou rotace o , zrcadlení vůči ose této úsečky a zrcadlení vůči úsečce samotné a všechny tyto symetrie jsou samy sobě inverzí. Celá grupa symetrií úsečky má tedy čtyři prvky. Její tabulka násobení vypadá takto: R0 R ZH ZV R0 R0 R ZH ZV R R R0 ZV ZH ZH ZH ZV R0 R ZV ZV ZH R R0 a je tedy celá tato grupa komutativní. Pro rovnostranný trojúhelník už symetrií nacházíme víc: můžeme rotovat o /3 nebo můžeme zrcadlit vůči osám stran. Abychom dostali grupu celou, musíme přidat všechna složení takovýchto transformací. Už v 1.43 jsme viděli, že složení dvou zrcadlení je vždy otočením. Zároveň je zřejmé, že složení takových zrcadlení v opačném pořadí dá otočení o stejný úhel, ale s opačnou orientací. V našem případě tedy zrcadlení kolem dvou různých os vygenerují postupnou opakovanou aplikací všechny symetrie, který bude dohromady šest. Jestliže si umístíme trojúhelník v souřadnicích jako na obrázku, bude našich šest transformací zadáno maticemi a = 1 0 0 1 , b = -1 2 3 2 - 3 2 -1 2 , c = -1 2 - 3 2 3 2 -1 2 d = -1 0 0 1 , e = 1 2 - 3 2 - 3 2 -1 2 , f = 1 2 3 2 3 2 -1 2 . 1Jestliže totiž má zobrazení F : R2 R2 zachovávat velikosti, totéž musí být pravda pro přenášené vektory rychlostí, tj. Jacobiho matice DF(x, y) musí být v každém bodě ortogonální. Rozepsání této podmínky pro dané zobrazení F = (f(x, y), g(x, y)) : R2 R2 vede na systém diferenciálních rovnic, který má pouze afinní řešení. Zkuste si aspoň začít výpočet jako cvičení! (Návod: máme ukázat, že všechny parciální derivace F jsou nulové. To ale je podmínka nezávislá na volbě afinních souřadnic, proto složením F s lineárním zobrazením výsledek nemění. Můžeme proto pro pevný bod (x, y) složit (DF)-1 F, takže bez újmy na obecnosti lze rovnou předpokládat, že DF(x, y) je matice identického zobrazení. Derivováním rovnic pak dostáváme důsledky, které přímo říkají požadované tvrzení.) Ve skutečnosti vede stejný postup ke stejnému výsledku pro euklidovské prostory libovolné dimenze. 1. GRUPY 307 Sestavením tabulky pro násobení, tak jak jsme ji udělali pro grupu permutací 3 obdržíme právě stejný výsledek. Pro větší názornost jsou vrcholy označeny čísly, takže jsou příslušné permutace přímo čitelné. Obdobně umíme nacházet grupy symetrií s k různými rotacemi a k zrcadleními. Stačí si k tomu vzít pravidelný k-úhelník. Takové grupy symetrií se často označují jako grupy Dk a říká se jim dihedrální grupy řádu k. Tyto grupy jsou nekomuta- tivní pro všechny k 3, zatímco D2 je komutativní. Název patrně je odvozen od skutečnosti, že D2 je grupa symetrií molekuly vodíku. Stejně tak lze snadno najít obrazce, které mají pouze rotační symetrie a jde tedy o komutativní grupy, které se v chemii značí jako Ck. Říkáme jim cyklické grupy řádu k. K tomu postačí např. uvažovat pravidelný mnohoúhelník, u kterého nesymetricky ale pořád stejně pozměníme chování hran, viz. čerchované rozšíření trojúhelníku na obrázku. Všimněme si, že grupu C2 lze realizovat dvěma způsoby ­ buď jedinou netriviální rotací o nebo jediným zrcadlením. Věta. Nechť je M ohraničená množina v rovině R2 s nejvýše spočetnou grupou grupou symetrií G. Pak je grupa G buď triviální nebo jedna z grup Ck, Dk, s k 1. Důkaz. Kdyby nějaká množina M připouštěla jako svoji symetrii translaci, nemůže být ohraničená. Pokud by M připouštěla netriviální rotace s různými středy, opět nemůže být ohraničená. Totéž platí pro případ, že by existovala rotační symetrie a zrcadlení podél přímky, která neprochází středem rotace. Máme tedy k dispozici pouze rotace se společným středem a zrcadlení podél přímek tímto středem procházející. Zbývá tedy dokázat, že je celá grupa složena vždy buď pouze z rotací nebo vždy ze stejného počtu rotací a symetrií. Protože je ale vždy složením dvou různých zrcadlení rotace o úhel rovný polovině úhlu svíraného osami zrcadlení (viz 1.43) a tedy i naopak složením zrcadlení podle přímky p s rotací o úhel /2 dostame zrcadlení podél přímky svírající úhel s p. Odtud již vcelku snadno lze odvodit požadované tvrzení. 10.5 10.5. Symetrie rovinných dláždění. Složitější chování lze vypozorovat u rovin- ných obrazců v pásech nebo v celé rovině (něco jako možnosti symetrií pro různé dlažby). Nejprve uvažme množinu M, která je celá obsažena v pásu uzavřeném mezi dvěma rovnoběžkami. Pro symetrie takové množiny nepřicházejí v úvahu žádné netriviální rotace, kromě R, a jediná možná zrcadlení jsou buď podle osy pásu nebo vertikální. Zůstavají ještě pouze translace podle vektoru rovnoběžného s osou pásu. Všimněme si, že každá netriviální translace svými iteracemi zapřičiní, že celá grupa symetrií M bude již nutně nekonečná. Nepříliš složitá diskuse vede k popisu všech tzv. diskrétních grup symetrií pro rovinné pásy. Jsou to takové, kdy obraz libovolného bodu při působení všemi prvky grupy je diskrétní podmnožinou v rovině. Každá takové grupa je generována někte- rými z následujících možných symetrií: translace T, posunutá reflexe G, vertikální reflexe V , horizontální reflexe H a rotace R o . Věta. Každá grupa symetrií je jednoho z následujících sedmi typů. Jsou generovány (1) jedinou translací T (2) jedinou posunutou translací G (3) jednou translací T a jedním vertikálním zrcadlením V (4) jednou translací T a jednou rotací R (5) jednou posunutou translací G a jednou rotací R 308 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY (6) jednou translací T a horizontálním zrcadlením H (7) jednou translací T, horizontálním zrcadlením H a jedním vertikálním zrcadle- ním V . Důkaz nebudeme uvádět, zkuste si alespoň vykreslit symbolicky vzory s těmito symetriemi. Složitější je to se symetriemi obrazců, které vyplní celou rovinu. Nemáme zde prostor pro podrobnější zkoumání, nicméně alespoň poznamenejme, že všech tako- vých grup symetrií v rovině je pouze sedmnáct. Říká se jim dvourozměrné krysta- lografické grupy. Obdobná úplná diskuse je známa i pro trojrozměrné konečné nebo spočetné grupy symetrií. Bohatá teorie byla vypracována zejména v 19. století v souvislosti se studiem symetrií krystalů a molekul chemických prvků. (symbolický obrázek všech symetrií, odkazy na literaturu a trochu podrobnější diskusi dodám snad později ...) 10.6 10.6. Homomorfismy grup. Zobrazení f : G H mezi dvěmi grupami G a H se nazývá homomorfismus grup, jestliže respektuje násobení, tj. pro všechny prvky a, b G platí f(a b) = f(a) f(b). Povšimněme si, že násobení vlevo je uvnitř grupy G předtím, než zobrazujeme, zatímco vpravo jde o násobení v H poté, co zobrazujeme. Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Tvrzení. Pro každý homomorfismus f : G H grup platí (1) obraz jednotky e G je jednotka v H (2) obraz podgrupy K G je podgrupa f(K) H. (3) vzorem f-1 (K) G podgrupy K H je podgrupa. (4) obraz inverze k prvku je inverzí obrazu. tj. f(a-1 ) = f(a)-1 . (5) je-li f zároveň bijekcí, pak i inverzní zobrazení f-1 je homomorfismus. (6) f je injektivní zobrazení právě, když f-1 (e) = {e}. Důkaz. Je-li K G podgrupa, pak pro každé dva prvky y = f(a), z = f(b) v H nutně také y z = f(a b) patří do obrazu. Je proto vždy obrazem podgrupy opět podgrupa. Specielně, triviální podgrupy mají za obrazy opět podgrupy. Protože z rov- nosti a a = a vynásobením prvkem a-1 vyplývá a = e, ověřili jsme, že jedinou jednoprvkovou podgrupou je triviální podgrupa {e}, zejména tedy f(e) = e. Stejně postupujeme u vzorů: jestliže a, b G splňují f(a), f(b) K H, potom také f(a b) K. Předpokládejme, že existuje inverzní zobrazení g = f-1 a zvolme libovolné y = f(a), z = f(b) H. Pak f(a b) = y z = f(a) f(b), což je ekvivalentní výrazu g(y) g(z) = a b = g(y z). Je tedy inverze skutečně homomorfismem. Pokud platí f(a) = f(b), pak f(a b-1 ) = e H. Pokud je tedy jediným vzorem jednotky v H jednotka v G, pak a b-1 = e, tj. a = b. Opačná implikace je zřejmá. Podgrupa f-1 (e) jednotkového prvku e H se nazývá jádro homomorfismu f a značíme ji ker f. Bijektivní homomorfismus grup nazýváme izomorfismus. Z předchozích tvrzení okamžitě vyplývá, že homomorfismus f : G H s triviálním jádrem je izomorfismem na obraz f(G). 1. GRUPY 309 10.7 10.7. Příklady. (1) Pro každou grupu permutací G = n jsme definovali zobra- zení sgn : n Z2 přiřazující permutaci její paritu. Z tvrzení Věty 10.3 vyplývá, že jde o homomorfismus grup. Jádrem tohoto homomorfismu jsou permutace se sudou paritou. (2) Při studiu grupy symetrií rovnostranného trojúhelníka jsme našli izomorfismus této grupy s grupou permutací 3. Realizaci 3 si snadno můžeme zvolit tak, že za množinu tří prvků pro permutace vezmeme vrcholy trojúhelníka a jednotlivým symetriím přiřadíme permutace těchto vrcholů, které vyvolají. (3) Zobrazení exp : R R+ (nebo C C \ 0, pokud pracujeme s příslušnou moc- ninnou řadou a rozšíříme zobrazení na komplexní čísla) je homomorfismus aditivní grupy reálných nebo komplexních čísel na multiplikativní grupu kladných reálných čísel, resp. na multiplikativní grupu všech nenulových komplexních čísel. V případě reálných čísel jde o izomorfismus. Pro komplexní čísla dostáváme netriviální jádro. Viděli jsme totiž, že zúžení exp na ryze imaginární čísla (což je podgrupa izomorfní R) je homomorfismem it eit = cos t + i sin t, tzn. že čísla 2ki, k Z, jsou v jádru. Snadno se dopočítá, že je to celé jádro (je-li es+it = es eit v jádru, musí být es = 1, tj. s = 0, a pak zbývá pouze t = 2k pro libovolné celé k). (4) Determinant matice je zobrazením, které každé matici skalárů z K přiřazuje nějaký skalár v K (pracovali jsme s K = Z, Q, R, C). Cauchyova věta o determinantu součinu čtvercových matic det(A B) = (det A) (det B) je tvrzením, že pro grupu G = GL(n, K) invertibilních matic je det : G K \ 0 homomorfismem grup. (5) Pro každé dvě grupy G, H definujeme součin grup G × H takto: Jako množina je G × H skutečně součin a násobení definujeme po složkách. tj. (a, x) (b, y) = (a b, x y) kde nalevo vystupuje součin, který definujeme, zatímco napravo používáme tečku k naznačení součinů v jednotlivých grupách G a H. Zobrazení pG : G × H (a, x) a G, pH : G × H (a, x) x jsou surjektivní homomorfismy s jádry ker pG = {(eG, x); x H} ker pH = {(a, eH); a G}. (6) Grupy zbytkových tříd Zk jsou izomorfní grupám komplexních k­tých odmocnin z jedničky, což jsou zároveň izomorfní obrazy konečných grup otočení v rovině o celé násobky úhlu 2 k . (7) Grupa Z6 je izomorfní součinu Z2 × Z3. Docela snadno můžeme toto tvrzení vidět při multiplikativní realizaci grup zbytkových tříd Zk jakožto komplexních k-tých odmocnin z jedničky. Skutečně tak vidíme, že Z6 je tvořeno body na jednot- kové kružnici v komplexní rovině ve vrcholech pravidleného šestiúhelníku, Z2 pak odpovídá 1, Z3 pravidelnému trojúhelníku s jedním vrcholem v jedničce. Jestliže budeme ztotožňovat příslušné body s otočeními v rovině, které jedničku převede právě do nich, pak skládání dvou takových otočení bude vždy komutativní a kom- binacemi jednoho otočení ze Z2 a jednoho ze Z3 dostaneme právě všechna otočení ze Z6. Nakreslete si obrázek! Takto tedy dostaneme (při obvyklejší aditivní notaci) 310 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY izomorfismus: [0]6 ([0]2, [0]3) [1]6 ([1]2, [2]3) [2]6 ([0]2, [1]3) [3]6 ([1]2, [0]3) [4]6 ([0]2, [2]3) [5]6 ([1]2, [1]3) Zkuste se přesvědčit, že to takto skutečně funguje. Umíte tvrzení zobecnit? (8) Libovolný prvek a v grupě G je obsažen v minimální podgrupě {a, a2 , a3 , . . . }, která jej obsahuje. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. Nejmenší k s touto vlastností nazýváme řád prvku a v G. Grupa G je cyklická grupa je-li celé G generované nějakým svým prvkem a výše uvedeným způsobem. Z definice přímo vyplývá, že každá cyklická grupa je izomorfní buď grupě celých čísel Z (pokud je nekonečná) nebo některé grupě zbytkových tříd Zk (když je konečná). 10.8 10.8. Rozklady podle podgrup. Uvažme grupu G a její podgrupu H. Na mno- žině prvků grupy G nyní definujeme relaci a H b jestliže b-1 a H. Snadno ověříme, že je takto definována relace ekvivalence: ˇ a-1 a = e H, ˇ je-li b-1 a = h H, potom a-1 b = (b-1 a)-1 = h-1 H, ˇ je-li c-1 b H a zároveň je b-1 a H, potom c-1 a = c-1 b b-1 a H. Celá grupa G se tedy rozpadá na tzv. levé třídy rozkladu podle podgrupy H vzá- jemně ekvivalentních prvků. Třídu příslušející prvku a značíme a H a skutečně platí, že a H = {a h; h H}, neboť prvek b je ve stejné třídě s a, právě když jde takovýmto způsobem vyjádřit. Množinu všech levých tříd rozkladu podle podgrupy H označujeme G/H. Obdobně definujeme pravé třídy rozkladu H a. Příslušná ekvivalence je: a b, jestliže a b-1 H. Proto H \ G = {H a; a G}. Tvrzení. Pro třídy rozkladu grupy platí: (1) Levé a pravé třídy rozkladu podle podgrupy H G splývají právě, když pro každé a G, h H platí a h a-1 H. (2) Všechny třídy (levé i pravé) mají shodnou mohutnost s podgrupou H. Důkaz. Obě vlastnosti vyplývají bezprostředně z definičních vlastností. V pr- vém případě chceme, aby pro jakékoliv a G, h H platilo ha = ah pro vhodné h H. To ale nastane právě, když a-1 h a = h H. Ve druhém případě si stačí uvědomit, že pokud a h = a h , pak také vynáso- bením a-1 zleva obdržíme h = h . 10.9 10.9. Důsledek. Nechť G je konečná grupa s n prvky, H její podgrupa. Potom (1) Mohutnost n = |G| je součinem mohutnosti H a mohutnosti G/H, tj. |G| = |G/H| |H| 1. GRUPY 311 (2) Přirozené číslo |H| je dělitelem čísla n. (3) Je-li a G prvek řádu k, pak k dělí n. (4) pro každé a G je an = e. (5) je-li mohutnost grupy G prvočíslo, pak je G izomorfní cyklické grupě Zn. Druhému tvrzení se říkává Lagrangeova věta, předposlednímu malá Fermatova věta. Důkaz. Viděli jsme, že každá třída levého rozkladu má právě |H| prvků. Při- tom dvě různé třídy rozkladu musí mít nutně prázdný průnik. Odtud vyplývá první tvrzení. Druhá je okamžitým důsledkem prvního. Každý prvek generuje cyklickou podgrupu {a, a2 , . . . , ak = e} a právě počet prvků této podgrupy je řádem prvku a. Proto musí řád dělit počet prvků v G. Jelikož je řád k prvku a dělitelem čísla n a již ak = e, je také an = (ak )s = e. Jestliže je n > 1, pak existuje prvek a G různý od jednotky. Jeho řád je přirozené číslo různé od jedničky a nutně dělí n. Proto musí být rovno n. Pak ovšem jsou všechny prvky G tvaru ak pro k = 1, . . . , n. 10.10 10.10. Normální podgrupy a faktorgrupy. Podgrupy H, pro které platí, že a h a-1 H pro všechny a G, h H, se nazývají normální podgrupy. Pro normální podgrupy je dobře definováno násobení na G/H vztahem (a H) (b H) = (a b) H. Skutečně, volbou jiných reprezentantů a h, b h dostaneme opět stejný výsledek (a h b h ) H = ((a b) (b-1 h b) h ) H. Totéž si můžeme odůvodnit tak, že nezáleží na tom jestli pracujeme s pravými nebo levými třídami, můžeme rovnou naše třídy psát jako H aH a potom snadno definujeme (H a) (b H) = H (a b) H. Zřejmě jsou splněny pro nové násobení na G/H všechny vlastnosti grupy: jed- notkou je sama grupa H jakožto třída e H jednotky, inverzí k a H je zřejmě a-1 H a asociativita násobení je zřejmá z definice. Hovoříme o faktorové grupě G/H grupy G podle normální podgrupy H. V komutativních grupách jsou všechny podgrupy normální. Podmnožina nZ = {na; a Z} Z zadává v celých číslech podgrupu a její faktorgrupou je právě (aditivní) grupa zbyt- kových tříd Zn. Jak jsme viděli, všechna jádra homomorfismů jsou normální podgrupy. Naopak, jestliže je podgrupa H G normální, pak zobrazení p : G G/H, a a H je surjektivní homomorfismus grup s jádrem H. Skutečně, p je dobře definované, přímo z definice násobení na G/H je vidět, že to musí být homomorfismus a je zjevně na. Je tedy vidět, že normální podgrupy jsou právě všechna jádra homomorfismů. Dále, pro libovolný homomorfismus grup f : G K je dobře definován také homomorfismus ~f : G/ ker f K, ~f(a H) = f(a), který je injektivní. 312 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY Zdánlivě paradoxní je příklad homomorfismu C C definovaný na nenulo- vých komplexních číslech vztahem z zk s přirozeným k. Zjevně jde o surjektivní homomorfismus a jeho jádro je množina k­tých odmocnin z jedničky, tj. cyklická podgrupa Zk. Předchozí úvaha tedy dává pro všechna přirozená k izomorfismus ~f : C /Zk C . Tento příklad ukazuje, že u nekonečných grup nejsou počty s mohutnostmi tak přehledný jako u konečných grup v Důsledku 10.9. 10.11 10.11. Akce grupy. Již jsme viděli, že často potkáváme grupy jako množiny transformací nějaké pevné množiny. Musí přitom být všechny invertibilní a zároveň musí být naše množina transformací uzavřená na skládání. Často ale také můžeme pracovat s pevně zvolenou grupou, jejíž prvky reprezentujeme jako zobrazení na ně- jaké množině. Přitom ale ne nutně jsou zobrazení příslušná různým prvkům grupy různá. Např. všechna otočení roviny kolem počátku o všechny možné úhly odpoví- dají grupě reálných čísel. Otočení o 2 je ale identické zobrazení. Formálně si můžeme takovou situaci popsat jako tzv. (levou) akci grupy G na množině S. Jde o homomorfismus grupy G do podgrupy invertibilních prvků v pologrupě SS všech zobrazení S S. Takový homomorfismus si také můžeme představit jako zobrazení : G × S S, které splňuje (a b, x) = (a, (b, x)), odtud název ,,levá akce . Často se k vyjádření akce prvku grupy na prvku S používá pouze zápis a x (byť jde o jinou tečku než u násobení uvnitř grup), definiční vlastnost pak vypadá takto: (a b) x = a (b x). Obraz prvku x S v akci celé grupy G nazýváme orbita Sx prvku x Sx = {y = (a, x); a G}. Pro každý bod x S definujeme izotropní podgrupu Gx G akce , Gx = {a G; (a, x) = x}. Je-stliže pro každé dva prvky x, y S existuje a G tak, že (a, x) = y, pak říkáme, že akce je tranzitivní. Snadno se vidí, že u tranzitivních akcí jsou všechny izotropní podgrupy stejně mohutné. Jako příklad tranzitivní akce konečné grupy můžeme uvést např. zjevnou akci grupy permutací pevně zvolené množiny X na samotné množině X. Přirozená akce všech lineárních transformací na nenulových prvcích vektorového prostoru V je také tranzitívní. Pokud vezmeme ale prostor V celý, je nulový vektor zvláštní orbitou. Jiný příklad akce grupy G je přirozená akce na množině levých tříd G/H pro nějakou podgrupu H zadaná levým násobením na reprezentantech tříd. Věta. Pro každou akci konečné grupy G na konečné množině S platí: (1) Pro každý prvek x S je |G| = |Gx| |Sx|. 1. GRUPY 313 (2) (Burnsidova věta) Je-li N počet orbit akce G na S pak |G| = 1 N gG |Sg|, kde Sg = {x S; g x = x} označuje množinu pevných bodů akce prvku g. Důkaz. Uvažmě x S a izotropní podgrupu Gx G. Akce grupy G zadává zobrazení G/Gx Sx, g Gx g x. Pokud (g Sx) x = (h Sx) x, pak zjevně g-1 h Sx, je tedy naše zobrazaní injektvní. Zároveň je zjevně surjektivní, proto |G/Gx| = |Sx|. Odtud již vyplývá první vlastnost z věty, protože |G| = |G/Gx||Gx|. Druhé tvrzení dokážeme tak, že dvěma způsoby spočteme mohutnost množiny pevných bodů akce v jejím grafu: F = {(x, g) S × G; g(x) = x} S × G. Protože jde o konečné množiny, můžeme si představit prvky součinu S × G jako prvky v matici (sloupce označujeme prvky v S, řádky pak podle prvků v G). Sčí- táním po řádcích i sloupcích obdržíme |F| = gG |Sg| = xS |Gx|. Nyní si pro přehlednost vyberme po jednom reprezentantu x1, . . . , xN z každé orbity v S. Dostáváme |F| = gG |Sg| = N i=1 xSxi |Gx| = N i=1 |Sxi ||Gxi | = N |G| a důkaz je ukončen. Tato tvrzení jsou velice často užitečná pro řešení kombinatorických úloh. Příklad. Kolika způsoby můžeme vytvořit korálky na krk z 3 černých a 7 bílých korálků stejného tvaru? Kusy stejné barvy nerozlišujeme a za stejné korálky pova- žujeme všechny, které lze na sebe převést symetrií v rovině. Pro řešení úlohy si představíme korálky jako obarvené vrcholy pravidelného sedmistěnu. Za množinu S volíme všechny konfigurace, tj. kolika způsoby vybereme tři pozice z devíti. Velikost množiny S je tedy 9 3 = 84. Víme, že grupou všech symetrií je grupa D9 složená z 9 rotací (včetně identity) a stejného počtu reflexí. Stejné náhrdelníky jsou ty, které leží ve stejné orbitě akce grupy D9 na množině všech konfigurací S, zajímá nás tedy počet orbit N. Pro výpočet N stačí probrat prvky grupy D9 a všímat si velikostí Sg: Identita je jediný prvek řádu 1, |Sid| = 84. Příspěvek do sumy je 84. Zrcadlení g jsou všechna řádu 2 a je jich 9. Přitom je zjevně |Sg| = 4, celkový příspěvek je proto 4 9 = 36. Dvě rotace g o úhel 2/3 nebo 4/3 mají řád 3 a |Sg| = 3. Jejich příspěvek je tedy 6. Konečně, zbývajících rotací (řádu 9 v D9) je 6 a nenechávají na místě žádný prvek, do celkové sumy tedy ničím nepřispívají. Celkem dostáváme podle formule z Burnsidovy věty: N = 1 |D9| gD9 |Sg| = 126 18 = 7. Najděte si příslušných sedm různých náhrdelníků! 314 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY 2. Okruhy polynomů a tělesa 10.12 10.12. Okruhy a tělesa. Jak jsme viděli, s grupami se potkáváme nejčastěji jako s množinami transformací. Zároveň ale byly vlastnosti grupy podstatné u skalárů i vektorů, tam ovšem vystupovalo několik obdobných struktur zároveň. Zaměříme se teď právě na takové případy. Jako standardní příklady přitom mějme na mysli skaláry (tj. celá čísla Z, racionální čísla Q, komplexní čísla C) a množiny polynomů nad takovými skaláry K. Celá čísla mají následující vlastnosti tzv. okruhu: Definice. Komutativní grupa (M, +) s neutrálním prvkem 0 M, spolu s další operací splňující ˇ (a b) c = a (b c), pro všechny a, b, c M; ˇ a b = b a, pro všechny a, b M; ˇ existuje prvek 1 takový, že pro všechny a M platí 1 a = a; ˇ a (b + c) = a b + a c, pro všechny a, b, c M; se nazývá komutativní okruh. Jestliže v okruhu K platí c d = 0 právě, když alespoň jeden z prvků c a d je nulový, pak nazýváme okruh K oborem integrity. Poslední vlastnosti v našem výčtu axiomů okruhu se říká distributivita. Pokud neplatí vlastnost komutativity operace , hovoříme o (nekomutativním okruhu). V dalším se ovšem omezíme pouze na okruhy komutativní. Operaci + budeme říkat sčítání a operaci násobení. Navíc budeme vždy předpokládat existenci jedničky 1 pro operaci násobení, neutrálnímu prvku pro sčítání říkáme nula. Obecně říkáme, že a K dělí c K, jestliže existuje b tak, že a b = c. Skutečnost že c K je dělitelné a K zapisujeme a|c. Dodatečnou vlastností oboru integrity oproti obecnému okruhu je neexistence netriviálních dělitelů nuly. Okamžitě odtud také vyplývá jednoznačnost dělitelů: je-li b = a c a b = 0, pak c je jednoznačně dáno volbou a, b. Pro b = ac = ac totiž platí 0 = a (c - c ) a a = 0, proto c = c . Dělitelé jedničky, tj. invertibilní prvky v K, se nazývají jednotky. Jednotky v komutativním okruhu vždy tvoří komutativní grupu. Netriviální (komutativní) okruh, ve kterém jsou všechny nenulové prvky invertibilní, se nazývá (komutativní) těleso. Komutativní těleso se také nazývá pole. Typickým příkladem komutativních okruhů, tj. polí, jsou číslené obory Q, R, C. Dále pak všechny okruhy zbytkových tříd Zp s prvočíselným p. Dobrým příkladem nekomutativního okruhu s jedničkou je množina Matk(K) všech čtvercových matic nad okruhem K s k řádky a sloupci. Jak jsme viděli dávno, není to ani obor integrity. Jako příklad nekomutativního tělesa uveďme těleso kvaternionů H. V každém komutativním okruhu K s jedničkou platí následující vztahy (které nám jistě připadají samozřejmé u skalárů) (1) 0 c = c 0 = 0 pro všechny c K, (2) -c = (-1) c = c (-1) pro všechny c K, (3) -(c d) = (-c) d = c (-d) pro všechny c, d K, (4) a (b - c) = a b - a c, (5) celý okruh K je triviální množinou {0} = {1} právě, když 0 = 1. 2. OKRUHY POLYNOMŮ A TĚLESA 315 Důkaz. Všechna tvrzení vyplývají z jednoduché úvahy a definičních axiomů. V prvém případě počítáme pro jakákoliv c, a: c a = c (a + 0) = c a + c 0 = c a a protože jediným neutrálním prvkem vůči sčítání je nula, dostáváme a 0 = 0. Stejně se dokáže i 0 a. Ve druhém případě teď stačí spočíst 0 = c 0 = c (1 + (-1)) = c + c (-1), proto je c (-1) opačný prvek k prvku c, což jsme chtěli dokázat. Další dvě tvrzení jsou už přímým důsledkem druhého vztahu a základních axi- omů. Jestliže je celý okruh tvořen jediným prvkem, je pochopitelně 0 = 1. Naopak, jestliže platí 1 = 0, pak pro jakékoliv c K je c = 1 c = 0 c = 0. 10.13 10.13. Polynomy. Definice komutativního okruhu s jedničkou abstrahuje právě vlastnosti potřebné k násobení a sčítání. Můžeme je hned využít pro práci s tzv. polynomy. Rozumíme jimi jakýkoliv konečný výraz, který lze poskládat ze známých konstantních prvků K a jedné neznámé proměnné pomocí operací sčítání a násobení. Formálně můžeme definovat polynomy takto:2 Definice. Nechť K je jakýkoliv komutativní okruh skalárů s jedničkou. Polynomem nad K rozumíme konečný výraz f(x) = k i=0 aixi kde ai K, i = 0, 1, . . . , k, jsou tzv. koeficienty polynomu. Je-li ak = 0, říkáme, že f(x) má stupeň k, píšeme deg f = k. Nulový polynom nemá stupeň, polynomy stupně nula jsou právě nenulové prvky v K, kterým říkáme konstantní polynomy. Polynomy f(x) a g(x) jsou stejné, jestliže mají stejné nenulové koeficienty. Množinu všech polynomů nad okruhem K budeme značit K[x]. Každý polynom zadává zobrazení f : K K, jehož hodnota vznikne dosazením hodnoty c za nezávislou proměnnou x, tj. f(c) = a0 + a1c + + akck . Všimněme si, že konstantní polynomy odpovídají právě konstantním zobrazením. Kořen polynomu f(x) je takový prvek c K, pro který je f(c) = 0 K. Obecně mohou různé polynomy definovat různá zobrazení. Např. polynom x2 + x Z2[x] zadává identicky nulové zobrazení. Obecněji, pro každý konečný okruh K = {a0, a1, . . . , ak} zadává polynom f(x) = (x - a0)(x - a1) . . . (x - ak) identicky nulové zobrazení. Zároveň ale platí tvrzení, které dokážeme zanedlouho: Tvrzení. Jestliže je K nekonečný okruh, pak dva polynomy f(x) a g(x) nad K jsou stejné právě, když jsou stejná příslušná zobrazení f a g. Dva polynomy f(x) = i aixi a g(x) = i bixi umíme přirozeně také sčítat i násobit: (f + g)(x) = (a0 + b0) + (a1 + b1)x + + (ak + bk)xk (f g)(x) = (a0b0) + (a0b1 + a1b0)x + + (a0b + a1b -1 + + a b0)x + . . . 2Ne náhodou je pro okruh použit symbol K ­ představujte si pod ním třeba kterýkoliv okruh naších skalárů, definice je ovšem obecná. 316 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY kde uvažujeme nulové koeficienty všude, kde v původním výrazu pro polynomy nenulové koeficienty nejsou3 a u sčítání nechť je k maximální ze stupňů f a g. Tato definice vskutku odpovídá příslušným operacím sčítání a násobení hodnot zobrazení f, g : K K, díky vlastnostem ,,skalárů v původním okruhu K. Přímo z definice vyplývá, že množina polynomů K[x] nad komutativním okru- hem s jedničkou je opět komutativním okruhem s jedničkou, přičemž jedničkou v K[x] je opět jednička 1 v okruhu K vnímaná jako polynom stupně nula. Lemma. Okruh polynomů nad oborem integrity je opět obor integrity. Důkaz. Máme ukázat, že v K[x] mohou být netriviální dělitelé nuly pouze, jetliže jsou už v K. To je ale zřejmé z výrazu pro násobení polynomů. Jsou-li f(x) a g(x) polynomy stupně k a jako výše, pak koeficient u xk+ v součinu f(x) g(x) je součin ak b a ten musí být nenulový, pokud nejsou dělitelé nuly v K. 10.14 10.14. Dělitelnost a nerozložitelnost. Naším dalším cílem bude pochopit, jak je to v obecném případě polynomů nad oborem integrity s jejich rozkladem na součin polynomů jednodušších, tj. ve speciálním případě budeme diskutovat kořeny polynomů. Směřujeme tedy ke zobecnění rozkladů polynomů nad číslenými obory a k tomu nejprve potřebujeme ujasnit, co je dělitelnost v základním okruhu K samotném. Uvažujme proto nějaký pevně zvolený obor integrity K, třeba celá čísla Z nebo okruh Zp s prvočíselným p. ˇ je-li a|b a zároveň b|c pak také a|c; ˇ a|b a zároveň a|c pak také a|(b + c) pro všechny , K; ˇ a|0 pro všechny a K (je totiž a 0 = 0); ˇ každý prvek a K je dělitelný všemi jednotkami e K a jejich násobky a e (jak přímo plyne z existence e-1 ) Řekneme, že prvek a K je nerozložitelný, jestliže je dělitelný pouze jednotkami e K a jejich násobky a e. Řekneme, že okruh K je obor integrity s jednoznačným rozkladem, jestliže platí: ˇ pro každý nenulový prvek a K existují nerozložitelné a1, . . . , ar K takové, že a = a1 a2 . . . ar ˇ jsou-li prvky a1, . . . , ar a b1, . . . , bs nerozložitelné, nejsou mezi nimi žádné jed- notky a a = a1a2 . . . ar = b1b2 . . . bs, pak je r = s a ve vhodném přeuspořádání platí aj = ejbj pro vhodné jednotky ej. Příklad. (1) Z je obor integrity s jednoznačným rozkladem. (2) Každé pole (komutativní těleso) je obor integrity s jednoznačným rozkladem (a každý nenulový prvek je jednotka). (3) Nechť K má prvky tvaru a0 + k i=1 ai 2ni xmi kde a0, . . . , ak Z, mi, n Z>0. Pak jednotky jsou pouze prvky 1, všechny prvky s a0 = 0 jsou rozloži- telné, ale např. výraz x nelze vyjádřit jako součin nerozložitelných. (Nerozloži- telných je zde příliš málo.) 3Formálně bychom mohli naopak za polynom považovat nekonečný výraz pro i = 0, . . . , s podmínkou, že jen konečně mnoho koeficientů je nenulových. 2. OKRUHY POLYNOMŮ A TĚLESA 317 10.15 10.15. Dělení se zbytkem a kořeny polynomu. Základním nástrojem pro dis- kusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Z je procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme. Lemma (Algoritmus pro dělení se zbytkem). Nechť K je komutativní okruh bez dělitelů nuly a f, g K[x] polynomy, g = 0. Pak existuje a K, a = 0, a polynomy q a r splňující af = qg+r, kde r = 0 nebo deg r < deg g. Je-li navíc K pole, nebo je aspoň vedoucí koeficient polynomu g roven jedné, potom lze volit a = 1 a polynomy q a r jsou v tomto případě určeny jednoznačně. Důkaz. Tvrzení dokážeme indukcí vzhledem ke stupni f. Je-li deg f < deg g nebo f = 0, pak volíme a = 1, q = 0, r = f , což vyhovuje všem našim podmínkám. Pro konstantní polynom g klademe a = g, q = f, r = 0. Předpokládejme tedy, že deg f deg g > 0 a pišme f = a0+ +anxn , g = b0+ +bmxm . Buď platí bmf-anxn-m g = 0 a nebo je deg(bmf-anxn-m g) < deg f. V prvém případě jsme hotovi, ve druhém pak, podle indukčního předpokladu, existují a , q , r splňující a (bmf - anxn-m g) = q g + r a buď r = 0 nebo deg r < deg g. Tzn. a bmf = (g + a anxn-m )g + r . Přitom je-li bm = 1 nebo BbbK je pole, pak podle indukčního předpokladu lze volit a = 1 a q , r jsou tak určeny jednoznačně. V takovém případě ovšem získáme bmf = (g + anxn-m )g + r a je-li BbbK pole, můžeme rovnost vynásobit b-1 . Předpokládejme, že f = q1g+r1 je jiné řešení. Pak 0 = f-f = (q-q1)g+(r-r1) a buď je r = r1, nebo deg(r - r1) < deg g. V prvém případě odtud ovšem plyne i q = q1, protože K[x] neobsahuje dělitele nuly. Nechť axs je člen nejvyššího stupně v q - q1 = 0 (určitě existuje). Potom jeho součin se členem nejvyššího stupňe v g musí být nulový (protože nejvyšší stupeň dostaneme tak , že vynásobíme nejvyšší stupně). To ovšem znamená, že a = 0. Protože axs byl největší nenulový stupeň, nutně dostáváme, že q - q1 žádné nenulové monomy neobsahuje, je tedy určitě nulové. Pak ovšem i r = r1. Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů poly- nomů. Uvažme tedy polynom f(x) K[x], deg f > 0, a zkusme jej vydělit poly- nomem x - b, b K. Protože je vedoucí koeficient jednička, algoritmus pro dělení dává jednoznačný výsledek. Dostáváme tedy jednoznačně zadané polynomy q a r splňující f = q(x-b)+r, kde r = 0 nebo deg r = 0, tj. r BbbK. Tzn., že hodnota polynomu f v b K je rovna právě f(b) = r. Z toho plyne, že prvek b K je kořen polynomu f právě, když (x - b)|f. Protože po vydělení polynomem stupně jedna vždy klesne stupeň výsledku alespoň o jedničku, dokázali jsme následující tvrzení: Důsledek. Každý polynom f BbbK[x] má nejvýše deg f kořenů. Tento výsledek také ověřil Tvrzení 10.13, protože dva polynomy nad nekoneč- ným komutativním okruhem, které zadávají stejné zobrazení K K, mají rozdíl, jehož kořenem je každý prvek v K. To však není možné, protože rozdíl polynomů má jen konečný stupeň, pokud není nulový. 10.16 10.16. Největší společný dělitel polynomů. Nejprve si připomeňme, že h je největší společný dělitel dvou polynomů a f a g K[x] jestliže: 318 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY ˇ h|f a zároveň h|g ˇ jestliže k|fa zároveň k|g pak také k|h. Důsledek (Bezoutova rovnost). Nechť K je pole a nechť f, g K[x]. Pak existuje největší společný dělitel h polynomů f a g. Polynom h je určený jednoznačně, až na násobek nenulovým skalárem. Přitom existují polynomy A, B K[x] takové, že h = Af + Bg. Důkaz. Přímá konstrukce polynomů h, A a B se provede tzv. Euklidovým algoritmem. Provádíme postupně dělení se zbytkem (K je pole, takže to vždy umíme jednoznačně, viz. předchozí lemma): f = q1g + r1 g = q2r1 + r2 r1 = q3r2 + r3 ... rp-1 = qp+1rp + 0. V tomto postupu neustále klesají stupně ri, proto jistě nastane rovnost z posledního řádku (pro vhodné p) a ta říká, že rp|rp-1. Z předposledního řádku pak ale plyne rp|rp-2 a postupně dojdeme až nazpět k prvnímu a druhému řádku, které dají rp|g a rp|f. Pokud h|f a h|g, pak ze stejných rovností postupně plyne, že h dělí všechny ri, zejména tedy rp, tzn. získali jsme největšího společného dělitele h = rp polynomů f a g. Nyní můžeme postupně dosazovat z poslední do předchozích rovnic. h = rp = rp-2 - qprp-1 = rp-2 - qp(rp-3 - qp-1rp-2) = -qprp-3 + (1 + qp-1)rp-2 = -qprp-3 + (1 + qp-1qp)rp-2 = -qprp-3 + (1 + qpqp-1)(rp-4 - qp-2rp-3) ... = Af + Bg. Zformulujeme si nyní velice elegantní tvrzení, jehož důkaz je poměrně technický a nebudeme jej prezentovat v detailech (i když jsme si vše potřebné pro něj již v podstatě připravili). 10.17 10.17. Věta. Je-li K obor integrity s jednoznačným rozkladem, pak také okruh polynomů K[x] je obor integrity s jednoznačným rozkladem. Důkaz. Myšlenka důkazu je velice jednoduchá. Uvažujme polynom f K[x]. Je-li f rozložitelný, pak je f = f1 f2, kde žádný z polynomů f1, f2 K[x] není jednotka. Předpokládejme na chvíli navíc, že je-li f dělitelný nerozložitelným poly- nomem h, pak jistě h dělí f1 nebo f2. Pokud tomu tak vždy bude, docílíme postupnou aplikací předchozí úvahy jed- noznačný rozklad. Pokud je totiž f1 dále rozložitelné, opět f1 = g1 g2, kde g1, g2 2. OKRUHY POLYNOMŮ A TĚLESA 319 nejsou jednotky, a přitom vždy buď oba polynomy g1 a g2 mají menší stupeň než f, nebo se sníží počet nerozložitelných faktorů ve vedoucích členech g1 a g2 (např. nad celými čísly Z je 2x2 +2x+2 = 2(x2 +x+1)). Proto po konečném počtu kroků dojdeme k rozkladu f = f1 . . . fr na nerozložitelné polynomy f1, . . . , fr. Z našeho dodatečného předpokladu také plyne, že každý nerozložitelný polynom h dělící f, dělí některý z f1, . . . , fr. Proto pro každý další rozklad f = f1f2 . . . fs nutně každý z faktorů fi dělí některý z fj a v takovém případě musí být fj = efi pro vhodnou jednotku e. Postupným krácením takových dvojic odvodíme, že r = s a jednotlivé faktory se liší pouze o násobky jednotek. Zbývá tedy dokázat, že je-li f = f1f2 dělitelný nerozložitelným polynomem h, pak jistě h dělí f1 nebo f2. Tento důkaz zde nebudeme provádět. Důsledkem této věty je skutečnost, že každý polynom nad komutativním okru- hem s jednoznačným rozkladem můžeme rozložit tak, jak to známe s polynomy s reálnými nebo komplexními koeficienty. Pokud má polynom tolik kořenů, včetně násobnosti, jako je jeho stupeň deg f = k, je odpovídající rozklad tvaru f(x) = (x - a1) (x - a2) . . . (x - ak). Zatímco reálné polynomy mohou být i úplně bez kořenů, každý komplexní polynom naopak takovýto rozklad připouští. To je obsahem tzv. základní věty algebry, kterou pro úplnost uvádíme s (v podstatě) kompletním důkazem: 10.18 10.18. Věta (Základní věta algebry). Pole C je algebraicky uzavřené, tj. každý po- lynom stupně alespoň 1 má kořen. Důkaz. Předpokládejme, že f C[z] je nenulový polynom, který nemá kořen, tj. f(z) = 0 pro všechny z C. Definujme zobrazení : C C, z f(z) |f(z)| tj. zobrazí celé C do jednotkové kružnice K1 = {eit , t R} R2 = C. Díky našemu předpokladu o nenulovosti f(z) je to skutečně dobře definované zobrazení. Dále definujme zobrazení s hodnotami v kružnici Kr C se středem v nule a poloměrem r 0 r : R Kr, t (t) = reit . Pro každé r 0, ) máme definováno spojité zobrazení r = r : R K1. Ze spojité závislosti na parametru r navíc vyplývá existence zobrazení r : R R jednoznačně zadaných podmínkami 0 r(0) < 2 a r(t) = eir(t) . Získané zobrazení r opět spojitě závísí na r. Celkem tedy máme spojité zobrazení : R × 0, ) R, (t, r) r(t) a z jeho konstrukce plyne že pro všechna r je 1 2 (r(2) - r(0)) = nr Z. Protože je spojité, znamená to, že nr je celočíselná konstanta nezávislá na r. Podívejte se na obrázek, odkud kam jdou jednotlivá zobrazení v naší konstrukci! 320 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY $0$ $2\pi$ $0$ $\psi_r$ $\alpha_r$ $psi_1$ $K_1$ $\phi$$e^{it}$ $K_r$ $2\pi$ Pro dokončení důkazu si stačí uvědomit, že pokud f = a0 + + adzd a ad = 0, pak pro malá r se bude r chovat podobně jako konstantní zobrazení, zatímco pro velká r to vyjde stejně, jako kdyby f = zd . Nejprve si spočtěme, jak tedy nr dopadne při f = zd , pak toto tvrzení upřesníme a důkaz tím bude ukončen. Funkce C C, z zd , z zd |zd| se snadno vyjádří pomocí goniometrického tvaru komplexních čísel z = r(cos + i sin ). zd = rd (cos d + i sin d) = rd eid zd |zd| = 1(cos d + i sin d) = eid zobrazení je tedy v tomto případě pouze ,,zatočení na jednotkové kružnici. Pak tedy r(t) = eidt a proto r(t) = dt, nezávisle na r. Odtud pro naši volbu f = zd vyplývá nr = d. Pokud zvolíme f = azd , a = 0, nebude to mít na předchozí výsledek žádný vliv (přesvědčte se!). Zvolme nyní obecný polynom f = a0 + +adzd , který nemá kořen. Víme tedy, že a0 = 0 (pokud by bylo a = 0, existoval by kořen). Pro z = 0 platí f(z) adzd = 1 + 1 ad (a0z-d + + ad-1z-1 ) a proto lim|z| f(z) adzd = 1. Když tohle víme, můžeme spočítat lim |z| ˛ ˛ ˛ ˛ f(z) |f(z)| - adzd |adzd| ˛ ˛ ˛ ˛ = lim |z| ˛ ˛ ˛ ˛ f(z) adzd adzd |adzd| |adzd | |f(z)| - adzd |adzd| ˛ ˛ ˛ ˛ = 0. Proto nr = d pro velká r. Podobnou úvahu uděláme i pro malá r. Připomeňme si, že a0 = 0. f(z) a0 = 1 + 1 a0 (a1z + + adzd ) proto lim|z|0 f(z) a0 = 1. Přitom opět platí f(z) |f(z)| = f(z) a0 a0 |a0| |a0| |f(z)| . Odtud lim|z|0 f(z) |f(z)| = lim|z|0 a0 |a0| , tj. nr = 0 pro malá r. Celkem vidíme, že stupeň našeho polynomu je d = 0. 10.19 10.19. Polynomy více proměnných. Okruhy polynomů v proměnných x1, . . . , xr definujeme induktivně vztahem K[x1, . . . , xr] := K[x1, . . . , xr-1][xr]. 2. OKRUHY POLYNOMŮ A TĚLESA 321 Např. K[x, y] = K[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem K[x]. Snadno si každý ověří (proveďte si to!), že polynomy v proměnných x1, . . . , xr lze chápat jako výrazy vzniklé z písmen x1, . . . , xn a prvků okruhu K konečným počtem (formálního) sčítání a násobení v komutativním okruhu. Například prvky v K[x, y] jsou tvaru f = an(x)yn + an-1(x)yn-1 + + a0(x) = (amnxm + + a0n)yn + + (bp0xp + + b00) = c00 + c10x + c01y + c20x2 + c11xy + c02y2 + . . . Pro zjednodušení zápisu se často zavádí tzv. multiidexová symbolika. Multiindex délky r je r-tice nezáporných celých čísel (1, . . . , r). Celé číslo || = 1 + +r nazýváme velikost multiindexu . Stručně pak píšeme x místo x1 1 x2 2 . . . xr r . Pro polynomy v r proměnných pak máme symbolické vyjádření velice podobné obvyklému značení pro polynomy v jedné proměnné: f = X ||n ax , g = X ||m ax K[x1, . . . , xr]. Říkáme, že f má celkový stupeň n, je-li alespoň jeden z koeficientů s multiindexem velikosti n nenulový. Okamžitě se také nabízejí analogické vzorce pro sčítání a násobení polynomů f + g = X ||max(m,n) (a + b)x fg = m+nX ||=0 0 @ X += (ab)x 1 A kde multiindexy se sčítají po složkách a formálně neexistující koeficienty považujeme za nulové. Samozřejmě musíme ověřit, že tyto vzorce opravdu popisují sčítání a násobení v induktivně definovaném okruhu polynomů v r proměnných. Dokážeme to indukcí přes počet proměnných. Předpokládejme, že vztahy platí v K[x1, . . . , xr-1] a počítejme součet f = ak(x1, . . . , xr-1)xk r + + a0(x1, . . . , xr-1) = X ak,x ! xk r + . . . g = bl(x1, . . . , xr-1)xl r + + b0(x1, . . . , xr-1) = 0 @ X bl,x 1 A xk r + . . . f + g = ` a0(x1, . . . , xr-1) + b0(x1, . . . , xr-1) ´ + + ` a1(x1, . . . , xr-1) + b1(x1, . . . , xr-1) ´ xr + . . . = `X (ak, + bk,)(x1, . . . , xr-1)´ xk r + + `X (a0, + b0,)(x1, . . . , xr-1)´ = X (,j) (aj, + bj,)(x1, . . . , xr-1) xj r. Podobně se provede důkaz pro součin (proveďte!). Jako důsledek naší definice a předchozích výsledků pro polynomy nad obecnými komutativními okruhy dostaneme: Důsledek. (1) Jestliže v okruhu K nejsou dělitelé nuly, pak také v okruhu poly- nomů K[x1, . . . , xr] nejsou dělitelé nuly. (2) Je-li K obor integrity s jednoznačným rozkladem, pak také okruh polynomů K[x1, . . . , xr] je obor integrity s jednoznačným rozkladem. 322 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY Důkaz. Budeme postupovat indukcí přes počet proměnných r. 4 Pro r = 1 uvažujme polynomy f = anxn 1 + + a1x1 + a0 a g = bmxm + + b0, přičemľ bm = 0 a an = 0. Vedoucí člen součinu fg je anbmxn+m , protože anbm = 0, zejména tedy je součin nenulových polynomů opět nenulový. Pokud tvrzení platí pro r - 1 proměnných, pak použijeme předchozí úvahu pro okruh polynomů v jedné proměnné xr s koeficienty v K[x1, . . . , xr-1]. Druhé tvrzení vyplývá s induktivní definice polynomů v r proměnných a z Věty 10.17. 10.20 10.20. Podílová tělesa. Nechť K je komutativní okruh (s jedničkou) bez dělitelů nuly. Jeho podílové těleso definujeme jako třídy ekvivalence dvojic (a, b) K × K, b = 0, které zapisujeme a b , a ekvivalence je dána a b = a b ab = a b. Sčítání a násobení definujeme prostřednictvím reprezentantů tříd a b + c d = ad + bc bd a b c d = ac bd Snadno se ověří korektnost této definice a všechny axiomy komutativního tělesa. Zejména je 0 1 neutrální prvek vzhledem ke sčítání, 1 1 je neutrální prvek vzhledem k násobení a pro a = 0, b = 0 je a b b a = 1 1 . Podílové těleso okruhu K[x1, . . . , xr] nazýváme těleso racionálních funkcí a zna- číme je K(x1, . . . , xr). Všechny algebraické operace s polynomy v softwarových sys- témech jako je Maple nebo Mathematica jsou prováděny ve skutečnosti nad podí- lovými tělesy, tj. v tělesech raciolnálních funkcí, zpravidla s použitím K = Q. 3. Uspořádané množiny a Booleovská algebra Tak jako jsme z vlastností čísel nebo symetrií objektů abstrahovali podstatné axiomy a dostali jsme daleko šířeji použitelné nástroje linerární algebry, teorie grup apod., nyní budeme postupovat obdobně a za východisko si vezmeme základní operace s množinami, tj. jejich sjednocení, průnik a vztahy inkluze. 10.21 10.21. Množinová algebra. S každou množinou M máme také množinu K = 2M všech jejích podmnožin a na ní operace : K × K K sjednocení množin a : K ×K K průniku množin. To jsou dvě binární operace, které se častěji značí a . Dále máme ke každé množině A K také její množinu doplňkovou A , což je další unární operace. Konečně máme ,,největší objekt , tj. celou množinu M, který je neutrální vůči operaci a který proto budeme v této souvislosti označovat jako 1, a obdobně se chová prázdná množina K vůči operaci . Tu budeme v této souvislosti značit jako 0. 4Důkaz lze vést také přímo s použitím multiindexových formulí pro součin, ale museli bychom si nadefinovat určité vhodné uspořádání monomů, abychom mohli pracovat s vedoucím koeficien- tem. Zkuste si to! 3. USPOŘÁDANÉ MNOŽINY A BOOLEOVSKÁ ALGEBRA 323 Na množině K všech podmnožin v M přitom platí pro všechny prvky A, B, C následující vlastnosti: A (B C) = (A B) C, A (B C) = (A B) C(1) A B = B A, A B = B A(2) A (B C) = (A B) (A C), A (B C) = (A B) (A C)(3) existuje 0 tak, že A 0 = A(4) existuje 1 tak, že A 1 = A(5) A A = 0, A A = 1.(6) Vlastnost (1) je asociativní zákon pro obě operace, (2) je komutativita, (3) je distributivita obou operací. Poslední vlastnost (6) vystihuje vlastnosti komple- mentu. Definice. Množině K spolu s dvěmi binárními operacemi a a jednou unární operací splňující vlastnosti (1)­(7) říkáme Booleovská algebra. Operaci budeme říkat infimum (případně sjednocení, anglicky často také meet), operaci budeme říkat supremum (případně průnik, anglicky také join). Prvku A se říká doplněk k prvku A. Všimněme si, že axiomy Booleovské algebry jsou zcela symetrické vůči záměně operací a , společně se záměnou prvků 0 a 1. Důsledkem tohoto faktu je, že jakékoliv tvrzení, které odvodíme z axiomů, má také platné duální tvrzení, které vznikne z prvého právě záměnou všech výskytů za a naopak a stejně tak všech výskytů 0 a 1. Hovoříme o principu duality. Jako obvykle si hned odvodíme několik elementárních důsledků axiomů. Zejména si povšimněme, že stejně jako u speciálního případu Booleovské algebry všech pod- množin v dané množině M je doplněk k A K určen jednoznačně (tj. máme-li dáno (K, , ), může existovat nejvýše jedna unární operace, se kterou dostaneme Booleovskou algebru). Skutečně, pokud B a C K splňují vlastnosti A , platí B = B 0 = B (A C) = (B A) (B C) = 1 (B C) = B C a podobně také C = C B. Je tedy nutně B = C. V následujícím výčtu se vlastnostem (2) říká absorpční zákony, vlastnosti (3) popisují idempotentnost operací a (4) jsou tzv. De Morganova pravidla. Tvrzení. V každé Booleovské algebře (K, , , ) platí pro všechny prvky v K (1) A 0 = 0, A 1 = 1 (2) A (A B) = A, A (A B) = A (3) A A = A, A A = A (4) (A B) = A B , (A B) = A B (5) (A ) = A. Důkaz. Podle principu duality potřebujeme z každého z duálních tvrzení na jednotlivých řádcích dokázat pouze jedno. Počítejme s využitím axiomů: A 0 = A (A A ) = (A A) A = A A = 0 A (A B) = (A 0) (A B) = A (0 B) = A 0 = A A = A (A A ) = (A A) 0 = A A 324 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY a první tři dvojice tvrzení máme dokázány. K důkazu De Morganových pravidel stačí ověřit, že A B má vlastnosti doplňku k A B (pak to totiž bude doplněk dle úvahy výše). S využitím (1) spočteme (A B) (A B ) = ((A B) A ) ((A B) B ) = (0 B) (A 0) = 0. Obdobně, s použitím (2) dostáváme (A B) (A B ) = (A (A B )) (B (A B )) = (1 B ) (1 A ) = 1. Konečně, přímo z definice je A A = 0 a A A = 1, má proto A požadované vlastnosti doplňku k A a je tedy A = (A ) . 10.22 10.22. Výroková logika jako Booleova algebra. V předchozím odstavci jsme použili symboliku, kterou je často rozumné interpretovat tak, že z prvků A, B, K tvoříme ,,slova pomocí operací , , a závorek vyjasňujících v jakém pořadí a na jaké argumenty jsou operace aplikovány. Samotné axiomy a jejich důsledky pak říkají, že velice často různá slova dávají stejnou hodnotu výsledku v K. V případě množiny všech podmnožin K = 2M je to zřejmé ­ prostě jde o rovnost podmnožin. Nyní uvedeme stručně jinou podobnou souvislost. Budeme pracovat opět se slovy jako výše, interpretujeme je ale jako tvrzení složené z elementárních výroků A, B, . . . a logických operací AND (binární operace ), OR (binární operace ) a negace NOT (unární operace ). Takové slova nazý- váme výroky a přiřazujeme jim pravdivostní hodnotu v závislosti na pravdivostní hodnotě jednotlivých elementárních argumentů. Pravdivostní hodnotu přitom be- reme jako prvek z triviální Booleovy algebry Z2, tedy buď 0 nebo 1. Pravdivostní hodnota výroku je plně určena přiřazením hodnot pro nejjednoduší výroky A B, AB a A , tj. AB je pravdivé pouze, když jsou oba výroky A a B pravdivé, AB je nepravdivé pouze. když jsou oba výroky nepravdivé a A má opačnou hodnotu než A. Výrok obsahující k elementárních výroků tedy představuje funkci (Z2)k Z2 a dva výroky nazýváme logicky ekvivalentní, jestliže zadávají stejnou funkci. Snadno se nyní přímo ověří, že na množině tříd logicky ekvivalentních výroků jsme takto zadefinovali strukturu Booleovy algebry (je pouze třeba projít naše axiomy a ověřit je). Nutně tedy pro výrokovou logiku bude v tomto smyslu platné vše, co dokážeme pro obecné Booleovy algebry. Stručně si proberme, jak vypadají obvyklé další jednoduché výroky ve výrokové logice jakožto prvky Booleovy algebry (tj. reprezentujeme vždy naším výrazem třídu výroků ekvivalentních): Implikaci A B dostaneme jako A B, ekvivalenci A B odpovídá (A B) (A B ). Dále vylučovací OR, neboli XOR, je dáno jako (A B ) (A B), negace NOR operace OR je vyjádřena jako A B a negace NAND operace AND je dána jako A B . Všimněme si také, že XOR odpovídá v množinové algebře symetrickému rozdílu množin. 10.23 10.23. Přepínače jako Booleova algebra. Přepínač je pro nás černá skříňka, která má jen dva stavy, buď je zapnut (a signál prochází) nebo naopak vypnut (a signál neprochází). 3. USPOŘÁDANÉ MNOŽINY A BOOLEOVSKÁ ALGEBRA 325 B A B A Jeden nebo více přepínačů zapojujeme do sítě sériově nebo paralelně. Sériové zapojení je popsáno pomocí binární operace , paralelní je naopak . Unární ope- race A zadává přepínač, který je vždy v opačné poloze než A. Každé konečné slovo vytvořené pomocí přepínačů A, B, . . . a operací , a umíme převést na obrázek, který bude představovat systém přepínačů propojených dráty a zcela obdobně jako v minulém odstavci nám každá volba poloh jednotlivých přepínačů zadá hodnotu ,,zapnuto/vypnuto pro celý systém. Opět se snadno krok po kroku ověří platnost základních axiomů Booleových algeber pro náš systém. Na obrázku je ilustrován jeden z axiomů distributivity. Propojení bez přepínače odpovídá prvku 1, koncové body bez propojení (nebo sériové zapojení A a A ) dává prvek 0. =A A A B C B C 10.24 10.24. Dělitelé. Dalším přirozeným příkladem Booleovské algebry je systém dě- litelů přirozeného čísla nebo polynomu. Zvolme pevně takové číslo p N nebo polynom p K[x1, . . . , xs] nad oborem integrity K s jednoznačným rozkladem. Za nosnou množinu Dp bereme množinu všech dělitelů q našeho p. Pro dva takové dělitele definujeme q r jako největší společný dělitel prvků q a r, q r je nejmenší společný násobek. Dále klademe p = 1 Dp a neutrálním prvkem vůči supremu je jednička v Z, resp. 1 K K[x1, . . . , xs]. Unární operaci dostáváme pomocí dělení: q = p/q. Lemma. Množina Dp spolu s výše uvedenými operacemi , a je Booleova algebra právě, když rozklad p neobsahuje kvadráty (tj. v jednoznačném rozkladu p = q1 . . . qn na nerozložitelné faktory jsou všechna qi po dvou různá). Důkaz. Ověření axiomů je vcelku snadné, projdeme jeden po druhém a bu- deme zkoumat, kdy je zapotřebí nešeho požadavku na nepřítomnost kvadrátů v rozkladu. Největší společný dělitel konečného počtu čísel nebo polynomů nezávisí na po- řadí, ve kterém jej počítáme. Stejně tak pro nejmenší společný násobek. To odpovídá axiomu (1) v 10.21. Komutativita, tj. axiom (2) je zcela zřejmá. Pro tři libovolné prvky a, b, a c můžeme bez újmy na obecnosti psát jejich rozklad ve tvaru a = qp1 1 . . . qps s , b = qm1 1 . . . qms s a c = qk1 1 . . . qks s , kde připouštíme i mocniny 0 a všechny prvky qj jsou po dvou nesoudělné. ab prvek s rozkladem, ve kterém se objeví všechna společná qi v mocnině, která bude minimem z mocnin v a a b. Naopak a b bude mít rozklad, ve kterém se objeví všechny členy z rozkladů a a b a to s mocninou, která bude tou větší z mocnin příslušného faktoru v a a b. Přímo se nyní snadno ověří distributivní zákony. Problém nemáme ani s existencí prvku 0 a 1, které jsme přímo definovali a zjevně splňují axiomy (4) a (5). Existecne kvadrátů ale znemožní definici doplňku. 326 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY Např. v D12 = {1, 2, 3, 4, 6, 12} nelze 6 6 = 1 dosáhnout, protože má 6 netriviál- ního společného dělitele se všemi ostatními prvky v D12 mimo jedničku, ta ovšem nesplňuje 6 1 = 12. Pokud ovšem nejsou v rozkladu čísla nebo polynomu p kvadráty, definujeme doplněk jako q = p/q. Snadno ověříme potřebné vlastnosti z axiomů (4)­(6). 10.25 10.25. Částečná uspořádání. K Booleovským algebrám teď půjdeme z jiné strany. Základní strukturou pro nás bude pojem uspořádání. Vzpomeňme na definici uspo- řádání jakožto reflexivní, antisymetrické a tranzitivní relace na množině K. Ta- ková relace obecně neříká o každé dvojici a, b K jestli je a b nebo b a (takové uspořádání se nazývá úplné uspořádání nebo dobré uspořádání). Často v našem případě obecného uspořádání hovoříme také o částečném uspořádání a množina (K, ) vybavená částečným uspořádáním se nazývá poset (z anglického ,,partial ordered set ). Takové uspořádání je zejména vždy na množině K = 2M všech podmnožin množiny M prostřednictvím inkluze podmnožin. Pomocí naší relace infima na K je můžeme definovat jako A B právě, když A B = A. Ekvivalentně, A B právě, když A B = B. Lemma. Je-li (K, , , ) Booleova algebra, pak relace definovaná vytahem A B právě, když A B = A, je částečné uspořádání. Navíc platí (1) A B A (2) A A B (3) jestliže A C a zároveň B C, pak také A B C (4) A B právě, když A B = 0 (5) 0 A a A 1 pro všechny A K. Důkaz. Všechny dokazované vlastnosti a vztahy jsou výsledkem jednoduchého výpočtu v Booleovské algebře K. Začněme s vlastnostmi uspořádání pro . Refle- xivita je přímým důsledkem idempotence: A A = A, tj. A A. Podobně komu- tativita pro zaručuje antisymetrii , protože z A B = A a zároveň B A = B vyplývá A = A B = B A = B. Konečně z platnosti A B = A a B C = B vyvodíme A C = (A B) C = A (B C) = A B = A, což dává tranzitivitu. Dále počítáme (A B) A = (A A) B = A B, takže A B A. Ze vztahu A (A B) = A plyne A A B, což dokazuje tvrzení (2). Distributivita ukazuje (A B) C = (A C) (B C), což zapředpokladu (3) dává A B, takže skutečně platí (3). Tvrzení (5) plyne přímo z axiomů pro 1 a 0. Jestliže A B, pak A B = A B B = 0. Naopak je-li A B = 0, pak A = A 1 = A (B B ) = (AB)(AB ) = (AB)0 = AB. Odtud A B a dokázali jsme i zbývající tvrzení (4). Všimněme si, že stejně jako v případě algebry podmnožin je v Booleovských algebrách A B = A právě, když je A B = B. Skutečně, je-li A B = A, pak z absorpčních zákonů plyne A B = (A B) B = B, a naopak. 10.26 10.26. Svazy. Viděli jsme, že každá Booleova algebra zadává poset (K, ). Zdaleka ne každý poset ovšem vzniká takovýmto způsobem. Např. triviální částečné uspořádání, kdy A A pro všechny A a všechny dvojice různých prvků jsou nesrovnatelné, samozřejmě z Booleovy algebry vzniknout nemůže, pokud je v K více než jeden prvek (viděli jsme, že největší a nejmenší prvek v Booleově algebře je totiž srovnatelný s každým prvkem). Zkusme se zamyslet, do jaké míry lze z uspořádání budovat operace a . 3. USPOŘÁDANÉ MNOŽINY A BOOLEOVSKÁ ALGEBRA 327 Pracujme s pevně zvoleným posetem (K, ). O prvku C K řekneme, že je dolní závorou pro nějakou množinu prvků L K, je-li C A pro všechny A L. Prvek C K je infimem množiny L K, jestliže je dolní závorou a pro každou jinou dolní závoru D téže množiny platí D C. Obdobně definujeme horní závory a supremum podmnožiny L záměnou za v posled- ním odstavci. Konečné posety se přehledně zobrazují pomocí orientovaných grafů. Prvky K jsou před- stavovány uzly a hranou jsou spojeny právě prvky v relaci s orientací od většího k menšímu. Hasseho diagram posetu je zakreslení takového grafu v rovině tak, že větší prvky jsou zobrazeny vždy výš než menší (a orientace hran je tedy dána takto implicitně). Definice. Svaz je poset (K, ), ve kterém každá dvouprvková množina {A, B} má supre- mum A B a infimum A B v K. Na svazu (K, ) tedy máme definovány binární operace a a přímo z definice je zjevná asociativita a komutativita těchto operací. Snadno lze ale nakreslit Hasseho diagram svazu, který není distributivní. Nyní můžeme snadno definovat Booleovskou algebru v jazyce svazů: Booleovská algebra je distributivní svaz s největším prvkem 1 a nejmenším prvkem 0 takový, že v něm existují ke všem prvkům komplementy. Ověřili jsme již, že v takovém případě komplementy jsou definovány jednoznačně (viz úvahy za definicí 10.21), takže je naše alternativní definice Booleovské algebry korektní. Všimněme si také, při diskusi dělitelů daného čísla nebo polynomu p jsme narazili na svazy Dp, které jsou Booleovskou algebrou právě tehdy, když rozklad p neobsahuje kvadráty. 10.27 10.27. Normální tvary. Při diskusi výrokové logiky jsme se potýkali s problé- mem, co vlastně jsou prvky příslušné Booleovy algebry. Formálně vzato jsme je definovali jako třídy ekvivalentních výroků. Jinak řečeno, pracovali jsme s hod- notovými funkcemi pro výroky s daným počtem argumentů. Vůbec jsme přitom neřešili obtížný problém, jak rozpoznat stejné výroky v tomto smyslu. Také jsme neřešili, jestli všechny formálně možné hodnotové funkce (Z2)n Z2 lze zadat pomocí základních logických operací. Zcela obdobně se můžeme tázat, jak poznat, zda dva systémy přepínačů mají stejnou funkci. Obdobně jako u výroků zde pro systém s n přepínači pracujeme s funkcemi (Z2)n Z2 a zjevně existuje právě 22n různých takových přepínacích funkcí. Na těchto funkcích umíme přirozeným způsobem zadat strukturu Booleovy algebry (využíváme, že hodnoty, tj. Z2 jsou Booleovou algebrou). Odpovíme nyní na výše uvedené otázky tak, že pro libovolný prvek o becné Booleovy algebry sestrojíme jeho tzv. normální disjunktivní tvar, tj. napíšeme jej pomocí vybrané skupiny nejjednodušších prvků a operace . Prvek A K nazveme atom v Booleově algebře K, jestliže pro všechny B K platí A B = A nebo A B = 0. Jinak řečeno, A je atom, když pro všechny ostatní prvky B A implikuje B = 0 nebo B = A. Lemma. Booleova algebra funkcí přepínačového systému s n přepínači A1, . . . , An má 2n atomů, které jsou tvaru A1 1 An n , kde buď A i = Ai nebo Ai i = Ai. Důkaz. Pro dvě funkce a je jejich infimem funkce , jejíž hodnoty jsou dány součinem jejich hodnot v Z2. Platí tedy jestliže má hodnotu 1 všude kde má hodnotu 1 Z2. Odtud už plyne, že v naší Booleově algebře hodnotových funkcí je funkce atomem právě, když z 2n hodnot na jednotlivých možnostech 328 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY hodnot jednotlivých argumentů má právě jednou hodnotu 1 Z2. Všechny takové funkce ovšem lze vytvořit právě způsobem uvedeným v dokazovaném tvrzení. Věta. Každý prvek B v konečné Booleově algebře (K, , , ) lze zapsat jako supre- mum atomů B = A1 Ak. Tato formule je navíc jednoznačná až na pořadí atomů. Důkaz. Uvažme všechny atomy A1, A2, . . . , Ak v K, které jsou menší nebo rovny B. Z vlastností uspořádání na množině K (viz 10.25(3)) je okamžitě vidět, že také Y = A1 Ak B. Dokážeme, že B Y = 0, což podle 10.25(4) zaručuje B Y . Tím bude dokázána rovnost B = Y . Budeme postupně potřebovat tři jednoduchá tvrzení: Tvrzení. Jestliže jsou Y, X1, . . . , X atomy v K, pak Y X1 X tehdy a jen tehdy, když Y = Xi pro nějaké i = 1, . . . , . Tvrzení. Pro každý prvek Y = 0 v K existuje atom X, pro který je X Y . Tvrzení. Jestliže jsou X1, . . . , Xr všechny atomy v K, pak Y = 0 právě, když Y Xi = 0 pro všechny i = 1, . . . , r. Důkaz. Dokončím později... 10.28 10.28. Homomorfismy. Jak jsme již viděli u mnoha matematických struktur, o objektech se dozvídáme informace pomocí tzv. homomorfismů, tj. zobrazení, které zachovávají příslušné operace. V případě Booleovských algeber definujeme podobně jako u okruhů: Definice. Zobrazení f : (K, , , ) (L, , , ) se nazývá homomorfismus Boo- leovských algeber, jestliže pro všechny A, B K platí (1) f(A B) = f(A) f(B) (2) f(A B) = f(A) f(B) (3) f(A ) = f(A) . Homomorfismus f je izomorfismus Booleovských algeber, jestliže je f bijektivní. Snadno se ověří, že bijektivnost f již zaručí, že f-1 je opět homomorfismem. Z definice uspořádání na Booleových algebrách je zřejmé, že každý homomor- fismus f : K L bude také splňovat f(A) f(B) pro všechny prvky A B v K. To je definiční vlastnost pro tzv. izotonní zobrazení neboli homomorfismy posetů. Jakkoliv umíme rekonstruovat operace suprema a infima z uspořádání, pokud toto vzniklo z Booleovy algebry, není pravda, že by každý homomorfismus posetů byl automaticky homomorfismem příslušných algeber. Zkuste si najít příklad (stačí vkládat algebru se dvěma atomy do algebry s alespoň čtyřmi atomy)! Věta. Každá konečná Booleova algebra je izomorfní Booleově algebře K = 2M , kde M je množina atomů v K. Důkaz. Dokončím později. 4. KÓDY (A ŠIFRY?) 329 4. Kódy (a šifry?) Kódy a šifry spolu často úzce souvisí. Často potřebujeme přenášet informace a přitom zajišťovat jejich správnost. Někdy stačí zajistit, abychom poznali, zda je informace nezměněná, a při chybě si vyžádáme informaci znovu, jindy potřebujeme zajistit, aby chyby byly i opraveny bez nového přebnášení správy. To vše je úkol kódování. Pokud navíc chceme, aby zprávu mohl číst pouze adresát, potřebujeme i tzv. šifrování.5 10.29 10.29. Kódování. Při přenosu informace zpravidla dochází k její deformaci. Bu- deme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou buď nuly nebo jedničky (tj. prvky v Z2) a přenášíme slova o k bitech. Obdobné po- stupy jsou možné nad konečnými poli. Přenosové chyby chceme ˇ rozpoznávat ˇ opravovat a za tím účelem přidáváme dodatečných n - k bitů informace pro pevně zvolené n > k. Všech slov o k bitech je 2k a každé z nich má jednoznačně určovat jedno kódové slovo z 2n možných. Máme tedy ještě 2n - 2k = 2k (2n-k - 1) slov, které jsou chybové. Lze tedy tušit, že pro veliké k nám i malý počet přidaných bitů dává hodně redundantní informace. Úplně jednoduchým příkladem je kód kontrolující paritu. Kódové slovo o k + 1 bitech je určené tak, aby přidáním prvního bitu byl zaručen sudý počet jedniček ve slově. Pokud při přenosu dojde k lichému počtu chyb, přijdeme na to. Dvě různá kódová slova se při tomto kódu vždy liší alespoň ve dvou pozicích, chybové slovo se ale od dvou různých kódových slov liší pouze v pozici jedné. Nemůžeme proto umět chyby opravovat ani kdybychom věděli, že došlo k právě jedné. Přehledně jsou všechna možná slova vidět na obrázku níže, kódová slova jsou zvýrazněna tučným puntíkem. Navíc neumíme detekovat tak obvyklé chyby, jako je záměna dvou sousedních hodnot ve slově. 100 110 101 111 001 010 011 000 10.30 10.30. Vzdálenost slov. Definice. Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. Věta. (1) Kód odhaluje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě r + 1. 5V letošním semestru je o 4 přednášky méně než obvykle, proto šifry teď nebudou. . . 330 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY (2) Kód opravuje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě 2r + 1. Důkaz. Obě tvrzení jsou zřejmá z přeedchozí diskuse. 10.31 10.31. Konstrukce polynomiálních kódů. K praktickému použití potřebujeme efektivně konstruovat kódová slova tak, abychom je mezi všemi slovy sladno roz- poznali. Kontrolu parity jsme už viděli, další triviální možnost je prosté opakování bitů ­ např. (3, 1)­kód bere jednotlivé bity a posílá je třikrát po sobě. Docela systematickou cestou ke konstrukci kódů je využití dělitelnosti poly- nomů. Zpráva b0b1 . . . bk-1 je reprezentována jako polynom m(x) = b0 + b1x + + bk-1xk-1 . Definice. Nechť p(x) = a0 + + an-kxn-k Z2[x] je polynom s a0 = 1, an-k = 1. Polynomiální kód generovaný polynomem p(x) je (n, k)­kód jehož slova jsou polynomy stupně menšího než n dělitelné p(x). Zpráva m(x) je zakódována jako v(x) = r(x) + xn-k m(x), kde r(x) je zbytek po dělení polynomu xn-k m(x) polynomem p(x). Z definice víme v(x) = xn-k m(x) + r(x) = q(x)p(x) + r(x) + r(x) = q(x)p(x). Budou tedy všechna kódová slova dělitelná p(x). Původní zpráva je obsažena přímo v polynomu v(x), takže dekódování správ- ného slova je snadné. Příklad. (1) Polynom p(x) = 1 + x generuje (n, n - 1)­kód kontroly parity pro všechna n 3. (2) Polynom p(x) = 1 + x + x2 generuje (3, 1)­kód opakování bitů. První tvrzení plyne z toho, že 1 + x dělí polynom v(x) tehdy a jen tehdy, když v(1) = 0 a to nastane tehdy, když je ve v(x) sudý počet nenulových koeficientů. Druhé je zřejmé. 10.32 10.32. Detekce chyb. Přenos slova v (Z2)n dopadne příjmem polynomu u(x) = v(x) + e(x) kde e(x) je tzv. chybový polynom repzentující vektor chyby přenosu. Chyba je rozpoznatelná pouze, když generátor kódu p(x) nedělí e(x). Máme proto zájem o polynomy, které které nevystupují jako dělitelé zbytečně často. Definice. Ireducibilní polynom p(x) Z2[x] stupně m se nazývá primitivní, jestliže p(x) dělí polynom (1 + xk ) pro k = 2m - 1 ale nedělí jej pro žádná menší k. Věta. Je-li p(x) primitivní polynom stupně m, pak pro všechna n 2m - 1 rozpo- znává příslušný (n, n - m)­kód všechny jednoduché a dvojité chyby. Důkaz. Důkaz doplním. Důsledek. Je-li q(x) primitivní polynom stupně m, pak pro všechna n 2m - 1 rozpoznává (n, n - m - 1)­kód generovaný polynomem p(x) = q(x)(1 + x) všechny dvojité chyby a všechna slova s lichým počtem chyb. 4. KÓDY (A ŠIFRY?) 331 Tabulka dává o informace o výsledcích předchozích dvou vět pro několik poly- nomů: primitivní polynom kontrolní bity délka slova 1 + x + x2 2 3 1 + x + x3 3 7 1 + x + x4 4 15 1 + x2 + x5 5 31 1 + x + x6 6 63 1 + x3 + x7 7 127 1 + x2 + x3 + x4 + x8 8 255 1 + x4 + x9 9 511 1 + x3 + x10 10 1023 Nástroje pro konstrukci primitivních polynomů dává teorie konečných polí. Souvisí s tzv. primitivními prvky v Galoisových polích G(2m ). Ze stejné teorie lze také dovodit příjemnou realizaci dělení se zbytkem (tj.) ověřování, zda je přijaté slovo kódové, pomocí zpožďovacích registrů. Jde o jednoduchý obvod s tolika prvky, kolik je stupeň polynomu.6 . 10.33 10.33. Lineární kódy. Polynomiální kódy lze efektivně popisovat také pomocí elemnetárního maticového počtu. Vyjdeme z obecnější definice, která požaduje lie- ární závislost kdového slova na původní informaci: Definice. Lineární kód je injektivní lineární zobrazení g : (Z2)k (Z2)n . Matice G typu k/n reprezentující toto zobrazení v standardních bazích se nazývá generující matice kódu. Pro každé slovo v je u = G v příslušné kódové slovo. Věta. Každý polynomiální (n, k)­kód je lineární kód. Důkaz. Vyplývá přímo z vlastností dělení polynomů se zbytkem. Např. matice příslušná k polynomu p(x) = 1 + x + x2 a odpovídajícímu (6, 3)­ kódu je G = 1 0 1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 . 10.34 10.34. Věta. Je-li g lineární kódování s maticí G = P Ik , potom zobrazení h : (Z2)n (Z2)k s maticí H = In-k P má následující vlastnosti 6 detaily později 332 10. ALGEBRAICKÉ STRUKTURY A TECHNIKY (1) Ker h = Im g (2) přijaté slovo u je kódové slovo právě, když je H u = 0 Důkaz. Dodám později (je snadný) Matici H z věty se říká matice kontroly parity přílušného (n, k)­kódu. 10.35 10.35. Samoopravné kódy. Jak jsme viděli, přenos zprávy u dává výsledek v = u + e. To je ale nad Z2 ekvivalentní e = u + v. Pokud tedy známe podprostor V (Z2)n správných kódových slov, víme u každého výsledku, že správné slovo (s opravenými prřípadnými chybami) je ve třídě rozkladu v + V v prostoru (Z2)n /V . Zobrazení h : (Z2)n (Z2)n-k má V za jádro, proto indukuje injektivní li- neární zobrazení h : (Z2)n /V (Z2)n-k . Jeho hodnoty jsou jednoznačně určeny hodnotami H u. Definice. Hodnota H u se nazývá syndrom slova u. Věta. Dvě slova jsou ve stejné třídě rozkladu u + V právě, když sdílí syndrom. Samoopravné kódy lze konstruovat tak, že pro každý syndrom určíme prvek v příslušné třídě, který je nejvhodnějším slovem. 10.36 10.36. Poznámky o šifrách. DOPLNIT!!!! KAPITOLA 11 Statistické metody Je statistika částí matematiky? ­ když ano, tak matematiky potřebuje hodně . . . 11.1 11.1. Pravděpodobnost nebo statistika? Statistika v širším slova smyslu je jakékoliv zpracování číselných dat o nějakém souboru objektů a jejich více či méně přehledná prezentace. V tomto smyslu hovoříme také o popisné statistice, když jsou zpracovávána a zpřehledňována data o všech objektech daného souboru (např. roční příjmy všech občanů zpracovávané z kompletních dat finančních úřadů), a ma- tematické statistice, když matematickými metodami zkoumáme jen data menšího počtu objektů (např. zjišťujeme údaje o příjmech pomocí dat získaných u několika nahodile vybraných osob). Podstatou matematické statistiky je pro prezentovaná data zjišťovat, jaké vlast- nosti skutečně mají objekty, které jou daty popisovány, a zároveň, jak věrohodné odvozené výsledky jsou. Zpravidla přitom jde o sběr a zpracování dat o nějakém souboru objektů, jejich následnou analýzu a konečně o vyslovení důsledků pozo- rování pro rozsáhlejší soubor objektů než jsou ty, jejichž data jsme zpracovávali. Jinak řečeno, výsledkem práce matematického statistika je sdělení o velkém souboru objektů na základě studia malé (zpravidla náhodně vybrané) části z nich, společně s kvalitativním odhadem věrohodnosti výsledného sdělení. Matematická statistika se opírá o teorii pravděpodobnosti, o které jsme něco málo uváděli na samotném počátku naší cesty matematikou, ve čtvrté části první kapitoly. Zatímco teorie pravděpodobnosti se zabývá modely popisujícími chování abstraktních souborů (hovořili jsme o pravděpodobnosti jevů z jevového pole), sta- tistika pracuje se skutečným náhodným výběrem z nějakého základního souboru a poskytuje podklady pro výběr teoretického pravděpodobnostního modelu, resp. kvalitativní informace o jeho parametrech. Uvidíme, že při zpracovávání statistic- kých dat provádíme v podstatě úkony popisné statistiky, teorii pravděpodobnosti však potřebujeme pro vyslovení kvalitativních údajů o výsledcích. Ne náhodou se právě k této části našich motivačních náznaků z první kapitoly vracíme až na samém konci našich přednášek. Statistikami je totiž dnes zaplaveno kdejaké sdělení, ať už v médiích, politické nebo odborné, nicméně porozumět obsahu takového sdělení a pochopit možnosti či oprávněnost využití jednotlivých statistic- kých metod a pojmů si vyžaduje mnoho znalostí z různých oblastí matematiky, kterými jsme dosud procházeli. Příklad. Za soubor objektů vezměme všechny studenty této přednášky ,,Drsná matematika , jako číselný údaj můžeme uvažovat (1) ,,průměrný počet bodů dosažený při hodnocení tohoto předmětu v minulém semestru, 333 334 11. STATISTICKÉ METODY (2) ,,průměrnou známku dosaženou u zkoušky z tohoto a z jiných pevně vybraných předmětů, (3) číslená data vypovídající o historii dřívějšího studia, (4) počet pracovních hodin týdně odpracovaných studentem či studentkou mimo fakultu a mnoho dalších údajů. Zastavme se u prvního údaje. Samotný aritmetický průměr bodů nám mnoho neřekne ani o kvalitě přednášky ani o kvalitě přednášejícího ani o samotném hodnocení konkrétních studetnů. Možná nás bude více zajímat hodnota, která bude ,,uprostřed souboru , tj. počet bodů, pro které je stejně studentů pod ní a nad ní (nebo obdobně první a poslední čtvrtina, desetina apod.). Všem takovým údajům říkáme statistiky posuzované veličiny. V uvedených příkladech se jim říká medián, kvartil, decil apod. Takové statistiky budou jistě zajímavé pro samotné studenty a je docela jednoduché je zavést a spočíst. Z obecné zkušenosti nebo jako výsledek teoretických úvah mimo samotnou ma- tematiku víme, že rozumné hodnocení by na mělo mít tzv. normální rozdělení. Tento pojem patří do teorie pravděpodobnosti a k jeho zavedení potřebujeme poměrně dost matematiky. Porovnáním výsledku třeba i docela malého náhodného výběru studentů s teoretickým předpokladem můžeme zjistit odhad parametrů takového rozdělení a činit závěry, zda je celé hodnocení postaveno rozumně. Zároveň lze z číselných hodnot našich statistik pro konkrétní výběr kvalitativně popsat věrohod- nost našich závěrů. Stejně tak budeme umět spočíst statistiky, které nebudou mě- řit polohy uvnitř daného statistického souboru ale variabilitu sledovaných hodnot. Tak například když výsledky hodnocení nebudou vykazovat dostatečnou variabi- litu, přičemž studenti jistě různé výkony prokazují, jde opět o náznak, že je něco v nepořádku. Daleko zajímavější vývody ovšem můžeme činit, když porovnáním statistik pro různé veličiny uvedené výše budeme moci dovozovat informace o souvislostech. Pokud např. neexistuje žádná doložitelná souvislost mezi historií předchozího studia a výsledky v dané přednášce, je jedním z možných vysvětlení vývod, že je přednáška prostě špatná. Zamysleme se nad závěry našich úvodních úvah: ˇ V matematice pracujeme s abstraktním matematickým popisem pravděpodob- nosti. ˇ Vývody pro konktrétní soubory dat, pro které je zvolený model relevantní, dává matematická statistika. ˇ To, zda je takový popis adekvátní pro konkrétní výběr dat, je také možné podpořit nebo zavrhnout pomocí metod matematické statistiky. Než se pustíme do elementárního náznaku statistických postupů, budeme se věnovat chvíli matematické pravděpodobnosti. 1. Pravděpodobnost 11.2 11.2. Jevová pole. Před dalším čtením lze čtenářům vřele doporučit zopakování obsahu čtvrté části první kapitoly (tj. odstavce 1.20­1.39). Tehdy jsme pracovali převážně s tzv. klasickou konečnou pravděpodobností zavedli jsme základy forma- lismu, který nyní zobrecníme. Hlavní změnou bude, že náš základní prostor už nebude obecně obsahovat jen konečně mnoho prvků. 1. PRAVDĚPODOBNOST 335 Budeme pracovat s neprázdnou pevně zvolenou množinou všech možných výsledků, kterou nazýváme základní prostor. Prvky představují jednotlivé možné výsledky. Systém podmnožin A základního prostoru se nazývá jevové pole a jeho prvky se nazývají jevy, jestliže ˇ A, tj. základní prostor, je jevem, ˇ je-li A, B A, pak A\B A, tj. pro každé dva jevy je jevem i jejich množinový rozdíl, ˇ je-li Ai A, i I, nejvýše spočetný systém jevů, pak také jejich sjednocení je jevem, tj. iIAi A. V souladu s obvyklými verbálními popisy skutečných problémů používáme také následující terminologii: ˇ Komplement Ac = \ A jevu A je jevem, který nazýváme opačný jev k jevu A. ˇ Průnik dvou jevů opět jevem, protože pro každé dvě podmnožiny A, B platí A \ ( \ B) = A B. Jevové pole je tedy systém podmnožin základního prostoru uzavřený na ko- nečné průniky, spočetná sjednocení a množinové rozdíly. Jednotlivé množiny A A nazýváme náhodné jevy (vzhledem k A). Jako příklad, proč nám i u zdánlivě klasických problémů nestačí konečná kla- sická pravděpodobnost, můžeme promyslet třeba experiment, ve kterém opakovaně házíme mincí dokud nepadne líc. Ptáme se, jaká je pravděpodobnost, že budeme házet právě 3­krát nebo právě 35­krát nebo nejvýš 10­krát apod. Elementární jevy jsou tedy tvaru k N1 {}, které slovně vyjadřujeme ,,líc padne poprvé právě v k­tém hodu . Zjevně můžeme takový problém dobře zvládat, když vyjdeme z pravděpodob- nosti 0,5 pro obě možné strany mince při jednom hodu, nemůžeme ale v abstraktním modelu vyloučit možnost neustálých rubů a už vůbec ne omezit celkový počet hodů nějakým povným přirozeným číslem N. Na druhé straně, očekávaná pravděpodob- nost, že padne právě (k - 1)­krát rub v n k pokusech je dána zlomkem 2n-k 2n = 2-k , kde v čitateli je počet možností příznivých z n nezávislých hodů (tj. možností jak rozestavit dvě hodnoty do n - k pozic) a ve jmenovateli je počet všech možností výsledků. Podle očekávání tato pravděpodobnost nezávisí na zvoleném n a platí k=1 2-k = 1 a tedy musí být pravděpodobnost neustálého opakování rubu nulová. 11.3 11.3. Pravděpodobnostní prostor. Souvislosti s popisem skutečných jevů a je- jich formálním pravděpodobnostním popisem vedou k definicím: ˇ celý základní prostor se nazývá jistý jev, prázdná podmnožina A se nazývá nemožný jev, ˇ jednoprvkové podmnožiny {} se nazývají elementární jevy, ˇ společné nastoupení jevů Ai, i I, odpovídá jevu iIAi, nastoupení alespoň jednoho z jevů Ai, i I, odpovídá jevu iIAi, ˇ A, B A jsou neslučitelné jevy, je-li A B = , ˇ jev A má za důsledek jev B, když A B, ˇ je-li A A, pak se jev B = \ A nazývá opačný jev k jevu A, píšeme B = Ac . 336 11. STATISTICKÉ METODY Konečně umíme popsat, co je v našem matematickém modelu pravděpodobnost: Definice. Pravděpodobnostní prostor je jevové pole A podmnožin (konečného) zá- kladního prostoru , na kterém je definována skalární funkce P : A R s násle- dujícími vlastnosti: ˇ je nezáporná, tj. P(A) 0 pro všechny jevy A, ˇ je aditivní, tj. P(iIAi) = iI P(Ai), pro každý nejvýše spočetný systém po dvou neslučitelných jevů, ˇ pravděpodobnost jistého jevu je 1. Funkci P nazýváme pravděpodobností na jevovém poli (, A). Příklad takto definované pravděpodobnosti na nekonečné množině elementár- ních jevů jsme viděli na konci předchozího odstavce. Jako přímé důsledky naší definice vidíme, že pro všechny jevy platí P(Ac ) = 1 - P(A). Zdůrazněme také, že additivnost platí pro jakýkoliv spočetný počet neslučitelných jevů Ai , i I, tj. P(iIAi) = iI P(Ai), kdykoliv je Ai Aj = , i = j, i, j I. Připomeňme si dále klasickou konečnou pravděpodobnost: Nechť je konečný základní prostor a nechť jevové pole A je právě systém všech podmnožin v . Kla- sická pravděpodobnost je pravděpodobnostní prostor (, A, P) s pravděpodobnostní funkcí P : A R, P(A) = |A| || . Zjevně takto zadaná funkce skutečně definuje pravděpodobnost. 11.4 11.4. Peterburgský paradox. (Bernoulli, 1738) Typický příklad klasické prav- děpodobnosti jsou jevy související s házením mincí. Představme si následující pra- vidla kasina: Návštěvník zaplatí vklad C a poté hází mincí. Je-li T počet hodů potřebných k první hlavě, pak obdrží výhru 2T . Jaká je ,,fér hodnota pro vklad C? Pravděpodobnostní model pro tuto hru jsme zavedli na konci 11.2. Pravdě- podobnost, že padne hlava je u férové mince 1/2, je proto P(T = k) = 2-k . Sečteme-li všechny pravděpodobnosti výsledků vynásobené výhrami 2k , dostaneme 1 1 = . Zdá se proto, že se vyplatí vložit i velký vklad. . . Ve skutečnosti simulací hry zjistíme, že nezávisle na počtu pokusů se prakticky všechny výhry budou pohybovat v rozmezí 3 až 6. Důvodem je, že vysoké výhry jsou velice nepravděpodobné a proto je při reálných úvahách nelze brát vážně. Zkuste si promyslet zdůvodnění podrobněji. 11.5 11.5. Podmíněná pravděpodobnost. Obvyklé je klást dotazy s dodatečnou podmínkou. Např. ,,jaká je pravděpodobnost, že při hodu dvěmi kostkami padly dvě pětky, je-li součet hodnot deset? . Připomeneme, že formalizovat takové úvahy umíme následovně. 1. PRAVDĚPODOBNOST 337 Definice. Nechť H je jev s nenulovou pravděpodobností v jevovém poli A v pravděpodobnostním prostoru (, A, P). Podmíněná pravděpodobnost P(A|H) jevu A A vzhledem k hypotéze H je definována vztahem P(A|H) = P(A H) P(H) . Definice odpovídá požadavku, že jevy A a H nastanou zároveň, za předpokladu, že A nastal s pravděpodobností P(A H)/P(A). Je také vidět přímo z definice, hypotéza H a jev A jsou nezávislé tehdy a jen tehdy, je-li P(A) = P(A|H). Přepsáním formule pro podmíněnou pravděpodobnost dostáváme P(A B) = P(B A) = P(A)P(B|A) = P(B)P(A|B). Věta (Bayesovy věty). Pro pravděpodobnost jevů A a B platí P(A|B) = P(A)P(B|A) P(B) (1) P(A|B) = P(A)P(B|A) P(A)P(B|A) + P(A )P(B|A ) .(2) Důkaz. První tvrzení je přepsáním předchozí formule, druhé z prvého plyne doszením P(B) = P(A)P(B|A) + P(A )P(B|A ). 11.6 11.6. Příklad ­ preventivní screening. Předpokládejme, že krevní test na HIV pozitivní osoby má 99% správnost v případě osoby skutečně HIV pozitivní. Zároveň předpokládejme, že u HIV negativní osoby dopadne test pozitivně v 0.2% případů. Náhodně z populace vybereme osobu a otestujeme pozitivně. S jakou pravdě- podobností je skutečně HIV pozitvní, jestliže četnost výskytu HIV v populaci je p promile (tj. p osob z tisíce je skutečně HIV pozitivní). Označme A jev, že je daná osoba HIV pozitivní, a B jev, že daná osoba má pozitivní test. Dle druhé Bayesovy věty je hledaná pravděpodobnost P(A|B) = p/1000 99/100 p/1000 99/100 + (1000 - p)/1000 2/1000 . Jestliže zvolíme za p nějaké konkrétní četnosti, dostaneme příslušné očekávatelné spolehlivosti testu. V následující tabulce je spočten výsledek pro 100 promile (tj. jeden z deseti je nemocný), pro 10 promile (tj. každý stý člověk je infikován), 1 promile a 1/10 promile (tj. pouze jeden z deseti tisíc je infikován ­ to asi může odpovídat realitě). p 100 10 1 0.1 P(A|B) 0.982 0.8333 0.3313 0.0471 Výsledek asi neodpovídá naší intuici a může se zdát šokující ve vztahu k použití takovýchto testů. V případě 0,1 promile nakažených lidí totiž při pozitivním testu nemáme ani 5% pravděpodobnost, že je dotčená osoba skutečně infikovaná. Všimněme si také, že i 100% účinný test při testu pozitvní osoby v podstatě neovlivní výsledné pravděpodobnosti. Evidentně prostý výběr náhodné osoby a použití jediného testu, byť velmi cit- livého, specifického a účinného, nejsou vhodné ani na otestování skutečného stavu populace, ani na preventivní vyšetření jednotlivců, pokud nemáme další podpůrné informace a lepší nástroje. 338 11. STATISTICKÉ METODY Právě matematická statistika dává nástroje na kvalifikovanější postupy v me- dicínské i průmyslové diagnostice, ekonomických modelech, vyhodnocování experi- mentálních dat atd. Opírají se většinou o několik parametrů, které k danému jevu přiřazujeme a při praktickém vyhodnocování je zjišťujeme a zpracováváme. Jsou obdobou obyčejných funkcí, potřebujeme je ale vztáhnout k danému prvděpodob- nostnímu prostoru. 11.7 11.7. Náhodné veličiny. Vraťme se k jednoduchému a názornému příkladu sta- tistik kolem výsledků studentů1 v daném předmětu. Ten je a není podobný klasické pravděpodobnosti a s ní související statistice při házení kostkou. Na jedné straně máme pouze konečný počet studentů a připustili jsme pouze konečný počet možných bodových hodnocení práce studenta za semestr (celá čísla od 0 do 20). Zároveň ale není patrně vhodné představovat si výsledky jednotlivých studentů jako analogii nezávislého házení pravidelnou kostkou (jednak neexituje pravidelný 21­stěn, ale hlavně by to byla skutečně divně vedená přednáška). Na základním (konečném) prostoru všech studentů máme ve skutečnosti definovánu funkci bodového ohodnocení X : R, která má tu vlastnost, že můžeme mode- lovat pravděpodobnosti, že její hodnota při náhodném výběru studenta padne do předem zvoleného intervalu. Např. můžeme chtít modelovat pravděpodobnost, že student uspěl s hodnocením A nebo B. Je to typický příklad náhodné veličiny a každá taková náhodná veličina je spo- jena s vhodnou množinou jevů. V našem příkladě bychom tedy měli umět říci prav- děpodobnost pro kterýkoliv interval (a, b) [0, 20] s reálnými čísly a, b a uzavřenými i otevřenými konci intervalu. Patrně bychom od rozumně vedené přednášky a dob- rých studentů očekávali, že nejvyšší pravděpodobnost výsledku bude ležet někde uprostřed škály v ,,úspěšném intervalu , zatímco ideální výsledek plného bodového zisku příliš pravděpodobný nebude. I obecné pro takové číselné veličiny X na základním prostoru požadujeme, abychom mohli pracovat s pravděpodobnostmi příslušnosti hodnoty X do předem zadaného intervalu. Musíme proto uvést do souladu požadavky na pravděpodob- nostní prostor s vlastnostmi takových funkcí: Na prostoru Rk uvažujme nejmenší jevové pole B obsahující všechny k­rozměrné intervaly. Množinám v B říkáme Borelovské množiny na Rk . Specielně pro k = 1 půjde o všechny množiny, které ze všech intervalů obdržíme konečnými průniky a nejvýše spočetnými sjednoceními. 2 Definice. Náhodná veličina X na pravděpodobnostním prostoru (, A, P) je ta- ková funkce X : R, že vzor X-1 (B) patří do A pro každou Borelovskou množinu B B na R. Reálná funkce PX(B) = P(X-1 (B)) definovaná na všech Borelovských množinách B R se nazývá rozdělení (pravděpodobnosti) náhodné veličiny X Všimněme si, že pro klasickou konečnou pravděpodobnost je náhodnou veliči- nou každá reálná funkce X : R. Skutečně, na konečné množině nabývá X jen konečně mnoho hodnot a každá podmnožina v je jevovým prostorem. 1Myslíme samozřejmě na ,,studenty a studentky , pro zestručnění textu ale používám po- dobně jako v legislativních textech bezpohlavní označní ,,student 2V této souvislosti se často také hovoří o tzv. ­algebře Borelovsky měřitelných množin na Rk a následující definici lze formulovat tak, že náhodné veličiny jsou Borelovsky měřitelné funkce. 1. PRAVDĚPODOBNOST 339 Rozdělení pravděpodobnosti náhodných veličin zadáváme nejčastěji pomocí pravidla, jak roste pravděpodobnost s přírůstkem intervalu B: 11.8 11.8. Distribuční funkce. Definice náhodné veličiny zajišťuje, že pro všechny - a b existují pravděpodobnost P(a < X < b), kde používáme stručné značení pro jev A = ( ; a < X() < b)). Stejně tak existují pravděpodobnosti pro hodnoty v intervalech uzavřených nebo z jedné strany uzavřených. Definice. Distribuční funkcí náhodné veličiny X je funkce F : R R definovaná pro všechny x R vztahem3 F(x) = P(X < x). 11.9 11.9. Diskrétní a spojité náhodné veličiny. Náhodné veličiny se chovají zá- sadně odlišně podle toho, jestli je veškerá nenulová pravděpodobnost ,,soustředěna do několika konečných hodnot nebo je naopak ,,spojitě rozprostřena po (části) reálné osy. Předpokládejme nejprve, že náhodná veličina X na pravděpodobnostním pro- storu (, A, P) nabývá jen konečně mnoha hodnot x1, x2, . . . , xn R. Pak existuje tzv. pravděpodobnostní funkce f(x) taková, že f(x) = P(X = xi) x = xi 0 jinak. Evidentně n i=1 f(xi) = 1 a pro rozdělení pravděpodobnosti platí P(X-1 B) = xiB f(xi) a tedy zejména je distribuční funkce tvaru FX(t) = xi xn. (4) Je-li X spojitá, pak je F(x) diferencovatelná a její derivace se rovná hustotě pravděpodobnosti X, tj. platí F (x) = f(x). Důkaz. Dodám později... 11.11 11.11. Důsledek. Distribuční funkce náhodné veličiny má vždy nejvýše spočetně mnoho bodů nespojitosti. Důkaz. Dodám později... Dodat poznámku o distribuci u veličin, které mají spojité i diskrétní chování současně (Riemann­Stieltjesův integrál a něco málo o míře). 11.12 11.12. Příklady diskrétních rozdělení. Požadavky na vlastnosti rozdělení ná- hodných veličin zpravidla vychází z modelovaných situací a ve skutečnosti pak ani nemáme moc možností, jak rozdělení pravděpodobnosti může vypadat. Uvedeme nejprve několik jednoduchých diskrétních rozdělení. Degenerované rozdělení Dg(). Toto rozdělení odpovídá konstantní hodnotě X = . Distribuční funkce FX a pravděpodobnostní funkce fX jsou tedy rovny FX(t) = 0 t 1 t > fX(t) = 1 t = 0 jinak . Alternativní rozdělení A(p) popisuje pokus s pouze dvěma možnými výsledky, kterým budeme říkat zdar a nezdar. Náhodné veličině X pro určitost přiřadíme hodnotu 0 pro nezdar a 1 pro zdar. Pokud má zdar pravděpodobnost p, pak nezdar musí mít pravděpodobnost 1-p. Jsou tedy distribuční a pravděpodobnostní funkce tvaru: FX(t) = 0 t 0 1 - p 0 < t 1 1 t > 1 fX(t) = p t = 1 1 - p t = 0 0 jinak . Binomické rozdělení Bi(n, p) odpovídá n­krát nezávisle opakovanému pokusu popsanému alternativním rozdělením, přičemž naše náhodná veličina měří počet zdarů. Je tedy zjevné, že pravděpodobnostní funkce bude mít nenulové hodnoty právě v celých číslech 0, . . . , n odpovídajícím celkovému počtu úspěchů v pokusech (a nezáleží nám na pořadí). Je tedy fX(t) = n t pt (1 - p)1-t t {0, 1, . . . , n} 0 jinak . Na obrázku jsou pravděpodobnostní funkce pro Bi(50, 0.2), Bi(50, 0.5) a Bi(50, 0.9). Rozdělení pravděpodobnosti dobře odpovídá intuici, že nejvíce výsledků bude blízko u hodnoty np: 4Pokud definujeme distribuční funkci s neostrou nerovností, bude naopak zprava spojitá, ostatní tvrzení této věty zůstavají v platnosti beze změny. 1. PRAVDĚPODOBNOST 341 S binomickým rozdělením se potkáváme velice často v praktických úlohách. Jednou z nich je popis náhodné veličiny, která popisuje počet X předmětů v jedné zvolené příhrádek z n možných, do nichž jsme náhodně rozdělili r předmětů. Umís- tění kteréhokoliv předmětu do pevně zvolené přihrádky má pravděpodobnost 1/n (každá z nich je stejně pravděpodobná). Zjevně tedy bude pro jakýkoliv počet k = 0, . . . , r P(X = k) = r k 1 n k 1 - 1 n r-k = r k (n - 1)r-k nr , jde proto o rozložení X typu Bi(r, 1/n). Jestliže nám bude vzrůstat počet přihrádek n společně s počtem předmětů rn tak, že v průměru nám na každou přihrádku bude připadat (přibližně) stejný počet prvků , můžeme dobře vyjádřit chování našeho rozdělení veličin Xn při limitním přechodu n . Takovéto chování popisuje např. fyzikální soustavy s velikým počtem molekul plynu. Standardní úpravy (s řádným připomenutím analýzy funkcí jedné proměnné!) vedou při limn rn/n = k výsledku: lim n P(Xn = k) = lim n rn k ! (n - 1)rn-k nrn = lim n rn(rn - 1) . . . (rn - k + 1) (n - 1)k 1 k! ,, 1 - 1 n rn = k k! lim n ,, 1 + -rn n rn rn = k k! e- protože obecně funkce (1 + x/n)n konvergují stejnoměrně k funkci ex na každém omezeném intervalu v R. Poissonovo rozdělení Po() popisuje náhodné veličiny s pravděpodobnostní funkcí fX(t) = k k! e- t N 0 jinak. Jak jsme odvodili výše, toto diskrétní rozdělení (rozložené do nekonečně mnoha bodů) dobře aproximuje binomická rozložení Bi(n, /n) pro konstantní > 0 a veliká n. Přímým výpočtem snadno ověříme, že k=0 fX(k) = k k k! e- = e- k k k! = e-+ = 1. 342 11. STATISTICKÉ METODY Takové chování lze očekávat při sledování výskytu jevů v prostoru s konstatní očekávanou hustotou na jednotku objemu (např. při sledování výskytu bakterií na sklíčku pod mikroskopem, které se stejně pravděpodobně vyskytují v kterékoliv jeho části). Je-li ,,průměrná hustota výskytu v jednotkové ploše , pak při rozdělení celé oblasti na n stejných částí bude výskyt k jevů v jedné výbrané části modelován náhodnou veličinou X s Poissonovým rozdělením. Takovéto pozorování při praktické diagnostice v biochemické laboratoři umožní výpočet docela přesného celkového počtu bakterií ve vzorku ze skutečného počtu odečteného jen v několika náhodně vybraných malých částech vzorku. Další přípak výskytu Poissonova rozdělení jsou události, které se vyskytují ná- hodně v čase a přitom pravděpodobnost výskytu v následujícím časovém intervalu o jednotkové délce nezávisí na předchozí historii a je rovna stále stejné hodnotě . Označme si náhodnou veličinu Xt vyčíslující počet výskytu sledovaného jevu v intervalu [0, t). Přesněji řečeno, požadujeme aby ˇ pravděpodobnost události v každém časovém úseku o délce h byla rovna h + o(h) ˇ pravděpodobnost více než jedné události v časovém úseku délky h je o(h) ˇ jevy [Xt = j] a [Xt+h - Xt = k] jsou nezávislé pro všechny j, k N a t, h > 0. Označíme-li si funkce pk(t) = P(Xt = k), k N, a položíme přirozené okrajové podmínky pk(0) = 0 pro k > 0 a p0(0) = 1, pak limitními přechody s využitím předchozích podmínek (dodat podrobnosti!!!!!!!!!!!!) obdržíme pro derivace funkcí pk p0(t) = -p0(t), t > 0, p0(0) = 1 pk(t) = -pk(t) + pk-1(t), t > 0, k > 0, pk(0) = 0. To je nekonečný (!) systém obyčejných diferenciálních rovnic s počáteční podmínkou, z nichž první má jediné řešení p0(t) = e-t . Pak okamžitě můžeme dosadit a vyřešit druhou a obdržíme p1(t) = t e-t . Matematickou indukcí teď už snadno dovodíme, že ve skutečnosti má celý systém jediné řešení a to pk(t) = (t)k k! e-t , t > 0, k N. Ověřili jsme tedy, že pro každý proces splňující tři výše uvedené vlastnosti má náhodná veličina Xt udávají počet výskytů v časovém intervalu [0, t) rozdělení Po(t). V praxi jsou takové procesy spojeny např. s poruchovostí strojů a zařízení. 11.13 11.13. Příklady spojitých rozdělení. Nejjednoduším příkladem spojitého roz- dělení je tzv. rovnoměrné rozdělení. Na něm lze dobře ilustrovat, že při jedno- duše formulovaném požadavku na chování rozdělení nám nezbude moc prostoru pro jeho definici. Nyní chceme, aby pravděpodobnost každé hodnoty v předem daném intervalu (a, b) R byla stejná, tj. hustota fX našeho rozdělení náhodné veličiny X má být konstantní. Pak ovšem jsou pro libovolná reálná čísla - < a < b < jen jediné možné hodnoty fX(t) = 0 t a 1 b-a t (a, b) 0 t b, FX(t) = 0 t a t-a b-a t (a, b) 1 t b. Exponenciální rozdělení ex() je dalším rozdělením, které je snadno určeno požadovanými vlastnostmi náhodné veličiny. Předpokládejme, že sledujeme výskyt náhodného jevu tak, že výskyty v nepřekrývajících se intervalech jsou nezávislé. Je- li tedy P(t) pravděpodobnost, že jev nenastane během intervalu délky t, pak nutně 1. PRAVDĚPODOBNOST 343 P(t + s) = P(t)P(s) pro všechna t, s > 0. Předpokládejme navíc diferencovatelnost funkce P a P(0) = 1. Pak jistě ln P(t + s) = ln P(t) + ln P(s), takže limitním přechodem lim s0+ ln P(t + s) - ln P(t) s = P (0). Označme si spočtenou derivaci zprava v nule jako - R. Pak tedy pro P(t) platí ln P(t) = -t + C a počáteční podmínka dává jediné řešení P(t) = e-t . Všimněme si, že z definice našich objektů vyplývá, že > 0. Nyní uvažme náhodnou veličinu X udávající (náhodný) okamžik, kdy náš jev poprvé nastane. Zřejmě tedy je distribuční funkce rozdělení pro X dána FX(t) = 1 - P(t) = 1 - e-t t > 0 0 t 0. Je vidět, že skutečně jde rostoucí funkci s hodnotami mezi nulou a jedničkou a správnými limitami v . Hustotu tohoto rozdělení dostaneme derivováním distribuční funkce, tj. fX = e-t t > 0 0 t 0. Normální rozdělení je ze všech nejdůležitější. Jestliže v binomiálním roz- dělení zachováme konstatní úspěšnost p, ale budeme přidávat počet pokusů n, bude pravděpodobnostní funkce kupodivu pořád mít podobný tvar (i když jiné rozměry). Na obrázku při rostoucím n se budou vynesené bodové hodnoty slívat do křivky, pro hodnoty Bi(500, 0.5) a Bi(5000, 0.5) je výsledek vidět na obrázku níže, rozdělení Bi(50, 0.5) jsme viděli dříve. Třetí křivka na obrázku je grafem funkce f(x) = e-x2 /2 . Podbízí se proto hledat vhodné spojité rozdělení, které by mělo hustotu da- nou nějakou obdobnou funkcí. Protože je e-x2 /2 vždy kladná funkce, potřebovali bychom spočíst b a e-x2 /2 dx což není pomocí elementárních funkcí možné. Je však možné (i když ne úplně snadné) ověřit, že příslušný nevlastní integrál konverguje k hodnotě - e-x2 /2 dx = 2. 344 11. STATISTICKÉ METODY Odtud vyplývá, že možná hustota rozdělení náhodného rozdělení může být fX(x) = 1 2 ex . Rozdělení s touto hustotou se nazývá normální rozdělení N(0, 1). Příslušnou distri- buční funkci FX(x) = x - e-x2 /2 dx nelze vyjádřit pomocí elementárních funkcí, přesto se s ní numericky běžně počítá (pomocí tabulek nebo softwarových aplikací). Hustotě fX se také často říká Gaussova křívka. Abychom uměli pořádněji sformulovat asymptotickou blízkost normáního a bi- nomického rozdělení pro n , musíme si vytvořit další nástroje pro práci s náhodnými veličinami. Budeme k tomu používat funkce dvojím různým způsobem. 11.14 11.14. Funkce náhodných veličin. Místo náhodné veličiny X, např. ,,roční plat zaměstnance , budeme vyčíslovat jinou závislou hodnotu (X), např. ,,roční čistý příjem zaměstnance po zdanění a včetně sociálních dávek . V systému se značnou sociální solidaritou je první veličina hodně variabilní, zatímco druhá může být skoro konstantní. Statisticky se proto budou značně odlišovat. Nejjednodušší funkcí, po konstantách, je afinní závislost (x) = a + bx s konstatními a, b R, b = 0. Je-li fX(x) pravděpodobnostní funkce náhodné veličiny s diskrétním rozdělením, snadno se vypočte f(X)(y) = P((X) = y) = (xi)=y f(xi). V případě afinní závislosti x = 1 b (y - a) je proto pravděpodobnostní funkce nenu- lová právě v bodech yi = axi + b. V případě rozdělení Xn typu Bi(n, p) převádí transformace x = y np(1 - p) + np náhodnou veličinu Xn na rozdělení Yn s distribuční funkcí blízkou distribuční funkci spojitého rozdělení N(0, 1). Podobně zkusme opačnou transformaci provést na veličinu Y s normálním roz- dělením N(0, 1). Pro pevně zvolená čísla , R, > 0 spočtěme rozdělení ná- hodné veličiny Z = + Y . Dostáváme distribuční funkci FZ(z) = P(Z < z) = P( + Y < z) = FY ( z - ) = z- - 1 2 e-t2 /2 dt = z - 1 2 e- (x-)2 22 dx, kde poslední úprava vychází ze substituce x = + t. Hustota naší nové náhodné veličiny Z je proto fZ = 1 2 e- (x-)2 22 a takovému rozdělení se říká normální typu N(, ). 1. PRAVDĚPODOBNOST 345 11.15 11.15. Číselné charakteristiky náhodných veličin. Při statistickém zkoumání hodnot náhodných veličin (např. zpracování výsledků nějakého měření) hledáme výpovědi o náhodné veličině pomocí různých z ní odvozených čísel. Jako nejjednodušší příklad může sloužit střední hodnota EX náhodné veličiny X, která je definována EX = i xifX(xi) pro diskrétní veličinu - xfX(x)dx pro spojitou veličinu. Obecně střední hodnota náhodných veličin nemusí existovat, protože příslušné sumy či integrály nemusí konvergovat. Obvykle říkáme, že střední hodnota existuje, když nastává absolutní konvergence. Střední hodnotu můžeme přímo vyjádřit také pro funkce Y = (X) náhodné veličiny X. V diskrétním případě můžeme přímo spočíst EY = j yjP(Y = yj) = j yj (xi)=yj P(X = xj) = i (xi)P(X = xi). Je tedy E(X) přímo spočítatelná pomocí pravděpodobnostní funkce fX. Podobně vyjadřujeme střední hodnotu funkce ze spojité náhodné veličiny: E(X) = - (x)fX(x)dx pokud tento integrál absolutně konverguje. Dalšími užitečnými charakteristikami jsou tzv. kvantily. Pro ryze monotóní distribuční funkci FX (tj. spojitou náhodnou veličinu X s všude nenulovou hus- totou, jako je tomu např. u normálního rozdělení) jde prostě o inverzní funkci F-1 X : (0, 1) R. To znamená, že hodnota y = F-1 () je taková, že P(X < y) = . Obecněji, je-li FX(x) distribuční funkce náhodné veličiny X, pak definujeme kvantilovou funkci F-1 () = inf{x R; F(x) }, (0, 1). Zřejmě jde o zobecnění předchozí definice. Nejčastěji jsou používané kvantily s = 0.5, tzv. medián, s = 0.25, tzv. první kvartil, = 0.75, tzv. třetí kvartil, a podobně pro decily a percentily (kdy je rovno násobkům desetin a setin). K těmto hodnotám se vrátíme v popisné statistice později. 11.16 11.16. Střední hodnoty některých rozložení. Spočtěme si nejprve střední hodnotu náhodné veličiny X s rozdělením Bi(n, p). 11.17 11.17. Elementární vlastnosti střední hodnoty. 11.18 11.18. Náhodné vektory. 11.19 11.19. Rozptyl a směrodatná odchylka. 11.20 11.20. Momenty a momentová funkce rozdělení. 346 11. STATISTICKÉ METODY 11.21 11.21. Kovariance. 11.22 11.22. Přehled rozdělení odvozených od normálního. 11.23 11.23. Limitní vlastnosti. 11.24 11.24. Věta (Centrální limitní věta). 2. Popisná statistika 11.25 11.25. Soubor hodnot a jeho popis. 11.26 11.26. Číselné charakteristiky polohové. 11.27 11.27. Míry variability souboru. 11.28 11.28. Další výběrové koeficienty. 11.29 11.29. Diagramy. 3. Matematická statistika 11.30 11.30. Výběry z populace. 11.31 11.31. Poznámky o statistické indukci. 11.32 11.32. Poznámky o testování hypotéz. 11.33 11.33. Poznámky o lineárních modelech. 11.34 11.34. Závěrečné poznámky. Literatura [1] Marie Budíková, Štěpán Mikoláš, Pavel Osecký, Teorie pravděpodobnosti a matematická statistika (sbírka příkladů), Masarykova univerzita, 3. vydání, 2004, 117 stran, ISBN 80- 210-3313-4. [2] Marie Budíková, Štěpán Mikoláš, Pavel Osecký, Popisná statistika, Masarykova univerzita, 3. vydání, 2002, 48 stran, ISBN 80-210-1831-3. [3] Marie Budíková, Tomáš Lerch, Štěpán Mikoláš, Základní statistické metody, Masarykova univerzita, 2005, 170 stran, ISBN 80-210-3886-1. [4] Zuzana Došlá, Jaromír Kuben, Diferenciální počet funkcí jedné proměnné, MU Brno, 2003, 215 s., ISBN 80-210-3121-2. [5] Zuzana Došlá, Roman Plch, Petr Sojka, Diferenciální počet funkcí více proměnných s pro- gramem Maple, MU Brno, 1999, 273 s. [6] William J. Gilbert, W. Keith Nicholson, Modern algebra with applications, 2nd ed. John Wiley and Sons (Pure and applied mathematics) ISBN 0-471-41451-4 [7] Pavel Horák, Úvod do lineární algebry, MU Brno, skripta. [8] Ivana Horová, Jiří Zelinka, Numerické metody, MU Brno, 2. rozšířené vydání, 2004, 294 s., ISBN 80-210-3317-7. [9] Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. [10] Luboš Motl, Miloš Zahradník, Pěstujeme lineární algebru, 3. vydání, Uni- verzita Karlova v Praze, Karolinum, 348 stran (elektronické vydání také na http://www.kolej.mff.cuni.cz/~lmotm275/skripta/). [11] Riley, K.F., Hobson, M.P., Bence, S.J. Mathematical Methods for Physics and Engineering, second edition, Cambridge University Press, Cambridge 2004, ISBN 0 521 89067 5, xxiii + 1232 pp. [12] František Šik, Lineární algebra zaměřená na numerickou analýzu, MU, 1998, 176 s. ISBN 80-210-1996-2. [13] Jan Slovák, Lineární algebra. učební texty, Masarykova univerzita, elektronicky dostupné na www.math.muni.cz/~slovak [14] Pavol Zlatoš, Lineárna algebra a geometria, skripta MFF Univerzity komenského v Brati- slavě. [15] Karel Zvára, Josef Štěpán, Pravděpodobnost a matematická statistika, Matfyzpress, Uni- versita Karlova, 2006, 230 s. 347