Minimalizacja funkcji (część 1)
1
Przedmioty prowadzone w ramach
Programu Rozwoju WSFiZ w Białymstoku realizowane są w ramach
Programu Operacyjnego Kapitał Ludzki, Priorytet IV Szkolnictwo wyższe i nauka, Poddziałanie 4.1.1
Wzmocnienie potencjału dydaktycznego uczelni, współfinansowanego ze środków
Europejskiego Funduszu Społecznego (POKL.04.01.01-00-030/08)
5. Minimalizacja funkcji
(część 1)
Spis treści
5.
Minimalizacja funkcji (część 1) ................................................................................................ 1
5.1
Wstęp ................................................................................................................................. 1
5.2
Metoda Karnaugha............................................................................................................. 2
5.3
Przykłady ........................................................................................................................... 7
5.1
Wstęp
Zazwyczaj jest tak, że układ, w którego skład wchodzi mniej elementów jest mniej zawodny i
tańszy w realizacji od układu bardziej złożonego. Z kolei porównując dwa układy o takiej samej
liczbie elementów składowych lepszy jest ten, do realizacji którego użyto mniej połączeń, czyli
ten, który operuje mniejszą liczba sygnałów. Ta ostatnia cecha mierzona jest zazwyczaj liczbą
wejściowych sygnałów wszystkich elementów układu. Rozważania te wskazują, że wśród
różnych możliwych realizacji funkcji przełączających warto poszukiwać takiej, którą da się
zapisać najprościej, tj. używając minimalnej liczby zmiennych i ich negacji. Postępowanie
prowadzące do takiej postaci nazywa sie minimalizacją funkcji. Formalnym narzędziem
używanym w tym celu są tzw. reguły sklejania wyrażające się następującymi tożsamościami:
Ax + Ax = A
(B + x)(B + x) = B
gdzie A i B są dowolnymi zmiennymi lub funkcjami przełączającymi. Jak zwykle prawdziwość
podanych związków można sprawdzić analizując ich lewe i prawe strony dla dwóch możliwych
wartości zmiennej x. Wynika z nich, że dwa wyrażenia (tu iloczyn i suma) różniące się między
sobą dokładnie na jednej pozycji znakiem negacji można zastąpić jednym wyrażeniem bez
zmiennej je różnicującej. Stosowanie podanych reguł nazywamy sklejaniem, a wyrażenia
podlegające sklejaniu – wyrażeniami sąsiednimi. Podane przykłady prezentują efekty sklejania:
x
1
x
2
x
3
+
x
1
x
2
x
3
= x
1
x
3
(x
1
+ x
2
+ x
3
)(x
1
+ x
2
+ x
3
) = x
1
+ x
3
x
1
x
2
+
x
1
x
2
= (x
1
+ x
1
) x
2
= 1∙ x
2
= x
2
Ostatni z przykładów pokazuje, że reguły sklejania mogą być wywiedzione wprost z wcześniej
podanych zależności. Jak bardzo skuteczne mogą być te reguły pokazuje kolejny przykład:
f(x
1
, x
2
, x
3
) = x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
=
= (x
1
x
2
x
3
+
x
1
x
2
x
3
) + (x
1
x
2
x
3
+
x
1
x
2
x
3
) + (x
1
x
2
x
3
+
x
1
x
2
x
3
) =
Minimalizacja funkcji (część 1)
2
= x
1
x
2
+
x
1
x
2
+
x
2
x
3
= x
1
+ x
2
x
3
Warto zwrócić uwagę, że zdwojenie czynnika x
1
x
2
x
3
, (w drugim wierszu prezentowanego
przykładu), które pozwoliło utworzyć dodatkowa parę wyrażeń sąsiednich, a jednocześnie na
mocy wzoru (4.8) nie zmieniło wartości wyrażenia.
Sklejanie tej samej funkcji przedstawionej w postaci kanonicznej iloczynu daje następujący
rezultat:
f(x
1
, x
2
, x
3
) = (x
1
+ x
2
+ x
3
)( x
1
+ x
2
+ x
3
)( x
1
+ x
2
+ x
3
) =
= (x
1
+ x
2
)( x
1
+ x
3
)
Licząc ilość działań: sum, iloczynów i negacji otrzymamy, że dla realizacji postaci kanonicznej
sumy potrzeba 1×OR, 5×AND i 5×NIE, a po sklejeniu: 1×OR i 1×AND. Natomiast dla postaci
kanonicznej iloczynu jest to odpowiednio: 1×AND, 3×OR i 2×NIE oraz 1×AND i 2×OR. Jak
widać różnice są bardzo istotne.
Z przedstawionych przykładów wynika, że w efekcie sklejania otrzymane postaci nie są już
postaciami kanonicznymi, ale zachowują swoją pierwotną postać, tj. odpowiednio sumy i
iloczynu. Postaci takie nazywa się postacią normalną sumy (albo normalną postacią
alternatywną) oraz normalną postacią iloczynu (albo normalną postacią koniunkcyjną).
Wyliczanie tych postaci przez wynajdowanie wyrażeń sąsiednich jest kłopotliwe i łatwo
prowadzi do błędów. Opracowano szereg metod, które istotnie upraszczają tą procedurę bądź
dają się oprogramować i ciężar obliczeń przerzucić na komputer. W dalsze części zostanie
zaprezentowana jedna z nich, użyteczna dla funkcji o liczbie zmiennych mniejszej od 6.
5.2 Metoda Karnaugha
Metoda tablic Karnaugha (inna jej nazwa to metoda kart Veitcha) polega na zapisaniu wartości
funkcji, tj. jej zer i jedynek w specjalnych tablicach w taki sposób, aby wyrażenia sąsiednie były
również sąsiednie w sensie ich umiejscowienia w tabeli, tzn. aby leżały w sąsiednich jej
wierszach lub kolumnach. Przykłady używanych w tej metodzie tablic pokazane są na rysunku
5.1. Każda kratka (i,j) leżąca w i-tym wierszu i j-tej kolumnie tablicy odpowiada wartości funkcji
dla jednej kombinacji jej zmiennych wejściowych. Kombinację tworzy ciąg 0 i 1 uzyskanych ze
zmiennych w taki sam sposób, jak przy wyliczaniu indeksu iloczynu pełnego funkcji (zmiennej
bez negacji odpowiada 1, a zmiennej z negacją – 0). Ta część ciągu, która odpowiada zmiennym
opisującym wiersze jest zapisana jako oznaczenie i-tego wiersza, a pozostała, odpowiadająca
zmiennym opisującym kolumny – jako oznaczenie j-tej kolumny tablicy. Cała kombinacja
została dobrana tak, aby ciągi opisujące wszystkie sąsiednie wiersze i kolumny różniły się na
dokładnie na jednej pozycji, a więc żeby odpowiadały wyrażeniom sąsiednim. Taki sposób
kodowania nazywany jest kodem Graya. Dla ułatwienia odnalezienia kratek, do których należy
wpisać wartości funkcji w tabelach na rysunku 5.1 (patrz niżej) w każdej kratce zamieszczono
wartość odpowiadającego jej indeksu (dziesiętnie).
Minimalizacja funkcji (część 1)
3
x
3
x
4
x
5
000 001 011 010 100 111 101 100
x
1
x
2
00
0
1
3
2
6
7
5
4
01
8
9
11
10
14
15
13
12
11
24
25
27
26
30
31
29
28
10
16
17
19
18
22
23
21
20
Rysunek 5.1b. Tablica Karnaugha dla funkcji 5 zmiennych
Jeżeli w dwóch sąsiednich kratkach tablicy Karnaugha występują takie same wartości (0 lub 1),
to odpowiadające tym kratkom wyrażenia można skleić, co - jak to było wcześniej pokazane -
prowadzi do usunięcia zmiennej i uproszczenia wyrażenia wynikowego. Wygodnie jest takie
pary zaznaczać, co między innymi ułatwia potem weryfikację procesu minimalizacji. Na rysunku
5.2 (niżej) pokazane są przez zakreślenie różne przykładowe, potencjalne lokalizacje takich par.
Jeżeli w zakreślonych kratkach są jedynki, to w miejsce odpowiadającego im wyrażenia Ax + Ax
można przyjąć A, jeżeli zawierają zera – to zamiast (B + x)(B + x) można przyjąć B.
Dla przykładu przeanalizujmy sytuację z rysunku 5.2b (patrz niżej). Załóżmy, że w
zakreślonych kratkach są jedynki, co odpowiada wyrażeniu.
x
1
x
2
x
3
+ x
1
x
2
x
3
= (x
1
+ x
1
)x
2
x
3
= x
2
x
3
x
2
0
1
x
1
0
0
1
1
2
3
x
3
x
4
00
01
11
10
x
1
x
2
00
0
1
3
2
01
4
5
7
6
11
12
13
15
14
10
8
9
11
10
x
2
x
3
00
01
11
10
x
1
0
0
1
3
2
1
4
5
7
6
Minimalizacja funkcji (część 1)
4
a)
b)
c)
d)
e)
f)
Rysunek 5.2. Przykłady lokalizacji obszarów sklejania dla funkcji trzech zmiennych
Wynik taki można otrzymać wprost z tablicy. Powody tego są następujące:
1) dwie występujące w zaznaczonej grupie kratki opisuje kolumna x
2
x
3
= 10, co oznacza, że
zmienna x
2
występuje w obu grupach bez przeczenia, a zmienna x
3
- w obu grupach z
przeczeniem;
2) opisujące grupę wiersze to x
1
= 0 oraz x
1
= 1, co oznacza, ze zmienna x
1
występuje w jednej
grupie z przeczeniem, a w drugiej bez, a to oznacza, że może być usunięta.
Ponieważ jedynkom w postaci kanonicznej odpowiadają iloczyny, to i wynik sklejenia też
będzie iloczynem, w którym zeru odpowiada zmienna przeczona x, a jedynce – zmienna bez
przeczenia: x.
Załóżmy z kolei, że w tych samych zakreślonych kratkach (rysunek 5.2b) są zera, co
odpowiada wyrażeniu.
(x
1
+ x
2
+ x
3
) (x
1
+ x
2
+ x
3
) = x
2
+ x
3
Tak jak uprzednio, wynik ten można otrzymać wprost z tablicy, jeżeli tylko zastosuję się
zasadę, że zmienna występująca w grupie jako 0 i jako 1 jest odrzucana, oraz że wynik finalny
będzie sumą (bo zeru w postaci kanoniczne odpowiada suma), w której zero odpowiada zmiennej
bez przeczenia: x, a jedynce – zmienna z przeczeniem: x.
Dwie kratki tablicy o takich samych wartościach można skleić z inną parą o analogicznych
wartościach, jeżeli tylko obrys zaznaczeń obu par tworzy prostokąt albo kwadrat (patrz rysunek
5.2d, e, f). W takich sytuacjach do sklejania można użyć następujących wzorów:
(Ax
1
x
2
+ Ax
1
x
2
) + (Ax
1
x
2
+ Ax
1
x
2
) = A
[(B + x
1
+ x
2
) (B + x
1
+ x
2
)][(B + x
1
+ x
2
) (B + x
1
+ x
2
)] = B
x
2
x
3
00
01
11
10
x
1
0
1
x
2
x
3
00
01
11
10
x
1
0
1
x
2
x
3
00
01
11
10
x
1
0
1
x
2
x
3
00
01
11
10
x
1
0
1
x
2
x
3
00
01
11
10
x
1
0
1
x
2
x
3
00
01
11
10
x
1
0
1
Minimalizacja funkcji (część 1)
5
Tak więc grupę jednakowych wartości w kształcie prostokąta można opisać iloczynem (grupę
jedynek) lub sumą (grupę zer), w skład której wejdą tylko te zmienne, których wartości w ramach
opisywanej grupy nie zmieniają się. Wyniki sklejania dla sytuacji z rysunku 5.2d, e i f (patrz
wyżej) wynoszą odpowiednio dla jedynek i zer: x
3
i x
3
; x
1
i x
1
oraz x
3
i x
3
.
Analogicznie opisuje sie grupy dwu- i cztero-kratkowe w tablicy dla funkcji czterech
zmiennych (patrz rysunek 5.3a, b, d, e, i f).
a)
b)
c)
d)
e)
f)
Rysunek 5.3 Przykłady lokalizacji obszarów sklejania dla funkcji czterech zmiennych
Możliwości sklejań jest tu więcej. Proszę zwrócić uwagę na 4-klatkową grupę w tabeli 5.3c.
Jeżeli byłyby w niej jedynki, to wyrażenie ją opisujące jest: x
2
x
4
. Dla grupy z rysunku 5.3e) i
jedynek opis jest: x
1
, a dla zer x
1
.
Im większa grupa tym więcej zmiennych jest wyeliminowanych i tym krótsze wyrażenie.
Grupa 2-kratkowa eliminuje 1 zmienną, 4-kratkowa – 2, a 8-kratkowa – 3 zmienne.
Tabela dla 5 zmiennych jest złożeniem dwóch tabel dla 4 zmiennych. Wewnątrz tych tabel
obowiązują reguły sklejania analogiczne jak dla zwykłej tabeli.
Ponadto dochodzi dodatkowa reguła: każda kratka ma kratkę sąsiednią położoną symetrycznie
wobec niej, przy czym osią symetrii jest linia rozdzielająca dwie tablice składowe.
x
3
x
4
00
01
11
10
x
1
x
2
00
01
11
10
x
3
x
4
00
01
11
10
x
1
x
2
00
01
11
10
x
3
x
4
00
01
11
10
x
1
x
2
00
01
11
10
x
3
x
4
00
01
11
10
x
1
x
2
00
01
11
10
x
3
x
4
00
01
11
10
x
1
x
2
00
01
11
10
x
3
x
4
00
01
11
10
x
1
x
2
00
01
11
10
Minimalizacja funkcji (część 1)
6
Wybrane grupy utworzone zwłaszcza przy użyciu tej ostatniej reguły pokazane są na
rysunkach 5.4a i b.
a)
b)
x
3
x
4
x
5
000 001 011 010 100 111 101 100
x
1
x
2
00
01
11
10
Rysunek 5.4. Przykłady lokalizacji obszarów sklejania dla funkcji 5 zmiennych
Tworzenie tabel dla większej ilości zmiennych jest możliwe i przebiega według reguł
identycznych jak dla tabeli dla 5 zmiennych. I tak tabela dla 6 zmiennych będzie złożeniem 2
tabel dla pięciu zmiennych z regułami sklejania wewnątrz nich takimi jak dla zwykłych tabel dla
5 zmiennych. Dodatkowa oś symetrii przebiegająca wzdłuż osi poziomej wprowadza nowe
reguły sklejania. Komplikuje to na tyle wyszukiwanie wyrażeń sąsiednich, że metoda Karnaugha
staje się nieprzydatna. Można wtedy posłużyć się innymi metodami, np. Quine’a-Mc Cluskeya.
Podane przykłady pozwalają sformułować zestaw kroków, które należy wykonać w celu
znalezienia minimalnej postaci funkcji przełączającej. I tak:
1. Należy zdecydować, czy będzie sie wyszukiwało grupy zer czy grupy jedynek. Jeżeli pole
decyzji nie jest ograniczone przez typ posiadanych elementów, to należy łączyć w grupy te
wartości, które dadzą prostsze rozwiązanie. Przesłankami do podjęcia konkretnej decyzji
może być np. porównanie liczby grup dla obu wartości. Czasami nie ma innego wyjścia jak
sprawdzić obydwa warianty.
2. Należy podjąć próbę wyszukania największej możliwej grupy lub kilku takich grup,
zaczynając od grupy 16-kratkowej, następnie 8-, 4- i 2-kratkowej. Jedynki lub zera leżące
poza zaznaczonymi grupami próbuje się łączyć w grupy mniejsze, przy czym można do tego
x
3
x
4
x
5
000 001 011 010 100 111 101 100
x
1
x
2
00
01
11
10
Minimalizacja funkcji (część 1)
7
wykorzystywać fragmenty już zaznaczonych grup, jeżeli tylko dzięki temu nowo utworzona
grupa ulegnie powiększeniu. Finalnie, jeżeli zostaną jakieś pojedyncze, niezaznaczone dotąd
wartości, to należy z nich utworzyć grupy jedno-elementowe.
3. Jeżeli wszystkie elementy jakiejś grupy należą do innych grup, to taką grupę należy pominąć.
Pozostałe grupy należy opisać jako postać normalną tak jak to było wcześniej wyjaśnione.
5.3
Przykłady
Poniżej zamieszczono kilka przykładów ilustrujących proces minimalizacji.
Zaczniemy od funkcji, która ma znajdować 3-bitowe liczby parzyste i niepodzielne przez 3.
Tabelaryczny opis tej funkcji jest na rysunku 4.1. Odpowiadająca jej tabela Karnaugha
przedstawiona jest na rysunku 5.5 a i b.
a)
c)
d)
b)
Rysunek 5.5. Przykłady minimalizacji funkcji.
Po minimalizacji otrzymujemy wzory:
f(x
1
x
2
) = x
2
x
3
+ x
1
x
3
f(x
1
x
2
) = x
2
(x
1
+ x
2
)
Minimalizacja funkcji zadanej wzorem:
f(x
1
x
2
x
3
x
4
) =
∑
(0, 3, 4, 6, 10, 11, 12, 14, 15)
pokazana jest na rysunku 5.5c i 5.5d. W jej rezultacie otrzymujemy wyrażenia:
x
2
x
3
00
01
11
10
x
1
0
1
0
0
1
1
1
0
0
0
x
3
x
4
00
01
11
10
x
1
x
2
00
1
0
1
0
01
1
0
0
1
11
1
0
1
1
10
0
0
1
1
x
3
x
4
00
01
11
10
x
1
x
2
00
1
0
1
0
01
1
0
0
1
11
1
0
1
1
10
0
0
1
1
x
2
x
3
00
01
11
10
x
1
0
1
0
0
1
1
1
0
0
0
Minimalizacja funkcji (część 1)
8
f(x
1
x
2
x
3
x
4
) = x
2
x
4
+ x
1
x
3
+ x
1
x
3
x
4
+ x
2
x
3
x
4
(1)
oraz
f(x
1
x
2
x
3
x
4
) = (x
3
+ x
4
)(x
1
+ x
2
+ x
4
)( x
1
+ x
2
+ x
3
)( x
1
+ x
2
+ x
3
+ x
4
)
A oto jeszcze inne przykłady:
a)
b)
c)
Rysunek 5.6. Przykłady minimalizacji funkcji.
Przykład z rysunku 5.6a) ilustruje tezę o nieuwzględnianiu we wzorze na minimalną postać
funkcji takiej grupy, której wszystkie elementy wchodzą w skład innych grup. Stąd dla tej funkcji
postać minimalna wyraża się wzorami:
f(x
1
x
2
x
3
x
4
) = x
1
x
2
x
3
+ x
2
x
3
x
4
+ x
2
x
3
x
4
+ x
1
x
2
x
3
f(x
1
x
2
x
3
x
4
) = (x
2
+ x
3
+ x
4
)( x
1
+ x
2
+ x
3
)( x
1
+ x
2
+ x
3
)( x
2
+ x
3
+ x
4
)
Pojawienie się nadmiarowych grup może być spowodowane zapisem wartości funkcji do tabeli
na podstawie jej postaci niekanonicznej normalnej, co może się zdążyć, jeżeli korzystamy np. z
opisu słownego funkcji. Sytuację taka ilustruje kolejny przykład, w którym punktem wyjścia jest
wzór uzyskany np. właśnie z takiego opisu:
f(x
1
x
2
x
3
x
4
) = (x
3
+ x
4
)(x
1
+ x
2
+ x
4
)( x
1
+ x
2
+ x
4
)( x
1
+ x
2
+ x
3
)
Na rysunku 5.5b) pokazana jest odpowiadająca temu wzorowi tablica. Linią przerywaną
zaznaczono nadmiarową grupę, która powstała jako realizacja ostatniej z sum w powyższym
wzorze. Jej zera wchodzą w skład innych grup i właśnie z tego powodu nie znajdzie się ona w
postaci minimalnej:
f(x
1
x
2
x
3
x
4
) = (x
3
+ x
4
)(x
1
+ x
2
+ x
4
)( x
1
+ x
2
+ x
4
)
Na rysunku 5.5c) pokazano z kolei funkcję, która posiada dwie minimalne postacie sumy:
f(x
1
x
2
x
3
x
4
) = x
1
x
3
+ x
1
x
3
x
4
+ x
1
x
2
x
4
albo
f(x
1
x
2
x
3
x
4
) = x
1
x
3
+ x
1
x
3
x
4
+ x
2
x
3
x
4
(alternatywne grupy, tj. x
1
x
2
x
4
i x
2
x
3
x
4
zaznaczone są linią przerywaną).
x
3
x
4
00
01
11
10
x
1
x
2
00
0
0
1
0
01
0
1
0
0
11
0
1
1
1
10
1
1
1
0
x
3
x
4
00
01
11
10
x
1
x
2
00
1
0
0
1
01
1
1
0
1
11
1
1
0
1
10
0
1
0
0
x
3
x
4
00
01
11
10
x
1
x
2
00
0
0
1
0
01
0
1
1
0
11
1
1
0
0
10
1
1
0
0
Document Outline