Booleova algebra Cílem této kapitoly je seznámit se se základy Booleovy logické algebry, která je matematickou disciplínou a tvoří teoretický prostředek pro návrh logických obvodů. Klíčové pojmy: Logická proměnná, logická funkce, logický člen, schematická značka, pravdivostní tabulka, zákony Booleovy algebry, minterm, maxterm, ÚNDF, ÚNKF.
Logická proměnná Logická proměnná se označuje písmenem- název logické proměnné. Logická proměnná nabývá dvou možných hodnot: -
Logická jednička ( true T- pravda, v počítači je reprezentována hodnotou 1)
-
Logická nula ( false F – nepravda, v počítači je reprezentována hodnotou 0)
V počítači je logická hodnota zobrazena v 1 bitu.
Booleova algebra Booleova algebra se zabývá vztahy mezi logickými proměnnými. Vztahy jsou vyjádřeny logickými funkcemi a pomocí zákonů Booleovy algebry. Logické funkce jsou popsány logickým výrazem, názvem logického členu ( hradla), který danou logickou funkci realizuje, pravdivostní tabulkou a schematickou značkou. Základní logické funkce -
Logický součet – OR ( ∨ disjunkce)
Y=A+B
A
B
Y
0+0=0
0
0
0
0+1=1
0
1
1
1+0=1
1
0
1
1+1=1
1
1
1
12/12/2012
Booleova algebra
1
1
-
Logický součin – AND ( ∧ konjunkce)
Y=A.B
A
B
Y
0. 0=0
0
0
0
0. 1=0
0
1
0
1. 0=0
1
0
0
1. 1=1
1
1
1
-
&
Negace - NOT
YA
A
Y
0 =1
0
1
1 =0
1
0
1
Další logické funkce ( odvozené ze základních logických funkcí) -
Negovaný logický součet - NOR
Y A B
A
B
Y
00= 1
0
0
1
0 1 = 0
0
1
0
1 0 = 0
1
0
0
11 = 0
1
1
0
-
Negovaný logický součin - NAND
Y = A B
A
B
Y
00 = 1
0
0
1
0 1 = 1
0
1
1
1 0 = 1
1
0
1
1 1 = 0
1
1
0
-
1
&
Nonekvivalence ( exklusive-or) – XOR
Y = A B + A B = A B
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
0
=1
Pomocí XOR se realizuje poloviční sčítačka tj. sčítání v nejnižším bitu. 12/12/2012
Booleova algebra
2
-
Ekvivalence – XNOR ( komparátor) Y = A B + A B = A B
A
B Y
0
0
1
0
1
0
1
0
0
1
1
1
=
Základní pravidla ( zákony) Booleovy algebry Zákony se uvádějí pro logický součet a logický součin. Obě podoby jsou vzájemně duální tzn., že pokud vzájemně zaměníme operátory a hodnoty 0 a 1, dostaneme druhý tvar. Zákon
Součet
Součin
Komutativní
A+B=B+A
A.B=B.A
Asociativní
A + (B + C) = (A + B) + C
A . (B + C) = (A . B) .C
Distributivní
(A + B) . (A + C) = A + (B . C)
A . B + A . C = A . (B + C)
Vyloučení třetího
A+ A =1
A. A =0
Agresivnosti 0 a 1
A+1=1
A.0=0
Neutrálnosti 0 a 1
A+0=A
A.1=A
Absorbce
A+A=A
A.A=A
A+A.B=A
A . (A + B) = A
A . ( A + B) = A . B
A+A .B=A+B
A . (A + B) = A . B
A +A.B= A +B
Dvojité negace
A= A
A= A
De Morganovy z.
A B = A.B
A B = A + B
Absorbce negace
De Morganovy zákony: Negaci funkce získáme nahrazením každé proměnné její negací a vzájemnou záměnou operátorů součtu a součinu. Zákony Booleovy algebry využíváme pro úpravy logických obvodů. V praxi se logické obvody většinou realizují pomocí hradel NOR a NAND, proto musíme logické výrazy upravit – používá se zákon dvojité negace a De Morganovy zákony. Příklad: Logický obvod realizovaný dvouvstupovým logickým členem OR realizujte pomocí dvouvstupových logických členů NAND. 12/12/2012
Booleova algebra
3
a + b =ab = a . b &
a a
1
a &
a+b
a.b
b &
b
b
Příklad: Upravte logický výraz A.B= A + B =A+B Příklad: Pomocí pravdivostní tabulky dokažte, že platí zákon absobce negace A . ( A + B) = A . B A
B
A
A +B
A . ( A + B)
A.B
0
0
1
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
1
1
0
1
1
1
Pomocí pravdivostní tabulky jsme dokázali, že daný zákon platí.
Způsoby popisu logických funkcí -
Pravdivostní tabulka
Pravdivostní tabulka je nejběžnějším způsobem popisu logické funkce. Popisuje chování logického obvodu. Obsahuje výčet všech kombinací vstupních proměnných a jim odpovídajících výstupů. Máme-li n- vstupních proměnných /2, pak pravdivostní tabulka bude mít 2n- řádků/4 ( = počet kombinací vstupních proměnných).
12/12/2012
Booleova algebra
4
Příklad: N
c
b
a
MIN
MAX
f1
f2
0
0
0
0
c .b .a
c+ b+ a
0
1
1
0
0
1
c .b .a
c+ b+ a
1
1
2
0
1
0
c .b .a
c+ b + a
1
0
3
0
1
1
c .b .a
c+ b + a
0
X
4
1
0
0
c .b .a
c + b+ a
0
0
5
1
0
1
c .b .a
c + b+ a
1
1
6
1
1
0
c .b .a
c +b + a
0
X
7
1
1
1
c .b .a
c +b +a
1
1
f1 – určitá funkce ( pro každou kombinaci vstupních proměnných má definovánu určitou hodnotu 0 nebo 1) f2 – neurčitá funkce ( obsahuje neurčité hodnoty X – pro danou kombinaci vstupních proměnných může mít funkce hodnotu 0 nebo 1) Základní součinový člen (minterm) – součin, který obsahuje všechny vstupní proměnné a platí MINTERM = 1. Např.: a . b .c = 1 tj. a = 0, b = 0, c = 1 Základní součtový člen (maxterm) – součet, který obsahuje všechny vstupní proměnné a platí MAXTERM = 0. Např.: a + b +c = 0 tj. a = 1, b = 1, c = 0 Platí: Maxtermy jsou negací mintermů. Např. c. b. a = c+b+a Z pravdivostní tabulky získáme logický výraz: 1. Úplná normální disjunktní forma ( ÚNDF) je dána součtem všech základních součinových členů ( mintermů), ve kterých je hodnota logické funkce rovna 1. ÚNDF: f1 ( c, b, a) = c . b . a + c . b . a + c . b . a + c . b . a Používá se častěji. 2. Úplná normální konjunktní forma ( ÚNKF) je dána součinem všech základních součtových členů ( maxtermů), ve kterých je hodnota logické funkce rovna 0. ÚNKF: f1 ( c, b, a) = (c +b +a) . (c + b + a ) . ( c +b +a) . ( c + b +a)
12/12/2012
Booleova algebra
5
-
Seznam stavových indexů
Zjednodušený zápis pravdivostní tabulky. Stavový index (N) – dekadická hodnota kombinace binárních vstupních proměnných. Logickou funkci zapisujeme jako seznam stavových indexů vstupních proměnných, pro něž logická funkce nabývá hodnotu 1 nebo 0. Příklad: Použijeme zadání minulého příkladu. ÚNDF: f1 ( c, b, a) = Σ ( 1, 2, 5, 7) ÚNKF: f1 ( c, b, a) = Π ( 0, 3, 4, 6) ÚNDF: f2 ( c, b, a) = Σ ( 0, 1, 5, 7) + ΣX ( 3, 6) ÚNKF: f2 ( c, b, a) = Π ( 2, 4) . ΠX ( 3, 6) -
Logický výraz
Logický výraz je popis logické funkce pomocí logických proměnných ve formě analytického zápisu. Z logického výrazu lze navrhovat logický obvod. Příklad: f ( a, b, c) = a . b c + a . b . c a b
1
& 1
&
c
-
f
&
Vénnův diagram
Logické funkce znázorňujeme pomocí množin, počet množin je dán počtem vstupních proměnných.
12/12/2012
Booleova algebra
6
Příklad: Logický člen NOR A B
NOR 1 A
B 0
A = 1, B = 0
0
0
A = 0, B = 1 A = 0, B = 0
A = 1, B = 1 -
Zobrazení pomocí map
Způsob používaný často ke grafickému zobrazení logické funkce. Zobrazení je přehlednější než Vénnův diagram a využívá se při minimalizaci logických funkcí (bude probráno v další kapitole). Máme-li n /2/ – vstupních proměnných, potom mapa bude obsahovat 2n /4/ políček. Mapa je transformací pravdivostní tabulky. Každému řádku tabulky odpovídá jedno políčko v mapě. V každém políčku je zapsána logická funkce pro danou kombinaci vstupních proměnných. Pruhem je u každé proměnné vyznačena její hodnota ( 1). Mapy: - Svobodovy – používají se s výhodou pro 5 až 6 vstupních proměnných - Karnaughovy – používají se pro 1, 2, 3 a 4 vstupní proměnné. Dále se budeme zabývat pouze těmito mapami. Příklady: n=1 f ( a) N
a
f
0
0
1
1
1
X a
f0 1
1
X
stavové indexy 12/12/2012
vstupní proměnná ( a = 1)
hodnota logické funkce Booleova algebra
7
n=2 f ( b, a) N
b
a
f
0
0
0
0
1
0
1
1
2
1
0
X
3
1
1
1
0
0
1
1
2
X
3
1
a
b n=3 f ( c, b, a) N
c
b
a
f
0
0
0
0
1
1
0
0
1
X
2
0
1
0
0
3
0
1
1
1
4
1
0
0
0
5
1
0
1
1
6
1
1
0
X
7
1
1
1
0
a b 0
1
1
X
3
1
2
0
4
0
5
1
7
0
6
X
c 12/12/2012
Booleova algebra
8
n=4 f ( d, c, b, a) N
d
c
b
a
f
0
0
0
0
0
0
1
0
0
0
1
1
2
0
0
1
0
1
3
0
0
1
1
0
4
0
1
0
0
X
5
0
1
0
1
0
6
0
1
1
0
0
7
0
1
1
1
1
8
1
0
0
0
1
9
1
0
0
1
X
10
1
0
1
0
X
11
1
0
1
1
1
12
1
1
0
0
1
13
1
1
0
1
0
14
1
1
1
0
0
15
1
1
1
1
1 a b
0
1
1
0
3
1
2
0
4
X
5
0
7
1
6
0
12
1
13
0
15
1
14
0
8
1
9
X
11
1
10
X
c d 12/12/2012
Booleova algebra
9
-
Zobrazení na n-rozměrném tělese
Používá se pro grafické zobrazení. Logická funkce pro jednu vstupní proměnnou se zobrazí na jednotkové úsečce, pro dvě proměnné na jednotkovém čtverci a pro tři proměnné na jednotkové krychli. Bližší popis viz učebnice [1]. Shrnutí: Booleova logická algebra je matematickou disciplínou a tvoří teoretický prostředek pro návrh logických obvodů.
Použité zdroje informací: [1] ANTOŠOVÁ, M. - DAVÍDEK, V. Číslicová technika: učebnice. 1.vyd. České Budějovice, KOPP, 2004. 286 s. ISBN 80-7232-206-0. [2] KESL,J. Elektronika III: číslicová technika. 1.vyd. Praha, BEN, 2003. 112s. ISBN 80-7300-076-8. [3] BLATNÝ, J. a kol. Číslicové počítače. 1.vyd. Praha, SNTL, 1980, 496s. [4] JANSEN, H. a kol. Informační a telekomunikační technika. 1.vyd. Praha, Europa-Sobotales cz.s.r.o, 2004, 400s. ISBN 80-86706-08-7. [5] HÄBERLE, G. a kol. Elektrotechnické tabulky pro školu i praxi. 1.vyd. Praha, Europa-Sobotales cz.s.r.o, 2006, 460s. ISBN 80-86706-16-8.
12/12/2012
Booleova algebra
10
