Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Drsná matematika IV – 4. přednáška Uspořádané množiny a Booleovské algebry Jan Slovák Masarykova univerzita Fakulta informatiky 12. 3. 2012 Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Obsah přednášky 1 Literatura 2 Množinová algebra 3 Výroková logika 4 Přepínače a dělitelé 5 Posety a svazy 6 Normální tvar 7 Homomorfismy Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Kde je dobré číst? vlastní poznámky, texty současného přednášejícího, GOOGLE, atd. 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. W. J. Gilbert, W. K. Nicholson, Modern algebra with applications, 2nd ed. John Wiley and Sons (Pure and applied mathematics) ISBN 0-471-41451-4 Zvára, Štěpán: Pravděpodobnost a matematická statistika ISBN 80-86732-71-7, 4.. vydn, 232 str., Matfyzpres, Praha. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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 komplementu. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Definition 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ě průnik, anglicky často také meet), operaci ∨ budeme říkat supremum (případně sjednocení, 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Stejně jako u speciálního případu Booleovské algebry všech podmnož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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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. Theorem 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Naši symboliku interpretujeme 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Nyní 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 bereme 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, A ∨ B a A , tj. A ∧ B je pravdivé pouze, když jsou oba výroky A a B pravdivé, A ∨ B je nepravdivé pouze. když jsou oba výroky nepravdivé a A má opačnou hodnotu než A. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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í). 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í operace A zadává přepínač, který je vždy v opačné poloze než A. B A B A Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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 Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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á). Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Vzpomeňme na definici uspořádání jakožto reflexivní, antisymetrické a tranzitivní relace ≤ na množině K. Taková 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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. 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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 ∨. 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Obdobně definujeme horní závory a supremum podmnožiny L záměnou ≤ za ≥ v posledním odstavci. Konečné posety se přehledně zobrazují pomocí orientovaných grafů. Prvky K jsou představová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ě). Definition Svaz je poset (K, ≤), ve kterém každá dvouprvková množina {A, B} má supremum A ∨ B a infimum A ∧ B v K. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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ě, 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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 hodnotový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 obecné Booleovy algebry sestrojíme jeho tzv. normální disjunktivní tvar, tj. napíšeme jej pomocí vybrané skupiny nejjednodušších prvků a operace ∨. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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 Aσ1 1 ∧ · · · ∧ Aσn n , kde buď Aσ i = Ai nebo Aσi i = Ai . Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy Theorem Každý prvek B v konečné Booleově algebře (K, ∧, ∨, ) lze zapsat jako supremum atomů B = A1 ∨ · · · ∨ Ak. Tato formule je navíc jednoznačná až na pořadí atomů. Pro důkaz budeme potřebovat tři jednoduchá tvrzení: Theorem 1 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, . . . , . 2 Pro každý prvek Y = 0 v K existuje atom X, pro který je X ≤ Y . 3 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. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar 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ů: Definition Zobrazení f : (K, ∧, ∨, ) → (L, ∧, ∨, ) se nazývá homomorfismus Booleovský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í. Literatura Množinová algebra Výroková logika Přepínače a dělitelé Posety a svazy Normální tvar Homomorfismy 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ý homomorfismus 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)! Theorem Každá konečná Booleova algebra je izomorfní Booleově algebře K = 2M, kde M je množina atomů v K.