Booleova algebra

Pro zjednodušování složených výroků byla již v roce 1847 propracována anglickým matematikem Georgem Boolem algebra logiky označována jako Booleova algebra. Na dlouhou dobu upadla v zapomnění. Její význam byl doceněn až v souvislosti s reléovými obvody a s rozvojem číslicové techniky. Její použití umožňuje systematický postup při návrhu číslicového zařízení a jeho konstrukci s minimálním počtem základních operátorů.

Základní pravidla Booleovy algebry

Pravidla Boolovy algebry můžeme rozdělit do několika skupin. Každému pravidlu pro logický součin odpovídá obdobné pravidlo pro logický součet. Říkáme, že funkce logického součtu a součinu jsou navzájem duální.

Zákon dvojí negace:

Zákon o neutrálnosti konstant, agresívnosti konstant, absorpce (pohlcení) a zákon o vyloučení třetího pro logický součet a součin:

x + 0 = x         x·1 = x

x + 1 = 1          x·0 = 0

x + x = x          x·x = x

x + x = 1          x·x = 0

Komutativnost součtu a součinu:

x + y = y+ x

x·y = y·x

Asociativnost součtu a součinu:

x + y + z = x + (y + z) = (x + y) + z

x·y·z  = x·(y·z) = (x·y)·z

Distributivní zákony:

x·(y + z) = x·y + x·z

x + y·z = (x + y)·(x + z)

de Morganovy zákony:

x + y + z + … = x·y ·z·…

x·y·z·… = x + y + z + …

Využití Booleovy algebry k minimalizaci logických výrazů

Booleova algebra umožňuje upravovat logické funkce tak, aby obsahovaly co nejmenší počet základních logických operátorů a aby v  nich figuroval co nejmenší počet proměnných. V praxi se nám ale více hodí úprava, ve které využijeme co nejmenší počet pouzder obvodů co největší integrace. Tím omezíme pořizovací náklady, hmotnost, příkon, atd.

Podstata minimalizace spočívá v hledání sousedních stavů logické funkce, tj. stavů kde v jednom vystupuje určitá proměnná jako přímá a v druhém jako negovaná. Tuto proměnnou pak můžeme z těchto stavů vyloučit.

Například ve funkci

f = xyz + xyz

jsou oba stavy sousední, protože se liší pouze v proměnné z. V jednom součinu je přímá, v druhém negovaná. Tu lze z obou stavů (po vytknutí xy před závorku) vyloučit.

f = xyz + xyz = xy(z + z) = xy1 = xy

Využití zákonů absorbce

f = x(x + y) = x

f = x(x + y) = xx + xy = x + xy = x(1 + y) = x1 = x

Minimalizace funkce:

f = xy + xy + xy + x·y

f = xy + xy + xy + x·y = x(y + y) + x(y + y) = x1 + x1 = x + x = 1

Minimalizace funkce:

f = xyz + xyz + xz + x·yz

f = xyz + xyz + xyz + x·yz = z(xy + xy + xy + x·y) =

= z(x(y + y) + x(y + y)) = z(x1 + x1) = z(x + x) = z1 = z

V příkladu vidíme, že pokud se některá skupina proměnných vyskytne ve všech možných kombinacích přímých a negovaných proměnných, je při minimalizaci vyloučena!

Minimalizace majoritní funkce:

f = xyz + xyz + xyz + xyz

Protože xyz = xyz + xyz můžeme k funkci dvakrát přidat součin xyz a zapsat ji takto:

f = (xyz + xyz) + (xyz + xyz) + (xyz + xyz)

Dále postupujeme obdobně jako v předchozích příkladech

f = yz(x + x) + xz(y + y) + xy(z + z)

f = yz1 + xz1 + xy1

Minimalizované vyjádření funkce nakonec je

f = xy + yz + xz

Využití Booleovy algebry k transformaci logických výrazů

Pomocí de Morganových výrazů lze transformovat logické funkce na tvary využívající pouze operátory minimálního úplného systému logických operátorů. K tomu použijeme de Morganových zákonů upravených negací na tvar:

Úprava minimalizované majoritní funkce:

f = xy + yz + xz

=

V prvním případě použijeme operátory AND a OR, ve druhém případě pouze operátory NAND. Tím snížíme sortiment užívaných operátorů. Operátory INV, které v tomto případě nepotřebujeme, bychom mohli vytvořit z operátorů NAND například využitím pouze jednoho vstupu každého z nich. Zbývající se s ním mohou propojit, nebo připojit na konstantu log. 1.