DRUHÁ ČÁST BOOLEOVY ALGEBRY 8 BOOLEOVY ALGEBRY V této kapitole zavedeme pojem Booleovy algebry a ukážeme několik důležitých příkladů těchto algeber. Potom uvedeme některé jejich základní vlastnosti a ukážeme, že existují jak úplné, tak i neúplné Booleovy algebry. V závěru kapitoly budeme pomocí základních booleovských operací n, u a ' definovat několik dalších operací. 8.1 Definice Booleových algeber Definice 8.1. Svaz S se nazývá Booleova algebra, právě když má nulu a jednotku, je komplementární a distributivní. Protože Booleova algebra je komplementární a distributivní svaz, můžeme důsledek věty 7.3 vyslovit takto: Věta 8.1. Necht B je Booleova algebra, pak ke každému prvku x e B existuje právě jeden jeho komplement x' e B. Na základě věty 8.1 lze říci, že v Booleových algebrách představuje tvoření komplementu unární operaci. Proto se na tyto algebry můžeme dívat jako na algebraické struktury mající dvě binární operace n a i_i a jednu unární operaci zvanou komplement a značenou '. Protože však Booleovy algebry obsahují také nulu a jednotku, můžeme tyto prvky považovat za vymezení dvou nulárních operací, které značíme 0 a 1. Booleovy algebry je proto možné značit (B, n, ') či dokonce (B, n, u, ', 0, 1). Operace n, u a ' se nazývají základní booleovské operace. Protože nemůže dojít k nedorozumění, budeme často místo Booleova algebra říkat pouze algebra. Podle definice 8.1 je tedy Booleova algebra (5, n, u, ',0, 1) algebraická struktura se dvěma binárními operacemi n a jednou unární operací ' a dvěma nulárními operacemi 0, 1 splňujícími následující požadavky. Nechť x, v, z jsou libovolné prvky z B, pak: x n y = y n x komutativnost (8.1) x lj v = y u .v (8. ľ) 149 (x n y) n Z = X n {y n z) asociativnost (8.2) (jc u y) u z = * i_i (y u z) (8.2'! .V n jc = X idempotence (8.3 j .r u a' = .v (8.3') x n (x u y) = x absorpce (8.4 ) X i_i (x r. = X (8.4' X n (y u z) = (x n ý) i_i (x n z) distributivnost (8.5) X i_i (y ri z) = {x i_i y) n (x i_i z) 18.5 X|-iO = OaJljO=X nula ÍS.6 In 1 =IAIu 1 = 1 jednotka IS.6 Xrnx' = 0 a X lj X = 1 komplementy (8.7) Předchozí systém požadavku isme uvedli tak. aby b>! ..snadný na zapamatování1*, a také. aby se s ním v další části dobře pracovalo. Z předchozí teorie svazů víme. že by bylo možné tento systém podstatně zestručnit. Napr. se ukázalo, že oba požadavky idempotence jsou nadbytečné (viz cv. 4.1). Take lze vypustit jednu z formulí (8.5) a (8.5') (viz věta 6.2) a vždy po jednom členu v konjunkci (8.6) a (8.6') (viz lemma 3.2 a 3.2'). Poznámka. Vyslovením formulí (8.1) až (8.7) jsme získali velmi důležitý úplný systém axiómů. Úplností systému axiómů rozumíme to. že pokud bychom přidali další axióm tvaru identity, který' není logickým důsledkem uvedených axiómů, dostaneme sporný nebo jinak řečeno nerealizovatelný systém. To znamená, že už neexistuje žádný netriviální svaz, který by splňoval všechny tyto axiómy. Obecně platí: Jestliže přidáme další logicky nezávislé požadavky na objekty nějaké základní množiny, pak se množina objektů splňujících tyto požadavky stále zužuje. Proto bychom měli vždy po přidání nového požadavku ověřit, zda ještě existuje nějaký objekt, který nově vytvořený systém požadavků splňuje. Následující příklady ukáží (a víme to již z teorie svazů I. že v případě Booleových algeber je odpověď kladná. Příklad 8.1. Uvažujme svaz (P{M), n, u), kde P{M) je potence libovolné množiny M. Z příkladu 2.7 víme, že se skutečně jedná o svaz. Tento svaz je distributivní (viz př. 6.1) a také komplementární (viz př. 7.2). Nulou a jednotkou tohoto svazu jsou po řadě množiny 0 a M. Komplementem libovolné množiny A e P(M) je množina A' - M — A Proto je tento svaz Booleova algebra. Pro M = {a, b, c} je Hasseův diagram Booleovy algebry P(M) znázorněn na obr. 5c. V kapitole 10 ukážeme, že tento druh algeber je mimořádně důležitý, protože se pomocí něho dá reprezentovat libovolná konečná Booleova algebra. Uvedený příklad lze zobecnit. Lemma 8.1. Každé těleso množin je Booleova algebra. Příklad 8.2. Nejjednodušší Booleova algebra je algebra mající pouze jeden prvek — označme ho 0. Tento prvek je samozřejmě nula i jednotka. Takovéto algebře říkáme triviální Booleova algebra a mohli bychom ji značit ({O}, n, li, ', 0, 0). Pro její operace zřejmě platí: 0ri0 = 0u0 = 0' = 0 150 Příklad 8.3. Nejjednodušší netriviální Booleova algebra má dva prvky, z nichž jeden musí být nula a druhý jednotka. Můžeme ji proto značit ({0, l}, n, u,', 0, l) nebo stručně 2. Tabulky pro její operace jsou: n 0 1 0 1 0 0 0 1 LJ 0 1 0 1 0 1 1 1 0 1 1 0 (8.8) Často se místo těchto Cayleyho tabulek používají k zadávám tzv. Schróderovy tabulky známé z matematické logiky: X y x n y x i_i y x' 0 0 0 0 1 0 i t) 1 1 1 0 0 1 0 1 1 1 1 0 (8.9) Dvouprvkové Booleovy algebry jsou velmi jednoduché a přitom zajímavé a důležité z hlediska svých aplikací. Právě vzhledem k těmto aplikacím pojednáme podrobně v kap. 11 o Booleových funkcích definovaných na těchto algebrách. Příklad 8.4. Uvažujme množinu B všech dělitelů číslo 30 v množině N. Jestliže v množině B = {l, 2, 3, 5, 6, 10, 15, 30} zavedeme operace takto (viz př. 2.5b): x n y =df D{x, y) , x u v =df n (x, y) , _ 30 x -Af , pak B tvoří Booleovu algebru, v níž nulou je číslo 1 a jednotkou je číslo 30. Hasseův diagram této algebry je na obr. 18b. Právě uvedený příklad lze zobecnit. Pro výchozí číslo 30 platilo: 30 = 2 . 3 . 5. Booleovu algebru totiž obdržíme, právě když úplný rozklad (tj. rozklad v součin prvočísel) výchozího čísla n obsahuje každé prvočíslo nejvýše jednou. Booleovy algebry tak dostaneme např. u těchto výchozích čísel: 2, 3, 7 (dvouprvkové algebry), 10 = 2 . 5, 21 = 3 . 7 (čtyřprvkové algebry), 30 = 2 . 3 . 5, 42 = 2 . 3 . 7 (osmiprvkové algebry), 210 = 2.3.5.7 (šestnáctiprvková algebra). Operace komplement je v těchto algebrách pro výchozí číslo n definovaná formulí x' = - . 151 Svazy, které nejsou Booleovými algebrami, obdržíme např. pro čísla 12 = 22. 3 (viz obr. 53a) nebo 36 = 22 . 32 (viz obr. 53b). Tyto svazy jsou sice distributivní, mají nulu a jednotku (jako každý konečný svaz), nejsou však komplementární. Obr. 53 Příklad 8.5. Nechť dvojice (M, je řetězec, kde M ^ 0. pak uvažujme v množině M všechny následující druhy intervalu: polouzavřené intervaly [a. b). koncové intervaly příslušné k prvku a[a,->). otevřené počáteční intervaly příslušné k prvku a (*-, a) a ještě celou množinu M. Nechť 5 je množina všech konečných sjednocení výše uvedených množin, pak (B, n, u,') je Booleova algebra. .Algebra B se nazývá intervalová algebra řetězce M. Pokud např. vyjdeme z řetězce racionálních čísel (Q, á), pak obdržíme nekonečnou (ale spočetnou) intervalovou Booleovu algebru. Příklad 8.6. V příkladu 2.13 jsme definovali pojem obojetná množina topologického prostoru M. Tam jsme také uvedli, že množina 5* všech obojetných množin topologického prostoru M tvoří svaz. Nyní můžeme dodat, že čtveřice [S*, n, u, ') je dokonce Booleova algebra, v níž je množina 0 nula a množina M jednotka. Tato Booleova algebra se nazývá algebra obojetných množin topologického prostoru M. Tři konečné případy těchto algeber jsou znázorněny na obr. 20c. Topologický prostor M se nazývá souvislý, právě když má právě dvě obojetné množiny, tj. množinu 0 a množinu M. Algebra obojetných množin je v tomto případě dvouprvková (viz př. 8.3). Příkladem souvislého topologického prostoru je euklidovský prostor E„ dimenze n (se standardní topologií). Z nesouvislých topologických prostorů uveďme ty, jejichž libovolné dva různé body lze oddělit obojetnou množinou. Topologické prostory s touto vlastností se nazývají totálně nesouvislé. Jednoduchým příkladem totálně nesouvislého prostoru M je diskrétní topologický prostor, tj. prostor, jehož množina S otevřených množin je rovna P(M). Jiným příkladem totálně nesouvislého topologického prostoru je tzv. Cantorovo diskontinuum, které popíšeme následovně. Vyjdeme z intervalu (0, l) v řetězci (R, g), z něhož vynecháme nekonečný spočetný systém otevřených intervalů pomocí této konstrukce: V prvním kroku vynecháme in:; intervalů < 0 1 2 čtyř intervalů jí 8.2 Zakl ProhJť algebry, pak z;: ? gické vlastnosti, i v Booleových Každý pravd, pouze specifick 0, 1 nahradíme Poznamenej pomocí spojky a kterou budem Nyní se buje algebry a které věta 8.1. V první zákony lze zobe algebry B. Na zál bez dvojznačnost nebo rt-. kde A je konečná tivní zákon\ mi kvantifikátoru;: Xn|j Ut-.j 152 , . /l 2\ vynecháme interval I —, — 1. V druhém kroku vynecháme z každého ze zbylých intervalů ^0, i\ a ^ , 1^ jeho „střední třetinu", tj. vynecháme intervaly jt> -^j > ■ Ve třetím kroku vynecháme zase z každého ze zbývajících čtyř intervalů jeho „střední třetinu" atd. 8.2 Základní vlastnosti Booleových algeber Prohlédneme-li si seznam základních axiómů kladených na Booleovy algebry, pak zjistíme, že od každé z operací průsek a spojení požadujeme analogické vlastnosti. Proto platí následující metavěta představující princip duality i v Booleových algebrách: Každý pravdivý výrok o Booleových algebrách, v jehož formulaci se vyskytují pouze specifické symboly n, u,', 0 a 1, zůstane pravdivý, pokud symboly n, u, 0, 1 nahradíme po řadě symboly u, n, 1, 0. Poznamenejme, že v dalším textu někdy spojíme navzájem duální formule pomocí spojky a do jedné formule. Obdržíme tak formuli, která je autoduální a kterou budeme značit bez čárky. Nyní se budeme zabývat některými důležitými vlastnostmi, které mají Booleovy algebry a které nejsou vysloveny v definici 8.1. Jednu takovou vlastnost už udávala věta 8.1. V první řadě však zopakujme, že jak asociativní zákony, tak i distributivní zákony lze zobecnit pro libovolný konečný počet prvků uvažované Booleovy algebry B. Na základě zobecněného asociativního zákona pro n i pro i_i můžeme bez dvojznačnosti zapisovat symboly rt-ixi a \J=lx,, nebo [V a UA> kde A je konečná podmnožina uvažované Booleovy algebry. Zobecněné distributivní zákony můžeme vyjádřit následujícími formulemi (bez uvedení obecných kvantifikátorů): Xr,\J.íXi~\J_1{xnX^ (8.10) Xunř-i*-n"-i(JtLJ*<) (8-10') L]?_ i X, rn U'l = [Jluh-x m (*i ^ V,) (8.11 ) 153 Formuli (8.11), popř. (8.1 ľ) lze ještě zobecnit pro libovolný počet spojení, popř. průseků. Věta 8.2. Nechť B je Booleova algebra, pak platí: (Vx e B) (x')'= x (8.12) Důkaz. Nechť x je libovolný prvek Booleovy algebry B a x' je jeho komplement. Pro tyto prvky proto platí formule (8.7). Protože operace nau jsou komutativní, je také prvek x komplementem prvku x', což právě udává formule (8.12). Věta 8.3 a 8.3'. Nechť B je Booleova algebra, pak platí de M organová pravidla: (Vx,yeB)(xny)' = x!i->y (8.13) {Vx,yeB)(xu y)' = jťn/ (8.13') Důkaz. Věty 8.3 a 8.3' jsou důsledkem vět 7.5 a 7.5'. Protože Booleova algebra je distributivní svaz a ke každému prvku existuje komplement, platí formule (7.4) pro libovolnou dvojici prvků x, y, což právě udávají de Morganova pravidla. Poznámka. Platnost formulí (8.13) a (8.13') můžeme dokázat také tak, že „spočítáme" levé strany následujících rovností a obdržíme tak jejich pravé strany. Tím však pouze zopakujeme důkaz věty 7.4: Nechť x, y jsou libovolné prvky z B, pak: (x n >') n (x' u y) = 0 (x u )') n (x' n /) = 0 (x n y) lj (.v' u y') = 1 (x u y) i_i (x n /) = 1 De Morganova pravidla lze zobecnit pro libovolný konečný počet prvků Booleovy algebry B, což lze zapsat takto (bez uvedení obecných kvantifikátorů): qt-■4 = u?-> < u?-14=n;=. a (8.14) Dále lze na základě formulí (8.12), (8.13) a (8.13') dokázat: (Vjc, y e B) x n y = (x' u y')' (8.15) (Vx, y e fi) x lj y = (*'n y')' (8.15') Tyto formule ukazují, že každou z operací n a u lze zavést pomocí komplementu a druhé z nich. Důsledkem vět 8.2, 8.3 a 8.3' je následující pravidlo pro určení komplementu k libovolnému termu. Pravidlo. Nechť t je libovolný term (jazyka Booleovy algebry B). Tento term nejprve pomocí de Morganových pravidel upravíme tak, aby neobsahoval „očár-kované závorky". Potom stačí vzájemně zaměnit symboly n a u a k neočárkova-ným proměnným připojit čárky a od očárkovaných proměnných je odebrat. Tím obdržíme term t'. 154 -ľ -eni. popr. (8.12) efao komplement. pou komutativní, *(8.12). rganora pravidla: t (8-13) 18.13') Booleova algebra latí formule (7.4) ova pravidla. - . . - . les é strany ■jeme důkaz věty 7.4: Ený počet prvků kvantifikátorů): (8.14) 18.15) 18.15') od komplementu komplementu j B\. Tento term obsahoval „očár-i a k neočárkova-Je odebrat. Tím Příklad. Určeme komplement k termu x u (x' u y i_i zf u z. Nejprve pomocí de Morganova pravidla (8.14) dostaneme x u (x n / n z') u z. Předepsanou záměnou symbolů obdržíme term x' n (x' u y i_i z) n z', který je komplementem původně zadaného termu. Důkaz pravidla. Indukcí podle počtu n písmen obsažených v daném termu r. a) n = 1. V tomto případě r = x nebo t = x. Pak ale r' = x nebo r' = (x')' = x. b) Nechť n > 1. Protože je odstraněno „očárkování závorek", můžeme term r zapsat takto: r = tí n r2 nebo r = r, u r2. Pro komplement ť pak platí ť = r j u r2 nebo r' = r, n tí . Termy t, a t2 však už mají nejvýše n písmen, a proto pro ně platí indukční předpoklad. Tím je pravidlo dokázáno. Věta 8.4 a 8.4'. Nechť B je Booleova algebra, pak platí: (Vx, y e B) x n y = x n (x' u y) (8.16) (Vx, y e 5) jc u y = x i_i (x? n y) (8.16') Důkaz. Dokážeme pouze formuli (8.16). Nechť x, y jsou libovolné prvky z B, pak: x n (x u y) = (x n x') u (x n y) = Podle (8.5). = Ou(xrny) = xr1y Podle (8.7), (8.ľ) a (8.6). j Věta 8.5 a 8.5'. Nechf B je Booleova algebra, pak platí (Vx, y € B) x = y (x u y') n (x' u y) = 1 (Vx, y e B) x = y (x n y') u (x' n y) = 0 (8.17) (8.17') Důkaz. Dokážeme pouze formuli (8.17). Nechť x, y jsou libovolné prvky z B, pro něž platí: I. l.x = y 2. y = x' 3. x u y ■ x' u y = 1 (x lj y') n (x' u y) = 1 H. l.(lu/)n(x'uy)= 1 2. x u y = 1 3. (x u y) n y = 1 n y = y 4. (x u y) n y = x n y 5. X n y = y 6. X n y = X x = y Předpoklad ' je operace na ř. 1. lj je operace na ř. 1, 2; podle (8.1') a (8.7). Podle (8.3) na ř. 3. Předpoklad Podle cv. 3.3. n je operace na ř. 2, podle (8.1) a (8.6'). Podle (8.16), (8.1) a (8.1'). Z ř. 3 a 4. Obdobně jako ř. 5. Z ř. 5 a 6. 155 Nyní se budeme zabývat uspořádáním v Booleových algebrách. Zjistili jsme, že ve svazech je možné zavést uspořádání :s pomocí některé z následujících formulí (x, y jsou libovolné prvky z B): x _v x n y = x nebo x á y ** x lj y = y (8.18) Tuto možnost máme samozřejmě i v Booleových algebrách. V Booleových algebrách jako speciálních svazech však máme ještě další možnosti, jak ukáže následující věta. Věta 8.6. Nechť B je Booleova algebra, pak následující formule jsou ekvivalentní (pro libovolné x, y e B): xny = x (8.19) x u y = y (8.20) xÄy' = 0 (8.21) x' u y = 1 (8.22) Důkaz. Ekvivalenci formulí (8.19) a (8.20) jsme dokázali ve větách 2.6 a 2.6'. Nyní dokážeme, že a) z formule (8.20) vyplývá formule (8.22), b) z formule (8.22) vyplývá formule (8.21), c) z formule (8.21) vyplývá formule (8.19). Tím se impli-kační cyklus uzavře. a) x' u y = x' u (x u y) = Podle (8.20). - (x* u x) ú y - 1 u y - Podle (8.2') a (8.7). = 1 Podle (8. ľ) a (8.6'). b) x n ý - (x n y')" = Podle (8.12). - (x' u y)' = ľ - Podle (8.13), (8.12) a (8.22). = 0 Podle věty 7.1. c) x n y = (x n y) u 0 = Podle (8.6). - (x n y) lj (x n y) = Podle (8.21). = x n (y lj y') = x n 1 - Podle (8.5) a (8.7). = x Podle (8.6'). Důsledek věty 8.6. Nechť B je Booleova algebra, pak platí: (Vx, veB)ixny' = 0 (8.24) Uvažujme těleso množin P(M) (viz př. 8.1) a znázorněme např. formuli (8.24) pomocí Vennových diagramů. Situace pak bude velmi názorná. Nechť A, B jsou libovolné podmnožiny množiny M. Na obr. 54 a je vyznačena levá strana ekvivalence (8.24), na obr. 54b její pravá strana. Šrafovaním označujeme množiny, jejichž průnik máme sestrojit. Je zřejmé, že jejich průnikem je množina prázdná, tj. nula v P(M). 156 Obr. 54 Věta 8.7. Nechť B je Booleova algebra, pak platí: (Vx, y e B) x :s y <=> y ^ x (8.25) Důkaz. Nechť x,y jsou libovolné prvky Booleovy algebry B, pro něž platí: Důkaz obrácené implikace je analogický a přenecháme ho proto čtenáři. Je vidět, že zobrazení F: x e B ** x e B je prosté zobrazení algebry B na sebe, které obrací uspořádání (je antitonní). Dále na základě de Morganových pravidel (8.13) a (8.13') víme, že vzájemně zaměňuje operace n a u. Z definice komplementu 7.1 vyplývá, že v libovolné Booleově algebře B jsou každé dva komplementární prvky navzájem disjunktní. Navíc platí, že k libovolnému prvku a e B je jeho komplement a' největší z prvků, které jsou disjunktní s a (viz poznámka na str. 140). Všechny ostatní prvky disjunktní s prvkem a proto předcházejí před prvkem a' a dokonce vyplní celý interval [0, a']. To je také obsahem následující věty. Věta 8.8. Nechť B je Booleova algebra, pak (Vfl e B) (Vx e B) a n x = 0 o x sa a'. Větou 8.8 jsme prozatím zakončili výčet důležitých vlastností Booleových algeber. V následujícím příkladě si procvičíme některé z těchto vlastností pomocí řešení booleovské rovnice. Příklad 8.7. V Booleově algebře B řešte následující rovnici, v níž je x neznámá: Zdůvodňování jednotlivých kroků řešení přenecháme čtenáři. Pouze poznamenejme, že vedle vět vyslovených v této kapitole použijeme např. i formuli ze cv. 3.3. 1. x s y 2. y = x u y 3. ý = (x u y)' = x' n y Předpoklad Podle (8.18). Podle V 8.1 a (8.13'). Podle (8.18). a r-\ x = b 157 [(a n x) i-i b'] u [(a n x)' n b] = O [(a m 6') nl]u [(fl' lj x') n b = O [(a n b') n x] u (ď n b) u (fe n x') = O (an/?')nX = OAfl'nÍ> = OAÍ)nx' = 0 X S (a n Ŕ')' AŔ^tíAŽl^X Protože formule b ^ a' u b platí pro libovolné a, b e B, představuje jedinou podmínku řešitelnosti zadané rovnice formule b s a. V tom případě je množinou všech řešení interval [b, a' u b]. Pokud l(b s a) (tzn. a < 6 v a H pak množinou řešení je množina 0. V kapitole 3 jsme zavedli pojem úplný svaz. Tím máme zaveden i pojem úplné Eíf)oleovy algebry. Přesto vyslovme definici. i Definice 8.2. Booleova algebra B se nazývá úplná, právě když pro libovolnou množinu A c B existuje \~\A i \_\A. Algebra B je tedy úplná, právě když je možné vedle operací n a u definovat i jejich zobecnění, tj. operace f~] a U ■ Definičním oborem zobecněného průseku a zobecněného spojení je množina P{B). V následujícím příkladě ukážeme, že existují úplné i neúplné Booleovy algebry. Příklad 8.8. Každá konečná Booleova algebra je úplná. Také libovolná algebra P(M) (viz př. 8.1) je úplná. Její úplností jsme se zabývali v příkladu 3.1. Uvažujme následující těleso množin: Množina B obsahuje všechny konečné podmnožiny množiny N a dále všechny jejich (nekonečné) komplementy v N. Množina B tvoří Booleovu algebru (viz lemma 8.1), která však není úplná, protože např. neexistuje spojem prvků množiny A, kde A = {{3}, {3,6}, {3,6, 9},...}. Příklad 8.9. Nechť M je topologický prostor a nechť množina X q M, pak uzávěrem množiny X, který značíme cl (X), je nejmenší uzavřená nadmnožina množiny X a vnitřkem množiny X, který značíme int (X), je největší otevřená podmnožina množiny X. Pro libovolnou množinu X s M položme r (X) = int cl (z). Množina r (X) se nazývá regularizace množiny X. Říkáme, že X je regulární otevřená množina, právě když r (X) = X. Uvažujme neprázdný topologický prostor M. Nechť R značí množinu všech regulárních otevřených množin, pak R je Booleova algebra vzhledem k operacím (X, Y jsou libovolné množiny z R): X lj Y = r {X u Y) A' = int (M - A) Inľ=ínľ Nula a jedr. její zobecně n Uvedeny dr tovat libo\ o Poznámka. uvedené kons dolních množir z D(P) je opět topologie otevr< Sestrou'me-1: množin, pak ne Z předchozí] V posledn pomocí záklai Pomocí násle x - x x x x x Operace x - y čteme „relativní ps Poznámka. pojmu těleso mr množin se však jestliže chceme protože je boolt v tomto připadl Operaci ; x©y čteme symetrické formule: (V 158 edstavuje jedinou pod-; - : __ř je množinou v a x b), pak množi- zaveden i pojem úplné když pro libovolnou perací n a i_i definovat zobecněného průseku příkladě ukážeme, že Také libovolná algebra : :'■.....iu 3.1. ; --;hny konečné komplementy která však není úplná, fel {3,6}, {3,6,9},...}. množina X s M, pak ■zavřená nadmnožina \ je největší otevřená n X q M položme nožiny A'. Říkáme, že značí množinu všech vzhledem k operacím -mx(M-Á) Nula a jednotka této algebry jsou množiny 0 a M. Algebra R je navíc úplná a pro její zobecněné operace platí (S je libovolná podmnožina R): Uvedený druh algeber je důležitý především proto, že pomocí něho lze reprezentovat libovolnou úplnou algebru. Poznámka. Ukažme, že každý poset jednoznačně určuje nějakou úplnou Booleovu algebru. Tdea uvedené konstrukce je následující: Nechť (P, je neprázdný poset. Sestrojíme množinu D(P) všech dolních množin tohoto posetu. Platí, že sjednocení i průnik libovolného systému dolních podmnožin z D(P) je opět domí podmnožina z D(P). Proto můžeme říci, že systém všech dolních podmnožin je topologie otevřených množin na množině P. Nazývá se topologie dolních podmnožin. Sestrojíme-li množinu B všech regulárních otevřených množin prostoru P s topologií dolních množin, pak množina B tvoří úplnou Booleovu algebru. O této algebře říkáme, že je určena posetém (P, Z předchozího vyplývá, že také k libovolné Booleově algebře lze sestrojit úplnou Booleovu algebru. V poslední části této kapitoly ukážeme, že v Booleových algebrách můžeme pomocí základních booleovských operací n, u a' definovat další binární operace. Pomocí následujících formulí zavedeme tři dvojice navzájem duálních operací: x - y =df x n y x*y =df x" i-i y x® y =df {x n y) u (x? n y) = (x - y) i_i (y - x) x y =df (x" u y) n (x u y') = (x * y) n (y * x) x t y =df (x n y)' = x uý x 1 y =df {x u y)' = xf n y (8.26) (8.26') (8.27) (8.27') (8.28) (8.28') Operace - a * jsou navzájem duální. Operaci — nazýváme diference a term x — y čteme ,jc minusy". Operaci *, o níž jsme hovořili v článku 7.2, jsme nazývali „relativní pseudokomplement". Poznámka. Pokud bychom vyšetřovali Booleovy algebry z hlediska teorie množin (jako zobecnění pojmu těleso množin), pak je booleovské odčítám zobecněním odčítání množin (viz obr. 55a). V teorii množin se však nevyšetřuje operace, která by byla analogií booleovské operace *. Naproti tomu, jestliže chceme aplikovat Booleovu algebru na matematickou logiku, pak je operace * velmi důležitá, protože je booleovskou analogií logické operace zvané implikace. Booleovská operace zvaná diference v tomto případě nemá použití. Operaci © nazýváme symetrická diference nebo též disjunktní sčítání. Term x®y čteme „x minus symetricky y". Tato operace je opět booleovskou analogií symetrické diference z teorie množin (viz obr. 55b). Pro operaci © např. platí tato formule: (Vx, yeB)x®y = (x u y) n {x n y)' (8.29) 159 Duální operace k operaci © je operace <=>, která se nazývá ekvivalence a je skutečně booleovskou analogií logické operace zvané ekvivalence. Term „ x o y" se čte „x je ekvivalentní s y". K poslední dvojici navzájem duálních operací uvedeme prozatím toto: Jedná se o univerzální operace mající tu vlastnost, že pomocí každé z nich lze definovat všech 16 možných binárních operací a všechny 4 možné unární operace v algebře 2 (viz př. 8.3). Operace f se nazývá Shefferova a operace j se nazývá Pierceova. Z výše uvedeného důvodu mají tyto operace mimořádnou důležitost při matematickém zpracovávání konstrukce logických obvodů (viz kapitola 12). CVIČENÍ 8 1 Sestrojte Hasseovy diagramy Booleových algeber P(M) (viz př. 8.1) pro M = 0, {a}, {a, b], {a, b, c}, {a, b, c, d). 2 Sestrojte Hasseovy diagramy Booleových algeber všech dělitelů čísla n (viz př. 8.4) pro h = 1, 7, 2 . 5, 2 . 3 . 5, 2 . 3 . 5 . 7. Porovnejte tyto diagramy s diagramy ve cvičení 1. 3 Znázorněte věty 8.4, 8.5, 8.6 a 8.7 pomocí Vennových diagramů (v algebře 4 Nechť M je topologický prostor, pak množina všech obojetných množin tohoto prostoru (tj. množina všech otevřených a současně uzavřených množin — viz př. 2.13) tvoří Booleovu algebru. Nulou této algebry je množina 0 a jednotkou je celý prostor M. Dokažte. 5 Nechť Z je množina všech celých čísel a nechť m e Z. Množina X s Z se nazývá periodická s periodou m, právě když je rovna množině, kterou obdržíme tak, že ke každému jejímu prvku přičteme m. Množina všech periodických podmnožin množiny Z majících danou periodu m je Booleova algebra. Dokažte. 6 V Booleově algebře B řešte následující rovnice, kde x je neznámá: a) (a n x) u (b n x) ui c = 0 b) a' n x = b c) (a u b) n x = b' u c P(M)). 160 7 Dokažte, že v libovolné Booleově algebře platí formule (8.29). 8 Dokažte, že v libovolné Booleově algebře B platí (x, v jsou libovolné prvky z B): a) x -* y — / * x' b) (x * y)' = x n y' c) (x * y) * x = x d) x' = (x * 0) 9 Dokažte, že operace © v libovolné Booleově algebře B je asociativní. 10 Dokažte, že Shefferova ani Pierceova operace (viz formule (8.28) a (8.28')) nejsou asociativní. 161 DALŠÍ VLASTNOSTI BOOLEOVÝCH ALGEBER V této kapitole zavedeme nejprve binární relaci „být Booleovou podal-gebrou" v třídě všech Booleových algeber a budeme studovat nejdůležitější vlastnosti této relace. Ukážeme např., že unární relace „být Booleovou podalgebrou dané algebry B" je uzáverová vlastnost v množině B. V dalším článku se budeme zabývat binární operací „direktní součin", která přiřazuje Booleovým algebrám „složitější" Booleovy algebry. V poslední části kapitoly ukážeme, že teorie Booleových algeber je ekvivalentní s teorií určitých speciálních okruhů, kterým se říká Booleovy okruhy. 9.1 Booleovy podalgebry Jak víme z předchozí kapitoly, je Booleova algebra B struktura se dvěma binárními operacemi n a u, jednou unární operací' a dvěma nulárními operacemi 0, 1 a můžeme ji značit B = (B, n, u,', 0, 1) nebo stručněji B = (/?, n, u,'). Dále víme, že podsvazem Booleovy algebry 5 je každý svaz A = (A, n, □), kde A e B a současně operace n a u jsou zúžením operací n a u na množinu A. Definujme nyní relaci „být Booleovou podalgebrou". Definice 9.1. Svaz s unární operací {A, n, □, ~) se nazýva Booleova podalgebra Booleovy algebry (B, n, u,'), právě když A c B a operace n, n, ~ jsou zúžením operací n, u,' na množinu A. Definice 9.1 se někdy vyslovuje také takto: Množina A tvoří Booleovu podalgebra Booleovy algebry (B, n, u,'), právě když A e B a množina A je uzavřená vzhledem k operacím n, u a '. V dalším textu budeme operace v Booleově algebře i v její podalgebře značit stejně. Navíc jsme právě užili další úmluvu: místo „Booleova podalgebra" budeme často říkat pouze „podalgebra". O extrémních případech podalgeber Booleovy algebry B lze říci následující. Lemma 9.1. Podalgebrou každé alespoň dvouprvkové Booleovy algebry B je jednak sama algebra B a dále dvouprvková algebra 2 = [0. l}. kde 0. 1 e B. Definic a trhialni Jestliže A vzhlede všechny vi Proto múz Lemrrjj f O li. Booleov prvky 0, 1 však 7..-.Ĺ- Nechf x Lemnij a jednotku Ukazuje dávky. -;- Lemma uzavřená v. n a li, pak Příklad (viz př. 8.1) P\M) (viz obr. 56b) si nem uzavřt neobsahuje 162 BER i Jbýt Booleovou podal-vtat nedůležitější vlast-looleovou podalgebrou Idaftam článku se bude-Knje Booleovým algeb-tahr ukážeme, že teorie okruhů, kterým se B struktura se dvěma - - - . rr.imi operacemi p B = {B. n, u, ')• Dále = U. n, c I. kde A s 5 množinu /I. Definujme Bi >leo> a podalgebra _: =. z. _ /som zúžením v Definice 9.2. Podalgebry B a 1 z lemmatu 9.1 se nazývají po řadě nevlastní a triviální podalgebra algebry i?. Jestliže je A podalgebrou Booleovy algebry B, pak z uzavřenosti množiny A vzhledem k operacím n, i_i a ' vyplývá, že si tyto operace v A ponechávají všechny vlastnosti, které jsme požadovali v definici Booleovy algebry (viz def. 8.1). Proto můžeme vyslovit: Lemma 9.2. Booleova podalgebra A Booleovy algebry B je Booleovou algebrou. Booleova algebra B obsahuje nulární operace 0, 1, a proto se zdá, že jsme i pro prvky 0, 1 e B měli požadovat, aby patřili do podalgebry A. Tento požadavek je však nadbytečný, neboť lze již snadno dokázat: Nechť x je libovolný prvek z A, pak v A existuje i prvek x a také prvky x n x' a x u x', což jsou právě prvky 0. 1. Proto můžeme vyslovit: Lemma 9.3. Booleova podalgebra A Booleovy algebry B obsahuje stejnou nulu a jednotku, jako má Booleova algebra B. Ukazuje se, že jsme v definici Booleovy podalgebry mohli vyslovit slabší požadavky, neboť na základě formulí (8.15) a (8.15') můžeme říci. Lemma 9.4. Jestliže neprázdná podmnožina A Booleovy algebry (B, n,') je uzavřená vzhledem k unární operaci' a dále vzhledem k jedné z binárních operací n a u, pak je uzavřená i vzhledem k druhé binární operaci. Příklad 9.1. Nechť M = {a, b, c}, pak těleso množin P(M) je Booleova algebra (viz př. 8.1). Množina A = {0, {a}, {b, c},{a, b, c}} tvoří Booleovu podalgebru algebry P(M) (viz obr. 56a). Naproti tomu množina C = {{c}, {a, c), {b, c}, {a, b, c}} (viz obr. 56b) sice tvoří podsvaz algebry B, netvoří však podalgebru algebry B, neboť není uzavřená vzhledem k operaci '. Množina C např. obsahuje množinu [b, c}, neobsahuje však její komplement v P(M), tj. množinu {a}. I tvoří Booleovu podal-i množina A je uzavřená ▼ její podalgebře značit m podalgebra" budeme ijr B lze říci následující. ŕ Booleovy algebry B je ÍO. ll. kde 0. 1 e B. Obr. 56 163 Obecně zřejmě platí, že žádný vlastní interval [x, y] Booleovy algebry B není její podalgebrou, protože není uzavřený vzhledem k operaci komplement. Interval [x, y] nemůže obsahovat ani prvek x, ani prvek y'. Kdyby např. obsahoval prvek x\ pak by musel obsahovat i prvky 0 a 1, a to by znamenalo, že splývá s intervalem [0, l], který však není vlastní. Interval [0, l] = B je také jediným intervalem, který je podalgebrou Booleovy algebry B. Zdůrazněme znovu, že pokud množina A tvoří podalgebru algebry B, pak je A sama Booleovou algebrou (viz lemma 9.2). Pokud je však/l Booleova algebra a platí, že A je podsvazem algebry B, pak^4 nemusí být podalgebrou algebry B (viz obr. 56b). Příklad 9.2. Uvažujme Booleovu algebru P(N), kde N je množina všech přirozených čísel. Do množiny A zařadíme všechny konečné podmnožiny množiny N a dále všechny jejich nekonečné komplementy. Množina A je vlastní podmnožinou množiny FÍN) a tvoří podalgebru Booleovy algebry -P(N). Nulou je množina 0 a jednotkou je množina N. Obecně zřejmě platí, že podalgebru Booleovy algebry P (M), kde M je libovolná množina, tvoří libovolná neprázdná množina A c P(M), která je uzavřená vzhledem k operaci ' a také vzhledem k operacím n a u (podle lemmatu 9.4 stačí uzavřenost vzhledem k jedné z binárních operací n, u). Takovéto množiny A však nazýváme tělesa množin. Je proto dobře vidět, že pojem podalgebry Booleovy algebry B je booleovskou analogií pojmu podtěleso množinového tělesa. Nyní se budeme zabývat problematikou generování podalgeber dané Booleovy algebry B. Jestliže podalgebra A Booleovy algebry B obsahuje nějaký prvek x, pak musí obsahovat i prvek x' a také prvky 0 a 1. Množina {x, x', 0, 1} však již tvoří podalgebru v B, obsahující prvek x. Tato podalgebra je nejmenší podalgebrou algebry B obsahující prvek x a nazývá se podalgebra generovaná prvkem x. Je zřejmé, že průnikem dvou podalgeber Ax, A2 Booleovy algebry B je opět podalgebra Booleovy algebry B. Jestliže totiž x, y .s A, n A.2, pak i x n y, x u y a x ležív^l, n A2, protože tyto prvky patří do obou podalgeber Ax ,A2 algebry B. Vyslovené tvrzení lze rozšířit na libovolný neprázdný systém podalgeber algebry B. Lemma 9.5. Nechť B je Booleova algebra a {A}, 6 ,je libovolný neprázdný systém jejích podalgeber, pak průnik p), 6, A, je také podalgebra algebry B. Když si dále uvědomíme, že každá algebra B je podalgebrou sebe sama, dojdeme k závěru, že vlastnost „být Booleovou podalgebrou algebry 5" je uzáverová vlastnost v množině B (viz def. 3.4). Proto platí: Lemma 9.6. Množina všech podalgeber dané Booleovy algebry B tvoří úplný svaz. Nechť B je Booleova algebra a množina M q B, pak také průnik systému všech podalgeber algebry B obsahujících množinu M (tento systém je neprázdný, neboť 164 určitě obsahuje algebru B) je podalgebrou algebry B obsahující množinu M. Na základě tohoto důsledku lemmatu 9.5 můžeme vyslovit následující definici. Definice 9.3. Nechť M je podmnožina Booleovy algebry B, pak algebra, která je průnikem všech podalgeber algebry B obsahujících množinu M se nazývá podal-gebra generovaná množinou M a značí se [Mj. Množina M se nazývá množina generátorů algebry [MJ. K definici 9.3 dodejme, že pokud je množina M prázdná, pak podalgebrou algebry B (B má alespoň dva prvky) generovanou touto množinou je algebra 2. Na základě definice 9.3 a lemmatu 9.6 lze říci, že podalgebra Booleovy algebry B generovaná množinou M c B je nejmenší podalgebra algebry B obsahující množinu M. Tato skutečnost se znovu projeví ve znění a především v důkazu následující věty. Věta 9.1. Podalgebra A Booleovy algebry B generovaná neprázdnou množinou M q B je množina právě všech prvků x, které lze zapsat ve tvaru kde pro každé i, j buď a^ e M, nebo a], e M. Duálně: do podalgebry A patří právě všechny prvky x, které lze zapsat ve tvaru j-nr-iUr-i**. (9-ľ) kde pro každé i, j buď a^ e M, nebo a'y e M. Důkaz. Nechť Aj je množina všech prvků x e B, které lze zapsat ve tvaru (9.1). Je zřejmé, že každý takovýto prvek musí patřit do A, protože množina A je uzavřená vzhledem ke všem třem základním booleovským operacím. Proto stačí dokázat, že množina Ax již tvoří podalgebru Booleovy algebry B. Spojení dvou prvků zA{, tj. prvků tvaru (9.1), je opět prvek tvaru (9.1), a tedy prvek z At. Dále, jestliže x e A1, pak dokážeme, že i x' € A{. Jestliže x e A1, pak lze x zapsat ve tvaru (9.1). Na základě pravidla pro určení komplementu k danému termu (viz čl. 8.2) platí: x' = nr.,ii"=i< (9.2) Použitím zobecněného distributivního zákona upravíme pravou stranu (9.2) na tvar (9.1), a proto x' e Ax. Na základě lemmatu 9.4 můžeme říci, že množina A, je uzavřená i vzhledem k operaci u. Množina Ax proto tvoří podalgebru Booleovy algebry B. Duálně lze dokázat druhou část věty. Další věta se bude zabývat počtem prvků Booleovy algebry B v případě, že množina jejích generátorů je konečná. 165 Věta 9.2. Podalgebra A Booleovy algebry B generovaná množinou M mající k prvků obsahuje nejvýše 2'2'' prvků. Věta 9.2 mimo jiné říká, že pokud je množina generátorů M konečná, pak je konečná i Booleova algebra [Ar]. Připomeňme, že v teorii svazů takovéto tvrzení dokázat nelze, protože už tříprvková množina může generovat nekonečný svaz. Důkaz věty 9.2. Nechť a,, a2,..., ak jsou prvky množiny M. Z věty 9.1 vyplývá, že každý prvek x podalgebry A generované množinou M lze např. podle formule (9.1) získat jako spojem konečně mnoha prvků tvaru ľ? ..>;• (M kde y j je buď a,, nebo a). Všech posloupností tvaru y,, y2,..., yk je celkem 2k (pro y, jsou dvě možnosti a, nebo a\ , proy2 jsou opět dvě možnosti atd.). Každé takové posloupnosti odpovídá nějaký prvek (9.3), tzn. že různých prvků tvaru (9.3) může být nejvýše 2k. Uvažujme nyní množinu všech prvků tvaru (9.3). Tato množina má nejvýše 2k prvků, a proto má nejvýše 2,2t) podmnožin. Každé takovéto podmnožině odpovídá určité spojení prvků tvaru (9.3), tzn. prvek tvaru (9.1). Proto můžeme říci, že všech různých prvků tvaru (9.1) je nejvýše 2í2l\ což jsme měli dokázat. Ukázali jsme, že vlastní interval [a, b] Booleovy algebry B nikdy není Booleovou podalgebrou algebry B. Tento interval je však sám o sobě Booleova algebra. Komplement libovolného prvku x e [a, b] vzhledem k nové nule a jednotce, kterými jsou prvky a, b, označme y. Tento relativní komplement y můžeme v rámci Booleovy algebry B určovat pomocí formule y = (a u x") n b. Tuto skutečnost jsme však už vyslovili ve větě 7.8 a zdůvodnili v jejím důkazu. V závěru článku ještě připomeňme, že každý distributivní svaz 5 s nulou a jednotkou v sobě obsahuje určitou největší Booleovu algebru B. Do algebry B zařadíme právě všechny ty prvky svazu S, k nimž existuje komplement (minimálně jsou to prvky Ü a l). Tuto skutečnost jsme však už vyslovili ve větě 7.4 a zdůvodnili v jejím důkaze. 9.2 Direktní součin Booleových algeber V článku 4.4 jsme zavedli binární operaci na třídě svazů, kterou jsme nazvali direktní součin svazů. Direktním součinem svazů je svaz (viz věta 4.4). Protože Booleovy algebry jsou speciální svazy, můžeme vytvářet i jejich direktní součiny. Přitom platí následující věta: 166 Věta 9.3. Nechť A = (A, n, u(, x)aB = (B, n, □, ~) /sou Booleovy algebry, pak direktním součinem A x těchto algeber, v němž operace n a u zavedeme formulemi (4.12) a (4.12') a operaci komplement zavedeme takto: [x,, x2]' =df [x? , x2], (9.4) /e Booleova algebra. Důkaz věty spočívá v tom, že při provádění operací s dvojicemi [x, y]e A x B se s prvními složkami dělají booleovské operace z A a nezávisle na tom se s druhými složkami dělají booleovské operace z B. Operace zvaná direktní součin tedy dvojicím Booleových algeber přiřazuje Booleovu algebru. Definice 9.4. Nechť A = (A, n\ u\ x)aB = (B, n, □, _) jsou Booleovy algebry, pak Booleova algebra A x B, jejíž operace n, u a ' jsou definovány po řadě formulemi (4.12), (4.12') a (9.4), se nazývá direktní součin algeber A, B. Jestliže je potřeba zavést v direktním součinu A x B svazové uspořádání, pak to lze udělat např. pomocí formule [x,, x2] ra [y,, y2] «df (x, *A y, a x2 =sb ><,). Protože operace direktní součin Booleových algeber je asociativní*), lze ji rozšířit na libovolný konečný, popř. i nekonečný soubor Booleových algeber. Zobrazení F: [x, y] e A x B - x e A (9.5) a zobrazení G: [x, y] e A x B^y e B (9.6) jsou svazovými homomorfismy Booleovy algebry A x B na Booleovu algebru A, popř. B. Příklad 9.3. V příkladu 8.1 jsme uvažovali Booleovu algebru P(M), kde M = {a, b, c}. Tuto algebru lze získat jako direktní součin dvouprvkových Booleových algeber {0, {a}}, {0, {fr}} a{0,{c}} (viz poznámka na str. 101). Obecně platí, že libovolnou Booleovu algebru P(M), kde M = {a{,a2, —, a„}, lze získat jako direktní součin algeber {0, {a,}}, {0, {a2}} až {0, {a,}}. Příklad 9.4. V příkladu 8.4 jsme uvažovali Booleovu algebru B všech dělitelů čísla 30 = 2 . 3 . 5 v množině N. Tuto algebru lze získat jako direktní součin dvouprvkových Booleových algeber {l, 2}, {l, 3}, {l, 5}. Obecně platí, že libovolnou Booleovu algebru B všech dělitelů čísla n = Pi .p2.....p„, kde p, jsou navzájem různá prvočísla, lze získat jako direktní součin dvouprvkových Booleových algeber {l, pj, {l, p2} až {l, pj. *) Viz poznámka pod čárou str. 97. 167 9.3 Booleovy okruhy Booleovy algebry byly ve skutečnosti prvními svazy, které matematici studovali. Boole pomocí nich formalizoval výrokovou logiku. Poměrně dlouho panoval názor, že Booleovy algebry mají podstatně jiný charakter než ostatní známé algebraické struktury. Později se ukázalo, že tomu tak nem. A právě tímto problémem se budeme nyní zabývat. Ukážeme, že teorie Booleových algeber je ekvivalentní s teorií určitých speciálních okruhů. Je-li dána Booleova algebra (B, u, n,'), pak ukážeme, že tuto algebru můžeme považovat za okruh vzhledem k operaci symetrická diference (v tomto kontextu by bylo příhodnější říkat disjunktní sčítání) a dále vzhledem k operaci průsek. Symetrická diference bude hrát roli okruhového sčítání a průsek roli okruhového násobení, které budeme při této příležitosti značit ■. Pro uvažované operace platí: Věta 9.4. Nechť (B, u, n,') je Booleova algebra, pak zavedeme-li v ní operace © a ■ formulemi (9.7) a (9.8), obdržíme okruh (B, ©, •). Okruh B má navíc tyto vlastnosti: je komutativní, má jednotkový prvek, každý prvek z B je idempotentní vzhledem k operaci •, každý prvek z B má vzhledem k operaci © řád ž 2, tzn. (Vxe B)x@x = 0. Důkaz, že operace © a • mají okruhové i další uvedené vlastnosti, přenecháme čtenáři. Dodejme pouze, že z teorie okruhů je známo, že jestliže je každý prvek okruhu (M, +, ■) vzhledem k operaci • idempotentní, pak je okruh M komutativní a každý jeho prvek má řád ž 2. Pro okruhy, o nichž se hovoří ve větě 9.4, zavedeme následující název: Definice 9.5. Okruh (M, +, •) se nazývá Booleův, právě když každý jeho prvek je vzhledem k operaci • idempotentní. Ve větě 9.4 jsme ukázali, že ke každé Booleově algebře B lze sestrojit určitý Booleův okruh s jednotkovým prvkem. Platí však také obráceně: K libovolnému Booleovu okruhu B s jednotkovým prvkem lze sestrojit Booleovu algebru. Konstrukci uvedeme formou následující věty, jejíž důkaz necháme do cvičení. Věta 9.5. Nechť(B, +, •) je Booleův okruh s jednotkovým prvkem, pak definuje-me-li v tomto okruhu operace i_i, n a ' následujícími formulemi: (9.7) (9.8) (Vx, yeB)x.y = xny (Vx, yeB)x\-jy=*x + y-x.y (Vx, y<=B)xriy = x.y (Vx e B) x' = 1 - x, 168 obdržíme Booleovu algebru (B, n,'), v níž je nulový a jednotkový prvek okruhu B po řadě nulou a jednotkou. Konstrukce, která vede od Booleovy algebry k odpovídajícímu Booleovu okruhu s jednotkovým prvkem, a konstrukce, která vede od Booleova okruhu s jednotkovým prvkem k Booleově algebře, jsou k sobě navzájem inverzní. Tím chceme říci toto: Vyjdeme-li např. od určité Booleovy algebry B, můžeme k ní sestrojit odpovídající Booleův okruh s jednotkou. Jestliže potom k tomuto okruhu sestrojíme Booleovu algebru, pak obdržíme Booleovu algebru B, z níž jsme vyšli. Nyní máme vše připraveno k vyslovení tzv. Stoneovy věty. Věta 9.6. Teorie Booleových algeber a teorie Booleových okruhů s jednotkovým prvkem jsou ekvivalentní. Článek ukončíme příkladem, v němž k zadané Booleově algebře sestrojíme odpovídající Booleův okruh. Příklad 9.5. Uvažujme Booleovu algebru B všech dělitelů čísla 30 v N (viz př. 8.4). Tabulky 1, 2, 3 jsou tabulky základních Booleových operací v B. Tab. 1 Tab. 2 1 2 3 5 6 10 15 30 i 1 1 1 1 1 1 1 1 2 1 2 1 1 9 2 1 2 3 1 1 3 1 3 1 3 3 5 1 1 i 5 1 5 5 5 6 1 2 3 1 6 2 3 6 10 1 2 1 5 2 10 5 10 15 1 1 3 5 3 5 15 15 30 1 2 3 5 6 10 15 30 Tab. 3 1 2 3 5 6 10 15 30 30 15 10 6 5 3 2 1 l_l 1 2 3 5 6 10 15 30 1 1 2 3 5 6 10 15 30 2 2 2 6 10 6 10 30 30 3 3 6 3 15 6 30 15 30 5 5 10 15 5 30 10 15 30 6 6 6 6 30 6 30 30 30 10 10 10 30 10 30 10 30 30 15 15 30 15 15 30 30 15 30 30 30 30 30 30 30 30 30 30 Sestrojme k uvedené Booleově algebře B odpovídající Booleův okruh, tzn. zaveďme v množině B operace © a • (viz formule (9.7) a (9.8)). Tabulka pro operaci • bude shodná s tabulkou pro operaci n. Vzhledem ke konstrukci tabulky operace © ukážeme nejprve dva výpočty symetrických diferencí a pak vypíšeme celou tabulku 4. 5 © 3 = (5 n 3') u (5' n 3) = (5 n 10) u (6 n 3) = 5 u 3 = 15 5 © 15 - (5 n 15') u (5' n 15) = (5 n 2) u (6 n 15) = 1 u 3 = 3 169 Tab. 4 e 1 2 3 5 6 10 15 30 i 1 2 3 5 6 10 15 30 2 2 1 6 10 3 5 30 15 3 3 6 1 15 2 30 5 10 5 5 10 15 1 30 2 3 6 6 6 3 2 30 1 15 10 5 10 10 5 30 2 15 1 6 3 15 15 30 5 3 10 6 1 2 30 30 15 10 6 5 3 2 1 Poznamenejme, že tabulka operace ©je grupová, v níž je nulovým prvkem číslo 1. Prvky 1 v celé hlavní diagonále ukazují, že každé číslo je opačné samo k sobě. Symetričnost tabulky podle hlavní diagonály představuje komutativnost operace ©. V tabulce operace • vidíme, že jednotkovým prvkem je číslo 30. Idempotenci libovolného prvku vzhledem k této operaci poznáme podle složení hlavní diagonály (hlavní diagonála se shoduje se záhlavím tabulky). Symetričnost tabulky podle této diagonály ukazuje, že operace • je komutativní. Ostatní vlastnosti Booleova okruhu (B, +, •) nechť si čtenář ověří na několika konkrétních případech. CVIČENÍ 9 1 Určete všechny Booleovy podalgebry Booleovy algebry P{M), kde M = {a}, {a, b},{a, b, c},{a, b, c, d}. Sestrojte Hasseův diagram svazu všech těchto podal-geber. 2 Dokažte, že Booleova podalgebra A algebry B je uzavřená vzhledem k Sheffe-rově i vzhledem k Pierceově operaci. Totéž dokažte pro operace -, *, ©, a ** (viz formule (8.26) až (8.28')). 3 Nechť A je podalgebra Booleovy algebry B a nechť prvek a e B, pak podalgebra algebry B generovaná množinou A u {a} je tvořena všemi prvky x e B tvaru x — (xl n a) u (x2 n a'), kde x,, x2 e A. Dokažte. 4 K svazu znázorněnému na obr. 47a sestrojte jeho největší Booleovu podalgebra (viz věta 7.4). Totéž udělejte pro svazy znázorněné na obr. 51. 5 Sestrojte Hasseovy diagramy Booleových algeber P{{a}) a P({a, b}) a pomocí nich sestrojte Hasseův diagram algebry P{{a}) x P({a, b}). Pomocí Hasseova diagramu algebry P({a, b}) sestrojte Hasseův diagram algebry P({a, b}) x P({a, b}). 6 Dokažte věty 9.4 a 9.5. 7 K Booleovým algebrám P({a}) a P({a, b}) sestrojte odpovídající Booleovy okruhy. 170 10 BOOLEOVY HOMO M OKUS M Y V této kapitole nejprve ukážeme další důležité vlastnosti ideálů a filtru v rámci Booleových algeber. Dále budeme studovat Booleův homomorfismus, tj. homomorfismus, který zachovává všechny tři základní booleovské operace. Dodatečně se ukáže, že pojmy svazový homomorfismus a Booleův homomorfismus nad třídou Booleových algeber splývají. Důležitou vlastností Booleových algeber je existence vzájemně jednoznačného zobrazení mezi jejich kongruencemi a jejich ideály, popř. filtry. V důsledku toho lze např. homomorfní obrazy Booleových algeber studovat nejen pomocí kongruencí jako u svazů, ale také pomocí ideálů, popř. filtrů. V závěru ukážeme, že libovolnou konečnou Booleovu algebru lze reprezentovat pomocí potence nějaké množiny. 10.1 Ideály a filtry Ideály a filtry ve svazech jsme studovali v článku 4.3. Připomeňme, že ideálem / ve svazu S rozumíme každou neprázdnou množinu / s S, pro niž platí: (Vx, y e S) x e / a y s / =* x u y e / (10.1) (Vx,ye S)xeI a y-ix=>y e / (10.2) Vlastní ideál / svazu S se nazývá maximální, právě když ve svazu S neexistuje žádný vlastní ideál obsahující / jako vlastní podmnožinu. Vlastní ideál / svazu S se nazývá prvoideál, právě když pro něj platí: (Vx, y e S) x n y e / =* x e / v y e / (10.3) Duálm'mi pojmy k třem výše uvedeným pojmům jsou: filtr, maximální filtr a ultra-filtr. Ideály a filtry tvoří důležitý druh podsvazů daných svazů. Také v Booleových algebrách tvoří ideály a filtry podsvazy těchto algeber. Z předchozí kapitoly však víme, že žádný vlastní ideál nebo filtr Booleovy algebry B netvoří její podalgebru, neboť neobsahuje buď jednotku, nebo nulu algebry B. O vztahu mezi ideály a filtry v Booleových algebrách hovoří následující lemmata, jejichž důkazy se opírají o de Morganova pravidla a o formuli (8.25). 171 Lemma 10.1. Nechť I je ideál Booleovy algebry B, pak množina F všech prvků x', kde x e /, tvoří filtr algebry B. Lemma 10.1'. Nechť F je filtr Booleovy algebry B,pak množina I všech prvků x', kde x e F, tvoří ideál algebry B. Každé z uvedených lemmat určuje vzájemně jednoznačné zobrazení mezi množinou všech ideálů a množinou všech filtrů dané Booleovy algebry B. Jestliže / je ideál v B, pak filtr F zkonstruovaný podle lemmatu 10.1 se nazývá duální filtr k /, a obdobně, jestliže F je filtr v B, pak se ideál / zkonstruovaný podle lemmatu 10.1' nazývá duální ideál k F. Příklad 10.1. Uvažujme těleso množin P(M), kde M - {a, b, c, d}, pak množina / = {{a, b), {a}, {b}, 0} tvoří ideál v P(M). Duálním filtrem k / je množina F = {{c, d}, {b, c, d], {a, c, d], {a, b, c, d}}. Uvažujme množinu / všech konečných podmnožin nekonečné množiny M. Množina / je vlastní ideál v tělese množin P(M). Duálním filtrem k / je množina F všech nekonečných podmnožin množiny M, které mají konečné komplementy v M. Přcforrnulujeme-li lemmata 4.6 a 4.6' pro Booleovy algebry, obdržíme: Lemma 10.2 (10.2'). Každý ideál (filtr) Booleovy algebry B obsahuje nulu (jednotku) algebry B. V kapitole 6 jsme dokázali, že v libovolném distributivním svazu S je každý maximálni ideál / prvoideálem (viz věta 6.7). Protože Booleovy algebry jsou speciální případ distributivních svazů, platí uvedená věta i v Booleových algebrách. V Booleových algebrách (na rozdíl od libovolných distributivních svazů) platí i obrácení této věty. Proveďme následující úvahu: Nechť B je Booleova algebra a nechť / je prvoideál v algebře B, pak podle lemmatu 10.2 je 0 e/. Pro libovolné x e B proto musí platit x n x' = 0 e /. Protože / je prvoideál (viz formule (10.3)), vyplývá z toho, že x e /, nebo x' £ /. Oba prvky x a x však nemohou do ideálu 7 patřit současně, neboť pak by ideál / podle formule (10.l) obsahoval i jejich spojení x u x' = 1 a ideál by nebyl vlastní. Výsledek naší prozatím nedokončené úvahy můžeme vyslovit takto: Lemma 10.3 (10.3'). Nechť B Booleova algebra a I je prvoideál (F je ultra-filtr) v B, pak platí: (Vx e B) x e I v x e I, kde v značí vylučovací nebo (10.4) ((\/x e B)x€ Fv x/ e F) (10.4') Pokračujme v úvaze započaté před vyslovením lemmatu 10.3. Vyšli jsme z předpokladu, že / je prvoideál v S a chceme dojít k závěru, že / je maximální ideál vS. K tomutí znamená, že . takový, že v ; komplement tak i x , musí J nebyl vlastn Věta 10.1. 1. Ideál 1 2. ideál I Věta 10.1 1. Filtr F 2. Filtr F - Podle lerr.— formule (10.4). ideál / vyplýva, kou 1. věty 10 vyslovit: Věta 10.2. z podmínek 1 Věta 10.2 z podmínek 1 Z lemmatu žinu 0 tvoří ú Booleovy alge svaz i bez toh( Lemma 10 v němž je nulo Lemma 10. v němž je nulo V závěru čli i v teorii Boo následující vět Věta 10.3. i gebře B, právě 172 množina F všech prvků nožina I všech prvků x', é zobrazení mezi mno-algebry B. Jestliže 7 je nazývá duální filtr k /, ý podle lemmatu 10.1' a, b, c, d}, pak množi-::trr. k 7 je množina r.ckonečné množiny :": /.rem k 7 je množina v -iiné komplementy á>ry, obdržíme: B obsahuje nulu (jednom svazu 5 je každý leovy algebry jsou spe-Booleových algebrách. . - nich svazů) platí algebře B. pak podle r n jí = 0 6 7. Protože nebo x e 7. Oba prvky . . J podle formule I vlastní. Výsledek naší prvoideál (F je ultra- (10.4) (10.4') ntu 10.3. Vyšh jsme že / je maximální ideál v B. K tomuto tvrzení dojdeme sporem. Nechť prvoideál 7 není maximální v 7?. To znamená, že existuje vlastní ideál J v B takový, že 7 /, a tedy existuje prvek x e B takový, že x í I a x e J. Protože x nepatří do 7, musí do 7 podle (10.4) patřit jeho komplement x'. Z předpokladu laj vyplývá, že x' e /. Protože J obsahuje jak x, tak i x', musí podle (l 0.1) obsahovat i x u x1 = 1, což je spor, neboť pak by ideál / nebyl vlastní. Ideál 7 proto musí být maximální. Nyní můžeme vyslovit větu: Věta 10.1. V Booleově algebře B jsou následující dvě podmínky ekvivalentní: 1. Ideál I je prvoideál. 2. Ideál I je maximální. Věta 10.1'. V Booleově algebře B jsou následující dvě podmínky ekvivalentní: 1. Filtr F je ultrafiltr. 2. Filtr F je maximální. Podle lemmatu 10.3 víme, že pokud je 7 prvoideál v algebře B, pak pro něj platí formule (10.4). Lze též dokázat (viz cv. 10.1), že z platnosti formule (10.4) pro ideál 7 vyplývá, že 7 je prvoideál. Podmínka (10.4) je proto ekvivalentní s podmínkou 1. věty 10.1 a v důsledku věty 10.1 i s podmínkou 2. této věty. Můžeme proto vyslovit: Věta 10.2. V Booleově algebře B je podmínka (10.4) ekvivalentní s každou z podmínek 1., 2. z věty 10.1. Věta 10.2'. V Booleově algebře B je podmínka (10.4') ekvivalentní s každou z podmínek 1., 2. z věty 10.1'. Z lemmatu 4.9 víme, že množina všech ideálů daného svazu S doplněná o množinu 0 tvoří úplný svaz. To samozřejmě platí i pro Booleovy algebry. Protože však Booleovy algebry mají nulový prvek, tvoří množina všech ideálů algebry B úplný svaz i bez tohoto doplnění o množinu 0. Lemma 10.4. Množina všech ideálů dané Booleovy algebry B tvoří úplný svaz, v němž je nulou množina {0} a jednotkou množina B. Lemma 10.4'. Množina všech filtrů dané Booleovy algebry B tvoří úplný svaz, v němž je nulou množina {l} a jednotkou množina B. V závěru článku zdůvodníme, proč užíváme pojem ideál jak v teorii okruhů, tak i v teorii Booleových algeber. Tyto pojmy spolu totiž velmi úzce souvisí. Platí následující věta: Věta 10.3. Nechť I je podmnožinou Booleovy algebry B, pak I tvoří ideál v algebře B, právě když I tvoří ideál v odpovídajícím Booleově okruhu B. 173 Důkaz. Nejprve dokážeme: pokud je / ideál v algebře B, pak je / ideál v odpovídajícím Booleově okruhu B (viz věta 9.4). Pro ideál / algebry B platí formule (10.1) a (l 0.2) a ideál / okruhu B je charakterizován formulemi (viz čl. 1.1): (Vx,yeB)x£l hyzl=*x@yél (10.5) (Vx,yeB)xeI^x.yeI (10.6) Nechť x, y jsou libovolné prvky z algebry B, pak 1. x € í a y e I Předpoklad 2. xný sä x a x' ny^y Podle (2.13) 3. (x n y') u (x' n y) :< x u y Podle cv. 2.15 na ř. 2. 4. x e y-a juve / Podle (9.7) a (10.1) x©ye/ Podle (10.2) na ř. 4. 1. x e I a y e B Předpoklad 2. xnyme zavedli kongruence ve svazech. Nyní se budeme zabývat kongruencemi v Booleov ých algebrách. Kongruence, které zavedeme, jsou speciálním případem svazových kongruencí. Definice 10.3. Nechť B je Booleoua algebra, pak ekvivalence K v B se nazývá Booleova kongruence v B, právě když Booleovu kongruenci budeme značit symbolem = a místo formule xKy píšeme x = y(mod K), nebo pouze x = y. Je zřejmé, že každá Booleova kongruence v algebře B je také svazovou kongruencí. Každá Booleova kongruence v B (stejně jako svazová) je zvláštní případ ekvivalence, a proto indukuje rozklad množiny B. Protože v dalším textu (10.11). (Vx, y, z e B) xKy ^-xnzKynz, (Vx, y,z € B) xKy ^xuzJfyuz, (Vx,ye B)xKy^x' Ky'. (10.12) (10.13) (10.14) 179 budeme pojednávat výhradně o Booleových kongruencích, budeme přívlastek „Booleova" vynechávat. Příklad 10.5. Uvažujme Booleovu algebru B všech dělitelů čísla 30 v N. Na obr. 60 jsou vyznačeny tři různé rozklady množiny B. Rozklady na obr. 60a, b odpovídají kongruencím. Ověřme alespoň na jednom příkladě, že pro ekvivalenci Kx z obrázku 60a platí formule (10.14). 3 = 15 (mod K}) =» 3' = 10 = 2 = 15' (mod K J Rozklad na obr. 60c neodpovídá kongruenci, neboť např. 3 = 5 (mod E) a přitom 10 u 3 = 30 jŕ 10 = 10 u 5 (mod É). f) E f ¥ 0 c) Obr. 60 Pomocí formulí (8.15) a (8.15') lze ukázat, že jsme v definici 10.3 mohli vyslovit méně požadavků. Platí totiž věta: Věta 10.7. Jestliže pro ekvivalenci E v Booleově algebře B platí formule (10.14) a jedna z formulí (10.12), (10.13), pak pro ekvivalenci E platí i druhá z formulí (10.12), (10.13). Nyní popíšeme konstrukci nových druhů Booleových algeber. Věta 10.8. Necht (B, n, u,') je Booleova algebra a K je kongruence v B, pak sestrojíme-li faktorovou množinu B/K a definujeme-li na této množině operace n, u a ' takto (Tx a Ty jsou libovolné bloky z BI K obsahující prvky x, y): TxnTy=TXny (10.15) ľ,uľ,= TIul, (10.15') n=7V, (10.16) pak trojice (B/K, u, n, ') je Booleova algebra, v níž je blok Tfí nula a blok J, jednotka. 180 Důkaz. Vzhledem k větě 4.9 stačí dokázat: a) T0 a 1\ tvoří nulu a jednotku svazu B/K, b) definice komplementu nezávisí na volbě reprezentantů, c) formule (10.16) určuje komplement. Nechť Tx, Tv jsou libovolné bloky z B/K, pak: a) TxnT0 = TXrt0 - T0 Tx ^ T0 = TXljD = Tx TxnT1 = TXril = Tx r, - r,ul - r, b) Tx = Ty => x = y => X1 = y => Tx = Ty => T'x = T\, c) ľ.v n Ty = rw = T() Na základě věty 10.8 můžeme vyslovit následující definici. Definice 10.4. Nechť B je Booleoua algebra a K je kongruence v B, pak Booleo-va algebra sestrojená podle věty 10.8 se nazývá faktorová Booleova algebra algebry B podle kongruence K a značí se B/K. Spojíme-li větu 10.8 s tím, co víme z článku 4.6 a uvážíme-li i větu 10.5, pak můžeme stručně říci: Každá faktorová algebra B/K je homomorfním obrazem algebry B. Až na izomorfismus neexistují žádné jiné homomorfní obrazy dané Booleovy algebry B než její faktorové algebry B/K, kde K je kongruence v S. A protože dvěma různým kongruencím v B mohou odpovídat izomorfní faktorové algebry, lze říci, že homomorfních obrazů algebry B je až na izomorfismus nejvýše tolik, kolik existuje kongruencí v B. Nyní se budeme zabývat vztahem mezi ideály (duálně filtry) a kongruenccmi v Booleových algebrách. Následující věta ukáže, že ideály a kongruence si vzájemně jednoznačně odpovídají. Tato situace připomíná situaci v teorii grup, kde si také kongruence a normální podgrupy vzájemně jednoznačně odpovídají. Obecně ve svazech však takovýto vztah neplatí (viz př. 4.23). Věta 10.9. V Booleově algebře B existuje vzájemně jednoznačné zobrazení množiny všech ideálů v B na množina všech kongruencí v B. Důkaz. Nechť / je ideál algebry B, pak dokážeme, že k němu lze sestrojit kongruencí K pomocí následující formule: x = y(mod K) x © y e / (10.17) Připomeňme, že © značí symetrickou diferenci (viz formule (8.27)). Důkaz, že relace K je ekvivalence vB, necháme do cvičení. Zde pouze dokážeme a) platnost formule (10.13)) a b) platnost formule (10.14). Na základě věty 10.7 pak můžeme říci, že platí i formule (10.12). Nechť x, y, z jsou libovolné prvky z B: 181 a) Předpokládejme, že x © v e /, pak chceme dokázat, že (x lj z) © (y u z) e I. (x u z) © (y u z) = = [(x u z) n (y u z)'] lj [(x lj z)' n (y u z)] = Podle (8.27) = [(x lj z) n (>' n z1)] lj [(x i i z') i i (y i—i z)] = Podle (8.13'). = (x n y' n z') u (z n y' n z') u (x' n z" n y) lj u {x1 n ť n z) - Podle (8.5), (8.1). = (x n >' n z') lj (x' n y n z') = Podle (8.7), (8.6). = z' n [(x n V') lj (x' n >')] = Podle (8.5). = ť n (x © y) si® y Podle (8.27), (2.13). Protože (x lj z) © (y i_i z) :s x © y e /, piati podle (10.2) i formule (x u z) © (y u z) 6 7. b) Předpokládejme, že x © y e /, pak chceme dokázat, že (x'©y) e/. x' © y - = (x' n y") lj (x" n y) = Podle (8.27). = (x' n y) u (x n yjI = x © y e / Podle (8.12), (8.ľ), (8.27) a před- pokladu. Důkaz obrácené implikace. Nechť K je kongruence v algebře B, pak dokážeme, že k ní lze sestrojit vhodný ideál /. Za tento ideál prohlásíme blok rozkladu B/K obsahující nulu, tzn. / = {x e B; x m O (mod K)}. Musíme však dokázat, že ideál / souvisí s kongruencí K tak, jak to předepisovala formule (10.17). Postupovat můžeme např. tak, že sestrojíme množinu M všech takových prvků x © y, kde oba prvky x, y patří vždy do téhož bloku z B/K, a zjistíme, zda M = /. Nechť tedy M = {ze B; (lx, yeB)x = y (mod K) a z = x © y}. Nejprve dokážeme, že M e /. Nechť z je libovolný prvek z M, tzn. existují prvky x, y £ B takové, žez = x©yax = y (mod K), pak: z = x © y = Předpoklad = (x u y) n (x n y) = Podle (8.29). ■ (x n y) n (x n y)' = 0 Podle cv. 4.21, (8.7). Odtud vyplývá, že z s 0 (mod K), a proto ze/. Dokažme, že / c M. Nechť z je libovolný prvek z /, tzn. z = 0 (mod A"), pak: z © 0 = (z n 0') u (z n 0) = Podle (8.27). = (z n lj u (z' n 0) = Podle V 7.1. = zlj0 = z Podle (8.6), (8.6'). 182 i a pŕed- dokážeme, skladu B/K odepisovala M všech K. a zjistí- stují prvky Nechť z je Vyjdeme-li od ideálu / v B, pak po provedení obou výše uvedených konstrukcí (v patřičném pořadí) obdržíme opět ideál I. Obdobně, pokud bychom vyšli od kongruence Kv B, pak po provedení obou konstrukcí obdržíme opět kongruenci K vB. ZobrazeníF, které každému ideálu / v B přiřazuje odpovídající kongruenci v B (viz formule 10.17), je proto vzájemně jednoznačným zobrazením množiny všech ideálů na množinu všech kongruenci. Věta 10.9'. V Booleově algebře B existuje vzájemně jednoznačné zobrazení množiny všech filtrů v B na množinu všech kongruenci v B. Místo důkazu, který je duální k důkazu věty 10.9, pouze zopakujme obě konstrukce, které tvoří jeho základ. Jestliže je v algebře B zadán filtr F, pak odpovídající kongruenci sestrojíme pomocí následující formule: (Vjc, y e B) x = y(mod K) «* {x « y) e F (10.1 T) Druhý symbol <=> značí operaci zavedenou formulí (8.27'). Tato operace je duální k operaci ©. Jestliže je v algebře B zadána kongruence K, pak odpovídající filtr F sestrojíme takto: F - {x e B; x = 1 (mod K)} Příklad 10.6. Nechť B je Booleova algebra všech dělitelů čísla 30 v N. Uvažujme ideál/ = {1, 5}. Tomuto ideálu odpovídá podle formule (10.17) kongruence K, jejíž rozklad je vyznačen na obr. 60a. Uvažujeme-li ideál /= {l, 3, 5, 15}, pak tomuto ideálu odpovídá kongruence, jejíž rozklad je znázorněn na obr. 60b. Analogicky jako jsme se u svazů v čl. 4.6 zabývali vztahem mezi kongruencemi a homomorfními obrazy daného svazu, můžeme se nyní zabývat vztahem mezi ideály (filtry) a homomorfními obrazy dané Booleovy algebry. Dříve však připomeňme: Nechť B, A jsou Booleovy algebry, pak dolním jádrem homomorfismu F: B 2* A je idál nFO a horním jádrem je filtr nFl (pokud 0,1 e A). Nechť / je ideál v B, pak definujeme-li faktorovou množinu Bjl předpisem {x © l}xeB a na ní operace n, u a' formulemi (10.15), (10.15') a (10.16), obdržíme Booleovu algebru. Důkaz tohoto tvrzení přenecháme čtenáři. Definice 10.5. Necht I je ideál v Booleově algebře B, pak (Bjl, n, u, '), kde operace n, ui a ' jsou definovány formulemi (10.15), (10.15') a (10.16) se nazývá faktorová Booleova algebra algebry B podle ideálu / a značí se Bjl. Duálně lze vyslovit definici faktorové Booleovy algebry algebry B podle filtru F, kterou značíme BjF. Příklad 10.7. Uvažujme Booleovu algebru B všech dělitelů čísla 30 v N (viz obr. 60a). V ní existuje jeden jednoprvkový ideál {l}, tři dvouprvkové ideály (l, 2], 183 {1, 3}, {1, 5}, tři čtyřprvkové ideály {l, 2, 3, 6}, {l, 2, 5, 10}, {l, 3, 5, 15} a jeden nevlastní ideál, tj. B. Ke každému z těchto ideálů lze sestrojit faktorovou algebru B/I. Např. prvky faktorové algebry B/I, kde / je ideál {l, 5}, jsou bloky rozkladu vyznačené na obr. 60a. Je zřejmé, že pomocí výše uvedených ideálů lze sestrojit jednu osmiprvkovou faktorovou algebru, tj. B/jí] (viz obr. 61 a), dále tři čtyřprvkové faktorové algebry, tři dvouprvkové faktorové algebry a jednu jednoprvkovou faktorovou algebru, tj. B/B (viz obr. 6Id). Všechny tři čtyřprvkové faktorové algebry jsou navzájem izomorfní a odpovídá jim Hasseův diagram na obr. 61b. Také všechny dvouprvkové Booleovy algebry jsou navzájem izomorfní a odpovídá jim diagram na obr. 61c. Obr. 61 Poznámka. Připomeňme situaci u grup. Sestrojujeme-li rozklad grupy (G, •) podle normální pod-grupy H, pak bloky tohoto rozkladu zapisujeme a . H, kde a je některý prvek tohoto bloku. Pro každý prvek x e G platí, že vynásobíme-li postupně prvek x zprava (popř. zleva) všemi prvky normální podgrupy H grupy G, pak obdržíme všechny prvky bloku, v němž tento prvek leží. Praktický postup konstrukce faktorové množiny G/H pro konečnou grupu G je tento: Jeden blok rozkladu tvoří normální podgrupa V prvním kroku zvolíme libovolný prvek a, e G - H a sestrojíme a, . H. Obdržíme další blok rozkladu. Dále zvolíme a2 e (G - H) - a, . H a sestrojíme a, . H. Opět obdržíme blok rozkladu atd. Po konečném počtu kroků, který je menší nebo roven počtu prvků grupy G, získáme všechny bloky rozkladu G/H. I když u Booleových algeber nezdůrazňujeme svazové uspořádání, projeví se nám jeho existence na nejrůznějších místech. Např. právě nyní. Jestliže chceme bloky rozkladu Booleovy algebry B podle jejího ideálu / zapisovat v analogickém tvaru jako u grup, pak můžeme použít značení aul, kde a je nejmenší prvek tohoto bloku. Množinu au/ obdržíme jako spojení prvku a s každým z prvků ideálu /. Pokud bychom za a nevzali nejmenší prvek uvažovaného bloku, pak bychom při popsaném spojování tento nejmenší prvek nemohli dostat. Praktický postup konstrukce faktorové množiny B/I pro konečnou algebru B je tento: Jeden blok rozkladu tvoří ideál /. V prvním kroku zvolíme libovolný minimální prvek a, e B - I a sestrojíme a, i_i /. Obdržíme blok rozkladu obsahující prvek a,. Dále zvolíme libovolný minimální prvek a2 e (B - i) - a, u / a sestrojíme a2 u /. Obdržíme blok rozkladu obsahující prvek a2, atd. Po konečném počtu kroků, který je menší nebo roven počtu prvků Booleovy algebry B, získáme všechny bloky rozkladu B/I. O vztahu mezi Booleovou algebrou B a její faktorovou algebrou B/l hovoří následující věta, která úzce souvisí s větou 4.10. 184 Věta 10.10. Necht B je Booleova algebra a 1 je ideál v B, pak faktorová algebra B/I je homomorfním obrazem algebry B. Uveďme pouze, že homomorfismem je zobrazení (Tx značí blok rozkladu B/I obsahující prvek x): F:xeB~Txe B/I Věta 10.10'. Nechť B je Booleova algebra a F je filtr v B, pak faktorová algebra B/F je homomorfním obrazem algebry B. Věta 10.10 říká, že každá faktorová algebra B/I algebry B podle ideálu / je homomorfním obrazem algebry B. Následující věta, která souvisí s větou 4.11, ukáže, že až na izomorfismus žádné jiné homomorfní obrazy algebry B neexistují. Této větě se ve spojení s větou 10.10 říká základní věta o homomorfismu Booleo-vých algeber. Věta 10.11. Nechť Booleova algebra A je homomorfním obrazem Booleovy algebry B, pak existuje taková faktorová algebra B/I, kde I je ideál v B, že algebra A je izomorfní s algebrou B/I. Podle věty 10.11 existuje ideál I v B takový, že faktorová algebra B/I je izomorfní s algebrou A. Místo důkazu se omezíme pouze na konstatování, že hledaný ideál / je dolním jádrem homomorfismu F: B ™ A, tzn. množina nFO. Isomorfismem algeber B/I a A je následující zobrazení: G: Tx e B/I h. F(x) e A Věta 10.11'. Nechť Booleova algebra A je homomorfním obrazem Booleovy algebry B, pak existuje taková faktorová algebra B/F, kde F je filtr v B, že algebra A je izomorfní s algebrou B/F. Shrňme: Každá faktorová algebra B/I je homomorfním obrazem algebry B. Až na izomorfismus neexistují žádné jiné homomorfní obrazy dané Booleovy algebry B než její faktorové algebry B/I, kde / je ideál v B. A protože dvěma různým ideálům v B mohou odpovídat izomorfní faktorové algebry (viz př. 10.7), lze říci, že homomorfních obrazů algebry B je až na izomorfismus nejvýše tolik, kolik existuje ideálů v B. Duální shrnutí lze vyslovit pro filtry. Příklad 10.7 (pokračování). V Booleově algebře B existuje celkem 8 různých ideálů. Hasseovy diagramy všech faktorových'algeber B/I jsou znázorněny na obr. 61. Podle základní věty o homomorfismu Booleových algeber můžeme proto říci, že kromě algeber znázorněných na obr. 61 nemá uvažovaná algebra B žádné jiné homomorfní obrazy. Nyní je zcela zřejmé, že studujeme-li otázku homomorfních obrazů dané Booleovy algebry B pomocí ideálů (filtrů) nebo pomocí kongruencí, pak dostáváme 185 různými postupy stejné výsledky. Tento závěr jsme sice mohli vyslovit ihned po vyslovení definice 10.5, ale raději jsme zvolili delší postup, aby měl čtenář dostatek času vytvořit si správnou představu. Na rozdíl od teorie svazů je tedy tato problematika v Booleových algebrách zcela analogická obdobné problematice v teorii grup nebo okruhů. Víme, že studujeme-li např. v teorii grup otázku homomorfních obrazů dané grupy G, je zcela jedno, zda to děláme pomocí normálních podgrup v G nebo pomocí kongruencí v G. 10.4 Množinová reprezentace V posledním článku této kapitoly se budeme zabývat problematikou reprezentace konečných Booleových algeber. Protože Booleovy algebry jsou speciální případ distributivních svazů, bude tento článek bezprostředně souviset s článkem 6.2, v němž jsme hovořili o reprezentaci konečných distributivních svazů. Ukážeme, že k libovolné konečné Booleově algebře B existuje potence určité množiny, která je s algebrou B izomorfní. Ještě před toto pojednání však zařadíme několik příkladů různých, ale navzájem izomorfních booleovských algeber. Všechny tyto algebry budou mít 2(2"' prvků, kde n je určité přirozené číslo. Příklad 10.8. Nechť M je neprázdná množina mající 2" prvků. Utvořme potenci P(M). Tato potence má celkem 2(2"' prvků. Booleovské operace průsek, spojení a komplement jsou realizovány po řadě množinovými operacemi průnik, sjednocení a komplement. Uspořádání množiny P(M) je dáno relací „být podmnožinou". Nulou je množina prázdná, jednotkou je množina M. Booleova algebra P(M) je těleso množin, v němž je atomem, tj. horním sousedem nuly, každá jednoprvková množina {x}, kde x e M. Algebra P(M) má celkem 2" atomů. Pro n = 1 a n = 2 obdržíme algebry mající 4 a 16 prvků. Hasseovy diagramy těchto algeber jsou na obr. 62a, b. O a) Obr. 62 186 Príklad 10.9. Nechť 2, 3, 5, 7,... ,p je prvních 2" prvočísel. Sestrojíme číslo m, které je jejich součinem, tzn. to = 2 . 3 . 5 . 7.....p. Utvořme množinu K všech dělitelů čísla m v N, tzn. K = {x e N; x í m}. Booleovské operace průsek a spojení jsou realizovány po řadě operacemi „největší společný dělitel" a „nejmenší společní ný násobek". Booleovským komplementem čísla x e K je číslo — . Uspořádání x množiny K je dáno relací „dělit". Nulou algebry je číslo 1, jednotkou je číslo to. Atomem je každé z prvočísel 2, 3, 5, 7, p. Tato algebra má opět 2" atomů. Pro n — 1 a n = 2 obdržíme algebry mající 4 a 16 prvků. Hasseovy diagramy těchto algeber jsou opět na obr. 62. Příklad 10.10. Nejprve zavedeme Booleovy algebry, o nichž jsme prozatím nehovořili, a pak je dáme do souvislosti s ostatními příklady. Uvažujme množinu K všech vrcholů n -dimenzionální krychle v euklidovském prostoru E„ dimenze n. Ukažme, jak vytvoříme grafické znázornění množiny K, čímž zároveň obdržíme Hasseův diagram níže uvedené algebry. Nechť je dán systém n orientovaných os prostoru dimenze n. V jednotkových bodech těchto os umístíme určité vrcholy krychle (souřadnice bodu na /-té ose bude tvořit uspořádaná n-tice mající pouze na /-tém místě číslo 1 a na všech ostatních místech číslo 0). Tyto vrcholy či jejich souřadnice budou tvořit atomy algebry K. Z množiny A všech těchto atomů vytvoříme potenci P{A). Každou množinu X e P(Á) nahradíme jednou uspořádanou rc-ticí, v níž je na /-tém místě číslo 1, právě když v některé «-tici z X je na temže místě číslo 1. Na ostatních místech budou nuly. Např. pro n = 4 aX = {(l, 0, 0, 0), (0, 0, 1, 0), (0, 0, 0, l)} obdržíme uspořádanou čtveřici (1,0, 1, 1), která zastupuje množinu X a která navíc představuje souřadnice jednoho z vrcholů čtyřdimenzionální krychle. Uvedeným postupem získáme souřadnice všech vrcholů krychle o hraně 1 (pro prázdnou množinu 0 c A obdržíme n-tici (0, 0, ... , 0)). Načrtnutím hran spojujících sousední vrcholy získáme Hasseův diagram algebry K. Nulou algebry K je vrchol o souřadnicích (0, 0, ..., 0), jednotkou je vrchol o souřadnicích (l, 1, 1). Je zřejmé, jak se v uvedeném grafickém znázornění sestrojuje průsek a spojení vrcholů krychle. Komplementem vrcholu X je protilehlý vrchol krychle, tj. vrchol, který leží na spojnici vrcholu X se středem krychle. Pro n = 3 obdržíme trojrozměrnou krychli (viz obr. 61a), pro n = 4 obdržíme čtyřrozměrnou krychli (viz obr. 62b), pro n = 2 obdržíme dvojrozměrnou krychli (viz obr. 62a). Zařaďme právě uvedený druh Booleových algeber do našeho souboru příkladů: Sestrojme množinu K vrcholů 2"-dimenzionální krychle. Množina K má 2(2"' prvků. Atomem je každý vrchol mající právě jednu souřadnici 1. Algebra K má proto 2" atomů. Pro n = 1 an = 2 obdržíme algebry mající 4 a 16 prvků. Hasseovy diagramy těchto algeber jsou na obr. 62. 187 Příklad 10.11. Nechť je dáno n jednoduchých navzájem nezávislých výroků Cl ] , Cl"), ... , Cln , Uvažujme množinu V všech výpovědí, které lze z daných n výroků vytvořit pomocí spojek a, v a ~i. Každá výpověď představuje množinu navzájem logicky ekvivalentních výroků. Množina V má celkem 2'2") prvků. Booleovský průsek dvou výpovědí je realizován pomocí spojky a, spojem pomocí spojky v a komplement pomocí spojky n. Jednotkou algebry V je výpověď vyslovená pomocí výroku majícího stavbu tautologie, nulou je výpověď, kterou lze vyslovit pomocí výroku majícího stavbu negace tautologie. Atomem této algebry je každá výpověď, kterou lze vyslovit ve tvaru X, A X2 A ... A Xn, kde každé xi je buď a,, nebo "la,-. Algebra V má proto 2" atomů. Pro n = 1 a n = 2 obdržíme algebry mající 4 a 16 prvků. Hasseovy diagramy těchto algeber jsou na obr. 62. Uvedené čtyři příklady jsou pro n - 1 a n = 2 navzájem izomorfní. Graficky se tato skutečnost projeví tím, že mají stejné Hasseovy diagramy. Zřejmě bude platit obecně, že pro stejné n dostáváme čtveřici navzájem izomorfních algeber. O dalších příkladech Booleových algeber, které jsou izomorfní s uvedenými příklady, budeme hovořit v následujících kapitolách. Je to především algebra A„ všech booleovských funkcí ^-proměnných definovaných v algebře 2 = {0, lj, algebra Pn všech úplných disjunktivních normálních forem n -proměnných definovaných také v algebře 2, algebra Qn všech úplných konjunktivních normálních forem rt-proměnných definovaných v algebře 2. Dále to budou algebry představující fyzikální realizaci Booleových funkcí v algebře 2, tj. algebry logických obvodů. Přistupme k pojednání o množinové reprezentaci konečných Booleových algeber. Specifičnost řešení tohoto problému v Booleových algebrách se proti řešení v libovolných distributivních svazech projeví v následujícím lemmatu. Lemma 10.5. Nechť B je Booleova algebra, pak prvek p e B je zdola ireducibilní, právě když p je nula nebo p je atom. Z lemmatu 10.5 vyplývá, že v Booleově algebře B jsou každé dva různé, nenulové a zdola ireducibilní prvky q navzájem disjunktní, tzn. p n q = 0. Nemůže proto nastat případ znázorněný na obr. 49b. V distributivním svazu D existuje zdola ireducibilní prvek p, který nem sousedem nuly a není disjunktní se svým předchůdcem, který je také ireducibilní. Příklad 10.12. V libovolné Booleově algebře P{M) jsou nenulovými zdola ireducibilními prvky, tzn. atomy, právě všechny jednoprvkové množiny {x}, kde xe M. Čtenář si může vyznačit atomy např. v diagramech na obr. 61 a 62. 188 Důkaz lemmatu 10.5. Nechť p je libovolný atom z B, pak z rovnosti p = a i_i b vyplývá a = p nebo a = 0. Pokud a - 0, pak p = 0 u b = b. V obou případech tak docházíme k závěru (viz formule (6.5)), že prvek p je zdola ireducibilní. Obráceně: nechť x je libovolný prvek z B, který není nula ani atom, pak existuje takový prvek a e B, že platí O^a^x, (10.18) a proto x = x n 1 = x n (a u a') = (x n a) u (x n tí') - « u (x n tí'). (10.19) Poslední term jsme získali z předposledního pomocí formule (10.18) a formule (8.18). Z formule x = a i_i (x n a') vyplýva podle (2.13'), že x n a' =9 x. Ukážeme, že dokonce musí platit x n tí' -a x. Předpokládejme, že x n a' = x. Z tohoto předpokladu vyplývá, že tí = X n tí = (x n tí') n tí = X n 0 = 0, což je spor s formulí (10.18). Proto skutečně platí x n a! o x. Z rovnosti prvního a posledního termu v (10.19) proto vyplýva, že prvek x nem zdola ireducibilní. Vyslovme lemma 6.6 pro Booleovy algebry. Lemma 10.6. Nechť B je konečná Booleova algebra, pak každý její prvek x lze zapsat jako spojení určitých atomů. Poznamenejme, že nulu algebry B lze zapsat jako spojení prázdné množiny atomů, tzn. 0 = |_|0. Označíme-lM(x) množinu všech atomů p algebry B předcházejících před prvkem x e B, pak lze lemma 10.6 přepsat v silnější podobě (viz lemma 6.7). Lemma 10.7. Nechť B je konečná Booleova algebra, pak každý její prvek lze zapsat ve tvaru Místo zobrazení F definovaného u distributivních svazů formulí (6.6) zavedeme nyní zobrazení G, které každému prvku x e B přiřadí množinu A(x), která je podmnožinou množiny A všech atomů z B, tzn. G:xeB~A(x)eP{A). (10.20) Protože pro libovolný prvek x e B platí A(x) = /(x) - {0} a protože nula je obsažena ve všech množinách l(x), má zobrazení G tytéž pro nás důležité vlastnosti, jako mělo zobrazení F, tzn. G je prosté, převádí průsek na množinový průnik A(x n y) = A(x) n A(y) 189 a dále převádí spojení na množinové sjednocení A(x u y).= A(x) u A{y). Také platí A(0) = 0 a A{\) =A. Ukažme ještě, že každá množina X e P(Á) je obrazem nějakého prvku Booleo-vy algebry B, tzn. že G:B^P{A). (10.21) Stačí ukázat, že různým množinám atomů X, Y přiřazuje operace u různé prvky z B. Postupujme takto: Nechť p je atom, pro nějž platí/? s \_\X, kde X e P(A), pak podle formule (8.10) platí: P = P n UA' = U*«v (P n #,) Protože p je ireducibilní prvek, musí existovat atom g, e Z takový, že p = p n qh což znamená 0

-«■ 1, neboť (0 n 1) u (0' n 1) = 0 u (1 n 1) = 0 u 1 = 1. Jestliže spočítáme hodnoty funkce F pro všechny vektory (x, y) e 22, pak obdržíme tabulku funkce Fj z příkladu 11.4. Poznamenejme, že rovnost dvou polynomů lze zavést různě. Pro naše účely se dobře hodí tzv. funkční definice rovnosti polynomů. Definice 11.2. Říkáme, že polynomy f(x1,..., xn) a g{x1,..., x J Booleovy algebry i? jsou si rovny, právě když oba určují stejnou Booleovu funkci n proměnných, a zapisujeme: /(x,,..., x„) = g(x,,..., x„) Nyní přistoupíme k popisování funkcí pomocí polynomů. Nejprve zopakujme, že libovolný polynom f{xx,...,x,) definuje pro libovolnou Booleovu algebru B funkci F: B" -* B. Toto tvrzení lze částečně obrátit. Částečným obrácením myslíme to, že se nový výrok nebude týkat libovolné Booleovy algebry, ale pouze algebry 2. V další části kapitoly proto budeme pojednávat už jenom o dvouprvkových algebrách {0, l}. Věta 11.2. Každou Booleovu funkci F: 1" - 2 lze vyjádřit nějakým Booleovým polynomem. 198 Abychom lépe rozuměli následujícímu konstruktivnímu důkazu, zavedeme v algebře 2 polynomy speciálního druhu. Definice 11.3. Polynomy tvaru ["]*_ vyt = yx n y2 n ... n y„, tóe y,- je buď xř, nebo x], se nazývají minimální průsekové polynomy proměnných x] až x„. O polynomu, který je spojením minimálních průsekových polynomů proměnných x, až xn, říkáme, že je zapsán v úplné disjunktivní (spojové) normální formě. Definice 11.3'. Polynomy tvaru \_\"_ lyi = y{ u y2 i_i ... u y„, ta/e y, /e bwďx,, neŕo x,', se nazývají maximální spojové polynomy proměnných xx až x„. O polynomu, který je průsekem maximálních spojových polynomů proměnných x, až xn, říkáme, že je zapsán v úplné konjunktivní (průsekové) normální formě. V minimálním průsekovém polynomu m(x^, ..., x„) se každá proměnná vyskytuje právě jednou, a to buď ve formě x,, nebo x\. Úplná disjunktivní normální forma je spojením několika minimálních polynomů. Protože minimálních polynomů m(xl,x„) lze zkonstruovat 2", je úplná disjunktivní normální forma /■(x,,..., x„) spojením nejvýše 2" různých minimálních polynomů. Z praktických důvodů je vhodné dodržovat v jednotlivých minimálních polynomech stejné pořadí proměnných. Analogické poznámky lze vyslovit i o úplné konjunktivní normální formě. Příklad 11.6. Následující polynomy/(x, y) a g(x,, x2, x3) jsou zapsány v úplné disjunktivní normální formě, polynom h(xi, x2, x3) je zapsán v úplné konjunktivní normální formě: f(x, y) = (x n y) u (x n y) lj (x' n ý) g(x,, x2, x3) = (x', n x2 n x3) u (x, n x2 n x3) h(xl , x2 , x3) = (x, u x2 i_i x3) n (x', lj x2 lj x3) n (x, lj x'2 lj x3) Důkaz věty 11.2. Podstata důkazu spočívá v tom, že popíšeme, jak k Booleově funkci F sestrojíme její úplnou disjunktivní normální formu. Nechť F je libovolná Booleova funkce 2" - 2. Pak ke každému vektoru v = (v1} vn) e 2" můžeme sestrojit následujícím způsobem minimální polynom mr: í \ i j I— x,, jestliže v, = 1 mv(x, - , x„) - y, n y2 n ... n y„, kde y, - -[, ^ _ Z konstrukce minimálnílio polynomu mv vyplývá, že m, nabývá hodnoty 1 přesně jenom pro vektor v. Pro jakýkoli jiný vektor u e 2" obdržíme 0. Označme množinu všech vektorů, pro něž nabývá funkce F hodnoty 1, symbolem T(F) a sestrojme ke každému vektoru v e T(F) odpovídající minimální polynom mv. Sestrojíme-li dále spojem všech těchto minimálních polynomů mv, pro v e T(F), obdržíme úplnou disjunktivní normální formu: /(x1,...,xH) = U„enr)mv(x1.....x„) 199 Na základě toho, co jsme řekli o vlastnostech minimálních polynomů, a protože jsou tyto polynomy spojeny znaky můžeme o polynomu/(x,.....x,) říci toto: Zkonstruovaný polynom f(xx,..., jej proto definuje zadanou Booleovu funkci F. Důkaz věty 11.2 je cenný především proto, že dává návod, jak k dané funkci F sestrojit odpovídající polynom. Tento polynom má úplnou disjunktivní normální formu. Uvedenou konstrukci budeme demonstrovat v příkladě 11.7. Zopakujme ještě, že každý vektor v e 2" představuje dvojkové vyjádření nějakého desítkového čísla /. Odpovídající minimální polynom se značí my. Důkaz věty 11.2 bychom mohli podat také tak, aby vedl k zadání funkce F pomocí úplné konjunktivní normální formy. Maximální polynom odpovídající výše uvedenému vektoru v pak značíme Mr Příklad 11.7. Uvažujme funkci F(x, y, z) v algebře 2, která je zadaná tabulkou 11. Tab. 11 X y z 0 0 0 0 0 1 0 0 1 1 2 0 1 0 0 3 0 1 1 0 4 1 0 0 0 5 1 0 1 1 6 1 1 0 0 7 1 1 1 1 Sestrojme úplnou disjunktivní normální formu odpovídající funkci F. Minimální polynomy odpovídající třem řádkům s jednotkami (v posledním sloupci) jsou: nty = x1 n ý n z, ra5 = x n y n z, m7 — x n y n z Hledaná úplná disjunktivní normálni forma definující funkci F proto vypadá takto: f(x, y, z) = (x' n y' n z) u (x n / n z) i_i (x n y n z) = m, u m5 lj m-, Úplnou konjunktivní normálni formu funkce F sestrojíme takto: Maximálni polynomy odpovídající řádkům s nulami jsou M0 = x i_i y u z, M2 = x lj y' u z, M3 = Xu/u/, M4 = jc' lj y u z, M6 = x" u y7 u z. 200 Úplná konjunktivní normální forma funkce F: g(x, y, z) = M0 n M2 n M3 n M4 n M6 Ukažme ještě přechod od úplné disjunktivní normální formy /funkce F k její úplné konjunktivní normální formě: a) Sestrojíme úplnou disjunktivní normální formu funkce F' (tzn. sestrojíme spojení minimálních polynomů pro řádky s nulami v posledním sloupci tabulky F) f (x, y, z) — mQ L-i m2 u m3 u m4 u m6. b) Pomocí de Morganových pravidel sestrojíme k polynomu /' jeho komple-ment f" g{x, y, z) = M0 n M2 n M3 n M4 n M6. Z předchozích úvah vyplývá, že pokud zadáme dvě úplné disjunktivní normální formy, které budou vytvořeny z různých minimálních průseků, pak budou tyto formy definovat různé Booleovy funkce. Zdůvodnění můžeme podat ještě takto: Nechť existují dvě různé úplné disjunktivní normální formy /,, f2, které určují stejnou Booleovu funkci F, tzn. f1(xl,...,xn)=f2{x1,...,x„) (11.8) Protože /, ,/2 jsou různé disjunktivní normální polynomy, musí existovat alespoň jeden minimální polynom m{xx, ..., x„), který se vyskytuje např. v/, a nevyskytuje se v f2 . Pokud sestrojíme průsek rovnosti (11.8) s tímto minimálním polynomem m(xl,..., x„), obdržíme rovnost: m(x1,...,x„) = 0 (použili jsme zobecněný distributivní zákon, formuli (8.3), a dále to, že libovolné dva různé minimální polynomy jsou disjunktní — viz cv. 11.7). Minimální polynom však nemůže určovat nulovou funkci, protože nabývá právě pro jeden vektor v e 2" hodnoty 1. Tím jsme obdrželi spor. Úvahy o zobrazení, které každé Booleově funkci přiřazuje její úplnou disjunktivní normální formu, nás vedou k vyslovení následujícího lemmatu. Lemma 11.4. Množina A„ všech Booleových funkcín proměnných a množinaP„ všech Booleových polynomů n proměnných majících úplnou disjunktivní normální formu v Booleově algebře 2 jsou navzájem ekvivalentní. Množina P„ všech polynomů n proměnných majících úplnou disjunktivní normální formu je uzavřená vzhledem k operacím n, ' (viz cv. 11.8), a tvoří proto Booleovu algebru. Poznamenejme, že toto tvrzení také bezprostředně vyplývá z mze uvedené věty 11.4. Nulou této algebry je nulový polynom, který vznikne 201 jako spojení prázdné množiny minimálních polynomů, jednotkou je polynom, který vznikne spojením všech 2" minimálních polynomů, a atomem je právě každý minimální polynom. Zobrazení, které jsme zavedli v důkazu věty 11.2 určuje izomorfismus algeber An a P„. Hasseův diagram Booleovy algebry P„ má nejníže nulu, v prvním patře všechny minimální polynomy, v druhém patře všechna spojení právě dvou minimálních polynomů atd. Nejvýše je jednotka, která vznikne spojením všech minimálních polynomů. Hasseův diagram algebry P„ lze proto načrtnout tak, aby vypadal stejně jako diagram algebry A„ (viz poznámka na str. 194). Naše úvahy shrneme do následující věty. Věta 11.3. NechťPn je množina všech polynomů n proměnných majících úplnou disjunktivnínormálníformu vBooleověalgebře 2. PakP„ tvoříBooleovu algebru, jejímiž atomy jsou právě všechny minimální polynomy m(xu x„). Algebra P „je izomorfní s algebrou A„ všech Booleových funkcíF\ 1" — 2. Věta 11.3'. Nechť Q„ je množina všech polynomů n proměnných majících úplnou konjunktivní normální formu v Booleově algebře 2. Pak Qn tvoří Booleovu algebru, jejímiž atomy jsou právě všechny maximální polynomy M[xu ...,xj. Algebra Q„je izomorfní s algebrou A„ všech Booleových funkcí F: 2" -» 2. Poznámka. V kapitole 10 jsme ukázali čtyři příklady navzájem izomorfních Booleových algeber majících 2'2"1 prvků, kde n je určité přirozené číslo. Tyto algebry jsou uvedeny v příkladech 10.8, 10.9, 10.10 a 10.11. Nyní k nim můžeme přidat další tři druhy. Jsou to: — algebra A„ všech Booleových funkcí n proměnných definovaných v algebře 2. Atomy této algebry jsou všechny funkce, které nabývají právě jednou hodnoty 1; — algebra P„ všech úplných disjunktivních normálních forem n proměnných v algebře 2. Atomy této algebry jsou právě všechny minimální polynomy m(xí,..., x„); — algebra Q„ všech úplných konjunktivních normálních forem n proměnných v algebře 2. Atomy této algebry jsou právě všechny maximální polynomy M[x,,..., x„). Uvedené druhy algeber mají 2 "atomů a 2'2"' prvků. Pro n = 1 a n— 2 jsou jejich Hasseovy diagramy znázorněny na obr. 62a, b. V následující části se budeme zabývat úpravou libovolného polynomu f(x,,..., x„) z algebry 2 na úplnou disjunktivní normální formu. Popis konstrukce: Konstrukce úplné disjunktivní normální formy polynomu /: 0. Nechť/(x,,..., x„) je polynom n proměnných v algebře 2. 1. Pokud/(x-!,..., x„) obsahuje čárkované závorky, pak lze pomocí de Morga-nových pravidel (viz formule (8.13) a (8.13')) přemístit tyto čárky k jednotlivým proměnným, popř. použít ještě formuli x" = x (viz formule (8.12)). 2. Pokud se v polynomu/'(x,,..., x„) vyskytuje symbol n mimo závorku, v níž je nějaký symbol u, pak můžeme tento symbol přemístit dovnitř pomocí zobecněného distributivního zákona (viz formule (8.10)). 202 3. Polynom/(xj,..., x„) lze dále upravit např. na základě následujících formulí: X n X = X X i_i X = X X n x' = 0 ínO=0 x li 0 = x 4. Pokud je polynom f(x1,..., x„) vyjádřen jako spojení průseků a přitom v některém průseku p chybí určitá proměnná x;, sestrojíme průsek tohoto p s jednotkou ve formě x, u x,. Tím z průseku p obdržíme spojem dvou nových průseků, z nichž jeden bude obsahovat navíc proměnnou xr a druhý x';. p = p n 1 = p n (x i_i x't) = {p n X;) u {p n 4) 5. Ve všech minimálních polynomech, jejichž spojením je výsledný polynom g(xj,..., x„), vypíšeme proměnné ve stejném pořadí. Získaný polynom g má úplnou disjunktivní normální formu a přitom je roven zadanému polynomu /. Z předchozího vyplývá, že uvedené kroky jsou postačující k sestrojení úplné normální disjunktivní formy. Ukažme právě popsanou konstrukci na příkladě. Příklad 11.8. Úprava polynomu na úplnou disjunktivní normální formu. 0. Uvažujme polynom f(x, y) = [(x' n y)' n x'] u y = Úpravy polynomu /(x, y) budeme číslovat stejně, jako tomu bylo v uvedené konstrukci. 1. = [x" u /) n x'] uj= [(x u >'') n x'] u V = 2. = [(x n x') i_j (y' n x')] u y = 3. = 0 i_i (y i-i x') u y = (y n x') u y = 4. = (y' n x') u [y n (x u x')] = (y r-i x') i_i (y i-i x) lj (y n x') = 5. = (x' n y') u (x i-i y) u (x n y) = m0 u m, i_i m3 Na základě výše popsané konstrukce nebo na základě lemmatu 11.4 můžeme vyslovit následující větu. Věta 11.4. Každý Booleův polynom f(xu ...,xn) v Booleově algebře 2 lze vyjádřit právě jedním způsobem v úplné disjunktivní normální formě. Věta 11.4'. Každý Booleův polynom /'(x,, x„) v Booleově algebře 2 lze vyjádřit právě jedním způsobem v úplné konjunktivní normální formě. Poznámka. Uvažujme Booleovu algebru V„ všech polynomů/(x,,..., x„) v algebře 2. Zobrazení H, které každému polynomu /přiřadí funkci F definovanou polynomem/, je homomorfismem algebry V„ na algebru A„ všech funkcí n proměnných v algebře 2. Jádrem / homomorfismu H je ideál všech polynomů určujících nulovou funkci. Sestrojíme-li faktorovou Booleovu algebru V„/J, pak je tato algebra izomorfní s algebrou A„ a na základě věty 11.3 a 11.3' s algebrou P„ a Q„. To souvisí se skutečností, že každý blok rozkladu ty/lze charakterizovat určitou úplnou disjunktivní či konjunktivní normální formou, na niž lze polynomy tohoto bloku upravit. 203 Na předchozích stránkách jsme se seznámili se dvěma způsoby, jak upravit libovolný Booleův polynom f(x,,..., x„) na úplnou disjunktivní normální formu. Připomeňme oba tyto postupy. Jeden z nich označíme jako přímý a druhý jako nepřímý. Přímá metoda: Při této metodě upravujeme zadaný polynom tak, jak jsme vypsali v konstrukci před příkladem 11.8 a jak jsme konkrétně ukázali v příkladu 11.8. Podstatou je tedy přímá úprava zadaného polynomu na úplnou disjunktivní normální formu. Nepřímá metoda: Při této metodě nejprve k zadanému polynomu sestrojíme tabulku odpovídající Booleovy funkce a potom pomocí této tabulky zkonstruujeme úplnou disjunktivní normální formu. Postup při konstrukci této formy je popsán v důkaze věty 11.2 a konkrétní ukázku představuje příklad 11.7. Obdobně lze vyslovit obě metody i pro úpravu libovolného Booleova polynomu na úplnou konjunktivní normální formu. Na závěr článku poznamenejme, že jsme získali metodu dovolující rozhodnout o rovnosti dvou Booleových polynomů f(xí, ■■•, xn) a g{xx, • • •, xn). Stačí když např. přímou metodou upravíme polynomy / a g na úplnou disjunktivní normální formu. Pokud z obou polynomů získáme tutéž formu, pak jsou si oba uvažované polynomy f a g skutečně rovny. 11.2 Minimalizace Booleových funkcí Celá tato problematika je podstatně ovlivněna především používáním teorie Booleových algeber při konstrukcích logických obvodů, které se vyskytují v číslicových počítačích. Problematice těchto obvodů se však budeme věnovat až v následující kapitole. Nyní tuto souvislost připomínáme především proto, že od symboliky a terminologie, které jsme používali v předchozím textu, přejdeme k symbolice a terminologii, která se používá právě v aplikacích. Podrobně rozebereme Quineovu—Mc Cluskeiovu metodu minimalizace Booleových polynomů, která se stala východiskem pro celou řadu dalších metod, při jejichž realizaci se využívají počítače. Úmluvy o nové symbolice a terminologii Operaci průsek začneme nazývat násobení a místo symbolu n budeme používat obvyklý symbol •. Místo průsek x n y budeme tedy psát x . y nebo pouze xy. Operaci spojení začneme nazývat sčítání a místo symbolu lj budeme používat 204 a způsoby, jak upravit ktrvní normální formu, fco přímý a druhý jako symbol +. Operaci komplement budeme nazývat negace a značit pruhem -. Tabulky 12a, b představují booleovské operace • a + v algebře 2. Pozor! Nesmíme zaměnit operaci + s operací symetrické odčítám © (viz tabulka 12c)), která je totožná s operací sčítání modulo 2. ve vypsali v konstrukci adu 11.8. Podstatou je ktivní normální formu. ■e tabulku odpovídající : . _r nou disjunktivní sán v důkaze věty 11.2 lého Booleova polyno- idu dovolující rozhod-Mfffo,—, xn). Stačí ".- '-tr-inou disjunktivní formu, pak jsou si oba Tab. 12a především používáním odů. které se vyskytují ak budeme věnovat až iedevším proto, že od : •• textu, přejdeme ach. Podrobně rozebe-tooleových polynomů, při jejichž realizaci se bolu - budeme použí--: \ nebo pouze xy. b ^ budeme používat 0 1 0 1 0 0 0 1 Tab . 12b + 0 1 0 0 1 1 1 1 Tab. 12c e 0 1 0 1 0 1 1 0 Protože se v dalších výrazech budou vyskytovat jak proměnné, tak i jejich negace, budeme pro jejich označení používat slovo literál. Literál proto značí jak proměnnou, tak i její negaci. Příklady čtyř různých literálů jsou x, x, y, z. Součinovým členem nebo pouze součinem nazveme průsek několika literálů. Součtovým členem nebo pouze součtem nazveme spojení několika literálů. Součinovými členy jsou např. x n y n ž nebo x n y. Součtovými členy jsou např. xf u y u 2 nebo x' u y u z . Tyto termy však budeme zapisovat po řadě xyž, xy, x + y + z a x + y + z. Součtem součinových členů rozumíme spojení několika součinových členů. Příkladem součtu součinových členů jsou např. termy (x n y n z) u (x' n n y n z) i_i (x' n y' n z') nebo (x' n y n z) i_! z' u (x n y), které budeme zapisovat: xyz + xy: + xýž nebo xyz + ž + xy. Součinem součtových členů rozumíme průsek několika součtových členů. Příkladem součinu součtových členů jsou termy (x lj y i_j z') n (x u ý u z) n (.ť u y) nebo x n (y u x u z'), které budeme zapisovat (x + y + z). (x + ý + ž). [x + y) nebo x(y + x + ž). Místo úplná disjunktivní normální forma budeme říkat úplná součtová normální forma a místo úplná konjunktivní normálni forma budeme říkat úplná součinová normální forma. Vzhledem k úplné součtové normální formě /, kterou budeme v dalším textu neustále používat, zavedeme následující názvy: Každý součin (minimální polynom) v této formě budeme nazývat mintermem nebo termem řádu 0. Odstraníme--li z mintermu n literálů, pak obdržíme term řádu n. Např. v úplné součtové normální formě f(x, y, z) = xyž + xyž + xyz jsou mintermy xyz, xyž a xyz. Z mintermu xyz lze vytvořit tři termy prvního řádu xy, xf a yz a tři termy druhého řádu x, y, z. Pojmu minterm v úplné součinové formě odpovídá maxterm. Zde úmluvy a zavádění nových pojmů prozatím končí. 205 Vyslovme základní problém tohoto článku: Je zadána určitá Booleova funkce F mající n proměnných (např. tabulkou nebo polynomem) a my máme sestrojit polynom /, který by definoval funkci F a přitom byl mezi všemi takovými polynomy co nejjednodušší. Chceme-li se touto problematikou zabývat hlouběji, musíme v první řadě vymezil pojem „být jednodušší" mezi polynomy. Existuje celá řada i neekvivalentních definic tohoto pojmu. Záleží vždy na tom, kterou vlastnost polynomu preferujeme. Uvedeme zde na ukázku dvě takové definice. Vzhledem k tomu, že se v celém článku budeme zabývat pouze polynomy majícími tvar součtu součinových členů, budou se i tato dvě kritéria vztahovat pouze k polynomům uvedeného tvaru. Kritérium 1. Součet součinových členů / je minimální vzhledem k počtu literálů, právě když žádný Booleův polynom g, pro nějž platí g = /, neobsahuje menší počet literálů než f, přičemž počítáme i vícenásobné výskyty literálů. Např. v polynomu xyž + xýžje 6 literálů, a přitom výskyt literálů x, zje dvojnásobný. Kritérium 2. Součet součinových členů /je minimální vzhledem k počtu součinových členů, právě když žádný Booleův polynom g, pro nějž platí g = /, neobsahuje menší počet členů a pokud jich obsahuje stejně, pak neobsahuje menší počet literálů než /, přičemž počítáme i vícenásobné výskyty literálů. Příklad: Lze dokázat např. pomocí tabulky, že polynom xyz + xý~z + xyž + xyz (11.9) je roven polynomu xy + yz + xz. (11.10) Je zřejmé, že polynom (l 1.10) je jednodušší než polynom (11.9), a to jak vzhledem k počtu literálů, tak i vzhledem k počtu členů. Poznamenejme, že postup zjednodušení polynomu (11.9) na polynom (11.10) ukážeme v příkladě 11.9. Zdůrazněme, že pod pojmem minimální polynom rozumíme maximální prvek v příslušném uspořádání polynomů. Duální kritéria pro polynomy mající tvar součinu součtových členů si může čtenář vyslovit sám. Poznamenejme ještě, že jiné kritérium by se např. mohlo týkat počtu výskytu negovaných proměnných. Přistupme k problematice minimalizace. Existuje více metod, pomocí nichž můžeme daný nepříliš složitý polynom minimalizovat. Vyjmenujme na tomto místě alespoň tři nej známější: — minimalizace algebraická neboli přímá, — minimalizace pomocí Karnaughovy mapy, — metoda Quineova—Mc Cluskeiova. 206 Metoda pomocí Karnaughovy mapy je pravdepodobne ze všech nejznámější a užívá se s úspěchem především u polynomů obsahujících maximálně čtyři proměnné. Dá se však použít i pro větší počet proměnných. Touto metodou se zde zabývat nebudeme. Odkazujeme čtenáře např. na knihu [5]. Minimalizace přímá je nejjednodušší prostředek pro úpravu polynomů. Tento způsob využívá pravidla pro počítání v Booleově algebře. Ukažme si příklad: Příklad 11.9. Zjednodušme co nejvíce následující polynom: Uvedená metoda je vhodná ve velmi jednoduchých případech. Jinak je dosti riskantní a úpravy nejsou vždy jednoduché. Pro více než tři proměnné se však prakticky nedá použít. Zdůrazněme, že podstatu této metody vyjadřuje následující řetězec rovností, kde t je součin neobsahující proměnnou x ani její negaci: Součiny tx a tx nazýváme sousední součiny (termy) a dále říkáme, že součin / vznikl z jejich součtu vykráčením proměnné x. Z (ll.ll) vyplývá, že funkční hodnota součtu tx + tx vůbec nezávisí na hodnotě proměnné x. Toto zjištění budeme využívat i v následující metodě. Hlavní pozornost budeme věnovat metodě Quineově—Mc Cluskeiově, která je z hlediska algebry velmi zajímavá. Při jejím popisu budeme používat binární relaci „implikovat" mezi polynomy. Definice 11.4. Říkáme, že polynom /, implikuje polynom /\ právě když neexistuje taková kombinace hodnot proměnných, pro kterou nabývá polynom /, hodnoty 1 a současně polynom j\ hodnoty 0. Definici 11.4 lze formulovat také takto: polynom /j implikuje polynom f2, právě když funkce Fx definovaná polynomem f\ předchází před funkcí F2 definovanou polynomem f2, tzn. /] implikuje/, <=> FlsF2. Příklady 11.10. Polynom xy + xy implikuje polynom xy + xý + xy. Důvodem je to, že první polynom určuje funkci F25, zatímco druhý polynom určuje funkci F] (viz tabulka v příkladu 11.4) a přitom F\st Fj. Také minterm xý implikuje polynom ať + xý + xy. Obdobně i mintermy vy a xy implikují tento polynom. xyz + xyz + xyz + xyz Řešení, xyz + xyž + xýz + xyz = = (xyz + xyz) + (xýz + xyz) + (xyz + xyz) = xy(z + z) + xz(y + ý) + yz(x + x) = = xy . 1 + xz . I + yz . í = xy + xz + yz zadaný polynom Podle (8.3'). Podle (8.5). Podle (8.7) a (8.6'). tx + tx = t(x + x) = t . 1 = t (11.11) 207 Zaveďme ještě tři nové pojmy a ukažme jejich důležité vlastnosti. Tyto pojmy budou prakticky ukazovat cestu, jak se od úplné součtové normální formy nějaké funkce F dostaneme k jejímu minimálnímu polynomu. Definice 11.5. Implikantem Booleovy funkce F se nazývá každý součin, který implikuje funkci F či přesněji, který implikuje úplnou součtovou normální formu funkce F. Poznamenejme, že existuje jednoduchý způsob dovolující zjistit, zda daný součin p je implikantem funkce F. Stačí, když proměnným bez pruhů přiřadíme hodnotu 1 a proměnným s pruhem hodnotu 0. Součin p pro tuto (a jenom tuto) kombinaci hodnot proměnných nabývá hodnoty 1. Pokud pro uvedenou kombinaci hodnot proměnných nabývá i funkce F hodnoty 1, pak p je implikantem funkce F. V příkladu 11.10 jsme uvedli, že mintermy xy, xýa xy jsou implikanty polynomu xy + xý + xy. Zřejmě platí obecně, že každý minterm obsažený v úplné součtové normální formě / je implikantem /' (viz lemma 11.5). Příklad 11.11. Uvažujme polynom /(x, y, u, v) = xyuv + xyuv + xyuv + xyíii. pak implikantem tohoto polynomu je např. minterm xyuv, ale také term prvního řádu xyv a také dokonce term druhého řádu xy. Dokažme toto poslední tvrzení. Term xy nabývá hodnoty 1, právě když x = 0 a y - 1. Dosadíme-li tyto hodnoty do polynomu/, pak obdržíme: /(O, 1, u, v) = 1 . 1. uv + 1 .1. uv + 1 .1. úv + 1. 1 . uv = = u(v + v) + ú(v + v) = u. 1 + ú. 1 = u + u = 1 Mezi všemi implikanty dané funkce F nás budou zajímat především ty nejkratší. Definice 11.6. Implikant p funkce F se nazývá prostý, právě když p přestane být implikantem funkce F, pokud z něho odstraníme libovolný literát neboli pokud zvýšíme jeho řád. Příklad 11.11 (pokračování). Uvedli jsme, že součiny xyuv, xyv a xy jsou implikanty funkce F zadané polynomem /. Dokažme, že xy je prostým implikantem. Z termu druhého řádu xy lze vytvořit dva termy třetího řádu x a y. Ukážeme, že žádný z nich už není implikantem. Platí x = 1, právě když x = 0. Proto /(O, y, u, v) = 1 . yuv + 1 . yuv + 1 . yuv + 1 . yúv = =yu(v + v) + yú(v + v) = y(u + u) = y. Protože y může nabývat jak hodnoty 0, tak i hodnoty 1, může i polynom / určující funkci F nabývat jak hodnoty 0, tak i hodnoty 1. Závěr: Pro x — 1 může/nabývat hodnoty 0. Obdobně je tomu pro term y. 208 Mezi všemi součty prostých implikantů určujícími funkci F nás budou zajímat ty součty, které mají nejmenší počet členů. Definice 11.7. Součet součinových členů / určující funkci F se nazývá nezkrotitelný, právě když platí současně: 1. každý součinový člen z f je prostý implikant funkce F; 2. vynecháme-li v polynomu f libovolný člen, pak vzniklý polynom nedefinuje funkci F. Nyní uvedeme několik pro nás důležitých vlastností právě zavedených pojmů. Nechť je nenulová Booleova funkce F n proměnných vyjádřena pomocí polynomu / ve tvaru součtu součinových členů. Jestliže je p libovolný součin z /, pak pro každý vektor (v1,v2,..., vn), pro nějž p = 1, platí, že i / = 1, a tedy i funkce F má hodnotu 1. Proto lze vyslovit: Lemma 11.5. Nechť je Booleova funkce F vyjádřena pomocí polynomu f majícího tvar součtu součinových členů a nechť p je jedním z těchto součinových členů, pak p je implikant e m funkce F. Důsledkem lemmatu 11.5 je následující tvrzení: Jestliže je Booleova funkce F vyjádřena pomocí minimálního polynomu / majícího tvar součtu součinových členů, pak každý součin z /je implikantem funkce F. Jestliže funkci F vyjádříme pomocí úplné součtové normální formy / a jestliže z každého mintermu polynomu / vytvoříme zvyšováním řádu prostý implikant, pak obdržíme vyjádření funkce F pomocí součtu prostých implikantů. Proto platí: Lemma 11.6. Libovolnou nenulovou Booleovu funkci F lze zadat alespoň jedním polynomem f, který je součtem prostých implikantů. Nechťp(x,,..., xr) je implikantem Booleovy funkce F mající úplnou součtovou normální formu f(xlx„). Je zřejmé, že platí r < n. Proměnné xr + , až xn se proto vyskytují ve formě/a nevyskytují se v implikantů p. Jestliže z implikantů p vytvoříme součin s(xl,...,xn) = p(xl,...,xr).yr+J.....y„, (11.12) kde literály yr +, až y„ jsou vytvořeny po řadě z proměnných x,. t, až x„, pak součin (11.12) je sčítancem ve formě / Zdůvodnění. Nechť doplněný součinový člen s není obsažen ve formě/. Přiřadí-me-li proměnným xx až x„ takové hodnoty, aby s — 1 (to lze právě jedním způsobem), pak i implikant p = 1. Protože forma/neobsahuje součin s, nabývá pro tuto kombinaci hodnoty 0. To je však spor s předpokladem, že p je implikant funkce F, která má úplnou součtovou normální formu/. Závěr vyslovíme takto: Lemma 11.7. Jestliže je p implikantem Booleovy funkce F mající úplnou součtovou normální formu f pak forma f obsahuje všechna možná doplnění(11.12) implikantů p. 209 Příklad 11.12. Nechť p = xu je implikantem funkce F, která má úplnou součtovou normální formu f(x, y, z, «). Pak musí forma/obsahovat všechna možná doplnění součinu p. tj. xuyz, xuyž, xuýz, xuýz. (11.13). Poznamenejme ještě, že právě z těchto čtyř součinů obsažených v/získáme pomocí trojího použití formule (11.11), tj. pomocí trojího krácení, implikant p. Zaveďme ještě následující relaci mezi součinovými členy. Definice 11.8. Říkáme, že součin Sj pokrývá součin s2, právě když každý literál, který se vyskytuje v sl, vyskytuje se i v s2 ■ Poznamenejme, že relace „pokrývat" zavedená definicí 11.8 je reflexívní, anti-symetrická a tranzitivní*). Je to tedy uspořádání na množině součinů. Budeme-li tuto relaci uvažovat pouze na množině součinů, pomocí nichž může být vyjádřena daná funkce F (ve tvaru součtu součinů), pak minimálními prvky zavedeného posetu jsou mintermy a maximálními prvky jsou prosté implikanty. Příklad 11.12 (pokračování). Součin/? = xu pokrývá každýz mintermů(11.13). Vraťme se k definici 11.6. Je zřejmé, že pokud je polynom minimální (podle kteréhokoli z uvedených kritérií), pak je nezkratitelný. Obrácené tvrzení však neplatí. Můžeme říci pouze toto: Jestliže je zkonstruovaná množina všech nezkrotitelných polynomů dané funkce F, pak jsou v této množině obsaženy všechny minimální polynomy. Jestliže chceme sestrojit libovolný nezkratitelný polynom funkce F, pak musíme v první řadě sestrojit množinu všech prostých implikantů a potom z ní vybrat takovou podmnožinu, aby jejím součtem vznikl nezkratitelný polynom. Nyní máme připraveno vše k tomu, abychom popsali konstrukci minimálních polynomů funkce F. Konstrukce minimálního polynomu Booleovy funkce F. 0. Nechť F je Booleova funkce (zadaná např. pomocí tabulky nebo pomocí formule). 1. Sestrojíme úplnou součtovou normální formu / odpovídající funkci F. 2. Sestrojíme množinu všech prostých implikantů funkce F. 3. Sestrojíme množinu M všech nezkratitelných polynomů funkce F. 4. Z množiny M vybereme všechny polynomv splňující dané kritérium mini-málnosti. *) Uvažovanou relaci nazýváme tak. jak je to v technické literatuře zvykem. Jde však o relaci různou od relace zavedené v definici 1.8. 210 má úplnou součto-- - - r.r.j možná dopl- (11.13). ■ ľakáme pomo-implikant p. když každý literát, já je reflexívní, anti-součinú. Budeme-li může být vyjádřena prvky zavedeného kanty zmintermů (11.13). rr: minimální (podle ráčené tvrzení však ozina všech nezkra-' obsaženy všechny tratitelný polynom irostých implikantů rznikl nezkratitelný itnikci minimálních muky nebo pomocí ■pcí funkci F. funkce F. né kritérium mini- - - • relaci různou Nechť je zadána Booleova funkce F, pak podle bodu 1. konstrukce sestrojíme nejprve její úplnou součtovou normální formu /. Použít k tomu můžeme buď přímou, nebo nepřímou metodu uvedenou na konci článku 11.1. Nyní přistoupíme k bodu 2. konstrukce a popíšeme, jak z formy / získáme všechny prosté implikanty funkce F. Podstatou postupu je neustálé krácení sousedních součinů, tj. používání formule t.x + t.x = t. (11.14) Nejprve vykrátíme všechny možné dvojice sousedních mintermů (liší se v právč jednom literálu). Tím získáme termy 1. řádu. Potom vykrátíme všechny možné dvojice sousedních termů 1. řádu. Tím obdržíme termy 2. řádu atd. Součin p, který při tomto postupu pokryjeme kratším součinem, nemůže být prostým implikan-tem. Prostým implikantem je proto každý takový součin, který už nelze pokrýt dalším součinem. Abychom získali dobrý přehled, můžeme oba krácené sousední součiny označit hvězdičkou. Prostými implikanty jsou pak neoznačené součiny. Popsaný postup nejlépe osvětlí konkrétní příklad. Příklad 11.13. Určeme všechny prosté implikanty funkce F, mající následující úplnou součtovou normální formu: / = xyzu + xyzu + xýžu + xýzu + xyžu + xyzu = = m(, + m-, + mg + mn + mu + m15 Vykráčením m6 a m7 obdržíme xyz, m7am]5 obdržímeyzu, m9amn obdržíme xýu atd. Zapíšeme-li mintermy do prvního sloupce, termy 1. řádu získané krácením do druhého sloupce a termy 2. řádu získané krácením termů druhého sloupce do třetího sloupce, obdržíme: xyzu * xyzu * xýžu * xýzu * xyžu * xyzu * xyz yzu xýu * xžu * xzu * xxu * .17/ xu Neoznačené zůstaly pouze součiny xyz, yzu a xu, a proto jsou tyto součiny prostými implikanty funkce F. Postup, který jsme demonstrovali v příkladě 11.13, je možné zdokonalit tak, že nebudeme pracovat přímo se součiny z polynomu /, ale s dvojkovými čísly, která těmto součinům odpovídají. Původní metodu vymyslel Quine a její zdokonalení (vzhledem k použití počítačů) navrhl Mc Cluskei. Postup rozdělíme do několika kroků. 211 2a) Ve všech mintermech uspořádáme proměnné stejně a potom každému součinu přiřadíme dvojkové číslo (místo x, píšeme 1 a místo i, píšeme 0). Každému tomuto číslu dále přiřadíme jednak index termu, což je počet jedniček v dvojkovém zápisu, a dále stavový index, což je desítkový zápis tohoto dvojkového čísla (tzn. index i v zápise m,). Poznamenejme, že stavový index pro minterm n proměnných může být nejvýše roven číslu 2" - 1. Příklad 11.13 (pokračování). Ukažme pomocí tabulky 13, jak bude vypadat krok 2a) v případě formy /: Minterm Dvojkové číslo Index termu Stavový index xyzu 0110 2 6 xyzu 0111 3 7 xyzu 1001 2 9 xyzu 101 1 3 11 xyžu 1 101 3 13 xyzu 1111 4 15 Tab. 13 2b) Zápis pomocí dvojkových čísel upravíme takto: Vytvoříme skupiny dvojkových čísel se stejným indexem termu, tzn. se stejným počtem jedniček. Tyto skupiny mezi sebou uspořádáme (shora dolů) podle vzrůstajícího indexu termu. Jednotlivé skupiny od sebe oddělíme vodorovnou čárou (viz první sloupec tabulky 14). 2c) Nyní přistoupíme ke krácení dvojkových čísel. Abychom toto krácení mohli lépe popsat, připíšeme před každé dvojkové číslo i jeho stavový index. Porovnávat lze pouze čísla ze sousedních skupin. Jestliže se porovnávaná čísla liší právě v jedné dvojkové číslici (na stejném místě), zkrátíme je, označíme a nahradíme číslem novým, které zapíšeme do dalšího sloupce i se stavovými indexy obou krácených čísel. Zkrácenou číslici nahradíme pomlčkou (-), aby i nadále zůstalo zachováno původní přiřazení dvojkových číslic a literálú Příklad 11.13 (pokračování). Abychom při porovnávání dvojkových čísel na žádnou dvojici nezapomněli, vypíšeme je pomocí stavových indexů: 6,7; 6,11; 6,13; 9,7; 9,11; 9,13; 7,15; 11,15; 13,15 Krácení zapíšeme pomocí tabulky 14. Mintermy Termy 1. řádu Termy 2. řádu 6 0110 * 9 1001 * 7 0111 * 11 1011 * 13 1101 * 15 1111 * 6,7 011-9,11 10-1 * 9,13 1-01 * 7,15 -111 11,15 1-11 * 13,15 11-1 * 9,11,13,15 1 — 1 9, 13, 11, 15 1 — 1 Tab. 14 212 Neoznačená zůstala čísla 011-, -111 a 1— 1. Těm odpovídají prosté implikanty xyz, yzu a xu. Zdůrazněme, že krátit můžeme pouze taková čísla, která mají stejný počet pomlček na stejných místech a jejichž dvojkové číslice se liší právě na jednom místě. Tím je konstrukce prostých implikantů ukončena. 3. Přistupme ke konstrukci nezkratitelných polynomů. Z množiny prostých implikantů zkonstruované v bodě 2 c) je třeba vybrat takové podmnožiny, aby jejich součet definoval původní funkci F a přitom aby byl nezkratiielný. Tuto problematiku budeme řešit pomocí mřížky prostých implikantů. 3a) Mřížku prostých implikantů sestrojíme tak. že do vodorovného záhlaví vypíšeme stavové indexy odpovídající všem mintermům a do svislého záhlaví vypíšeme dvojková čísla odpovídající prostým implikantům získaným v bodě 2c). Skutečnost, že prostý implikant /; pokrývá určitý minterm, vyznačíme křížkem v příslušném políčku. Příklad 11.13 (pokračování). Vyznačme pro porovnání mřížku prostých implikantů dvojím způsobem: a) pomocí součinů v tabulce 15 Tab. 15 # I 3 xýzu xyžu 1 xyz x x yzu x x xu x x x x b) pomocí dvojkových čísel a stavových indexů v tabulce 16 Tab. 16 6 7 9 i 1 13 15 011--111 1—1 x x x x x x x x 3b) Nyní je třeba nalézt takové co nejmenší množiny prostých implikantů, aby každý minterm z/byl pokrytý některým z těchto implikantů. Z hlediska mřížky to znamená, že musíme nalézt vždy takovou co nejmenší množinu řádků, aby v každém sloupci byl alespoň jeden křížek. Je zřejmé, že pokud některý sloupec obsahuje jen jeden křížek, pak prostý implikant označující řádek tohoto křížku musí patřit do každého výběru prostých 213 implikantů. Těmto prostým implikantům říkáme podstatné implikanty a množina všech podstatných implikantů tvoří tzv. jádro. V případě, že podstatné implikanty z jádra pokrývají všechny mintermy z /, je jejich součtem minimální polynom (podle obou kritérií), čímž je vyřešen i bod 4 konstrukce. Příklad 11.13 (pokračování). Jádro tvoří dvojková čísla 011- (v prvním sloupci je jediný křížek) a 1— 1 (ve třetím, čtvrtém a pátém sloupci je jediný křížek). Těmto číslům odpovídají prosté implikanty xyzaxu. Protože tyto dva podstatné implikanty pokrývají všechny mintermy z /, platí, že minimálním polynomem funkce F je polynom xyz + xu. Obecně však prvky z jádra nemusí pokrývat všechny mintermy z / V tom případě je třeba při konstrukci nezkratitelných polynomů přidat k jádru ještě další prosté implikanty a to tak, abychom vždy „co nejúsporněji" pokryli všechny mintermy z /. Příklad 11.14. Sestrojme všechny nezkratitelné polynomy funkce F, jejíž mřížka prostých implikantů je v tabulce 17. Tab. 17 6 7 10 11 14 011- X X -110 X X 101- X X 1-10 X X Do jádra náleží zřejmě součiny odpovídající dvojkovým číslůmOll- a 101-, tzn. xyz a xyz. Abychom však pokryli všechny mintermy formy /, musíme k jádru přidat buď prostý implikant yzú (odpovídá číslu -110), nebo prostý implikant xzu (odpovídá číslu 1-10). Nezkratitelnými polynomy funkce F jsou v tomto případě xyz + xyz + yzú a xyz + xyz + xzú. (11.15) 4. Jestliže porovnáme nezkratitelné polynomy získané v bodě 3c) konstrukce pomocí příslušného kritéria minimálnosti, pak získáme hledané minimální polynomy splňující dané kritérium. Příklad 11.14 (pokračování). Booleova funkce F má dva nezkratitelné polynomy (viz (11.15)), přičemž jsou oba minimální podle obou výše uvedených kritérií. V závěru tohoto článku načrtneme ve formě poznámek některé další problémy minimalizace ve spojení s technickou praxí, i když o logických obvodech budeme pojednávat až v další kapitole. 214 implikanty a množina chny mintermy z /, je ímž je vyřešen i bod Dl 1 - (v prvním sloupci je jediný křížek). Těmto ha podstatné implikan-orynomem funkce F je irrr.y z /. V tom čidat k jádru ještě další pokryli všechny min- v funkce F, jejíž mříž- Poznámka o neurčených stavech funkce. V praxi se setkáváme s tím, že pro některé vektory z definičního oboru Booleovy funkce nem určena funkční hodnota. Těmto stavům říkáme neurčité stavy a budeme je označovat symbolem „x". V technické realizaci to znamená, že se buď příslušný vektor z definičního oboru vůbec nevyskytuje, nebo že jeho přítomnost nikterak neovlivní funkční správnost obvodu. Jinými slovy: neurčitý stav xje možné nahradit podle potřeby buď hodnotou 1, nebo hodnotou 0. Tuto skutečnost lze dobře využít právě při minimalizaci, což ukážeme na příkladě, Z matematického hlediska to znamená, že začínáme uvažovat „ne úplně" zadané Booleovy funkce. Tyto funkce však můžeme vzhledem k naší problematice vhodně dodefinovat na „úplně" zadané Booleovy funkce. Při minimalizaci jsme vycházeli z mintermů obsažených v úplné součtové normální formě. Nahradí-me-li neurčitý stav „x" hodnotou 1, pak se zvýší počet výchozích mintermů. Tím se ale rozšiřuje i možnost zvýšení řádu prostých implikantů a současně snížení počtu těchto implikantů potřebných k pokrytí všech mintermů. Zdůrazněme, že dodatečně přibrané mintermy (tj. mintermy získané nahrazením stavu x hodnotou 1) nemusíme pokrývat. Ukažme problematiku na příkladě. Příklad 11.15. Uvažujme funkci F tří proměnných zadanou tabulkou 18. Tab. 18 X y f(xyz) 0 0 0 0 0 1 0 0 1 X 2 0 i 0 1 3 0 1 1 1 4 1 0 0 1 5 1 0 1 1 6 1 1 0 1 7 1 1 1 X *am011- a 101-, tzn. ■ musíme k jádru přidat f implikant xzú (odpo-v tomto případě (11.15) bodě 3c) konstrukce minimální polyno- r.i -,:atitelné polyno-■ - _ edených kritérií. další problémy pefa obvodech budeme Sestrojíme mimmální polynom tak, jak jsme uvedli při popisu Quineovy-Mc Cluskeiovi metody: 1. / = xyž + xyz + xyž + xýz + xyž - Tab. 19 Tab. 20 Mintermy Termy 1. řádu 2 010 * 4 100 * 2,3 01-2,6 -10 4.5 10-4.6 1-0 3 011 * 5 101 * 6 110 * 2 3 4 5 6 01- X X -10 X X 10- X X 1-0 X X 215 4. Mimmálními polynomy funkce F jsou: /, = xy + xý + yi nebo f2 - xy + xý + xž Provedeme-li minimalizaci tak, jak jsme uvedli v předchozí' poznámce, tzn. nahradíme-li neurčité stavy x v druhém a osmém řádku tabulky hodnotou 1, obdržíme: 1. /' = xyz + xyž + xyz + xyž + xyz + xyž + xyz = = m, + m, + m3 + m4 + ms + mk + m7 Tab. 21 Mintermy Termy 1. řádu Termy 2. řádu 1 001 * 2 010 * 4 100 * 1,3 0-1 * 1.5 -01 * 2,3 01- * 2.6 -10 * 4.5 10- * 4.6 1-0 * 1,5,3,7 —1 2,6.3,7 -1-1, 3, 5, 7 —1 4, 6, 5, 7 1 — 2, 3, 6, 7 -1-4, 5, 6, 7 1 — 3 011 * 5 101 * 6 110 * 7 111 * 3,7 -11 * 5,7 1-1 * 6,7 11- * Tab. 22 1 2 3 4 5 6 7 —1 X X X X -1- X X X X 1— X X X X 4. Minimálním polynomem funkce F je/-, = y + x (není třeba pokrýt mj. Pokud jsme při minimaUzaci využili i stavy x, pak jsme získali minimální polynom, který je jednodušší (podle obou kritérií) než polynomy fx, /2 sestrojené obvyklou metodou minimalizace. Poznámka o minimalizaci souboru Booleových funkcí. Dosud jsme se zabývali minimalizací jedné Booleovy funkce. V praxi však existují logické obvody mající více výstupů, přičemž množina vstupů je stejná. Nechť je vstupů n a výstupů m, pak z matematického hlediska studujeme zobrazení Z: 2" -> 2"1. Toto zobrazení však můžeme považovat za m samostatných Booleových funkcí F: 1" — 2. Minimalizaci uvedeného souboru funkcí lze provést tak, že minimalizujeme každou z těchto funkcí zvlášť. Výsledné řešení však může být značně neekonomické, neboť v množinách prostých implikantů jednotlivých funkcí se mohou některé implikanty opakovat. Takovýmto implikantům říkáme skupinové implikanty. 216 Základní princip metody minimalizace souboru logických funkcí spočívá v tom, že zkonstruujeme nejen množiny prostých implikantů jednotlivých funkcí, ale také prosté skupinové implikanty všech dvojic, trojic atd. funkcí. Z těchto všech implikantů se pak vyhledá minimální množina. Je zřejmé, že při pokrývám množiny mintermú výchozích funkcí mají přednost skupinové implikanty. Poznámka o dalších metodách minimalizace. Quineovou—Mc Cluskeiovou metodou lze při ručním zpracování minimalizovat úplné součtové normální formy mající osm až deset proměnných. Při použití počítačů lze počet proměnných zvýšit až na několik desítek. Přesto se však od poloviny sedmdesátých let a zvláště pak v osmdesátých letech objevují snahy vytvořit nové metody minimalizace. Šlo především o to, aby zjednodušením algoritmu obsaženého v Quineově—Mc Cluskeiově metodě byla snížena náročnost na čas a paměť počítače. A tak se objevily další metody, které dávají prakticky stejně dobré výsledky jako uvedená metoda a které jsou časově i paměťově méně náročné. Jmenujme zde pro zajímavost tyto metody: MINI, PRESTO, PRONTO a CAMP. CVIČENÍ 11 1 Uvažujme množinu A{ všech Booleových funkcí F) jedné proměnné v Booleově algebře 2. Sestrojte tabulky operací n, u a ' v množině A1 a dále Hasseův diagram uspořádání ^ v této množině. 2 Určete počet všech funkcí jedné proměnné, dvou proměnných, tří proměnných a n proměnných v algebře 2. 3 Sestrojte úplnou disjunktivní normální formu funkcí F\, F\, F2l3 a F2i5 (viz př. 11.4). Jak vypadá tato forma pro funkci F\l K těmto funkcím sestrojte také úplnou konjunktivní normální formu. 4 Sestrojte tabulky Booleových funkcí tří proměnných x, y, z zadaných následujícími úplnými disjunktivními normálmmi formami: (x n y n z) u (x' n y n z) (x n y n /) u (jt n / n z) u (x n / n z') u (x' n y n z') lj (x' n y' n z') (x n y n z) i_j (x' n y n z) u (x' n / n Z1) 5 K funkcím ze cv. 4 sestrojte úplné konjunktivní normálni formy. 6 Sestrojte úplnou disjunktivní normální formu funkcí tří proměnných zadaných následujícími polynomy: x i_i (x n /)' lj x n y n z' (x n y n z)' n (x lj y') n (x lj z)' lj z [(x u y) n (x u z)]' lj [(x u z)' n (x u y')] 7 Dokažte, že libovolné dva různé minimální polynomy px, p2 proměnných xt,x„ jsou disjunktní, tzn.p, n p2 = 0. Návod: různé minimální polynomy se musí lišit alespoň v jedné proměnné xt (v jednom je xt a v druhém x-). Sestrojte průsek px m p2 a přitom využijte výše uvedené zjištění. 8 Dokažte, že množina Pn všech polynomů n proměnných majících úplnou disjunktivní normální formu je uzavřená vzhledem k operacím n, u a '. 217 9 Odůvodněte, proč lze libovolnou Booleovu funkci jedné proměnné F) v algebře 2 vyjádřit formulí y = (Fj(0)nx')u(FHl)n4 10 Odůvodněte, proč lze libovolnou Booleovu funkci dvou proměnných Fj v algebře 2 vyjádřit formulí Z = (f? (00) n x' n /) lj (F? (01) n x' n y) lj (F? (10) n X rn y') lj u(f?(ll)r.JCny). 11 Na základě cvičení 9 a 10 napište formuli pro vyjádření libovolné funkce n proměnných F" v algebře 2. 12 Sestrojte důkaz věty 11.2 tak, aby vedl k úplné konjunktivní normální formě. 13 Zdůvodněte přímou konstrukci úplné disjunktivní normální formy polynomu /'(x|.....x„) v algebře 2. 14 Vyslovte kritéria minimálnosti pro polynomy mající tvar součinu součtových členů. 15 Popište konstrukci minimálních polynomů majících tvar součinu součtových členů. 16 Sestrojte všechny minimální polynomy pro funkce tří proměnných, které jsou uvedeny v tabulce 23. Tab. 23. X y z f2 f, 0 0 0 0 l 1 0 1 0 0 1 0 1 0 2 0 1 0 0 0 1 3 0 1 1 0 0 1 4 1 0 0 1 1 0 5 1 0 1 1 1 0 6 1 1 0 1 0 1 7 1 1 1 1 1 0 17 Sestrojte minimální polynomy pro funkce čtyř proměnných zadané následujícími formulemi: a) /i = {xy + zux) (x + u) b) fi = ix + yu + y1') (y + u + jy)j c) /3 = xý + xyú + xýu + (xy + xýžú) ý 218 12 LOGICKÉ OBVODY V této kapitole se budeme zabývat použitím Booleových algeber při konstrukci určitých logických obvodů. Hlavní a nej důležitější součástí nejrůznějších logických automatů je logický obvod. Logický obvod přetváří vstupní signály ve výstupní signály podle žádané činnosti zařízení (viz obr. 64). Všechny uvedené signály nabývají pouze dvou hodnot, které budeme označovat 0 a 1. Tyto hodnoty signálu však nijak přímo nesouvisí se skutečnou fyzikální hodnotou signálu. Speciálním případem logických obvodů jsou tzv. kombinační logické obvody, jejichž výstupní signály jsou jednoznačně určeny kombinací současně působících vstupních signálů. Těmito obvody se budeme v další části zabývat. Logický obvod Vstupní signály Výstupní signály Obr. 64 Obvod mající n vstupů a m výstupů představuje zobrazení Z: 2" -* 2'". V další části pojednáme pouze o obvodech s n vstupy a jedním výstupem. Každý takový obvod představuje Booleovu funkci F: 2" -* 2. Výše uvedené zobrazení Z lze pak chápat jako m samostatných Booleových funkcí n proměnných. Z předchozího textu víme, že při n vstupech můžeme vytvořit celkem 2" různých kombinací vstupních signálů, a proto existuje přesně 2'2"' různých Booleových funkcí F: 2" -+ 2. Také víme, že všechny tyto funkce lze popsat pomocí Booleových polynomů. 12.1 Systém logický součin, logický součet, negace Logické obvody, o nichž budeme pojednávat, jsou vlastně fyzikální realizací Booleových funkcí. Tyto funkce, jak jsme již uvedli, lze definovat pomocí polynomů, v nichž se vyskytují pouze symboly základních Booleových operací ^ b 219 součin, součet a negace*). Abychom mohli sestavit libovolný logický obvod, budeme muset zvládnout realizaci těchto základních booleovských operací. Proto musíme mít k dispozici základní stavební prvky (viz obr. 65), které realizují po řadě logický součin, logický součet a negaci. Fyzikální podstatou těchto stavebních částí, kterým se říká logické členy nebo také hradla, se nebudeme zabývat. x.y x+y Obr. 65 Schématům, která znázorňují logické obvody, budeme říkat logické sítě (viz např. obr. 66). Jsou to vlastně ohodnocené grafy, jejichž hrany reprezentují elektrické vodiče a jejichž uzly jsou logické členy. Dva logické obvody nazveme funkčně ekvivalentní, právě když realizují stejnou Booleovu funkci. Protože Booleovy algebry jsou distributivní, jsou např. obvody znázorněné na obr. 66 funkčně ekvivalentní. Obvod na obr. 66a realizuje funkci zadanou polynomem x . (y + z), zatímco obvod na obr. 66b realizuje tutéž funkci, ale tentokráte zadanou polynomem x . y + x . z. x- y- 2- 1 Ji x[y*2) — a Q) LP xy*xz Obr. 66 Obraťme pozornost k analýze nebo jinak řečeno k logické simulaci logických obvodů. Nechť je z logických členů sestaven určitý logický obvod. Úloha zní: Určete Booleovu funkci F, kterou tento obvod realizuje. Jeden možný způsob určení funkce F spočívá v tom, že budeme postupně volit všechny možné kombinace hodnot na vstupech a podle vlastností logických členů doplníme hodnoty na jejich výstupech až k výsledné hodnotě výstupu z logického obvodu. Tak můžeme sestrojit tabulku funkce F. *) Protože Booleovy algebry úzce souvisí s logikou, nazývá se někdy navrhování logického obvodu pro počítač navrhováním logiky počítače. Proto se používá i terminologie užívaná v logice. Logické členy znázorněné na obr. 65 se např. často nazývají: člen a. člen nebo a člen ne (anglicky: and, or. not). 220 Příklad 12.1. Na obr. 67a je znázorněn určitý logický obvod se třemi vstupy. Jestliže na vstupech x, y, z budou po řadě hodnoty 1,0,1, pak na výstupu z logického obvodu bude hodnota 0. Booleova funkce, kterou tento logický obvod realizuje, proto přiřazuje vektoru (1, 0, 1) funkční hodnotu 0. Obdobně bychom mohli určit funkční hodnoty i v sedmi zbylých případech, a tak sestrojit tabulku funkce F, kterou obvod realizuje. 1 r z- & x.y 1 xy+z 1 xy+z a) Obr. 67 Druhá metoda určení Booleovy funkce F je mnohem efektivnější. Při postupném procházení obvodem od vstupů k výstupu nebudeme pracovat s konkrétními hodnotami proměnných, ale přímo s proměnnými nebo s termy, které jsou z těchto proměnných vytvořeny. U výstupu z obvodu pak obdržíme polynom odpovídající hledané Booleově funkci. Tento polynom můžeme ještě upravit a bude-li to potřeba, sestrojit na jeho základě tabulku funkce F. Příklad 12.1 (pokračování). Určeme Booleovu funkci F, která je realizována logickým obvodem znázorněným na obr. 67b. Postup určení polynomu pro funkci F jsme vepsali přímo do logické sítě. Je vidět, že uvažovaný logický obvod lze popsat formulí f(x, y, z) = xy + z. Nyní se budeme zabývat problematikou syntézy logických obvodů. Jde o úlohu opačnou k té, kterou jsme řešili v předchozí části. Nechť je zadána Booleova funkce F. Máme sestrojit logický obvod, který funkci F realizuje. Postupovat můžeme např. takto: Pokud nem funkce F zadána tabulkou, pak tuto tabulku sestavíme. Pomocí tabulky vytvoříme úplnou součtovou normální formu funkce F (viz nepřímá metoda uvedená na konci kap. 10). K této formě pak sestrojíme logickou síť. Problematiku ukážeme na příkladě. Příklad 12.2. Sestrojme logickou síť odpovídající Booleově funkci F tří proměnných zadané tabulkou 24. Úplná součtová normální forma funkce F je / = xyz + xyz + xyž + xyz = = m, + m3 + m6 + m7. (12.1) Logická síť je znázorněná na obr. 68a. 221 Tab. 24 x y z F (x, y, z) 0 0 0 0 0 1 0 0 1 1 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 1 0 1 7 1 l 1 1 xyz & xyz h xyz & r~(x,y,z) Obr. 68a Logický obvod uvedený v príklade 12.2 zřejmě nem nej ekonomičtější pro danou funkci F a tak obvykle dříve, než určitý logický obvod sestrojíme, provedeme minimalizaci příslušné úplné součtové normální formy např. metodou Quineo-vou—Mc Cluskeiovou (viz článek 11.2). Příklad 12.2 (pokračování). Pokud budeme polynom (12.1) minimalizovat, obdržíme polynom/, = xy + xz. Logický obvod odpovídající tomuto polynomu je 222 znázorněn na obr. 68b. Logické obvody vyznačené na obr. 68a, b tedy realizují stejnou Booleovu funkci a jsou proto funkčně ekvivalentní. Obvod na obr. 68b je však zřejmě ekonomičtější. .l_r lr- F(x,y,z) Obr. 68b Poznamenejme, že logickou síť libovolné Booleovy funkce zadané ve tvaru součtu součinových členů „lze načrtnout" tak, aby logické členy byly ve třech sloupcích. V posledním sloupci je člen realizující součet a počet jeho vstupů odpovídá počtu součinů. V prostředním sloupci jsou členy, které realizují součiny, a v prvním sloupci jsou členy realizující negování (viz obr. 68). Takovým logickým obvodům se říká dvoustupňové logické obvody AND—OR (neuvažujeme tvorem negací vstupních proměnných) *). 12.2 Další logické systémy První logické systémy odvozené z teorie Booleových algeber byly skutečně založené na třech logických členech realizujících logické násobení, logické sčítám a negaci. Na základě formulí (8.15) a (8.15'), které jsou bezprostředními důsledky de Morganových pravidel, však víme, že počet základních operací lze zredukovat na dvě. Uvedené formule v naší nové symbolice zapíšeme takto: [Vx,y)x.y = x + ý (12.2) (Vjc, y) x + y = x~ý (12.2') Z libovolného Booleova polynomu, v němž se mohou vyskytovat všechny základní booleovské operace, lze pomocí těchto formulí vytvořit polynomy, které jsou jim rovny a které obsahují pouze dvě z těchto operací: + a _ nebo • a ~. Tato skutečnost byla také brzy využita při tvorbě dalších logických systémů. *) Ve dvoustupňovém obvodu projde vstupní signál nejvýše dvěma logickými členy (neuvažujeme člen ne), než dosáhne výstupu. Protože na každém členu dojde k určitému zpoždění signálu, je rychlost obvodu nepřímo úměrná počtu stupňů. Dvoustupňové obvody mají tedy výhodu, že jsou poměrně rychlé. 223 Máme-li při konstrukci logického obvodu k dispozici pouze logické členy realizující sčítání a negování, lze logický součin vyjádřit způsobem, který ukazuje síť na obr. 69a. Máme-li při konstrukci logického obvodu k dispozici logické členy realizující násobení a negování, lze logický součet vyjádřit způsobem, který ukazuje síť na obr. 69b. Je bezprostředně vidět, že při konstrukci uvedených logických sítí využíváme formule (12.2) a (12.2'). 1 _ x+y 1 x +/ = x-y & xy UT-1 xy= x+y a) b) Obr. 69 Vedle původního logického systému majícího tři základní logické členy realizující logické násobení, sčítání a negování, kterému se říká úplný systém logických funkcí, tak existují i logické systémy mající pouze dva základní členy realizující buď násobení a negování, nebo sčítám a negování. Tyto systémy patří mezi tzv. minimální úplné systémy logických funkcí. Konstruktéři logických obvodů však poměrně rychle zmenšili počet základních členů až na jeden. Tomu se samozřejmě přizpůsobili i výrobci. Víme již, že existuje dvojice univerzálních operací taková (viz formule (8.28) a (8.28')), že pomocí každé z nich lze vyjádřit libovolnou Booleovu funkci. Jsou to operace ShefTerova a Pierceova. V naší současné symbolice lze tyto operace popsat pomocí následujících formulí: (Vx, y) x f y = x. y - x + ý (Vx, y)x[y = x + y = x.ý Těmto operacím odpovídá tabulka 25. Tab. 25 Shefferova operace (12.3) Pierceova operace (12.3') X y x t y x l y 0 0 1 1 0 i 1 0 L 0 1 0 1 i 0 0 224 Chceme-li dokázat, že tyto operace jsou skutečně univerzální, stačí ukázat, jak pomocí každé z nich zavést negaci a jednu z operací • nebo + . Zmíněné definice lze formulovat takto (pro libovolné x, y): x = x \ x a x + y = x f ý ' x = x l y a x. y = x J ý Logický člen, který realizuje Shefferovu operaci, se nazývá NAND (spojení anglických slov Not AND — česky: ne a) a logický člen, který realizuje Pierceovu operaci, se nazývá NOR (spojení anglických slov Not OR — česky: ne nebo). Formule (12.3) a (12.3') ukazují opodstatněnost přijatých názvů. Zabývejme se nejprve logickým členem NAND. Na obr. 70a je znázorněn logický obvod realizující logický člen NAND pomocí základních logických členů násobení a negace. Tyto dva členy jsou ve většině případů spojeny již ve výrobě v jeden standardní prvek a tím právě vzniká člen NAND. Symbolická značka členu NAND je na obr. 70b. L. x.y M I x.y I _J Obr. 70 Ukažme, jak pomocí členů NAND realizovat základní booleovské operace: negaci, násobení a sčítám. Na obr. 7 la, b jsou znázorněny dvě možnosti negování, přičemž se obě v praxi využívají, na obr. 71c, d je znázorněno násobení a sčítám. hodnota 1—I & x-1 = Jř x ■ a) x.y xy =x-y í & X.X= X b) xy = x+y lir Obr. 71 225 Nyní obraťme pozornost k logickému členu NOR. Na obr. 72a je znázorněn logický obvod realizující logický člen NOR pomocí základních logických členů sčítání a negace. Tyto dva členy jsou ve většině případů spojeny již ve výrobě v jeden standardní prvek a tím právě vzniká člen NOR. Symbolická značka členu NOR je na obr. 72b. r 1______ a) Ukažme, jak pomocí členů NOR realizovat základní booleovské operace: negaci, násobení a sčítání. Na obr. 73a, b jsou znázorněny dvě možnosti negování, na obr. 73c a d je znázorněno násobení a sčítám. x+x = x b) 9—r x*y b) Obr. 72 hodnota o- x+ 0=x x+y=x.y x+y x+y = x+y c) Obr. 73 d) Poznamenejme, že ani Shefferova, ani Pierceova operace nejsou asociativní. Např. platí {x\y)\zrx\(y\z), pokud za proměnné x, y, z dosadíme hodnoty 0, 1, 1. Proto nem obecně možné realizovat logické členy tohoto typu s více vstupy tak, že vedle sebe zapojíme více logických členů stejného typu se dvěma vstupy. Ukažme, jak pomocí logických členů NAND a NOR realizovat libovolnou Booleovu funkci. Uvažujme nejprve logický člen NAND. Nechť F je libovolná 226 Booleova funkce. K funkci F sestrojme její úplnou součtovou normální formu (popř. úplnou součinovou normální formu). Potom formu minimalizujeme. Minimální polynom upravíme tak, aby obsahoval pouze negace a negace součinů. Získaný polynom pak již snadno realizujeme pomocí logických členů NAND. Ukažme postup na konkrétních příkladech. Příklad 12.3. Nechť Booleova funkce F tří proměnných je pro jednoduchost zadána přímo minimálním polynomem f = xy + xz + v:. Upravme tento polynom následujícím způsobem: / = xy + xz + y z f = xy . xz ■ yz Takto upravený polynom již můžeme realizovat pomocí logických členů NAND. Logická síť je na obr. 74. & & xy & xz P{x,y,z) >-*■— Obr. 74 Příklad 12.4. Nechť Booleova funkce F tří proměnných je pro jednoduchost zadána přímo minimálmm polynomem (získaným z úplné součinové normální formy): f={x + y){x + z)(y + z) Upravme tento polynom tak, abychom ho mohli realizovat opět pomocí logických členů NAND. Úprava bude vypadat následovně: f=x + y-x + z- y + z f = x .ý. x. ž.ý. ž J — x .ý. x .ž.ý .ž 227 Takto upravený polynom již můžeme realizovat pomocí logických členů NAND. Logická síť je "na obr. 75. Z- li xz & & Obr. 75 Zcela analogicky lze postupovat, pokud chceme vyjádřit libovolnou Booleovu funkci pomocí logických členů NOR. Nechť F je libovolná Booleova funkce F. K funkci F sestrojíme její úplnou součtovou normální formu (popř. úplnou součinovou normální formu). Potom tuto formu minimalizujeme. Minimální polynom upravíme tak, aby obsahoval pouze negace a negace součtů. Získaný polynom potom již snadno realizujeme pomocí logických členů NOR. Ukažme postup na konkrétních příkladech. Příklad 12.5. Nechť Booleova funkce F tří proměnných je pro jednoduchost zadána přímo minimálním polynomem / = xy + xz + yz. Upravme tento polynom následujícím způsobem: f^x.y + x.z + y.z f^x+ý+x+ž+ý+ž f^x+ý+x+ž+ý+ž Konstrukci logické sítě funkce F pomocí logických členů NOR necháme čtenáři jako cvičení. Příklad 12.6. Nechť Booleova funkce F tří proměnných je pro jednoduchost zadána přímo minimálním polynomem (získaným z úplné součinové normální formy): f={x + y){x + z)(y + z) 228 Upravme tento polynom následujícím způsobem: /- (x + y) {x + z) {y + z) f=x+y+x+y+y+z Konstrukci logické sítě funkce F pomocí logických členů NOR necháme čtenáři jako cvičení. Zdůrazněme, že při konstrukci logických obvodů pomocí členů NAND postupujeme většinou tak, že zadanou funkci nejprve vyjádříme ve tvaru úplné součtové normální formy. Pak provedeme minimalizaci a teprve minimální polynom převedeme do tvaru realizovatelného pomocí členů NAND. Při konstrukci logických obvodů pomocí členů NOR vycházíme obvykle z úplné součinové normální formy. Uveďme ještě konkrétní příklad konstrukce jednoduchého logického obvodu. Příklad 12.7. Sestrojme logický obvod pro sčítám tří jednociferných dvojkových čísel, máme-li k dispozici členy NAND se dvěma, třemi a čtyřmi vstupy. Označme jednociferná dvojková čísla písmeny x, y, z. Je zřejmé, že sečteme-!i tři jednociferná dvojková čísla, obdržíme maximálně dvojciferné dvojkové číslo, které označíme ab. Proměnná b představuje číslici nultého řádu a proměnná a číslici prvního řádu nebo jinak řečeno proměnná a představuje přechod do vyššího řádu. Uvažujme proto dvě Booleovy funkce, které jsou zadány tabulkou 26. Tah. 26 X y * a b 0 0 0 0 0 0 o 1 0 1 0 i 0 0 1 0 i 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 i 0 1 1 1 1 1 Úplné součtové normální formy získané z uvedených tabulek jsou následující: a = xyz + xýz + xyž + xyz b = xyz + xyž + xyž + xyz Polynom a lze minimalizovat, zatímco polynom b nikoli. Minimální polynom pro funkci a je následující: a - xy + xz + y z 229 Upravme polynomy a a b tak, aby při návrhu logického obvodu bylo možné použít pouze logické členy NAND: = xy + xz + y z b = xyz + xyž + xýž + xyz o = xy ■ xz .yz b = xyz ■ xyž ■ xýž ■ xyz Logická síť je na obr. 76. Nechť si čtenář provede analýzu uvedeného obvodu, aby ověřil, že skutečně realizuje obě uvažované funkce. x-y xz & x- y- z- xyz & r & xyz 4 & xyz Obr. 76 230 Poznámka. Zájem používat spiš členy NAND a NOR místo členů logického součtu, součinu a negace je dán snahou o zmenšení počtu typů členů. V souvislosti se vznikem stavebnic integrovaných obvodů se však v praxi používají v jednom obvodu jak členy NAND, tak i NOR a i negace. Cesta od předepsání funkce a návrhu vysoce integrovaného obvodu k vlastní výrobě je proces velmi složitý, který vyžaduje spolupráci týmu odborníků. Např. nejjednodušší zápis polynomu nemusí vždy vést k nejlepší realizaci. Ve velkých systémech je často výhodnější zapsat některé funkce jako funkce jiných funkcí, protože je výhodnější využívat mezivýpočty než optimalizovat každou z nich. Při vytváření návrhů optimálních integrovaných obvodů se proto využívají i statistické metody a používají se i samotné počítače. Rychlý vývoj polovodičové techniky dosáhl toho, že lze na jediném polovodičovém krystalu vytvářet veliké množství elektronických součástek spojených ve složité elektronické logické obvody. Právě v souvislosti s tím se mluví o integrovaných obvodech. Technici navrhují s rostoucí integrací stále složitější obvody. V současné době se již vyrábějí obvody velmi velké integrace, jako jsou např. mikroprocesory a paměťové čipy, které obsahují až několik miliónů tranzistorů. CVIČENÍ 12 1 Načrtněte logické sítě logických obvodů realizujících funkce tří proměnných Fi> F21 ^3 ze cvičení 11.16 a přitom použijte tyto logické členy: a) součet, součin, negace; b) součet, negace; c) součin, negace; d) NAND; e) NOR. Logickou síť zkonstruujte před provedením minimalizace příslušného polynomu i po provedení minimalizace. 2 Načrtněte logické sítě logických obvodů realizujících funkce čtyř proměnných ze cvičení 11.17. Před konstrukcí proveďte minimalizaci. Použijte logické členy a) součet, součin, negace; b) součet, negace; c) součin, negace; d) NAND; e) NOR. 3 Načrtněte logickou síť logického obvodu pro automat na nápoje. Tento automat má pracovat tak, aby si zákazník po vhození příslušné mince a stisknutí jednoho z tlačítek „čaj" nebo „káva" mohl vybrat nápoj, který si přeje. K dispozici máte a) logické členy pro sčítání, násobení a negování; b) logické členy NAND s potřebným počtem vstupů. Návod. 1. Formulujte jasně úlohu a označte vstupní i výstupní proměnné. Vstupní proměnné: Výstupní proměnné: x: žádáme čaj F: přidává se čajový extrakt y: žádáme kávu C: přidává se kávový extrakt z: vhodili jsme minci H: vytéká horká voda 2. Sestavte tabulky Booleových funkcí. 3. Určete úplné součtové normální formy funkcí a minimalizujte je. 4. Načrtněte logickou síť. 231 13 DODATEK. BOOLEOVY ALGEBRY V LOGICE Vzhledem k zjednodušení vyslovíme úmluvu, že v rámci výrokové logi- ky budeme uvažovat pouze logické spojky a, v a ~l. Nechť V je třída všech formulí výrokové logiky, pak V spolu s operacemi a, v a n tvoří algebraickou strukturu, kterou nazýváme algebra formulí výrokové logiky. V třídě V zavedeme relaci „být ekvivalentní": Formule

v xp) a (~i %p v cp) je tautologie*). Ekvivalenci formulí q>, rp označíme cp = ip. Relace „být ekvivalentní" je ekvivalence v třídě V a dokonce kongruence v rámci algebry formulí. Sestrojme faktorovou množinu Vj=. Bloky rozkladu budeme značit Tv, kde

jperacemi :uli vvrokové wé když formule f označíme q> = ip. konce kongruence m. Bloky rozkladu ■ ■ ■ : - r množině kterou nazýváme Booleova algebra predikátové logiky. Jednotkou a nulou této algebry je po řadě blok tautologií a blok „vyvratitelných" formulí. Na operace V a 3 můžeme v rámci Booleovy algebry P/= pohlížet jako na zobecněné operace a a v. Algebra P j= má dvě významné podalgebry. Jsou jimi: algebra otevřených formulí a algebra uzavřených formulí. (13.1) (13.2) (13.3) = z kongruen-: dokázat, že algebra formulí ngčú nulou je blok pefc*;-":.....a., pak má p fenole tvaru wé logiky a algebru i rdad „být ekviva-T- ;' •• a algebra, 233 LITERATURA [l] Abbot, J. C: Sets, Lattice and Boolean Algebra. New York 1969. [2] Adámek, J.—Koubek, V.—Reiterman, J.: Základy obecné topologie, Praha, SNTL 1977. [3] Balcar, B.—Štěpánek, P.: Teorie množin. Praha, Academia 1986. [4] Beran. L.: Grupy a svazy. Praha, SNTL 1974. [5] Bernard, J. M.: Od logických obvodů k mikroprocesorům I. Praha, SNTL 1982. [6] Birkhoff, G.—Bartee, T. O.: Aplikovaná algebra. Bratislava, Alfa 1979. [7] Birkhoff, G— Mac Lane, S.: Prehľad modernej algebry. Bratislava, Alfa 1979. [8J Birkhoff, G.: Lattice Theory. Providence 1966. [9] Blažek, J. a kol.: Algebra a teoretická aritmetika I a II. Praha SPN, 1983, 1985. [lO] Borůvka, O.: Základy teorie grupoidú a grup. Praha 1962. [11] Bourbaki. N.: Algebra. Moskva 1962. [l2] Cohn, P.: Universaľnaja algebra. Moskva 1986. [l3] Faure. R.—Heurgonová, E.: Uspořádání a Booleovy algebry. Praha, Academia 1984. [14] Friedman, A. D.—Menon, P. R: Teorie a návrh logických obvodů. Praha, SNTL 1983. [l5] Geoseg, F.—Peak, L: Algebraic Theory of Automata. Budapešť 1972. [16] Grätzer, G.: Lattice Theory. New York, Freeman 1971. [17] Grätzer, G.: Universal algebra. Princeton, D Van Nostrand Co, Inc 1968. [18] Halmor, P.: Lectures on Boolean Algebra. New York, Van Nostrand 1966. [19] Hejný, M.—Kulich, I.—Tvarožek, J.: Čo je topológia? Bratislava, Alfa 1983. [20] Hohn, F. E.: Applied Boolean Algebra. New York, Mac Millan 1960. [2l] Jacobson, N.: Lectures in Abstract Algebra. New York 1951. [22] Ježek, J.: Univerzálni algebra a teorie modelu. Praha, SNTL 1976. [23] Kalužin. A. A.: Vvedenije v obščuju algebru. Moskva 1973. [24] Katriňak, T.—Gavalec, M.—Gedeonová, E.—Smítal, J.: Algebra a teoretická aritmetika I. Bratislava, Alfa 1985 — Praha, SNTL 1985. [25] Kelley, J. L.: Obščaja topológia. Moskva, Nauka 1968. [26] Kořínek, V.: Základy algebry. Praha, ČSAV 1956. [27] Kosmák, L.: Množinová algebra. Bratislava, Alfa 1987. [28] Kuroš, L. G.: Kapitoly z obecné algebry. Praha, Academia 1966. [29] Legéň, A.: Grupy, okruhy a zväzy. Bratislava, Alfa 1980. [30] Mac Lane, S.—Birkhoff, G.: Algebra. Bratislava, Alfa 1973. [3l] Malcev, A. L: Algebraičeskije sistemy. Moskva, 1970. [32] Nagy, J.: Vybrané partie z moderní matematiky. Praha, SNTL 1976. [33] Preparata, F. P.—Yeh, R.: Úvod do teórie diskrétnych matematických štruktúr. Bratislava, Alfa 1982. [34] Pritz, J. a kol.: Úvod do číslicové techniky. Praha, SNTL 1983. [35] Rasiowa, H.—Sikorski, R.: The Mathematics of Metamathematics. Warszawa, PWN 1963. 234 Rieger, L.: O svazech a grupách. Praha, Přírodověd, nakladatelství 1952. Rutherford, D. E.: Introduction to Lattice Theory. New York, Hafner 1965. Sikorski, R.: Bulevy algebry. Moskva, Mir 1969. Slupecki, J.—Borkowski, L.: Elementy logiky matematycnej i teorii mnogošči. Warsza-wa, PWN 1963. Szasz, G.: Introduction to Lattice Theory. New York, Mc Graw Hill 1963. Šalát, T.—Haviar, A.—Hecht, T.—Katriňak, T.: Algebra a teoretická aritmetika II. Bratislava, Alfa 1986 — Praha, SNTL 1986. Tarski, A.: Úvod do logiky a metodologie deduktivních věd. Praha, SNTL 1969. Van der Warden, B. L: Algebra. Moskva, Mir 1976. Whitesid, J. E.: Boolean Algebra and its Application. New York 1961. 235 SEZNAM UŽITÝCH SYMBOLŮ Užití Význam

nebo (nevylučovací) xp qi v xp qi nebo (vylučovací) xp (p =*> tp jestliže cp pak xp q> <=> xp q> právě když xp (v*) pro všechna x (3x) existuje aspoň jedno x (3!*) existuje právě jedno x q> je ekvivalentní s xp na základě definice N množina všech přirozených čísel Z množina všech celých čísel Q množina všech racionálních čísel R množina všech reálných čísel K množina všech komplexních čísel x e M x je prvkem množiny M x i M x není prvkem množiny M A c M množina A je podmnožinou množiny M Aa M množina A je vlastní podmnožinou množiny M Au B sjednocení množin A, B A n B průnik množin A, B A' komplement množiny A P(M) potence množiny M {M}U1 soubor množin Mř [juíMi sjednocení souboru množin M, f]ieIMi průnik souboru množin M, A x B kartézský součin množin A, B A" n-tá kartézská mocnina množiny A xRy prvek x je v relaci R s prvkem y dR první obor relace R Rd druhý obor relace R aR u Ra obor relace R 236 zRb první obor relace R příslušný prvku b aR □ druhý obor relace R příslušný prvku a R~' inverzní relace k relaci R R o Q složená relace z relací R a Q oF definiční obor zobrazení F F □ obor hodnot zobrazení F F: x i— v zobrazení F přiřazuje prvku x prvek y F: A — B F je zobrazení množiny A do množiny B F: A ™ B F je zobrazení množiny A na množinu B F: A <-» B F je vzájemně jednoznačné zobrazení množiny A na množinu B F'1 inverzní zobrazení k zobrazení F x~x prvek inverzní k prvku x x\y x dělí y x s y(mod E) x je ekvivalentní (kongruentní) s y modulo E Ml E rozklad množiny M indukovaný ekvivalencí E M/S ekvivalence indukovaná v množině M rozkladem S x ^ y x předchází před y x -a y x ostře předchází před y x — y x bezprostředně předchází před y x £: y x následuje za y x o- y x ostře následuje za y x "~ y x bezprostředně nasleduje za y x X y x je neporovnatelné s y ^P uspořádání :s v množině P (M, R) relační struktura, kde M je množina a R je uspořádání v této množině (P, y ekvivalence prvků x, y x * y relativní pseudokomplement prvku x vzhledem k prvku y x f y Schefferova operace x i y Pierceova operace m{xx, x,) minimální polynom proměnných x{ až xn M(x1,..., maximami polynom proměnných xx až x„ x', x komplement prvku x T blok ekvivalentních formulí výrokové (predikátové) logiky obsahující formuli q> 2 dvouprvková Booleova algebra {O, 1} f: í-tá Booleova funkce F mající n proměnných 238 REJSTŘÍK a abeceda 52, 62 algebra abstraktní 112 - Booleova 149 --atomární 191 — faktorová 181 — formulí 232 — intervalová 152 — obojctných množin 152 --potence množiny 150 --triviální 150 --úplná 158 - formulí predikátové logiky 232 ----otevřených 233 ---- uzavřených 233 - výrokové logiky 232 algebraická struktura 15 analýza logického obvodu 220 antireflexivnost 17 asociativnost 15 atom 31 axióm výběru 32 B blok rozkladu množiny 22 Booleova algebra 149 - funkce 193 Booleův polynom 198 - term 197 C Cantorovo diskontinuum 152 C částečné uspořádání 23 člen součinový 205 - součtový 205 D Dedekindův řez 82 definice svazu algebraická 83 — množinová 83 definiční obor zobrazení 14 de Morganova pravidla 140, 154 délka kompozičního řetězce 122 - modulárního svazu 123 --- konečná 123 dělitel společný 56 --nej větší 56 diagram Hasseův 25 diamant 68 diference 159 - symetrická 159 direktní součin algeber 167 -- svazů 97 doplněk 12 důkaz nepřímý 53 - přímý 52 dvojice neuspořádaná 12 - uspořádaná 12 E ekvivalence 21, 160 - indukovaná rozkladem 22 F faktorová Booleova algebra 181, 1 - grupa 108 - množina 22 faktorový svaz 109 filtr duální 172 - generovaný množinou 41, 93 - hlavní 41, 91 - jednotkový 91 - maximální 95 - v Booleově algebře 171 - v posetu 41 - ve svazu 91 - vlastní 91 formule 52, 62 - slučitelné 62 funkce Booleova 193 G graf kartézský 18 - uzlový 18 grupa 16 - faktorová 120 - Kleinova 107 - komutativní 16 - maximální 123 H Hasseův diagram 27 homomorfismus Booleův 174 - posetový 47 - přirozený 108, 110 - svazový 104 - struktur 16 homomorfní zobrazení 16, 104, 175 hradlo 220 I ideál duální 172 - generovaný množinou 41, 92 - hlavní 91 - maximální 95 - nulový 91 - v Booleově algebře 171 - v okruhu 17 - v posetu 40 - ve svazu 90 - vlastní 90 idempotcnce 64 identita 63 implikant 208 - podstatný 214 - prostý 208 - skupinový 217 index stavový 212 - termu 212 infimum množiny 35 interval otevřený 39 -- koncový 39 --počáteční 39 - polouzavřený 39 - uzavřený 39 - koncový 39 --počáteční 39 intervaly podobné 119 - projektivní 119 - transponované 119 izomorfismus 16, 99, 175 - Booleův 175 - posetový 42 - svazový 99 izomorfní zobrazení 16, 99, 175 - průsekové 99 - spojové 90 - obraz 42, 99, 175 - vnořeni Booleovo 175 - vnoření svazové 104 J jazyk 63 jádro 214 - homomorfismu dolní 47, 104 - - horní 47, 104 jednotka Booleovy algebry 150 - posetu 31 - svazu 74 jednotkový prvek 15 K kartézský součin množin 13 komplement 135, 141 - průsekový 141 - relativní 141 - spojový 141 komutativnost 15 kongruence v algebře 179 - v grupě 108 - ve svazu 108 konstrukce minimálního prvku 210 - reprezentanta Bool. algebry 191 --distributivního svazu 133 krácení 221 kritéria minimálnosti 206 kužel dolní 77 - horní 77 kvaziuspořádaná množina 19 kvaziuspořádání 19 - antisymetrické 23 - symetrické 21 L literál 206 logická síť 220 logické obvody funkčně ekvivalentní 220 logický člen 220 logický obvod 219 --dvoustupňový 223 --kombinační 219 M mapa Karnaughova 195 - Svobodova 195 maximální průsekový polynom 199 maxterm 205 minimalizace polynomu 204 --přímá 206 --Quineova-McCluskeiova 207 - scfciboru funkcí 216 minterm 205 240 M-modul 17 množina částečně uspořádaná 23 - dobre uspořádaná 32 - dolní 40 - faktorová 22 - generátorů 89, 165 - horní 40 - kvaziuspořádaná 19 - lexikograficky uspořádaná 30 - obojetná 61 - ohraničená 37 -- shora 37 - - zdola 37 - otevřená 17 - potenční 12 - regulární otevřená 158 - stabilní 79 - usměrněná 37 - - dolů 37 - nahoru 37 - uzavřená 17 - úplně uspořádaná 29 množinové těleso 137 monoid 16 ^ - komutativní 16 mřížka prostých implikantů 213 N NAND 225 násobení 15, 204 násobek společný 56 --nejmenší 56 negace 205 nerovnost 63 - distributivní 67 - modulární 67 neurčené stavy funkce 215 NOR 225 normální podgrupa 17 nosič algebraické struktury 15 - polosvazu 50, 51 - posetu 23 - relační struktury 15 - svazu 55 nula Booleovy algebry 150 - posetu 31 - svazu 74 O obor definiční 14 - hodnot 14 - relace 14 - druhý 14 ---příslušný k prvku 14 - první 14 ---příslušný k prvku 14 obraz Bool. algebry izomorfní 175 - prvku 14 - svazu izomorfní 69 okruh 16 - Booleův 168 - komutativní 16 - množinový 58 operace 15 - binární 15 - nulami 15 - Pierceova 160, 224 - Shefferova 160, 224 - unární 15 - základní Booleova 149 - zúžená 16 P pentagon 68 podalgebra Booleova 162 - generovaná prvkem 164 ---množinou 164 --nevlastní 163 --triviální 163 podgrupa 16 - normální 17 podmínka klesajících řetězců 35 podmnožina 12 podposet 38 podstruktura 16 podsvaz 86 - distributivní 128 - generovaný množinou 89 - vlastní 86 pokrytí 27, 210 polodistributivnost 67 pologrupa 16 polomodulárnost 68 polosvaz průsekový 50, 84 - úplný 73 - spojový 51 - - úplný 51, 85 polynom Booleův 198 ---maximální spojový 199 --minimální průsekový 199 poset 23 - duální 28 - konečný 23 - usměrněný dolů 37 - nahoru 37 potence 12 pravidlo de Morganovo 140, 154 - trojúhelníkové 18 - tvorby komplementu 154 princip duality 29, 64 prostor topologický 17, 61 --diskrétní 152 --souvislý 152 - totálně nesouvislý 152 - vektorový 17 průnik 12 průsek 50, 55 - zobecněný 72 prvek idempotentní 83 - inverzní 15 - jednotkový 15 - posetu maximální 33 - minimální 33 --nejmenší 31 ---největší 31 - zdola ireducibilní 130 prvky disjunktní 143 - neporovnatelné 29 prvoídeál 95 pseudokomplement 143 - relativní 145 reflexivnost 1" regulaňzace množím i 5* regulárni otevřena množina 158 relace 13 - antireflexivní 17 - antisymetrická 18 - binární 13 „implikovat" 207 - inverzní 14 - n-ární 13 - ostré uspořádání 26 - pokrývat 27 - reflexívní 17 - složená 14 - souvislá 18 - symetrická 18 - ternární 18 - tranzitivní 18 - unární 13 - v množině 13 - z množiny do množiny 14 - zúžená 14 rozklad množiny 21 --indukovaný ekvivalencí 22 rovina projektivní 139 rovnost 63 - izomorfická 81 R řetězec 29 - kompoziční 122, 123 řetězce ekvivalentní 120 řez Dedckindův 82 S sčítání 204 - disjunktní 159 sjednocení 12 skalár 17 smyčka 18 soubor množin 12 součet součinových členů 205 --nezkratitclný 209 součinový člen 205 součtový člen 205 souvislost 18 soused dolní 27 - horní 28 spojení 51, 55 - zobecněné 73 stav neurčitý 215 struktura algebraická 15 --asociativní 15 --distributivní 16 --komutativní 15 s inverzními prvky 15 --s jednotkovým prvkem 15 --s neutrálním prvkem 16 - relační 15 struktury izomorfní 16 suprémum množiny 36 svaz 55 - Dedekindův 114 - distributivní 125 - duální 64 - faktorový 109 - komplementární 135 - konečné délky 123 - modulární 114 - pseudokomplementární 143 --relativně 143 - Stoneův 144 - úplný 73 symetrické kvaziuspořádání 21 symetričnost 18 syntéza logických obvodů 221 systém axiómů úplný 150 Š šipka 18 tabulka Cayl - Schrodero term 52, 62. - Booleovy i - řádu n 205 - řádu 0 205 - svazu 62 těleso 16 - komutativn - množin 136 topologický p --diskrétní - - souvislý -- totálně n topologie 17 - standardní tranzitivnost 1 trojúhelník de třída 12 - univerzální U ultrafiltr 95 úplná forma d: --konjunkt:-. - součine-. - --součte. 1 l úplný syste— --logických uspořádán: :+i - duální 2> - lexikogTdri;.: - lineární % - ostré 29 --duální 26 - polosvazo-^e - svazové 55, 16 - úplné 26 uzávěr množin\ 242 T tabulka Cayleyho 151 - Schroderova 151 term 52, 62, 205 - Booleovy algebry 197 - řádu n 205 - řádu 0 205 - svazu 62 těleso 16 - komutativní 16 - množin 136 topologický prostor 17 --diskrétní 152 --souvislý 152 --totálně nesouvislý 152 topologie 17 - standardní 62 tranzitivnost 18 trojúhelník degenerovaný 18 třída 12 - univerzální 12 U ultrafiltr 95 úplná forma disjunktivní 199 --konjunktivní 199 --součinová 205 --součtová 205 úplný systém axiómů 150 --logických funkcí 224 uspořádání částečné 23 - duální 28 - lexikografické 30 - lineární 29 - ostré 29 --duální 26 - polosvazové 50 - svazové 55, 167 - úplné 26 uzávěr množiny 158 V vektor 17 vektorový prostor 17 Vennovy diagramy 140 věta autoduální 68 - Cayleyho 103 - Jordán Holderova 122 - Mac Neillova 80 - o homomorf. Bool. algeber 185 - o homomorf. grup 185 - o homomorf. svazů 110 - o množin, reprezentaci 133, 190 - Schreierova 120 - Zermelova 32 vlastnost elementární 18 - dědičná 18 - uzáverová 77 vnitřek množiny 158 vnoření posetové izomorfní 44 Z závora dolní 35 --největší 36 - horní 31 --nejmenší 36 zjemnění normálni řady 120 - řetězce 120 zobecněné spojeni ~? zobecněný průsek ~_; zobrazení 14 - homomorfní 16. 104, 175 - B. :'.eov: ! - inverzní 15 - izomorfní 16, 99, 171 - - Booteovo 175 - - pesetové 42 průsekev; - izotonr.i 41 - množiny do množiny 14 --na množinu 15 - prosté 15 - svazové 99 - vzájemně jednoznačné 15 zúžení operace 16 - relace 14 Prof. RNDr. Jan Kopka, CSc. /YflZY A BOOLCOYY ALCIBRY Obrázky narýsoval RNDr. Vlastimil Macháček Vydala Univerzita J. E. Purkyně v Ústí nad Labem roku 1991 jako svou publikaci č. 116-91 Edice Učebnice pro vysoké školy Vytiskl Tisk. s. p., Brno Počet stran 244 AA 14,81 (AA 13,50 textu, AA 1,31 grafiky) - VA 15,63 Náklad 1300 výtisků Tematická skupina a podskupina 03/2 1. vydání Cena brožovaného výtisku Kčs 45.- ISBN 80-7044-025-2