BOOLEOVY ALGEBRY Připomeňme si, že za Booleovu algebru považujeme každou algebru (B, ∧, ∨, 0, 1,0 ) s neprázdnou množinou B, binárními operacemi průsek ∧, spojení ∨, s prvky 0, 1 ∈ B a unární operací komplement 0 , ve které jsou splněny následující identity: (1) a ∧ a = a, a ∨ a = a; (2) a ∧ b = b ∧ a, a ∧ b = b ∧ a; (3) a ∧ (b ∧ c) = (a ∧ b) ∧ c, a ∨ (b ∨ c) = (a ∨ b) ∧ c; (4) a ∧ (a ∨ b) = a, a ∨ (a ∧ b) = a; (5) a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c), (a ∧ b) ∨ (a ∧ c) = (a ∨ (b ∧ c); (6) a ∧ 1 = a, a ∨ 1 = 1, 0 ∧ a = 0, 0 ∨ a = a; (7) a ∧ a0 = 0, a ∨ a0 = 1; (8) 00 = 1, 10 = 0, (a0 )0 = a, (a ∧ b)0 = a0 ∨ b0 , (a ∨ b)0 = a0 ∧ b0 . Uvedený výčet identit není minimální, mnohé identity lze odvodit z platnosti jiných identit. Pokuste se odvodit identity (8) z identit (1) až (7). Na množině B lze definovat relaci uspořádání předpisem a ≤ b právě tehdy, když je a ∧ b = a (což je právě tehdy, když je a ∨ b = b). Prvek 0 je nejmenším prvkem uspořádané množiny (B, ≤) a prvek 1 je největším prvkem (B, ≤). Nejjednodušší Booleovou algebrou je jednoprvková algebra, kde je největší prvek roven nejmenšímu. Tato algebra se nazývá triviální Booleova algebra. Nejmenší netriviální Booleova algebra je dvouprvková Booleova algebra, která obsahuje pouze největší prvek 1 a nejmenší prvek 0, další možné Booleovy algebry jsou jsou čtyřprvková, osmiprvková a šestnáctiprvková Booleova algebra. Diagramy těchto algeber jsou zobrazeny na Obr. 4. Dalším příkladem Booleovy algebry je množina P (M ) všech podmnožin (včetně prázdné podmnožiny ∅) nějaké množiny M . Zde je průsek roven průniku podmnožin, spojení je rovno sjednocení podmnožin a komplement je doplněk podmnožiny v množině M . Ověřte platnost všech potřebných identit.
Obr. 5: Booleovy algebry Definice. Nechť (B, ∧, ∨, 0, 1,0 ) a (C, ∧, ∨, 0, 1,0 ) jsou konečné Booleovy algebry. Budeme říkat, že zobrazení f z B do C je izomorfizmus, pokud je prosté (tj. pro a 6= b je f (a) 6= f (b)), je na (tj. pro každé y ∈ C existuje x ∈ B takové, že f (x) = y), a pokud pro všechny prvky a, b ∈ B platí: 1. f (0) je nejmenší a f (1) největší prvek v (C, ∧, ∨, 0, 1,0 ); 2. je–li a ∧ b = c v (B, ∧, ∨, 0, 1,0 ), pak je f (a) ∧ f (b) = f (c) v (C, ∧, ∨, 0, 1,0 ); 3. je–li a ∨ b = c v (B, ∧, ∨, 0, 1,0 ), pak je f (a) ∨ f (b) = f (c) v (C, ∧, ∨, 0, 1,0 ); 4. je–li a0 = b v (B, ∧, ∨, 0, 1,0 ), pak je f (a)0 = f (b) v (C, ∧, ∨, 0, 1,0 ). Řekneme, že Booleovy algebry (B, ∧, ∨, 0, 1,0 ) a (C, ∧, ∨, 0, 1,0 ) jsou izomorfní, pokud existuje izomorfizmus z (B, ∧, ∨, 0, 1,0 ) do (C, ∧, ∨, 0, 1,0 ).
Existuje–li izomorfizmus z f z (B, ∧, ∨, 0, 1,0 ) do (C, ∧, ∨, 0, 1,0 ), pak inverzní zobrazení f −1 je izomorfizmus z (C, ∧, ∨, 0, 1,0 ) do (B, ∧, ∨, 0, 1,0 ). Dvě navzájem izomorfní Booleovy algebry mají naprosto stejné vlastnosti, které lze formulovat pomocí operací ∧, ∨, 0, 1,0 . Proto jsou z hlediska studia Booleových algeber nerozlišitelné, tedy stejné. Uvědomme si, že body 1. až 4. z definice izomorfizmu lze stručně zapsat takto: 1. f (0) = 0 a f (1) = 1; 2. f (a ∧ b) = f (a) ∧ f (b); 3. f (a ∨ b) = f (a) ∨ f (b); 4. f (a0 ) = (f (a))0 . Pro nás budou důležité zejména Booleovy algebry (B, ∧, ∨, 0, 1,0 ), kde množina B má konečně mnoho prvků. V dalším se proto budeme zabývat již pouze konečnými Booleovými algebrami. Konečné Booleovy algebry Atomem Booleovy algebry (B, ∧, ∨, 0, 1,0 ) budeme rozumět každý prvek, který pokrývá nejmenší prvek z (B, ∧, ∨, 0, 1,0 ), tj. atomem je prvek a ∈ B, takový, že je 0 < a a neexistuje prvek x ∈ B s vlastností 0 < x < a. To, že je prvek a atomem značíme 0 ≺ a. Duálně můžeme definovat koatom jako prvek, který je pokrýván největším prvkem 1 z (B, ∧, ∨, 0, 1,0 ), tedy prvek t je koatomen, je–li t ≺ 1. Je evidentní, že v konečné Booleově algebře je každý nenulový prvek x (tj. 0 < x) buďto atomem, nebo existuje atom d pro který je 0 ≺ d < x. Dále je jasné, že pro každý nenulový prvek x a každý atom a je buďto a ∧ x = a (je–li a ≤ x) nebo a ∧ x = 0 (není–li a ≤ x). Pro největší prvek 1 Booleovy algebry B a libovolný atom a je a ≤ 1. Nechť a1 , . . . , an jsou právě všechny atomy z B. Označme d = a1 ∨ a2 ∨ · · · ∨ an . K prvku d existuje v B komplement. tj. prvek d0 pro který platí: d∨d0 = 1 a d∧d0 = 0. Kdyby prvek byl prvek d nenulový, pak by existoval atom a v B, pro který by platilo a ≤ d0 . Jelikož je a ≤ d pro každý atom a, muselo být a ≤ d∧d0 , což je ve sporu s předpokladem d∧d0 = 0. Je tedy d0 = 0 a odsud ihned plyne, že je d = 1. Největší prvek Booleovy algebry B je tedy sjednocením všech atomů B. Toto tvrzení lze zobecnit i pro libovolný prvek b Booleovy algebry B. Stačí použít distributivní zákony a vztah b = b ∧ 1 = b ∧ (a1 ∨ a2 ∨ · · · ∨ an ). Komplementem prvku b je spojení všech atomů, které jsou nesrovnatelné s b. Tento důležitý poznatek si formulujme jako větu. Věta. Nechť B je konečná Booleova algebra, b ∈ B, b 6≤ 0 a nechť a1 , a2 . . . , ak jsou právě všechny atomy v B, které jsou menší nebo rovny prvku b (ai ≤ b) a nechť c1 , . . . , cr jsou právě všechny atomy z B, které nejsou menší nebo rovny prvku b (ci 6≤ b). Potom je b = a1 ∨ a2 ∨ · · · ∨ ak a b0 = c1 ∨ c2 ∨ · · · ∨ ck . Duálně lze provést stejné úvahy s koatomy. Dostaneme, že každý prvek x, který není největší (tj. x < 1), je buďto koatomem nebo existuje koatom t, tak, že je x < t ≺ 1 a pro každý prvek x, který není největším prvkem, je x ∨ t = t (je–li x ≤ t) nebo x ∨ t = 1 (není–li x ≤ t). Platí i tvrzení, že nejmenší prvek Booleovy algebry B je průnikem všech koatomů B a podobné tvrzení pro každý prvek. Věta. Nechť B je konečná Booleova algebra, b ∈ B, b 6≤ 1 a nechť t1 , t2 . . . , tk jsou právě všechny koatomy v B, které jsou větší nebo rovny prvku b (ti ≥ b) a nechť z1 , . . . , zr jsou právě všechny koatomy z B, které nejsou větší nebo rovny prvku b (zi 6≥ b). Potom je b = t1 ∧ a2 ∧ · · · ∧ tk a b0 = z1 ∧ c2 ∧ · · · ∧ zk . Označme symbolem At(B) množinu všech atomů Booleovy algebry (B, ∧, ∨, 0, 1,0 ) a symbolem P (At(B)) množinu všech podmnožin množiny At(B) (včetně prázdné pod-
množiny ∅). Zobrazení, které přiřazuje prvku 0 z B prázdnou množinu a každému nenulovému prvku x z B množinu všech atomů z B které jsou menší nebo rovny x je, jak si snadno ověříte, izomorfizmus z Booleovy algebry (B, ∧, ∨, 0, 1,0 ) do Booleovy algebry (P (At(B), ∩, ∪, 0, 1,0 ), kde 0 = ∅, 1 = At(B) a pro X ⊆ At(B) je X 0 = At(B) \ X. Protože konečná n–prvková množina má 2n podmnožin, je důsledkem předcházejících tvrzení to, že každá Booleova algebra, která má přesně n (n ≥ 0) atomů, má 2n prvků a že každé dvě Booleovy algebry se stejným počtem atomů jsou izomorfní. Booleovy algebry, které mají n atomů, budeme obvykle značit symbolem Bn . Triviální Booleova algebra nemá žádný atom a značíme ji B0 . Poznámka. Počet prvků konečné množiny M budeme značit symbolem |M | a nazývat mohutností množiny M . Například to, že Booleova algebra s n atomy má 2n prvků, můžeme vyjádřit symbolicky zápisem |Bn | = 2n . Další reprezentaci konečné Booleovy algebry s n atomy dostaneme následující úvahou. Nechť Booleova algebra (B, ∧, ∨, 0, 1,0 ) má n atomů, které označíme a1 , . . . , an . Každému prvku x ∈ B přiřadíme posloupnost (e1 , e2 , . . . , en ) složenou z 0 a 1 takto: pro každé přirozené číslo i ∈ {1, 2, . . . , n} je ei = 1, je–li ai ≤ x a ei = 0, není–li ai ≤ x. Prvku 0 je tak např. přiřazena posloupnost ze samých 0 (tj. 0 → (0, 0, . . . , 0)) a prvku 1 je přiřazena posloupnost ze samých 1 (tj. 1 → (1, 1, . . . , 1)). Je snadné ukázat, že toto přiřazení je izomorfizmus Booleovy algebry (B, ∧, ∨, 0, 1,0 ) na n–tou kartézskou mocninu dvouprvkové Booleovy algebry 2. Booleova algebra 2, která má pouze dva prvky 0 a 1, je tak vlastně v jistém smyslu základní Booleovou algebrou, a to proto, že každá konečná Booleova algebra s n atomy je izomorfní Booleově algebře 2n . Pro úplnost připomeňme, že všechny operace v kartézské mocnině 2n jsou definovány „po složkách”, tj. je (e1 , e2 , . . . , en ) ∧ (d1 , d2 , . . . , dn ) = (e1 ∧ d1 , e2 ∧ d2 , . . . , en ∧ dn ), (e1 , e2 , . . . , en ) ∨ (d1 , d2 , . . . , dn ) = (e1 ∨ d1 , e2 ∨ d2 , . . . , en ∨ dn ) a pro operaci komplement je (e1 , e2 , . . . , en )0 = (e01 , e02 , . . . , e0n ). Přitom je 0 ∧ 0 = 0, 0 ∧ 1 = 0, 1 ∧ 1 = 1, 0 ∨ 0 = 0, 0 ∨ 1 = 1, 1 ∨ 1 = 1, 00 = 1 a 10 = 0. Všimněme si nyní, že na Obr. 5 jsou postupně zobrazeny diagramy Booleových algeber B1 = 2, B2 = 22 , B3 = 23 a B4 = 24 . Booleovy funkce Nyní si uvedeme několik základních informací o tzv. Booleových funkcích (nebo též booleovských funkcích), které úzce souvisí s výrokovou logikou a bez jejich znalosti se neobejdou teorie o informatice a programování. Začněme příkladem takové funkce. Mějme nějakou výrokovou formuli n proměnných, např ϕ(x1 , x2 , . . . , xn ). V závislost na ohodnocení jednotlivých proměnných (vždy 0 nebo 1) je hodnota formule ϕ(x1 , x2 , . . . , xn ) vždy vždy 0 nebo 1, což je dáno tzv. pravdivostní tabulkou formule ϕ(x1 , x2 , . . . , xn ). Tato formule tak definuje zobrazení z Booleovy algebry 2n do Booleovy algebry 2, které budeme nazývat Booleovou funkcí. Pojem Booleova funkce si trochu zobecníme i na jiné algebry než dvouprvkovou algebru 2. Definice. Nechť (B, ∧, ∨, 0, 1,0 ) je konečná Booleova algebra. Booleovým výrazem v proměnných x1 , x2 , . . . , xn (nad Booleovou algebrou (B, ∧, ∨, 0, 1,0 )) budeme rozumět každý výraz získaný konečným počtem použití pravidel: 1. libovolný prvek b z B a x1 , x2 , . . . , xn jsou Booleovy výrazy; 2. jsou–li p a q Booleovy výrazy, pak jsou p ∧ q, p ∨ q a p0 opět Booleovy výrazy. Zobrazení f z B n do B, které je definováno předpisem f (x1 , x2 , . . . , xn ) = q(x1 , x2 , . . . , xn ), kde q je nějaký Booleův výraz budeme nazývat Booleovou funkcí n proměnných nad (B, ∧, ∨, 0, 1,0 ).
Poznámka. Booleovy výrazy nám silně svou definicí připomínají výrokové formule a také spolu velmi úzce souvisí. Příkladem Booleových funkcí mohou být např. funkce jedné proměnné f1 (x) = (a ∨ x) ∧ x0 , f2 (x) = a ∧ x0 nebo funkce dvou proměnných g1 (x, y) = a ∨ (x ∧ y) ∨ (x ∧ a0 ) a g2 (x, y) = a ∨ x nad nějakou Booleovou algebrou obsahující prvek a. Snadno zjistíte, že funkce f1 (x) a f2 (x) jsou totožné. Ověřte, že také funkce g1 (x, y) a g2 (x, y) jsou také totožné. Vidíme tedy, že je možno tutéž Booleovu funci vyjadřovat více způsoby, což může být nepříjemné pro zjišťování zda dvě takovéto funkce jsou či nejsou totožné. Bylo by proto vhodné najít nějaký standardní způsob vyjádřovéní Booleových funkcí, což by umoňovalo snadné rozhodovování o totožnosti dvou funkcí. Toto je možno udělat dvěmi navzájem duálními způsoby. Jsou to vyjádření Booleovských funkcí v úplné disjunktivní a konjunktivní formě. Vyjdem z toho, že každá konečná Booleova algebra s n atomy je izomorfní Booleově algebře 2n . Definice. Nechť (B, ∧, ∨, 0, 1,0 ) je konečná Booleova algebra s n atomy ( tj. je izomorfní Booleově algebře 2n ). Pro každou posloupnost k = (k1 , k2 , . . . , kn ) složenou z nul a jedniček (tj. k ∈ {0, 1}n ) definujeme elementární průsek nad proměnnými x1 , x2 , . . . , xn jakožto výraz p[k] = xk11 ∧ xk22 ∧ · · · ∧ xknn , kde x1i = xi a x0i = x0i a elementární spojení k0 k0 k0 nad proměnnými x1 , x2 , . . . , xn jakožto výraz s[k] = x11 ∨ x22 ∨ · · · ∨ xnn , kde ki0 = 0 je–li k0 k0 ki = 1 a ki0 = 1 je–li ki = 0 (tj. xi i = x pro ki = 0 a xi i = x0 pro ki = 1). Např. pro Booleovu B1 = 2 a dvě proměnné x a y máme čtyři možnosti pro elementární průseky, a to p[(1, 1)] = x ∧ y, p[(1, 0)] = x ∧ y 0 , p[(0, 1)] = x0 ∧ y, p[(0, 0)] = x0 ∧ y 0 a čtyři možnosti pro elementární spojení, a to s[(1, 1)] = x0 ∨y 0 , s[(1, 0)] = x0 ∨y, s[(0, 1)] = x∨y 0 , s[(0, 0)] = x ∧ y. Lze ukázat, že každou Booleovu funkci je možno standardně vyjádřit jako spojení všech možných výrazů f (k) ∧ p[k] resp. jako průnik všech možných výrazů f (k) ∨ s[k], kde k probíhá všechny možné posloupnosti nul a jedniček. Toto tvrzení si naformulujme jako větu. Věta. Každou Booleovu funkci f z B n do B je možno vyjádřit v úplné disjunktivní normální formě, tedy W ve tvaru f (x1 , x2 , . . . , xn ) = {f (k1 , k2 , . . . , kn ) ∧ xk11 ∧ xk22 ∧ · · · ∧ xknn , (k1 , k2 , . . . , kn ) ∈ {0, 1}n } a každou Booleovu funkci f z B n do B je možno vyjádřit v úplné konjunktivní normální formě, tedy ve tvaru V k0 k0 k0 f (x1 , x2 , . . . , xn ) = {f (k1 , k2 , . . . , kn ) ∨ x11 ∨ x22 ∨ · · · ∨ xnn , (k1 , k2 , . . . , kn ) ∈ {0, 1}n }. Důsledkem této věty je, že každá Booleova funkce f z B n do B je jednoznačně určena soustavou 2n koeficientů f (k1 , k2 , . . . , kn ) a proto jich existuje právě tolik, kolik je různých n možností jak zobrazit množinu mající 2n prvků do B, což je |B|2 . Obecně je totiž počet možností jak zobrazit k–prvkovou množinu do m–prvkové množiny mk . A protože počet n prvků Booleovy algebry B n je |B|n existuje |B||B| různých zobrazení z množiny B n do B. Z toho ihned plyne, že pro B1 = 2 je každá funkce z 2n do 2 Booleova a že pro Booleovy algebry mající více než dva prvky existují i funkce z B n do B, které nejsou Booleovy. Ukažme si na třech příkladech vyjádření Booleovy funkce v obou standardních tvarech. Nejprve uvažujme dvouprvkovou Booleovu algebru B1 obsahující prvky 0, 1 a Booleovu funkci dvou proměnných x a y nad B1 (tj. funkci z B1 × B1 do B1 ), která je zadána předpisem f (x, y) = x ∨ y 0 . Utvořme si tabulku hodnot této funkce. Dostaneme:
x y f (x, y)
0 0 1
0 1 0
1 0 1
1 1 1
Hodnoty funkce f (x, y) = x ∨ y 0 v bodech (0, 0), (0, 1), (1, 0) a (1, 1) jsou f (0, 0) = 1, f (0, 1) = 0, f (1, 0) = 1 a f (1, 1) = 1. Nyní již snadno vyjádříme funkci f (x, y) v obou normálních formách. Úplná disjunktivní normální forma funkce f (x, y) je tvaru f (x, y) = (1 ∧ x0 ∧ y 0 ) ∨ (0 ∧ x0 ∧ y) ∨ (1 ∧ x ∧ y 0 ) ∨ (1 ∧ x ∧ y) a úplná konjunktivní normální forma funkce f (x, y) je tvaru f (x, y) = (1 ∨ x ∨ y) ∧ (0 ∨ x ∨ y 0 ) ∧ (1 ∨ x0 ∨ y) ∧ (1 ∨ x0 ∨ y 0 ). Ověřme si, že úplná disjunktivní normální forma vyjadřuje skutečně stejnou funkci. Použijeme–li identity Booleovy algebry, dostaneme: f (x, y) = (1 ∧ x0 ∧ y 0 ) ∨ (0 ∧ x0 ∧ y) ∨ (1 ∧ x ∧ y 0 ) ∨ (1 ∧ x ∧ y)= = (x0 ∧ y 0 ) ∨ 0 ∨ (x ∧ y 0 ) ∨ (x ∧ y) = (x0 ∧ y 0 ) ∨ (x ∧ (y 0 ∨ y)) = (x0 ∧ y 0 ) ∨ x = = (x0 ∨ x) ∧ (y 0 ∨ x) = y 0 ∨ x = x ∨ y 0 . Ověřte, že i úplná konjunktivní normální forma vyjadřuje opět stejnou funkci. Nyní mějme Booleovu funkci dvou proměnných x a y nad B1 , která je zadána předpisem g(x, y) = (x0 ∧ y)0 . Utvořme si tabulku hodnot této funkce. Dostaneme: x y g(x, y)
0 0 1
0 1 0
1 0 1
1 1 1
Protože hodnoty funkce g(x, y) jsou v bodech (0, 0), (0, 1), (1, 0) a (1, 1) stejné jako u funkce f (x, y) z prvního příkladu, budou i jejich úplné disjunktivní a konjunktivní normální formy stejné, tj. je: g(x, y) = (1 ∧ x0 ∧ y 0 ) ∨ (0 ∧ x0 ∧ y) ∨ (1 ∧ x ∧ y 0 ) ∨ (1 ∧ x ∧ y), f (x, y) = (1 ∨ x ∨ y) ∧ (0 ∨ x ∨ y 0 ) ∧ (1 ∨ x0 ∨ y) ∧ (1 ∨ x0 ∨ y 0 ). Důsledkem tohoto zjištění je, že funkce f (x, y) a g(x, y) jsou naprosto stejné. V dalším příkladě mějme čtyřprvkovou Booleovu algebru B2 obsahující prvky 0, 1, a, b (viz Obr. 6) a Booleovu funkci dvou proměnných x a y nad B2 (tj. funkci z B2 × B2 do B2 ), která je zadána předpisem f (x, y) = (a ∧ (x ∨ y 0 )) ∨ (b ∧ (x0 ∨ y)).
1
a
b
0
Obr. 6: Booleova algebra B2
Nyní si utvoříme tabulku hodnot této funkce. Dostaneme: x y f (x, y)
0 0 1
0 a b
0 b 1
0 1 b
a 0 1
a a 1
a b 1
a 1 1
b 0 a
b a 0
b b 1
b 1 b
1 0 0
1 a a
1 b b
1 1 1
Pro určení normálních forem Booleovy funkce f (x, y) nemusíme znát její hodnoty ve všech bodech, potřebujeme znát pouze hodnoty funkce f (x, y) v bodech (0, 0), (0, 1), (1, 0) a (1, 1), které jsou f (0, 0) = 1, f (0, 1) = b, f (1, 0) = a a f (1, 1) = 1. Nyní již snadno vyjádříme funkci f (x, y) v obou normálních formách. Úplná disjunktivní normální forma funkce f (x, y) je tvaru f (x, y) = (1 ∧ x0 ∧ y 0 ) ∨ (b ∧ x0 ∧ y) ∨ (a ∧ x ∧ y 0 ) ∨ (1 ∧ x ∧ y) a úplná konjunktivní normální forma funkce f (x, y) je tvaru f (x, y) = (1 ∨ x ∨ y) ∧ (b ∨ x ∨ y 0 ) ∧ (a ∨ x0 ∨ y) ∧ (1 ∨ x0 ∨ y 0 ). Ověřte, že při použití normálních forem funkce f (x, y) dostaneme stejné výsledky. Normální tvary Booleových funkcí samozřejmě nemusí být nejjednodušším vyjádřením funkce. Je zřejmé, že například místo 1 ∧ x0 ∧ y 0 můžeme psát x0 ∧ y 0 a proto v úplné disjunktivní normální formě můžeme a obvykle budeme vynechávat koeficienty 1. Jestliže je u elementárního průseku koeficient 0, pak ho opět můžeme vynechat. Analogicky v úplné konjunktivní normální formě budeme obvykle vynechávat koeficienty 0 a elementární spojení s koeficientem 1 (např. 1 ∨ x ∨ y). Speciálně u Booleových funkcí nad dvouprvkovou algebrou jsou všechny koeficienty 0 nebo 1. V případě disjunktivní normální formy tak členy s koeficientem 0 vynecháváme a koeficient 1 nepíšeme. Obdobně v případě konjunktivní normální formy vynecháváme členy s koeficientem 1 a koeficient 0 nepíšeme. Máme–li například nějakou Booleovu funkci g(x, y) nad B2 , která splňuje podmínky g(0, 0) = g(0, 1) = g(1, 0) = g(1, 1) = 1, pak její úplná disjunktivní forma je g(x, y) = (1 ∧ x0 ∧ y 0 ) ∨ (1 ∧ x0 ∧ y) ∨ (1 ∧ x ∧ y 0 ) ∨ (1 ∧ x ∧ y). Opakovaným používánín identit 1 ∧ x = x a (x ∧ y) ∨ (x ∧ y 0 ) = x ∧ (y ∨ y 0 ) = x můžeme předpis pro g(x, y) zjednodušit následujícím způsobem: g(x, y) = (x0 ∧ y 0 ) ∨ (x0 ∧ y) ∨ (x ∧ y 0 ) ∨ (x ∧ y) = (x0 ∧ (y 0 ∨ y)) ∨ (x ∧ (y 0 ∨ y)) = x0 ∨ x = 1. Funkce g(x, y) je tedy konstantní funkce, kterou je možno zadat předpisem g(x, y) = 1. Na tomto místě snadno najdeme příklad funkce h z B2 ×B2 do B2 , která není Booleova. Stačí aby platilo h(0, 0) = h(0, 1) = h(1, 0) = h(1, 1) = 1 a v jakémkoliv jiném bodě nabývala jinou hodnotu než je 1, například h(0, a) = b, a funkce už nemůže být Booleova. Realizace Booleových funkcí klopnými obvody V této části si ukážeme, že lze každou Booleovu funkci nad dvouprvkovou Booleovou algebrou realizovat pomocí elektrických obvodů. Vstupní i výstupní hodnoty jsou pouze nuly a jedničky (např. záporné a kladné napětí). Základními kameny těchto obvodů jsou tzv. logické členy, které se obvykle nazývají invertor, součinový člen a součtový člen. V invertoru se vstupní hodnota signálu mění na opačnou hodnotu, výstupní hodnotou součinového členu je 1, právě když všechny vstupní hodnoty mají hodnotu 1 a výstupní
hodnotou součtového členu je 0, právě když všechny vstupní hodnoty jsou 0. Všimněme si, že pokud x1 , x2 , . . . xn ∈ {0, 1}, pak je x1 · x2 · · · xn = 1, právě tehdy, když platí: x1 = x2 = · · · = xn = 1 a x1 + x2 + · · · + xn = 0, právě, když je x1 = x2 = · · · = xn = 0. Víme také, že stejnou vlastnost mají operace ∧ a ∨ ve dvouprkové Booleově algebře 2. Někdy se také operace v Booleových algebrách pro jednoduchost značí · pro průsek a + pro spojení a nazývají se násobení resp. sčítání. Odtud také plynou názvy součinový a součtový člen. Tyto členy se ve schematech obvodů značí obvykle symboly, které jsou zobrazeny na Obr. 7. My je v dalším budeme schematicky znázorňovat pomocí trojúhelníků (invertor) a obdélníků s určením typu uvnitř obdélníku pomocí nápisu AND (součinový člen) nebo OR (součtový člen). Součinový člen s n vstupními hodnotami má stejné vlastnosti jako n vypínačů zapojených seriově (proud prochází pouze pokud jsou všechny zapnuty) a součtový člen s n vstupními hodnotami má stejné vlastnosti jako n vypínačů zapojených paralelně (proud prochází je–li alespoň jeden vypínač zapnut).
x
NON
x’
x1
x1
x2
x2
. . . . xn
AND x1ßx2...ßxn
. . . . xn
ˇinovy ´ c ˇlen souc
invertor
OR
x1 Þx2 ...Þxn
ˇtovy ´ c ˇlen souc
ˇinovy ´ a souc ˇtovy ´ c ˇlen Obr. 7: Invertor, souc Ukažme si na dvou příkladech realizaci Booleových funkcí pomocí klopných obvodů. Příklad. Realizujme Booleovu funkci f (x, y) = (x0 ∧ y) ∨ (x ∧ y 0 ). Realizace je uvedena na Obr. 8. x
AND OR fHx,yL
y
AND
Obr. 8: Realizace funkce f (x, y) = (x0 ∧ y) ∨ (x ∧ y 0 ). Pokud bychom ve schematu na Obr. 8 vynechali invertor pro proměnnou y, dostali bychom realizaci pro Booleovu funkci g(x, y) = (x0 ∧ y) ∨ (x ∧ y), která je zobrazena na Obr. 9. Jelikož, ale je g(x, y) = (x0 ∧ y) ∨ (x ∧ y) = y, je takovýto obvod zbytečný. x
AND OR gHx,yL
y
AND
Obr. 9: Realizace funkce g(x, y) = (x0 ∧ y) ∨ (x ∧ y).
Příklad. Realizujme Booleovu funkci f (x, y) = x0 ∧ y 0 ∧ z 0 . Realizace je uvedena na Obr. 10 v levé polovině. Na její realizace jsou potřeba čtyři logické členy. Pokud si uvědomíme, že je f (x, y) = x0 ∧ y 0 ∧ z 0 = (x ∨ y ∨ z)0 , pak je jasné, že na Obr. 10 v pravé polovině je znázorněna realizace téže funkce. Na tuto realizaci postačí dva logické členy. x y
x AND fHx,y,zL
z
y OR
fHx,y,zL
z
Obr. 10: Realizace funkce f (x, y, z) = x0 ∧ y 0 ∧ z 0 . Z uvedených příkladů vidíme, že zejména pro potřeby realizace Booleovských funkcí pomocí klopných obvodů je potřebné umět vyjádřit danou Booleovu funkci nad B1 = 2 co nejjednodušším způsobem, tedy s použitím co nejmenšího počtu symbolů. Zjednodušování výrazů s využitím identit platných v Booleových algebrách je značně pracné a vyžaduje i jistý cvik a intuici. Existují ale podstatně jednodušší způsoby. Jedna metoda je založena na používání tzv. Karnaughových map, což je vhodné pro Booleovy funkce s nejvýše čtyřmi proměnnými. Další metoda je tzv. Quin-McCluskeyho metoda. Její princip spočívá v tom, že vycházíme z nějakého vyjádření ve tvaru „spojení průseků” a opakovaně předpis zjednodušujeme používáním identity (x ∧ y) ∨ (x ∧ y 0 ) = x. Quin-McCluskeyho metoda Mějme Booleovu funkci f (x1 , x2 , . . . xn ) nad ve tvaru „spojení průseků”. Každý průsek je tvaru (xh1 1 ∧ xh2 2 ∧ · · · ∧ xhnn ), kde hi ∈ {0, 1, ∗} a x1i = xi , x0i = x0i a x∗ znamená, že se proměnná xi ve výrazu nevyskytuje. Každému průseku přiřadíme posloupnost (h1 , h2 , . . . , hn ) složenou ze symbolů 0, 1, ∗. Vahou průseku budeme rozumět počet 1 v posloupnosti (h1 , h2 , . . . , hn ). Například výrazu (x1 ∧ x02 ∧ x4 ∧ x05 ) v pěti proměnných (x1 , x2 , x3 , x4 , x5 ) přiřadíme posloupnost (1, 0, ∗, 1, 0). Váha tohoto výrazu je 2. Dále budeme postupovat dle následujících dvou pravidel. 1. Pokud mezi všemi posloupnostmi, které odpovídají jednotlivým průsekům, najdeme dvě, které jsou stejné, jednu z nich vynecháme. 2. Pokud mezi nimi najdem dvě posloupnosti, které se liší na jediném místě, a to na místě i–tém, pak obě posloupnosti nahradíme jednou posloupností, ve které dáme na i–té místo symbol ∗ a ostatní místa necháme beze změn. Toto aplikujeme na každou takovou dvojici posloupností, a to i v případě, že se jedna posloupnost objevuje ve více dvojicích. Toto opakujeme tak dlouho, až nebudou existovat dvě stejné posloupnosti nebo dvě posloupnosti, které se liší na jediném místě. Při porovnávání posloupností se stačí omezit na porovnávání těch posloupností, jejichž váhy se liší nejvýše o 1. Poznámka. Pravidlo 1. odpovídá identitě a ∨ a = a. Pravidlo 2. odpovídá identitě (a ∧ b) ∨ (a0 ∧ b) = (a ∨ a0 ) ∧ b = b, je–li na i–tém místě jedné posloupností 0 a na i–tém místě druhé posloupnosti 1, resp. identitě a ∨ (a ∧ b) = a v případě, že na i–tém místě jedné posloupnosti je symbol ∗ a na i–tém místě druhé posloupnosti je 0 nebo 1. Princip metody si vysvětlíme na jednoduchém příkladě. Příklad. Zjednodušme předpis pro Booleovu funkci tří proměnných f (x, y, z) = (x0 ∧ y 0 ∧ z 0 ) ∨ (x0 ∧ y 0 ∧ z) ∨ (x0 ∧ y ∧ z 0 ) ∨ (x0 ∧ y ∧ z) ∨ (x ∧ y 0 ∧ z).
Jednotlivým průsekům odpovídají posloupnosti (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1) a (1, 0, 1). Máme pět dvojic posloupností, které se liší pouze na jednom místě. Jsou to dvojice první a druhá, první a třetí, druhá a čtvrtá, druhá a pátá, třetí a čtvrtá. Dostaneme nový systém posloupností, a to posloupnosti: (0, 0, ∗), (0, ∗, 0), (0, ∗, 1), (∗, 0, 1) a (0, 1, ∗). V tomto systému existují dvě dvojice posloupností, které se liší pouze na jednom místě. Jsou to první a pátá posloupnost a druhá a třetí posloupnost. Po aplikaci pravidla 2. dostaneme tři posloupnosti, a to (0, ∗, ∗), (0, ∗, ∗) a (∗, 0, 1). První posloupnost vynecháme podle pravidla 1. Zůstavájí nám dvě posloupnosti (0, ∗, ∗) a (∗, 0, 1) a proto funkci f (x, y, z) = (x0 ∧ y 0 ∧ z 0 ) ∨ (x0 ∧ y 0 ∧ z) ∨ (x0 ∧ y ∧ z 0 ) ∨ (x0 ∧ y ∧ z) ∨ (x ∧ y 0 ∧ z) lze zjednodušit jako f (x, y, z) = x0 ∨ (y 0 ∧ z). Tato metoda ještě není dokonalá. Pokud chceme zjednodušit výraz x0 ∨ (x0 ∧ y ∧ z), kterému odpovídají posloupnosti (0, ∗, ∗) a (0, 1, 1), tak nemůžeme použít pravidlo 2., protože se posloupnosti liší na dvou místech. Přitom je vidět, že nějaké zjednodušení je možné. Je totiž x0 ∨ (x0 ∧ y ∧ z) = x0 podle identity a ∨ (a ∧ b) = a. Toto můžeme zobecnit a identitu a ∨ (a ∧ b) = a (která říká, že spojení dvou prvků, které jsou srovnatelné v uspořádané množině, je rovno většímu prvku) použít i v dalších případech. V námi studovaných případech to je tehdy, jesliže jeden výraz obsahuje méně proměnných a u zbylých proměnných jsou oba výrazy stejné. Například x1 ∧ x3 ∧ x04 je větší nebo roven než x1 ∧ x2 ∧ x3 ∧ x04 a je větší nebo roven než x1 ∧ x02 ∧ x3 ∧ x04 a proto je (x1 ∧x3 ∧x04 )∨(x1 ∧x2 ∧x3 ∧x04 ) = x1 ∧x3 ∧x04 a také (x1 ∧x3 ∧x04 )∨(x1 ∧x02 ∧x3 ∧x04 ) = = x1 ∧x3 ∧x04 . V řeči posloupností složených ze symbolů 0, 1, ∗ to lze vyjádřit následujícím způsobem. Řekneme, že posloupnost (p1 , . . . , pn ) je obsažena v posloupnosti (q1 , . . . , qn ) jestliže platí: kdykoliv je pi 6= ∗, pak je pi = qi , tj. posloupnosti se shodují na všech místech, kde posloupnost (p1 , . . . , pn ) nemá ∗. Spojením výrazů, které odpovídají těmto posloupnostem je rovno výrazu, který odpovídá posloupnosti (p1 , . . . , pn ). Získali jsme další pravidlo pro zjednodušování Booleových výrazů. 3. Pokud je posloupnost (p1 , . . . , pn ) obsažena v posloupnosti (q1 , . . . , qn ), lze posloupnost (q1 , . . . , qn ) vynechat. Toto pravidlo ještě neřeší vše. Pokud chceme zjednodušit výraz x0 ∨(x∧y ∧z), kterému odpovídají posloupnosti (0, ∗, ∗) a (1, 1, 1), tak nemůžeme použít pravidlo 2. (posloupnosti se liší na třech místech) a ani jedna posloupnost není obsažena v druhé. Přitom jisté zjednodušení je možné. Je totiž x0 ∨ (x ∧ y ∧ z) = (x0 ∨ x) ∧ (x0 ∨ (y ∧ z)) = x0 ∨ (y ∧ z). K tomuto zjednodušení výrazu bychom dospěli, pokud bychom při zjednodušování funkce f (x, y) = x0 ∨ (x ∧ y ∧ z) vycházeli z úplné disjunktivní normální formy funkce f (x, y), která je tvaru f (x, y) = (x0 ∧y 0 ∧z 0 )∨(x0 ∧y 0 ∧z)∨(x0 ∧y∧z 0 )∨(x0 ∧y∧z)∨(x∧y∧z). Funkci odpovídají posloupnosti (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1) a (1, 1, 1). Pouze na jednom místě se liší posloupnosti první a druhá, první a třetí, druhá a čtvrtá, třetí a čtvrtá a čtvrtá a pátá. Po aplikaci pravidla 2. dostaneme posloupnosti (0, 0, ∗), (0, ∗, 0), (0, ∗, 1), (0, 1, ∗) a (∗, 1, 1). Zde se přesně na jednom místě liší posloupnosti první a čtvrtá a druhá a třetí. Použijeme pravidlo 2. a dostaneme posloupnosti (0, ∗, ∗), (0, ∗, ∗) a (∗, 1, 1). První posloupnost vynecháme (dle pravidla 1.) a zůstanou nám pouze dvě posloupnosti (0, ∗, ∗) a (∗, 1, 1), kterým odpovídá tvar funkce f (x, y) = x0 ∨ (y ∧ z). Naformulujme si nyní Quin-McCluskeyho algoritmus pro zminimalizování Booleovy funkce f (x1 , x2 , . . . , xn ) nad Booleovou algebrou B1 = 2. Budeme postupovat takto: 1) Funkci f (x1 , x2 , . . . , xn ) si vyjádříme v úplné disjunktivní normální formě. 2) Používáním pravidel 1., 2. a 3. zjednodušíme disjunktivní tvar funkce f (x1 , x2 , . . . , xn ).
3) U posloupností odpovídajícím výrazům získaných v bodě 2) otestujeme zda jsou či nejsou obsaženy v posloupnostech, které odpovídají vyjádření funkce f (x1 , x2 , . . . , xn ) v úplné disjunktivní normální formě. K tomu si vytvoříme tabulku, kde vodorovně umístíme posloupnosti odpovídající úplné disjunktivní normální formě a svisle umístíme posloupnosti odpovídající vyjádření získanému v bodě 2). Na každém volném místě tabulky otestujeme, zda je posloupnost uvedená v řádku obsažena v posloupnosti uvedené ve sloupci. V případě, že ano, příslušné pole tabulky označíme symbolem ×, není–li tomu tak, necháme pole volné. 4) Používáním pravidla 3. nalezneme minimální vyjádření funkce f (x1 , x2 , . . . , xn ) pomocí výrazů získaných v bodě 2). Musíme vybrat nějaký minimální systém posloupností umístěných v prvním sloupci tabulky tak, aby každá z posloupností umístěných v prvním řádku tabulky byla obsažena v nějaké posloupnosti z vybraných řádků. Toho docílíme takto: je–li v nějakém sloupci pouze jeden symbol ×, pak odpovídající řádek se ve výběru musí vyskytovat. Symbolem ⊗ nahradíme všechny symboly × obsažené v tomto řádku a tím máme označeno, které posloupnosti z prvního řádku jsou obsaženy v posloupnosti z prvního sloupce našeho řádku. Tento test provedeme pro všechny sloupce a získáme tím neopomenutelné řádky. Jestliže je nyní v každém sloupci tabulky (s výjímkou prvního) alespoň jeden symbol ⊗, pak posloupnosti v prvním sloupci těchto neopomenutelných řádků určuje hledaný minimální tvar. Pokud tomu tak není, pak neopomenutelné řádky doplníme co nejmenším počtem řádků ostatních tak, aby po doplnění každý sloupec obsahoval alespoň jeden ze symbolů ⊗ nebo ×. Posloupnosti z prvního sloupce těchto řádků (neopomenutelných a doplněných) určují minimální tvar funkce. Celý postup si ukážme na následujícím příkladě. Příklad. Nalezněme minimální tvar Booleovy funkce čtyř proměnných f (x1 , x2 , x3 , x4 ) = = (x01 ∧ x02 ∧ x3 ∧ x04 ) ∨ (x01 ∧ x2 ∧ x03 ∧ x04 ) ∨ (x01 ∧ x2 ∧ x3 ∧ x4 ) ∨ (x1 ∧ x02 ∧ x3 ∧ x04 )∨ ∨(x1 ∧ x2 ∧ x04 ) ∨ (x1 ∧ x02 ∧ x3 ∧ x4 ). Funkci odpovídají posloupnosti (0, 0, 1, 0), (0, 1, 0, 0), (0, 1, 1, 1), (1, 0, 1, 0), (1, 1, ∗, 0) a (1, 0, 1, 1). Vyjádření funkce není v úplné disjunktivní normální formě. Stačí nahradit posloupnost (1, 1, ∗, 0) posloupnostmi (1, 1, 0, 0) a (1, 1, 1, 0) a tím dostaneme systém posloupností, který odpovídá vyjádření v úplné disjunktivní normální formě. Posloupnosti si seřadíme tak, aby jejich váha neklesala. Dostaneme posloupnosti (0, 0, 1, 0), (0, 1, 0, 0), (1, 1, 0, 0), (1, 0, 1, 0), (1, 1, 1, 0), (1, 0, 1, 1) a (0, 1, 1, 1). Testujeme, které dvojice posloupností se liší přesně na jednom místě a aplikujeme bod 2. Dostaneme posloupnosti (∗, 0, 1, 0), (∗, 1, 0, 0), (1, 0, 1, ∗), (1, ∗, 1, 0), (1, 1, ∗, 0) a (0, 1, 1, 1). Tyto posloupnosti již nelze více upravit. Proto si podle bodu 3) vytvoříme tabulku z těchto posloupností a z posloupností odpovídajících vyjádření funkce v úplné disjunktivní normální formě. (0, 0, 1, 0) (0, 1, 0, 0) (1, 0, 1, 0) (1, 1, 0, 0) (0, 1, 1, 1) (1, 0, 1, 1) (1, 1, 1, 0) (∗, 0, 1, 0) (∗, 1, 0, 0) (1, 0, 1, ∗) (1, ∗, 1, 0) (1, 1, ∗, 0) (0, 1, 1, 1)
Dále provedeme test, zda posloupnosti z prvního sloupce jsou obsaženy v posloupnostech z prvního řádku. (0, 0, 1, 0) (0, 1, 0, 0) (1, 0, 1, 0) (1, 1, 0, 0) (0, 1, 1, 1) (1, 0, 1, 1) (1, 1, 1, 0) (∗, 0, 1, 0) × × (∗, 1, 0, 0) × × (1, 0, 1, ∗) × × (1, ∗, 1, 0) × × (1, 1, ∗, 0) × × (0, 1, 1, 1) × Výpočet dokončíme podle bodu 4). Symbolem ⊗ označíme neopomenutelné řádky. (0, 0, 1, 0) (0, 1, 0, 0) (1, 0, 1, 0) (1, 1, 0, 0) (0, 1, 1, 1) (1, 0, 1, 1) (1, 1, 1, 0) (∗, 0, 1, 0) ⊗ ⊗ (∗, 1, 0, 0) ⊗ ⊗ (1, 0, 1, ∗) ⊗ ⊗ (1, ∗, 1, 0) × × (1, 1, ∗, 0) × × (0, 1, 1, 1) ⊗ Neopomenutelné řádky neobsahují symbol ⊗ v posledním sloupci. Proto musíme přidat k neopomenutelným řádkům nějaké další, tak, aby obsahovaly symbol × v posledním sloupci. V našem případě máme dvě možnosti. Můžeme přidat pátý nebo šestý řádek. Vidíme, že úloha najít minimální tvar Booleovy funkce může mít i více řešení. V našem příkladě to jsou dvě následující řešení: f (x1 , x2 , x3 , x4 ) = = (x02 ∧ x3 ∧ x04 ) ∨ (x2 ∧ x03 ∧ x04 ) ∨ (x1 ∧ x02 ∧ x3 ) ∨ (x01 ∧ x2 ∧ x3 ∧ x4 ) ∨ (x1 ∧ x3 ∧ x04 ), nebo f (x1 , x2 , x3 , x4 ) = = (x02 ∧ x3 ∧ x04 ) ∨ (x2 ∧ x03 ∧ x04 ) ∨ (x1 ∧ x02 ∧ x3 ) ∨ (x01 ∧ x2 ∧ x3 ∧ x4 ) ∨ (x1 ∧ x2 ∧ x04 ). Poznámka. Uvědomme si, že Quin-McCluskeyho metoda dává pouze minimální možný tvar vyjádření Booleovy funkce ve tvaru „spojení průseků”. V žádném případě tato metoda nedává „nejkratší možné vyjádření”. Například je–li Booleova funkce zadána předpisem f (x1 , x2 , x3 , x4 ) = x01 ∨ x02 ∨ x03 ∨ x04 , pak její vyjádření je evidentně minimální možné vyjádření ve tvaru „spojení průseků”. Vyjádření předpisu pro tuto funkci ve tvaru f (x1 , x2 , x3 , x4 ) = (x1 ∧ x2 ∧ x3 ∧ x4 )0 je jednodušší, obsahuje méně (o tři) symbolů 0 pro operaci komplement a také její realizace klopnými obvody by vyžadovala méně prvků. Na Quin-McCluskeyho metodě je cenné zejména to, že se jedná o jednoznačný algoritmicky definovaný postup. Tento postup, při kterém se pracuje s posloupnostmi, které jsou složeny z nul a jedniček, je možno pochopitelně jednoduše zautomatizovat. Příklady k procvičení 1) Nechť a, b, c, d, e jsou prvky Booleovy algebry B, Vyjádřete x0 pomocí prvků a, b, c, d, e, je–li x = a ∧ (b ∨ (c ∧ (d ∨ e))).
2) Zjednodušte co nejvíce předpis pro Booleovu funkci h(x, y) dvou proměnných, je–li h(x, y) = (x ∨ y) ∧ (x ∨ y 0 ) ∧ (x0 ∨ y) ∧ (x0 ∨ y 0 ). 3) Jaká je úplná disjunktivní normální forma Booleových funkcí jedné proměnné nad Booleovou algebrou B? 4) Jaká je úplná konjunktivní normální forma Booleových funkcí jedné proměnné nad Booleovou algebrou B? 5) Kolik existuje Booleových funkcí jedné proměnné nad Booleovou algebrou B5 s pěti atomy? 6) Nalezněte všechny funkční hodnoty všech možných Booleových funkcí jedné proměnné nad Booleovou algebrou B2 = ({0, a, b, 1}, ∧, ∨, 0, 1,0 ). Které z nich jsou prosté? 7) Kolik existuje Booleových funkcí dvou proměnné nad B2 ? 8) Které z funkcí f (x, y), g(x, y) a h(x, y) jsou Booleovy funkce? Nalezněte jejich úplné normální formy. x y f (x, y) g(x, y) h(x, y)
0 0 1 1 0
0 a b 1 0
0 b a 1 0
0 1 0 1 0
a 0 1 1 0
a a 1 b a
a b a 1 0
a 1 a b a
b 0 1 1 0
b a b 1 0
b b 1 a b
b 1 b a b
1 0 1 1 0
1 a 1 b a
1 b 1 a a
1 1 1 0 1
9) Nalezněte minimální tvar Booleovy funkce f (x1 , x2 , x3 ), je–li f (x1 , x2 , x3 ) rovno: a) (x0 ∧ y 0 ∧ z 0 ) ∨ (x0 ∧ y ∧ z 0 ) ∨ (x0 ∧ y 0 ∧ z) ∨ (x ∧ y ∧ z 0 ) ∨ (x0 ∧ y ∧ z) ∨ (x ∧ y ∧ z); b) (x0 ∧ y 0 ∧ z 0 ) ∨ (x ∧ y 0 ∧ z 0 ) ∨ (x0 ∧ y ∧ z 0 ) ∨ (x0 ∧ y ∧ z) ∨ (x ∧ y ∧ z 0 ) ∨ (x ∧ y ∧ z); c) (x0 ∧ y 0 ∧ z 0 ) ∨ (x0 ∧ y 0 ∧ z) ∨ (x ∧ y 0 ∧ z 0 ) ∨ (x ∧ y 0 ∧ z) ∨ (x ∧ y ∧ z 0 ) ∨ (x ∧ y ∧ z); d) (x0 ∧ y 0 ∧ z) ∨ (x0 ∧ y ∧ z 0 ) ∨ (x0 ∧ y ∧ z) ∨ (x ∧ y 0 ∧ z) ∨ (x ∧ y ∧ z); e) (x0 ∧ y 0 ∧ z 0 ) ∨ (x0 ∧ y ∧ z 0 ) ∨ (x0 ∧ y 0 ∧ z) ∨ (x0 ∧ y ∧ z) ∨ (x ∧ y 0 ∧ z) ∨ (x ∧ y ∧ z 0 ); f) (x0 ∧ y 0 ∧ z 0 ) ∨ (x ∧ y 0 ∧ z 0 ) ∨ (x0 ∧ y ∧ z 0 ) ∨ (x0 ∧ y ∧ z) ∨ (x ∧ y 0 ∧ z) ∨ (x ∧ y ∧ z). Výsledky 1) 2) 3) 4) 5) 6)
x0 = a0 ∨ (b0 ∧ (c0 ∨ (d0 ∧ e0 ))). h(x, y) = 0. f (x) = (f (0) ∧ x0 ) ∨ (f (1) ∧ x). f (x) = (f (0) ∨ x) ∧ (f (1) ∨ x0 ). 1 Je jich (25 )2 = 1024. Funkční hodnoty všech funkcí jsou uvedeny v následující tabulce. Prosté jsou funkce f4 , f7 , f10 a f13 . 0 a b 1 2
f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 0 0 0 0 a a a a b b b b 1 1 1 1 0 a 0 a 0 a 0 a b 1 b 1 b 1 b 1 0 0 b b a a 1 1 0 0 b b a a 1 1 0 a b 1 0 a b 1 0 a b 1 0 a b 1
7) 42 = 16. 8) Funkce f (x, y) a g(x, y) jsou Booleovy a h(x, y) není Booleova (h(1, b) 6= b). Platí: f (x, y) = (x0 ∧y 0 )∨(x∧y 0 )∨(x∧y) = x∨y 0 , g(x, y) = (x0 ∧y 0 )∨(x∧y 0 )∨(x0 ∧y) = x0 ∨y 0 . 9) Minimální tvar pro f (x1 , x2 , x3 ) je: a) x01 ∨ x2 ; b) x2 ∨ x03 ; c) x1 ∨ x02 ; d) (x01 ∧ x2 ) ∨ x3 ; e) x01 ∨ (x2 ∧ x03 ); f) např. (x01 ∧ x03 ) ∨ (x01 ∧ x2 ) ∨ (x1 ∧ x3 ).
