7.2.2. Booleovy algebry a jejich vlastnosti

V předcházejícím odstavci jsme se zmínili, že množina dvojstavových proměnných spolu s operacemi logického součtu, součinu a negace tvoří tzv. Booleovu algebru. Pojem Booleovy algebry je však obecnější, takže námi uvedená množina je jen její speciální případ. Vyvinul se v návaznosti na analogii mezi množinovými operacemi sjednocení a průnik a aritmetickými operacemi sčítání a násobení. Rozsah a důležitost této analogie objasnil jako první britský matematik George Boole (1815-1864), který položil základy algebraické teorie množin před více než 100 lety.

Obecně je Booleova algebra definována takto:

Booleova algebra je množina B prvků a, b, c, ... s následujícími vlastnostmi:

a) B má dvě binární operace,  ∧ (průnik) a  ∨  ( sjednocení ), která jsou

idempotentní a ∧ a = a ∨ a = a

komutativní a ∧ b = b ∧ a , a ∨ b = b ∨ a

asociativní a ∧ (b ∧ c) = (a ∧ b) ∧ c

a ∨ (b ∨ c) = (a ∨ b) ∨ c

b) tyto operace vyhovují zákonům absorpce

a ∧ (b ∨ b) = a ∨ (a ∧ b) = a

c) obě operace jsou distributivní

a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c )

a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c )

d) obsahuje univerzální ohraničení 0 a 1 , která vyhovují vztahům

0 ∧ a = 0 , 0 ∨ a = a ,

e) B má unární operaci ../images/kap6/a41.gif

tvoření komplementu s vlastnostmi:

../images/kap6/a52.gif a ../images/kap6/a61.gif

Dále lze z definice dokázat řadu vlastností Booleových algeber. Jsou to především zobecněné distributivní zákony:

../images/kap6/a70.gif

pro x, a1, a2 , ..., an ∈ B

../images/kap6/a72.gif

../images/kap6/a73.gif

pro ai, bj ∈ B; i = 1, 2, ..., n; j = 1, 2, ..., m, kde

../images/kap6/a74.gif

Dále se dají dokázat zobecněné de Morganovy zákony

../images/kap6/a21.gif

../images/kap6/a22.gif

Pro další výklad budeme potřebovat následující větu. Každý Booleovský výraz (tj. výraz utvořený pomocí operací "∧", "∨" a "¯"), ve kterém se vyskytuje n prvků x1, .., xn se dá vyjádřit právě jedním způsobem jako sjednocení tzv. minimálních booleovských polynomů, tj. výrazů tvaru ../images/kap6/a23.gif, kde buď ai = Xi: nebo ai = ../images/kap6/a24.gif. Tomuto tvaru Booleovského výrazů (nebo Booleovské funkce) se říká disjunktivní kanonický tvar. Minimálním booleovským polynomům se často říká mintermy (z anglického minimal polynomial term). Důkaz této věty není složitý, avšak vybočuje již z rámce těchto skript. Čtenář jej může najít v běžně dostupné literatuře.
Dá se ukázat, že pro n proměnných X1, ..., Xn existuje 2n různých minimálních polynomů X1 X2 ...Xn, ../images/kap6/a25.gif1X2... Xn, ../images/kap6/a26.gif. Z těchto polynomů pak můžeme utvořit celkem ../images/kap6/a27.gifkombinací, což je také celkový počet různých booleovských funkcí n proměnných, protože podle právě uvedené věty je vyjádření v minimálních polynomech jednoznačné.
Pro úplnost je třeba ještě uvést, že právě tak, jako pomocí minimálních polynomů, se dá každá Booleovská funkce vyjádřit jednoznačně jako průnik tzv. maximálních booleovských polynomů (maxtermů), což jsou výrazy tvaru ../images/kap6/a28.gif,kde opět buď ai=Xi nebo ai = ../images/kap6/a29.gif.

Protože je však zřejmé, že lze pomocí de Morganových zákonů snadno převádět tvar mintermový na tvar maxtermový (vyjádříme-li nejprve inversi požadované funkce F v jednom tvaru a pak aplikujeme de Morganův zákon, abychom získali ../images/kap6/a30.giftj. F), nenachází maxtermový tvar tak široké využití jako mintermový.

Z definice Booleovy algebry plyne, že množina dvoustavových (logických) proměnných tvoří Booleovu algebru. Logický součin je průnikem a logický součet sjednocením které jsou:

1. komutativní

A + B = B + A

A . B = B . A

2 .asociativní

A + B + C = A + (B + C) = (A + B) + C

A . B . C = A . (B . C) = (A . B) . C

3. distributivní

A . (B + C) = A.B + A.C

A + (B . C) = (A + B) . (A + C)

Unární operace je tvoření inverze: A → ../images/kap6/a31.gifvytvoří negovaný komplement logické proměnné.

T a b u l k a 5.2

Funkce Název funkce Logický člen Algebraický výraz
f0 konstanta   0
f1 logický součet NEBO(OR,ODER) a + b
f2 implikace   ../images/kap6/a33.gif
f3 implikace   ../images/kap6/a34.gif
f4 Shefferova funkce NAND ../images/kap6/a35.gif
f5 logický součin A ( AND,UND) ab
f6 inhibice   ../images/kap6/a37.gif
f7 inhibice   ../images/kap6/a38.gif
f8 Pierceova funkce NOR ../images/kap6/a39.gif
f9 identita   a
f10 identita   b
f11 ekvivalence   ../images/kap6/a43.gif
f12 neekvivalence Exclusive OR ../images/kap6/a44.gif
f13 negace NE (NOT,NICHT) ../images/kap6/a45.gif
f14 negace NE (NOT,NICHT) ../images/kap6/a46.gif
f15 konstanta   1

Pomocí základních operací logického součtu součinu a negace můžeme pro jednu logickou proměnnou vytvořit devět základních identit:

1. A = ../images/kap6/a47.gif  identita invert

2. A. 1 = A

3. A. 0 = 0 identita logického součinu

4. A.A = A

5. ../images/kap6/a48.gif

6. A+1 = 1

7. A+0 = A  identita logického součtu

8. A+A = A

9. ../images/kap6/a49.gif

Dále v Booleově algebře logických proměnných můžeme de Morganovy teorémy vyjádřit pro dvě logické proměnné ve tvaru:

../images/kap6/a50.gif

../images/kap6/a51.gif

Uvedených vztahů a identit můžeme využít ke zjednodušení složitějších logických funkcí.

Jak bylo uvedeno v obecné části z Booleovy algebry plyne, že dvěma logickými proměnnými lze realizovat celkem 24 = 16 funkcí, z nichž některým se dostalo zvláštního pojmenování. Přehled těchto funkcí je uveden v tabulce 5.2.

Množina logických operací není ovšem jediná Booleovská algebra. Čtenář si může snadno ověřit, že například podmnožiny určité množiny M, ve které je definován průnik, sjednocení a tvoření komplementu způsobem běžným pro tyto množinové operace, tvoří rovněž Booleovu algebru.


Další ... Reprezentace základních logických funkcí elektronickými obvody