pokój EA 540,
[e-mail]
Układy Logiczne
i
Technika Cyfrowa
Część II  algebra Boole a i funkcje logiczne
Dr in\
. Paweł Raczyński
2008-03-07 P. R. KSA WETI PG 1
Algebra  definicja opisowa (1)
Algebra jest zespołem utworzonym przez zbiór elementów E = {ei} i
zbiór działań (funkcji) F = {fi} nad E. Zbiór elementów jest zamknięty
ze względu na zbiór operacji, tzn. dowolna operacja z F na dowolnych
elementach E daje w wyniku elementy E.
suma iloczyn
negacja
x y x+y x y xy
x x
0 0 0 0 0 0
0 1 0 1 1 0 1 0
1 0 1 1 0 0
1 0
1 1 1 1 1 1
Działania podstawowe algebry Boole a
obowiązuje konwencja: x*y = xy
2008-03-07 P. R. KSA WETI PG 2
Algebra  definicja opisowa (2)
Pewne działania są pojęciami pierwotnymi danej algebry, nazywamy
je działaniami podstawowymi. Inne są uzyskiwane jako superpozycja
działań podstawowych.
E = {0,1}, F = {(" , '" , �ł } /jak w algebrze zdań/
Inne notacje F = {*", )", �ł } /jak w algebrze zbiorów/
F = {+, *, �ł } /jak w algebrze/
Przykład superpozycji  wyra\
enie funkcji suma modulo dwa
poprzez operacje podstawowe algebry
X 9 Y = XY+ XY
2008-03-07 P. R. KSA WETI PG 3
Dwuelementowa algebra Boole a  definicja aksjomatyczna
Aksjomaty
To\
samości
1 x + 0 = x
9 x + 1 = 1
2 x * 1 = x
10 x * 0 = 0
prawa de
3 x + x = 1
Morgana
11 x + x = x
15 x y = x + y
4 x * x = 0
12 x * x = x
16 x + y = x * y
5 x + y = y + x
13 x = x
17 x + x y = x
reguły
6 x * y = y * x
14 x + x y = x + y
pochłaniania
18 x ( x + y ) = x
7 x y + x z = x ( y + z )
19 x y + x y = x
8 ( x + y ) ( x + z ) = x + y z
reguły
sklejania
20 ( x + y ) ( x + y ) = x
2008-03-07 P. R. KSA WETI PG 4
Algebra Boole a  upraszczanie wyra\
eń logicznych (1)
Działania zdefiniowane w dwuelementowej algebrze
Boole a, zarówno podstawowe, jak i zło\
one nazywamy
funkcjami logicznymi.
Poznane aksjomaty i to\
samości 1  20 pozwalają upraszczać
wyra\
enia opisujące funkcje wieloargumentowe funkcje
logiczne, ułatwiając ich analizę. Celem dalekosię\
nym
upraszczania funkcji logicznych jest upraszczanie układów,
których sposób działania te funkcje opisują.
Rozpatrzmy przykład:
korzystając z aksjomatów i to\
samości 1  20 uprościć poni\
szą funkcję
f(x,y,z) = xz + xyz + yz + xyz
2008-03-07 P. R. KSA WETI PG 5
Algebra Boole a  upraszczanie wyra\
eń logicznych (2)
f(x,y,z) = xz + xyz + yz + xyz = z 16 xz * xyz * yz+ xyz =
z 15 i 13 = (x + z)(x + y + z)(y + z) + xyz =
z 7 = [x(x + y + z) + z(x +y +z)]*(y + z) + xyz = xy+xz = x(y+z) (7)
z 7 i 6 = [xx + xy + z(x + x + y + z)](y + z) + xyz = xy = yx (6)
z 4, 1 i 3 = [xy + z(1 +y +z)](y + z) + xyz =
z 9 i 2 = (xy + z)(y + z) + xyz =
z 5 i 8 = z + xyy + xyz (x+y)(x+z)=x+yz (8)
z 6, 4, 10,1 = z + xyz =
z 6 i 17 = z
2008-03-07 P. R. KSA WETI PG 6
Algebra Boole a  upraszczanie wyra\
eń logicznych (3)
Wnioski:
1. Upraszczanie wyra\
eń logicznych przynosi wyraz
ne
korzyści.
2. Zaproponowane podejście nie jest efektywną metodą.
Jedynie du\
e doświadczenie pozwala wyznaczyć
właściwy kierunek przekształceń.
3. Zaproponowane podejście nie daje gwarancji, \
e
znalez
liśmy najprostszą postać wyra\
enia.
4. Potrzebna jest metoda algorytmiczna upraszczania
wyra\
eń logicznych dająca jednocześnie gwarancję
uzyskania postaci najprostszej z mo\
liwych-
minimalnej. Metody takie istnieją i noszą nazwę
procedury minimalizacji funkcji logicznych.
2008-03-07 P. R. KSA WETI PG 7
Bogactwo funkcji logicznych
Ile jest ró\
nych funkcji n zmiennych?
n Ln
a b f1 f2 ........ fLn
1 4
0 0 0 1 1
2 16
0 1 0 0 1
2n = 4
3 256
1 0 0 0 1
4 65536
1 1 0 0 1
5 4294967296
n
n=2
Ln =22 = 16
Jak to mo\
liwe, \
e istnieją a\
cztery funkcje jednej zmiennej?
2008-03-07 P. R. KSA WETI PG 8
Wybrane funkcje logiczne
OR NOR AND NAND XOR
�" a"
�" a"
�" a"
�" a"
x y x+y x y xy x/y x y x y x y 0 1
0 0 0 1 0 1 0 1 1 0 1
0 1 1 0 0 1 1 0 1 0 1
1 0 1 0 0 1 1 0 0 0 1
1 1 1 0 1 0 0 1 1 0 1
Funkcje jednej zmiennej:
Zmienna prosta, zmienna zanegowana, stała zero i stała
jeden.
2008-03-07 P. R. KSA WETI PG 9
o
ść
suma
suma
iloczyn
funkcja
funkcja
Piercea
Sheffera
implikacja
stała zero
stała jeden
modulo dwa
równowa
\

n
Rozwinięcie funkcji względem jej zmiennych
Ka\
dą funkcję logiczną mo\
na rozło\
yć na składniki według zasady:
f(x1,x2,...xn) = x1*f(1,x2,...,xn) + x1*f(0,x2,...,xn) (Tw. 1)
Ka\
dą funkcję logiczną mo\
na rozło\
yć na czynniki według zasady:
f(x1,x2,...xn) = [x1+f(0,x2,...,xn)] + [x1+f(1,x2,...,xn)] (Tw. 2)
Dokonując rozkładu funkcji na składniki zgodnie z Tw.
1 względem wszystkich jej zmiennych otrzymujemy
postać kanoniczną funkcji zwaną te\
Zupełną Normalną
Postacią Sumacyjna (ZNPS).
Analogicznie dokonując rozkładu funkcji na czynniki
zgodnie z Tw. 2 względem wszystkich jej zmiennych
otrzymujemy postać parakanoniczną funkcji zwaną te\

Zupełną Normalną Postacią Iloczynową (ZNPI).
2008-03-07 P. R. KSA WETI PG 10
Postać kanoniczna funkcji - ZNPS (1)
Rozwijając funkcję zgodnie z twierdzeniem 1 kolejno względem
wszystkich jej zmiennych otrzymujemy:
f(x1,x2,...xn) = x1x2...xn*f(1,1,...,1) + x1x2...xn *f(0,1,...,1) + ...
+ x1x2...xn *f(0,0,...,0)
Jak widać postać ta składa się z sumy iloczynów:
" pełnych iloczynów zmiennych funkcji (pełnych tj.wszystkich
zmiennych funkcji);
" próbek funkcji, czyli wartości funkcji od ustalonych wartości
zmiennych.
Zauwa\
my, \
e poszczególne pełne iloczyny ró\
nią się poło\
eniem
negacji nad zmiennymi. Iloczynów jest 2n, czyli występują wszystkie
mo\
liwe wariacje ustawienia negacji nad poszczególnymi zmiennymi.
2008-03-07 P. R. KSA WETI PG 11
Postać kanoniczna funkcji - ZNPS (2)
Przyjmijmy przyporządkowanie xk �! �! 0
�! 1 i xk �!
�! �!
�! �!
Na mocy tego przyporządkowania ka\
dy pełny iloczyn mo\
emy
zastąpić liczbą binarną (mo\
na ją zamienić na dziesiątkową)
reprezentującą ten iloczyn stanowiąc kolejny jego numer. Np. iloczyn
x1x2x3x4xn zastąpimy liczbą (10100)2 = (20)10 i oznaczymy I20
Oznaczmy przez ąi próbkę funkcji tworzącą iloczyn z Ii. W naszym
przykładzie ą20 = f(10100).
2n-1
ZNPS  ka\
dą funkcję
mo\
na przedstawić w
f(x1,x2,...xn) =Ł Ł Ii
Ł ąi * Ii = Ł
Ł Ł
Ł Ł
postaci sumy jej pełnych
i=0 ąi=1
iloczynów, dla których
próbka funkcji przyjmuje
wartość 1.
2008-03-07 P. R. KSA WETI PG 12
Postać parakanoniczna funkcji - ZNPI (1)
Rozwijając funkcję zgodnie z twierdzeniem 2 kolejno względem
wszystkich jej zmiennych otrzymujemy:
f(x1,x2,...xn) = [x1+x2+...+xn+f(0,0,...,0)]*[ x1+x2+...+xn+
+f(1,0,...,0)] * ... *[x1+x2+...+xn+f(1,1,...,1)]
Jak widać postać ta składa się z iloczynu sum:
" pełnych sum zmiennych funkcji (pełnych tj.wszystkich zmiennych
funkcji);
" próbek funkcji, czyli wartości funkcji od ustalonych wartości
zmiennych.
Zauwa\
my, \
e poszczególne pełne sumy ró\
nią się poło\
eniem negacji
nad zmiennymi. Sum jest 2n, czyli występują wszystkie mo\
liwe wariacje
ustawienia negacji nad poszczególnymi zmiennymi.
2008-03-07 P. R. KSA WETI PG 13
Postać parakanoniczna funkcji - ZNPI (2)
Przyjmijmy przyporządkowanie xk �! �! 1
�! 0 i xk �!
�! �!
�! �!
Na mocy tego przyporządkowania ka\
dą pełną sumę mo\
emy
zastąpić liczbą binarną (mo\
na ją zamienić na dziesiątkową)
reprezentującą tę sumę stanowiącą kolejny jej numer. Np. sumę
x1+x2+x3+x4+xn zastąpimy liczbą (10100)2 = (20)10 i
oznaczymy S20
Oznaczmy przez ąi próbkę funkcji tworzącą sumę z Si. W naszym
przykładzie ą20 = f(10100).
2n-1
ZNPI  ka\
dą funkcję
mo\
na przedstawić w
f(x1,x2,...xn) =   Si
 (ąi + Si )= 
 
 
postaci iloczynu jej
i=0 ąi=0
pełnych sum, dla których
próbka funkcji przyjmuje
wartość 0.
2008-03-07 P. R. KSA WETI PG 14
ZNPS i ZNPI a tablica funkcji (1)
f(x1,x2,x3) = x1 9 x2 x2x3
�" �"
�" �"
�" �"
�" �"
x1x2x3 x1 x2 x2x3 x1 x2 x2x3
f
000 0 0 1 0
001 0 1 1 0
ZNPS
010 1 0 0 1
011 1 0 0 1
ZNPI
100 1 0 0 1
101 1 1 1 0
110 0 0 1 0
111 0 0 1 0
2008-03-07 P. R. KSA WETI PG 15
ZNPS i ZNPI a tablica funkcji (2)
�" �"
�" �"
�" �"
�" �"
x1x2x3 x1 x2 x2x3 x1 x2 x2x3 f
000 0 0 1 0
001 0 1 1 0
Postać
postać
010 1 0 0 1
skrócona
jawna
011 1 0 0 1
(liczbowa)
100 1 0 0 1
101 1 1 1 0
110 0 0 1 0
111 0 0 1 0
f(x1,x2,x3) = x1x2x3 + x1x2x3 + x1x2x3 = Ł(2,3,4) ZNPS
Ł
Ł
Ł
f(x1,x2,x3) = (x1+x2+x3)* (x1+x2+x3)* (x1+x2+x3)*
(x1+x2+x3)* (x1+x2+x3) = (0,1,5,6,7) ZNPI



2008-03-07 P. R. KSA WETI PG 16
ZNPS i ZNPI a tablica funkcji (3)
Oznaczmy zbiór wszystkich numerów składników jedności I
czynników zera dla funkcji np. 3 zmiennych:
P = {0,1,2,3,4,5,6,7}  zbiór pełny
Dla funkcji z poprzedniego przykładu w postaci ZNPS zbiór
numerów składników jedności ma postać S = {2,3,4}.
Dla funkcji z poprzedniego przykładu w postaci ZNPI zbiór
numerów czynników zera ma postać I = {2,3,4}.
Zauwa\
my, \
e zale\
ność pomiędzy funkcją w postaci ZNPS i
ZNPI wyra\
a się następującą zale\
nością pomiędzy zbiorami
numerów składników jedności i czynników zera:
Zbiór S = dopełnienie zbioru I
oraz
zbiór I = dopełnienie zbioru S
f(x1,x2,x3) = Ł (0,1,5,6,7)
Ł(2,3,4) = 
Ł 
Ł 
2008-03-07 P. R. KSA WETI PG 17
System funkcjonalnie pełny
Ka\
dą funkcję logiczną mo\
na uzyskać w wyniku superpozycji innych
funkcji. Zbiór takich funkcji nazywamy systemem funkcjonalnie pełnym.
Z definicji algebry Boole a wynika, \
e takim systemem jest system zło\
ony
z podstawowych operacji algebry: NOT, OR i AND. Dowodem na to są
choćby wyprowadzone poprzednio postacie kanoniczna i parakanoniczna
funkcji.
Istnieją jednak\
e inne systemy funkcjonalnie pełne.System taki tworzy np.
sama ze sobą funkcja NAND, a tak\
e funkcja NOR.
Przedstawiając funkcję NOR w postaci ZNPS mamy:
x{y = x y stąd:
x{x = x x = x
(x{x)(y{y) = x{y = x y= xy
(x{y)(x{y) = x y{x y =x y = x+y = x+y
2008-03-07 P. R. KSA WETI PG 18
Inne algebry Boole a  rachunek zdań
i lub nie
~
'" ("
'" ("
'" ("
'" ("
Prawda = 1
Fałsz = 0
JEśELI ....... TO ......... IMPLIKACJA




......... ALBO........... SUMA MODULO 2
�"
�"
�"
�"
ANI ...... ANI ............. NOR
....... WTEDY I TYLKO
RÓWNOWAśNOŚĆ
a"
a"
a"
a"
WTEDY GDY ......
2008-03-07 P. R. KSA WETI PG 19
Inne algebry Boole a  rachunek zbiorów
Algebra Boole'a Algebra zbiorów
zmienna logiczna zbiór
sulalogiczna suma zbiorów
iloczyn logiczny iloczyn zbiorów
jedynka logiczna zbiór pełny
zero logiczne zbiór pusty
Niech zbiór Z={1,2,3}. Elementami algebry są wszystkie podzbiory
zbioru Z: {}=0, {1}=e1, {2}=e2, {3}=e3, {1,2}=e4, {1,3}=e5, {2,3}=e6,
{1,2,3}=1. Zatem E={0,1,e1,e2,e3,e4,e5,e6,e7}. Ogólnie zbiór n-
elementowy generuje2n- elementową algebrę zbiorów. Operacje tej
algebry są operacjami na zbiorach zdefiniowanymi poni\
szymi
diagramami Venna.
A A A
B B
Suma zbiorów  obszar Iloczyn zbiorów  obszar Dopełnienie zbioru  obszar
zaznaczony jakimkolwiek zaznaczony zarówno zaznaczony kolorem białym
kolorem niebieskim jak i czerwonym
kolorem
2008-03-07 P. R. KSA WETI PG 20
Diagramy Venna a algebra Boole a
Wykorzystując analogie pomiędzy algebrą Boole a a algebrą
zbiorów diagramy Venna mo\
na wykorzystywać do sprawdzania
to\
samości algebry Boole a.
15 x y = x + y
Przykład: - jedno z praw de Morgana
Lewa strona
Prawa strona
a"
a"
a"
a"
Obszar, który jest
Obszar, który nie jest
zakreskowany w jakikolwiek
pomarańczowy
sposób
2008-03-07 P. R. KSA WETI PG 21
Algebra sieci zestykowych
A
A A
Zestyk normalnie Zestyk normalnie
rozwarty zwarty
A+B
B
A B
AB
Opis sieci:
A B C
f=ABC + (D+G)F + HI + JK
D
F
G Dlaczego tak łatwo poszło? Dlatego,
\
e siec jest narysowana w postaci
H I
normalnej, tj. występują w niej tylko
połączenia szeregowe i równoległe
J K
(u\
yto sumy, iloczynu i negacji
pojedynczych zmiennych).
2008-03-07 P. R. KSA WETI PG 22
Analiza sieci zestykowych  metoda ście\
ek
A
B
W sieci nie występują
wyłącznie połączenia
szeregowe i
równoległe. Sieć ma
topologię mostkową,
nie jest narysowana w
postaci normalnej.
C
D E
A jak w tej metodzie
postąpić, gdy
wystąpią zmienne
zanegowane?
Metoda ście\
ek
prowadzi no opisu
w postaci
f() = AB + DE + ACE + BCD
normalnej
sumacyjnej (NPS)
2008-03-07 P. R. KSA WETI PG 23
Analiza sieci zestykowych  metoda cięć
A
B
W sieci nie występują
wyłącznie połączenia
szeregowe i
równoległe. Sieć ma
topologię mostkową,
nie jest narysowana w
postaci normalnej.
C
D E
A jak w tej metodzie
postąpić, gdy
wystąpią zmienne
zanegowane?
Metoda cięć
prowadzi no opisu
w postaci
f() = (A+D) * (B+E) *
normalnej
(A+C+E) * (B+C+D) iloczynowej (NPI)
2008-03-07 P. R. KSA WETI PG 24