2 MINIMALIZACJA FUNKCJI LOGICZNYCH

2.1 Elementy algebry Boole'a

Algebra Boole'a jest działem matematyki wykorzystywanym do pro­jektowania i analizy układów cyfrowych. Zmienne boolowskie (lo­giczne mog~ przyjmować wartości tylko ze zbioru f 0, 1}. W algebrze Boole'a do przedstawienia iloczynu logicznego AND zmiennych X i Y będziemy stosować zapis X ~ Y = XY. Do przedstawienia sumy lo­gicznej zmiennych X i Y będziemy stosować zapis X ~- Y. Negację zmiennej X będziemy zapisywać jako X . Na rysunku 2.1 s~ przed­stawione (za pomocy tablicy prawdy) definicje następuj~cych funkcji logicznych: AND, OR i NOT.

AND OR NOT X Y X ~Y X Y X +Y

0 0 0 0 0 0 X X 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1

Rys. 2.1. Tablice prawdy funkcji AND, OR, NOT

Funkcjami boolowskimi (funkcjami logicznymi) nazywamy funk­cje, których zmienne i one same przyjmuje wartości tylko ze zbioru f 0, l~. Rozważmy funkcję logiczni

f(x, y z) = xy --~ xz -~ yz

Zależność między wartoście funkcji a wartościami jej zmiennych można przedstawić w tablicy prawdy pokazanej na rysunku 2.2.

Algebra Boole'a (~1, 2, 3, 4~) jest algebry aksjomatyczni, przyj­muj~c~ aksjomaty przedstawione na rysunku 2.3. W algebrze Boole'a obowi~zuje tzw. zasada dualizmu. Zasada ta może być sformułowana w następuj~cy sposób ((2~): zastępuj~c w dowolnej tożsamości algebry Boole'a symbol OR (~-) symbolem AND (~) i symbol AND (~) sym­bolem OR (-~) oraz zastępuj~c jedynkę zerem, a zero jedynki (jeśli występuje w wyrażeniu), otrzymamy również tożsamość (rys. 2.3).

19

Wlasności (16) i (17) s~ nazywane prawami de Morgana. Prawa de Morgana uogólnione na n zmiennych przyjmuje postać:

xi-l-xz-~...+x~,=xl~xz.....x

xl.xz.....x,~=xl-~xz-1-...~--xn

Funkcje logiczne mog~ być przedstawione w postaci opisu słow­nego, tablic prawdy i w sposób analityczny.

Funkcja n zmiennych jest przedstawiana za pomocy tablicy prawdy o n -~ 1 kolumnach i 2~ wierszach. W kolejnych wierszach wpisuje się wszystkie kombinacje zmiennych niezależnych. Ostatnia kolumna jest przeznaczona do zapisania wartości funkcji dla poszczególnych kom­binacji zmiennych niezależnych. Aby wszystkie możliwe kombinacje zostaly uwzględnione, wpisujemy je w taki sposób, by tworzyly ko­lejne liczby (rys. 2.2).

i x y z f (x, y, z) = xy -~- xz ~- yz

0 0 0 0 0

1 0 0 1 0

2 0 1 0 0

3 0 1 1 1

4 1 0 0 0

5 1 0 1 1

6 1 1 0 1

7 1 1 1 1

Rys. 2.2. Tablica prawdy funkcji f (x, y, z) = xy -~- xz -i- yz

1. x-I-O=x 2. x-1=x

3. x+l=1 4. x~0=0

5. x -~ x = x 6. x ~ x = x

7. x-~x=1 8. x~x=0

9. x = x

10. x-f-y=y-f-x 11. x~y=y~x

12. x-f-~y-~-z)=(x+y)-f-z 13. x~(y~z)=(x~y)~z

14. x'(y-ł-z)=(x~y)-f-(x 'z) 15. x-ł-(y'z)=(x-ł-y)'(x-~-z)

16. x -~ y = x ~ y 17. x ~ y = x -i- y

Rys. 2.3. Aksjomaty algebry Boole'a

20

Definicja 2.1. Iloczynem pełnym n zmiennych nazywamy taki iloczyn tych zmiennych (lub ich negacji), w którym każda zmienna (lub jej negacja) występuje dokładnie jeden raz.

Definicja 2.2. Sumy pełni ~ zmiennych nazywamy taki sumę tych zmiennych (lub ich negacji), w której każda zmienna (lub jej negacja) występuje dokładnie jeden raz.

Na rysunku 2.4 s~ przedstawione iloczyny pełne mi i sumy pełne MŻ dla trzech zmiennych x, y, z.

x y z Iloczyny pełne m~ Sumy pełne M~

0 0 0 x y ź mo x -~ y + z Mo

0 0 1 xyz ml x+y-~ź Ml

0 1 0 Dyź mz x+y-~z Mz

0 1 1 xyz m3 x+y+ź M3

1 0 0 xyź m4 ~+y+z M4

1 0 1 xyz m5 x~-y~-ź M5

1 1 0 x y ź m 6 x -~ y -E- z M6

1 1 1 xyz m7 ~+y+ź M7

Rys. 2.4. Iloczyny i sumy pełne dla trzech zmiennych x, y, z

Iloczyn pełny przyjmuje wartość 1 tylko dla jednej kombinacji wartości zmiennych. Suma pełna przyjmuje wartość 0 tylko dla jednej kombinacji wartości zmiennych.

Twierdzenie 2.1. Dowolni funkcję logiczni n zmiennych można jednoznacznie przedstawić w postaci sumy iloczynów pełnych:

2n-1

f (xi, xz, . . . , x.~) _ ~ a; my y = f (z) ż-o

gdzie f (i) oznacza wartość funkcji f (xl, xz, . . . , xn) dla i-tej kombi­nacji zmiennych.

Twierdzenie 2.2. Dowolni funkcję logiczni n zmiennych można jednoznacznie przedstawić w postaci iloczynu sum pełnych:

tri -1

f(xi~x2~...,xn) _ ~ (a; -ł- M;), a2 = f(2) t=o

21

gdzie f (i) oznacza wartość funkcji f (xl, x2, . . . , x~,) dla i-tej kombi­nacji zmiennych.

Dowody tych twierdzeń s~ przedstawione między innymi w (5).

Przykład 2.1. Przedstawić funkcję f (x, y, z) zadam przez ta­blicę prawdy na rysunku 2.2 w postaci sumy iloczynów pełnych. Jak wynika z tablicy prawdy, funkcja ta przyjmuje wartość 1 w wierszach: 3, 5, 6 i 7, a wartość 0 w pozostałych. Zatem

an_1 f(x~ y~ z) _ ~ ~Żmi = 0 ' mo ~- 0 ' mi -f 0 ' m2-~ ż~o

-(-1~m3-f-O~m4-i-l~m5-ł-l~ms-i-l~m7

Każdy składnik 0 ~ mi = 0 może być wyeliminowany. Zatem funkcja przyjmuje postać

f ( x ~ y ~ z) = ms -ł- ms -ł- ras -I- rrt7 =

_ ~ yz ~-- x y z -~ x y ź -ł- x y z

Przykład 2.2. Przedstawić funkcję f (x, y, z) zadam przez ta­blicę prawdy na rysunku 2.2 w postaci iloczynu sum pełnych. Jak wynika z tablicy prawdy, funkcja ta przyjmuje wartość 0 w wierszach: 0, 1, 2, 4, a wartość 1 w pozostałych. Zatem

2n-1

f(x~y,z)= ~(a=+MŻ)=(O+Mo)~(O-I-M1)~(O+MZ)~ Ż-o

(1+Ms)~(O+M4)~(1+M5)~(1-ł-Ms)~(1+M7)

Każdy czynnik (1-~Mi) = 1 może być wyeliminowany. Zatem funkcja przyjmuje postać

f(x~y~z)=Mo'MmMa'M4=

=(x-ł-y-ł-z)(x~-y+z)(x+y+z)(x+y+'z)

Funkcja NAND (Not AND) jest negacji funkcji AND. Funkcja NOR (Not OR) jest negacji funkcji OR. Tablice prawdy funkcji NAND i NOR (dla dwóch zmiennych) zostały przedstawione na ry­sunku 2.5.

22

NAND x y x~y 0 0 1 0 1 1 1 0 1 1 1 0

NOR

x y x ~- y

0 0 1

0 1 0

1 0 0

1 1 0

Rys.2.5. Tablice prawdy funkcji NAND i NOR

Systemem funkcjonalnie pełnym nazywamy taki zbiór funkcji lo­gicznych, który umożliwia przedstawienie dowolnej funkcji logicznej (~5~). Zbiór zawieraj~cy funkcje: AND, OR, NOT tworzy podsta­wowy system funkcjonalnie pełny. Jednoelementowe zbiory zawiera­j~ce funkcje NAND lub NOR s~ systemami funkcjonalnie pełnymi.

2.2 Minimalizacja funkcji logicznych

2.2.1 Metoda przekształceń formalnych

Funkcje logiczne można upraszczać korzystaj~c z podstawowych wła­sności algebry Boole'a (rys. 2.3).

Przykład 2.3. Korzystaj~c z podstawowych własności algebry Boole'a, uprościmy funkcję: f (x, y, z) = xyz -E- xyz ~- xyź + xyz

f(x, y, z) = xyz -~- xyz -f- xyz -f- xyz =

= xyz .~ xyz -~- xyz -~ xyz + xyź + xyz =

= yz(x -ł~ x) + xz(y ~- y) + xy(z ~- z) = yz -ł- xz ~- xy

2.2.2 Metoda tablic Karnaugha

Funkcja n zmiennych przedstawiona za pomocy tablicy prawdy ma 2n iloczynów pełnych równoważnych 2~ liczbom dwójkowym otrzy­manym z n cyfr. Funkcja logiczna dla pewnych iloczynów pełnych jest równa 1, dla innych jest równa 0. Informację zawarty w tablicy prawdy można przedstawić podaj~c dziesiętny odpowiednik tych ilo­czynów pełnych, dla których funkcja przyjmuje wartość 1. Na przy­kład tablicę prawdy funkcji z rysunku 2.2 można przedstawić w na­stępuj~cy sposób:

f (x, y, z) _ ~(3, 5, 6, 7)

23

Liczby w nawiasie przedstawiaj zmienne dwójkowe w kolejności ich pojawiania się w tablicy prawdy. Symbol ~ oznacza sumę iloczynów pełnych wyszczególnionych w nawiasie. Iloczyny pełne, dla których funkcja przyjmuje wartość 1, s~ podane za pomocy ich dziesiętnych odpowiedników. Brakuj~ce iloczyny pełne to te, dla których funkcja przyjmuje wartość 0.

Tablica Karnaugha (~l, 2, 3, 4, 5, 6)~ jest tablicy składaj~c~ się z kwadratów, przy czym kaźdemu kwadratowi odpowiada jeden ilo­czyn pełny. Liczba kwadratów w tablicy n zmiennych jest równa 2n. Liczby odpowiadaj~ce iloczynom pełnym wpisuje się do tablicy w taki sposób, aby iloczyny pełne w s~siednich (maj~cych wspólni krawędź) kwadratach różniły sig od siebie tylko jedni zmienni {na jednej pozy­cji). Porz~dek taki jest charakterystyczni właściwości tablicy Kar­naugha, wykorzystywani do przeprowadzenia uproszczeń na podsta­wie zależności:

xy-ł-xy=x(y-ł-y)=x

gdzie x, y s~ zmiennymi logicznymi. Zatem zmienni, która w s~sied­nich kwadratach przyjmuje różne wartości, można pomin~ć. Tablice Karnaugha dla funkcji dwóch, trzech i czterech zmiennych s~ poka­zane odpowiednio na rysunkach 2.6, 2.7, 2.8.

y y y r~ r~ ~..

00 O1 0 1 x ~ x y x 10 11 x 2 3 x xy xy

Rys. 2.6. Tablica Karnaugha dla funkcji dwóch zmiennych (x, y) y y y

000001011010 0 1' 3 2 xyźxyzxyzxyź x 100101111110 x 4 5 7;9 61 x xyźxyzxyzxyź z z z

Rys. 2.7. Tablica Karnaugha dla funkcji trzech zmiennych (x, y, z)

Iloczyny pełne z s~siednich kwadratów s~ identyczne, z wyj~tkiem jednej zmiennej. Zgodnie z t~ definicji s~siedztwa, kwadraty znaj­duj~ce się na końcach tego samego rzędu też uważa się za s~siednie.

24

Podobnie, kwadraty znajduj~ce się na końcach tej samej kolumny również uważa się za s~siednie.

y

0000 0001 0011 0010

0100 0101 0111 0110

1100 1101 1111 1110

w

1000 1001 1011 1010

z

y

0 1- 3 2

4 5 7 6

x

12 13 15 14

w

8 9 11 10

z.

i°

Rys. 2.8. Tablica Karnaugha dla funkcji czterech zmiennych (w, x, y, z)

W procesie minimalizacji funkcję logiczni opisani za pomocy ta­blicy prawdy przedstawia się w postaci tablicy Karnaugha, wpisuj~c 1 w te kwadraty, dla których wartość funkcji jest równa 1.

Liczba kwadratów liczonych w grupy musi być równa calkowi­tej potędze 2. Każdej grupie kwadratów odpowiada jedno wyrażenie, a suma logiczna tych wyrażeń jest uproszczonym przedstawieniem funkcji.

Przykład 2.4. Uprościć funkcję f (x, y, z) _ ~(2, 4, 5, 6, 7), ko­rzystaj~c z tablicy Karnaugha.

Tablica Karnaugha dla tej funkcji jest pokazana na rysunku 2.9.

y 1

x 1 1 1 1 z

Rys. 2.9. Tablica Karnaugha dla funkcji .f (x, y~ z) _ ~(2, 4, 5, 6, 7)

W tablicy tej jest 5 kwadratów z wpisani jedynki, po jednej dla każdego iloczynu pelnego, dla którego funkcja przyjmuje wartość 1. W kolumnie 4 zostały policzone dwa s~siednie kwadraty. Kolumna ta

25

należy zarówno do y, jak i do ź, zatem odpowiadaj~ce jej wyrażenie jest równe yź. W wierszu drugim zostały poł~czone 4 s~siednie kwa­draty. Wiersz ten należy do x, zatem odpowiadaj~ce mu wyrażenie jest równe x. Uproszczona funkcja jest zatem równa

f(x~ y~ z) = L(~~ 4~ 5~ 0~ ~) = x -ł- y~

Przykład 2.5. Uprościć funkcję f (x, y, z) _ ~(l, 4, 5, 6), korzy­staj~c z tablicy Karnaugha.

Tablica Karnaugha dla tej funkcji jest pokazana na rysunku 2.10.

y 1

x 1 1 1 z

Rys. 2.10. Tablica Karnaugha dla funkcji f (x, y> z) _ ~(1, 4, 5, 6)

W kolumnie 2 zostały poł~czone dwa s~siednie kwadraty, dając wy­rażenie yz. Dwa kwadraty z 1 na obu końcach drugiego wiersza s~ s~siednie i zostały poł~czone, daj~c wyrażenie xź. Uproszczona funk­cja jest zatem równa

f (x, y, z) = ~(l, 4, 5, 6) = xź =ł- yz

Przykład 2.6. Uprościć funkcję f (x, y, z) _ ~(0, 2, 4, 6, 7), ko­rzystaj~c z tablicy Karnaugha.

Tablica Karnaugha dla tej funkcji jest pokazana na rysunku 2.m.

y 1 1

x 1 1 z

Rys. 2.11. Tablica Karnaugha dla funkcji .i(x ~ y, z) _ ~(0, 2, 4, 6, 7)

26

Cztery kwadraty w pierwszej i czwartej kolumnie s~ s~siednie i zo­stały poł~czone, dajk wyrażenie ź. Kwadraty odpowiadaj~ce iloczy­nom pełnym 6 i 7 zostały poł~czone, daj~c wyrażenie xy. Uproszczona funkcja jest zatem równa

f (x, y, z) _ ~(0, 2, 4, 6, 7) = xy + ź

Otrzymane w poprzednich przykładach funkcje miały postać sumy iloczynów. Czasami jest wygodnie przedstawić funkcję w postaci ilo­czynu sum. Jedynki w tablicy Karnaugha przedstawiaj iloczyny pełne, dla których wartość funkcji f jest równa 1. Kwadraty nie za­znaczone jedynkami określaj iloczyny pełne, dla których wartość funkcji f jest równa 0. Wpisuj~c w puste kwadraty zera i ł~cz~c je w grupy s~siednich kwadratów otrzymujemy negację funkcji f, to zna­czy f . W dalszym ci~gu, korzystaj~c z praw de Morgana i neguj~c f , otrzymujemy f = f . Otrzymana w ten sposób funkcja ( f ) przyjmuje postać iloczynu sum.

Przykład 2.7. Uprościć funkcję

f (a, b, c, d) _ ~(2, 3, 8, 10, 11, 12, 14, 15)

do postaci sumy iloczynów i do postaci iloczynu sum, korzystaj~c z tablicy Karnaugha.

Tablica Karnaugha dla tej funkcji jest pokazana na rysunku 2.12.

c

0 0 1

0 0 0 0

1 0 1 1

1 0 1

i~

c

0 0 1 1

0 0 0 0

1 0 1 1

a

1 .0 1 ~ 1

)~

-­d

d

Rys. 2.12. Tablica Karnaugha dla funkcji

f (a, b, c, d) _ ~(2, 3, 8, 10, 11, 12, 14, 15)

Jedynki w tej tablicy odpowiadaj iloczynom pełnym, dla których funkcja f przyjmuje wartość 1. Kwadraty z zerami odpowiadaj ilo­

27

czynom pełnym nie zawartym w f i określaj dopełnienie funkcji f, to znaczy f . Ł~cz~c s~siednie kwadraty z jedynkami otrzymujemy uproszczony funkcję w postaci sumy iloczynów

f (a, b, c, d) _ ~(2, 3, 8, 10, 11, 12, 14, 15) = ac -~ ad -~ bc

Ł~cz~c s~siednie kwadraty z zerami, otrzymujemy uproszczony postać negacji funkcji f , to znaczy

f=ab-~-ćd~-ać

Korzystaj~c z prawa de Morgana, otrzymujemy uproszczony postać funkcji w postaci iloczynu sum

,f = f = ab-~ćd~-a ć= a`b-ćd-a ć= (a-ł-b)-(c-I-d)-(a-E-c)

Jedynki w tablicy Karnaugha reprezentuje iloczyny pełne, dla któ­rych funkcja przyjmuje wartość 1. Zera w tablicy Karnaugha repre­zentuj~ iloczyny pełne, dla których funkcja przyjmuje wartość 0. S~ jednak sytuacje, kiedy nie ma znaczenia, czy dla danego iloczynu pełnego funkcja przyjmuje wartość 0, czy 1. Iloczyny pełne, dla któ­

rych wartość funkcji może być dowolna (0 lub 1), nazywa się ilo- ' czynami pełnymi nieokreślonymi i oznacza się w tablicy Karnaugha

na przykład przez x. Iloczyny pełne nieokreślone mog~ być używane do upraszczania funkcji. Wybieraj~c dla danej funkcji s~siednie kwa­draty w tablicy Karnaugha, iloczynom pełnym nieokreślonym można przypisać wartość 0 lub 1, w zależności od tego, czy umożliwi to uproszczenie funkcji.

Przykład 2.8. Uprościć funkcję

f(~~ y, z) _ ~(0~ 4~ 6)

nieokreślony dla następuj~cych iloczynów pełnych:

n(~, y, z) _ ~ n(1, 3, 5, 7),

korzystaj~c z tablic Karnaugha.

Powyższy funkcję można przedstawić w postaci

.f (x, ~~ z) _ ~(0, 4, 6) + ~ n(1, 3, 5, 7)

Tablica Karnaugha dla tej funkcji jest pokazana na rysunku 2.13.

28

y 1 x x

x 1 x x 1 z

Rys. 2.13. Tablica Karnaugha dla funkcji

f (x~ y~ z) _ ~(0, 4~ 6) + ~ ~(1, 3~ 5~ 7)

Dla iloczynów pełnych nieokreślonych ~ n(1, 3, 5, 7), oznaczonych przez x, funkcja może przyjmować wartość 0 lub 1. Przyjęcie wartości 1 dla iloczynów pełnych nieokreślonych 1, 5, 7 umożliwia uproszczenie funkcji. Kwadraty 1, 5, 7 zostały poł~czone z s~siednimi tak, aby uzyskać maksymalni liczbę kwadratów. Iloczyn pełny nieokreślony 3 nie umożliwia uproszczenia funkcji i dlatego nie został poł~czony z s~siednimi kwadratami. Uproszczona funkcja jest zatem równa

f (x, y, z) _ ~(0, 4, 6) -I- ~ n(1, 3, 5, 7) = x -ł- y

Przykład 2.9. Uprościć funkcję

f (a, b, c, d, e) _ ~(0, 1, 5, 7, 13,15, 16, 17, 25, 27, 29, 31)

korzystaj~c z tablicy Karnaugha.

Tablica Karnaugha dla funkcji pięciu zmiennych jest pokazana na rysunku 2.14.

a

d

a

d

0 1 3 2

4 5 7 6

c

12 13 15 14

b

b 8 9 11 10

v

e

16 17 19 18

20 21 23 22

c

28 29 31 30

24 25 27 26

e

Rys. 2.14. Tablica Karnaugha dla funkcji pięciu zmiennych (a,b,c,d,e)

Tablica Karnaugha dla funkcji

29

f (a, b, c, d, e) _ ~(0, 1, 5, 7, 13, 15, 16, 17, 25, 27, 29, 31) jest pokazana na rysunku 2.15.

a a d d

1 1

1 1

1 1

b

e

e

1 1

c

1 1

b

1 1

Rys. 2.15. Tablica Karnaugha dla funkcji

f (a, b, c, d, e) _ ~(0, 1, 5, 7, 13, 15, 16, 17, 25, 27, 29, 31)

Uproszczona funkcja jest równa

f (a, b, c, d, e) _ ~(0, 1, 5, 7, 13, 15, 16, 17, 25, 27, 29, 31) _

=ace-ł-abe-f-abćd-t-abćd=ace-ł-abe-I-(a-i-a)bćd=

= ace =t- abe -~- b e d

2.2.3 Metoda (duine'a-McCluskeya

Metodę ~,?uine'a-McCluskeya ((1, 2, 3, 4, 5, 6~), zwani również me­tod~ implikantów prostych, przedstawimy na przykładach:

Przykład 2.10. Uprościć funkcję

f (a, b, c, d) _ ~(5, 7, 8, 9, 10, 11, 13, 15)

Minimalizację rozpoczniemy od uporz~dkowania zbioru iloczynów pełnych funkcji w taki sposób, aby poszczególne grupy zawierały ilo­czyny pełne o takiej samej liczbie jedynek. Poszczególne grupy za­pisuje się w postaci kolumny, rozpoczynaj~c od grupy z najmniejszy liczby jedynek. Grupy te oddziela się od siebie poziomi kreski. Z le­wej strony kolumny wypisujemy dziesiętne odpowiedniki liczb dwój­kowych.

30

W omawianym przykładzie otrzymujemy tablicę pokazani na ry­sunku 2.16

a b c d

8 1 0 0 0

5 0 1 0 1

9 1 0 0 1

10 1 0 1 0

7 0 1 1 1

11 1 0 1 1

13 1 1 0 1

15 I 1

Rys. 2.16. Szeregowanie iloczynów pełnych według liczby jedynek (przykład 2.10)

Następnie porównujemy każdy kombinację należ~c~ do danej grupy z każdy kombinacji należ~c~ do grupy następnej. Jeżeli porównywane kombinacje różnij się od siebie tylko na jednej pozycji, to liczymy je w nowi kombinację, zastępuj~c różnice się pozycje dowolnym zna­kiem, na przykład znakiem -. Otrzymane w ten sposób kombinacje zapisujemy w nowej kolumnie. Z lewej strony kolumny wypisujemy dziesiętne odpowiedniki składników nowej kombinacji.

W omawianym przykładzie otrzymujemy tablicę pokazani na ry­sunku 2.17.

a b c d

8,9 1 0 0 -

8,10 1 0 - 0

5,7 0 1 - 1

5,13 - 1 0 1

9,11 1 0 - 1

9,13 1 - 0 1

10,11 1 0 1 -

7,15 - 1 1 1

11,15 1 - 1 1

13,15 1 1 - 1

Rys. 2.17. Ł~czenie kombinacji różni~cych się na jednej pozycji (przykład 2.10)

31

Kontynuujemy procedurę ł~czenia, usuwaj~c powtarzaj~ce się kom­binacje. Procedurę ł~czenia kończymy wtedy, kiedy nie ma już moż­liwości dokonywania dalszych ł~czeń. Każda kombinacja nie podlega­j~ca dalszemu ł~czeniu jest nazywana implikantem prostym.

W omawianym przykładzie otrzymujemy tablicę pokazani na ry­sunku 2.18.

a b c d 8,9,10,11 1 0 - ­5,7,13,15 - 1 - 1

9,11,13,15 1 - - 1

Rys. 2.18. Uczenie kombinacji różni~cych się na jednej pozycji (przykład 2.10)

Następnie rysujemy siatkę składaj~c~ się z linii pionowych i pozio­mych. Liczba linii pionowych jest równa liczbie iloczynów pełnych mi­nimalizowanej funkcji. Liczba linii poziomych jest równa liczbie otrzy­manych implikantów prostych. Liniom pionowym przypisujemy liczby dziesiętne odpowiadaj~ce iloczynom pełnym, liniom poziomym nato­miast implikanty proste. Analizuj~c siatkę stawiamy dowolny znak, na przyklad kropkę (~), w miejscach, w których linia odpowiedniego implikanta prostego określonego przez dane liczby przecina się z li­niami iloczynów pełnych odpowiadaj~cych tym liczbom.

W omawianym przykładzie otrzymujemy siatkę pokazani na ry­sunku 2.19

5 7 Ł~ 9 10 11 13 15

10 ab

9

11

8

, bd

,

,

7

13

15

5

, ad

,

,

11

13

15

9

,

,

,

Rys. 2.19. Tablica implikantów prostych (przykład 2.10)

Uproszczona funkcja, równoważna funkcji minimalizowanej, może być otrzymana w postaci sumy wybranych implikantów prostych. Wy­bór implikantów prostych jest przeprowadzony tak, aby wszystkie iloczyny pełne występuj~ce w funkcji minimalizowanej byty repre­zentowane w implikantach prostych. Liczba wybranych implikantów

32

prostych powinna być jak najmniejsza. W omawianym przykładzie otrzymujemy następuj~ce funkcje uproszczone, równoważne funkcji minimalizowanej:

fl (a, b, c, d) = ab -~- bd

f2(a, b, c, d) = ab -f- bd + ad

Najmniejsza liczba implikantów prostych występuje w funkcji

fl (a, b, c, d)

Ostatecznie otrzymujemy

f (a, b, c, d) _ ~(5, 7, 8, 9, 10, 11, 13, 15) = ab + bd

Przykład 2.11. Uprościć funkcję

f (a, b, c, d) _ ~(0, 1, 4, 6, 8, 12, 14) + ~ n(5, 10, 13, 15)

Porz~dkuj~c zbiór wszystkich iloczynów pełnych w grupy o takiej samej liczbie jedynek, otrzymujemy tablicę pokazani na rysunku 2.20.

a b c d

0 0 0 0 0

1 0 0 0 1

4 0 1 0 0

8 1 0 0 0

5 0 1 0 1

6 0 1 1 0

10 1 0 1 0

12 1 1 0 0

13 1 1 0 1

14 1 1 1 0

I15I 1 1 1 11

Rys. 2.20. Szeregowanie iloczynów pełnych według liczby jedynek (przykład 2.11)

33

Ł~cz~c różnice się na jednej pozycji kombinacje z s~siednich grup otrzymujemy tablicę pokazani na rysunku 2.21

a b c d

0,1 0 0 0 -

0,4 0 - 0 0

0,8 - 0 0 0

1,5 0 - 0 1

4,5 0 1 0 -

4,6 0 1 - 0

4,12 - 1 0 0

8,10 1 0 - 0

8,12 1 - 0 0

5,13 - 1 0 1

6,14 - 1 1 0

10,14 1 - 1 0

12,13 1 1 0 -

12,14 1 1 - 0

13,15 1 1 - 1

14,15 1 1 1 -

Rys. 2.21. Ł~czenie kombinacji różni~cych się na jednej pozycji (przykład 2.11)

Kontynuuj~c procedurę ł~czenia otrzymujemy tablicę pokazani na rysunku 2.22.

a b c d

0,1,4,5 0 - 0 -

0,8,4,12 - - 0 0

4,5,12,13 - 1 0 -

4,6,12,14 - 1 - 0

8,10,12,14 1 - - 0

12,13,14,15 1 l - -1

Rys. 2.22. Ł~czenie kombinacji różni~cych się na jednej pozycji (przykład 2.11)

34

Ponieważ nie ma już możliwości dokonywania dalszych liczeń, rysujemy siatkę pokazani na rysunku 2.23

0 1 4 6 8 12 14

1 a ć

4

0

5

, ć d

,

,

4

12

0

8

, b e

,

,

13

4

5

12

, b d

,

,

4

12

14

6

, a d

,

,

14

10

12

8

, a b

,

,

14

15

12

13

,

,

,

Rys. 2.23. Tablica implikantów prostych (przykład 2.11)

Otrzymujemy następuj~ce funkcje uproszczone, równoważne funk­cji minimalizowanej:

fl(a,b,c,d)=ać-ł-bd+ćd

f2 (a, b, c, d) = a ć -ł- bd + ad

2.3 Podsumowanie

Opisane w rozdziale 2 metody minimalizacji funkcji logicznych s~ me­todami podstawowymi, z których będziemy korzystali w dalszej części skryptu. S~ również inne metody minimalizacji funkcji logicznych, na przykład metoda bezpośredniego przeszukiwania (~4~). Osobni grupę stanowi metody minimalizacyjne układu funkcji logicznych odnosz~ce się do układów kombinacyjnych wielowyjściowych (układy kombinacyjne będ~ omawiane w rozdziale 3). W tym przypadku poza wymaganiem minimalnej złożoności każdej funkcji logicznej wymaga się również, aby miaky jak najwięcej elementów wspólnych (~1~). Opi­sywane w literaturze (~4, 6~~ metody wykorzystuje w tym przypadku zmodyfikowany algorytm Quine'a-McCluskeya.

35

Literatura

(l~ Kalisz J.: Podstawy elektroniki cyfrowej, WKŁ, 1993. (2J Majewski W.: Układy logiczne, WNT, 1993.

(3~ Mano M.M.: Computer engineering: tcardware design, Prentice-Hall, 1988.

(4~ Traczyk W.: Uklady cyfrowe. Podstawy teoretyczne i metody syntezy, WNT, 1986.

(5J Bromirski J.: Teoria automatów, WNT, 1969.

(6~ McCluskey E.: Logic design principles, Prentice-Hall, 1986

Z a d a n i a

Zadanie 2.1. Uprościć następuj~ce funkcje logiczne:

f~ (A, B, C, D ) _ ~(o, 2, 6, 8, lo,14) ..

f2(A, B, C, D} _ ~(o, 1, 5, 8, 9, 13)

f3(A, B, C, D} _ ~(0, 2, 6, 8) -~ ~ n(10, 11, 12, 13, 14, 15}

a: f~ (A, B, C, D ) _ ~{o, 1, 3, 4, 5, 6, 7, 8, 9) -f- ~ n(10, 11, 12, 13, 14, 15)

I