MINIMALIZACJA FUNKCJI LOGICZNYCH
Funkcja logiczna może być w ogólnym przypadku przedstawiona za pomocą
wielu różnych mniej lub bardziej skomplikowanych funkcji logicznych.
Zagadnienie minimalizacji polega na wyznaczeniu dla danej funkcji tej formuły
która jest najprostsza. Zagadnienie to formułuje się też inaczej  dla danej
funkcji logicznej należy wyznaczyć możliwą najprostszą funkcję równoważną.
Minimalizacja funkcji logicznej wiąże się z porównaniem stopnia
skomplikowania funkcji. Dla porównania funkcji wprowadza się pojęcie
współczynnika skomplikowania definiowanego w rożny sposób. Jedna z
możliwych definicji współczynnika skomplikowania brzmi:
Współczynnikiem skomplikowania W funkcji logicznej i (and), lub (or),
nie (not) nazywamy sumę liczby wyrażeń (pojedynczych liter lub ich
kombinacji) podlegających mnożeniu i liczby wyrażeń podlegających
dodawaniu.
Metody minimalizacji funkcji logicznych można podzielić na dwie grupy.
Do pierwszej grupy należą metody przekształceń algebraicznych. Metody te nie
są zbyt przydatne w praktyce. Do drugiej grupy należą metody algorytmiczne.
Metoda Quine a McCluskeya
Algorytm wprowadzimy rozważając następujący przykład.
Wyznaczyć minimalną funkcję logiczną równoważną funkcji:
F = x + x x + x x + x x x + x x + x x x + x x x +
x x x x x x x x x x x x
1 1 2 3 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
+ x x x x
1 2 3 4
1. Wypisujemy kombinacje zer i jedynek odpowiadające kolejnym pełnym
iloczynom. Iloczynom tym przyporządkowujemy numery w sposób analogiczny
do przyjętego poprzednio.
2 0010
3 0011
6 0110
7 0111
12 1100
13 1101
14 1110
15 1111
2. Szeregujemy te kombinacje według liczby jedynek. Otrzymujemy w ten
sposób grupy n = 0, 1, 2 ... jedynek
1
2 0010
3 0011
6 0110
12 1100
7 0111
13 1101
14 1110
15 1111
3. Porównujemy każdą kombinację należącą do grupy i-tej z każdą kombinacją
należącą do grupy i + 1. Jeżeli dwie takie kombinacje różnią się tylko na jednej
pozycji to kombinacje te sklejamy w jedną nową kombinację zastępując pozycje
y
różniące się symbolem Ć. Wykorzystujemy tu związek xy +x =x. W
poprzedniej tablicy odznaczamy ((") kombinacje używane przy dokonywaniu
sklejeń i tworzymy nową tabelę.
2 0010 2,3
(" 001Ć
3 0011 2,6
(" 0Ć10
6 0110 3,7
(" 0Ć11
12 1100 6,7
(" 011Ć
7 0111 6,14
(" Ć110
13 1101 12,13
(" 110Ć
14 1110 12,14
(" 11Ć0
15 1111 7,15
(" Ć111
13,15
11Ć1
14,15
111Ć
4. Kontynuujemy procedurÄ™ usuwajÄ…c kombinacje powtarzajÄ…ce siÄ™ i Å‚Ä…czÄ…c
kombinacje różniące się na jednej pozycji
5. Procedurę kończymy, gdy nie ma już możliwości dokonania dalszych sklejeń.
W rozważanym przykładzie otrzymujemy ostatecznie:
2, 3, 6, 7,
0Ć1Ć
6, 7, 14, 15,
Ć11Ć
12, 13, 14, 15,
11ĆĆ
W tabeli pomijamy zestawy numerów nie prowadzących do nowych kombinacji
 np. 2, 6, 3, 7 w stosunku do uwzględnionego 2, 3, 6, 7.
2
6. Tworzymy zbiór kombinacji nie mogących podlegać dalszemu sklejaniu. Do
zbioru tego należą te kombinacje, które znalazły się w tablicy końcowej oraz te,
które nie mogły być zastosowane do dalszego sklejania.
Punkt 6 kończy pierwszą część minimalizacji. Do jej kontynuowania
potrzebna jest następująca definicja:
Formułę G nazywamy implikantem formuły F, gdy (G F) =1 albo
G + F=1
Oznacza to, że jeżeli G = 1, to F = 1, ale nie musi być odwrotnie. Implikantami
formuły kanonicznej sumy są więc wszystkie iloczyny pełne i wszystkie ich
połączenia typu x x + x x x = x x .
x
1 2 3 1 2 3 1 2
Formułę G1 nazywamy prostym implikantem formuły F, gdy G1 jest
implikantem formuły F oraz gdy nie istnieje formuła G2 taka, że
(G1 G2) = 1 oraz (G2 F) = 1
Prostymi implikantami są więc wszystkie iloczyny, których kombinacje zer i
jedynek należą do zbioru otrzymanego w p. 6. Dla formuły x x + x x x +
x
1 2 3 1 2 3
+ x x x
1 2 3
wszystkie trzy iloczyny pełne są implikantami, a iloczyny x1x2, x 1 x 2 x 3
są prostymi implikantami. Można więc powiedzieć, że prostym implikantem jest
taki implikant, który nie może być połączony z żadnym innym implikantem bez
utraty swojej podstawowej własności.
Pojęcie implikantu sformułowane dla wyrażeń może być także odniesione
do funkcji tym wyrażeniom odpowiadającym. Niech wyrażeniom logicznym F i
G odpowiadają funkcje f 1 i g1. G jest wtedy implikantem F, jeżeli g1 ą" f 1, czyli
zbiór jedynek G zawiera się w zbiorze jedynek F.
Poszukiwana formuła minimalna F równoważna formule początkowej F
2 1
może być otrzymana w postaci sumy wyselekcjonowanych implikantów
prostych. Selekcji dokonuje się w taki sposób, aby wszystkie pełne iloczyny
występujące w formule F były reprezentowane w wybranych implikantach
1
prostych; liczba wybranych implikantów powinna być jak najmniejsza. Jeżeli
istnieje kilka takich zestawów implikantów prostych, wybieramy ten, w którym
występuje najmniejsza łączna liczba liter.
Zagadnienie selekcji wyjaśnimy na podanym przykładzie.
Proste implikanty rozważanej formuły możemy zapisać w sposób
następujący:
x x = G (2,3,6,7); x x = G (6,7,14,15);
1 3 1 2 3 2
3
x x = G (12,13,14,15)
1 2 3
Oznacza to, że np. implikant x x powstał w wyniku połączenia pełnych
1, 3
iloczynów o indeksach 2, 3, 6, 7. Selekcję wykonujemy, korzystając z tablicy
implikantów prostych.
x x 2, 3, 6, 7
1 3
x x 6, 7, 14, 15
2 3
x x 12, 13, 14, 15
1
2
2 3 6 7 12 13 14 15
Wybieramy taki zestaw implikantów, aby w każdej kolumnie występował co
najmniej jeden znaczek selekcji (kółeczko) i aby liczba wybranych
implikantów była jak najmniejsza. W rozważanym przykładzie mamy
ostatecznie F = x + x x . Współczynnik skomplikowania dla F i F
x
2 1 3 1 2 1 2
wynoszÄ… odpowiednio 12 i 6.
Jeżeli funkcja, której formuła podlega redukcji nie jest określona dla
pewnych wyrazów n-tych danej funkcji, to odpowiednie iloczyny kanoniczne
są stosowane w procesie wyznaczania implikantów prostych, ale nie
występują w tablicy implikantów przeznaczonej do selekcji. Przykład:
Należy wyznaczyć formułę minimalną, która będzie równoważna
formule: F = x x x + x x + z dodatkowymi warunkami x x
x x x x x
1 1 2 3 1 2 3 1 2 3 1 2 3
= x = 0
x x
1 2 3
Proces minimalizacji:
0 000 0 000 0, 4
(" Ć00
x4 100 x4 100 4, 5
(" 10Ć ("
x5 101 x5 101 4, 6
(" 1Ć0 ("
6 110 6 110 5, 7
(" 1Ć1 ("
7 111 7 111 6, 7
(" 11Ć ("
4
4, 5, 6, 7, 1ĆĆ
0 6 7
x x
0,4
2 3
x 4, 5, 6, 7
1
Otrzymujemy F = x + . Formule F bez warunków dodatkowych
x x
2 1 2 3 1
odpowiada formuła F = x x +
Współczynniki skomplikowania dla F ,
x x x
3 1 2 1 2 3 1
F , F wynoszÄ… odpowiednio 12, 5, 7.
2 3
Rozważana metoda w podanej postaci nadaje się do minimalizacji formuł
przedstawionych w postaci sumy pełnych iloczynów (formuł kanonicznych
sumy).
Minimalizacja formuł przedstawionych w postaci iloczynów pełnych sum
kanonicznych (formuł kanonicznych iloczynu) można dokonać przez przejście
od danej postaci iloczynu do jej negacji (postaci sumy); formuła ta jest
minimalizowana w podany sposób a następnie znowu wyznaczana jest negacja.
Metoda Veitcha-Karnaugh
Metoda Veitcha-Karnaugha polega na zastosowaniu tzw. diagramów Veitcha
lub tablic Karnaugha. Tablica taka  kwadratowa lub prostokÄ…tna  dla m
zmiennych składa się z 2m ponumerowanych kratek. W każdej kratce jest
wpisany numer kombinacji odpowiadajÄ…cy kratce (np. w prawym, dolnym rogu)
oraz wartość funkcji 0, 1 albo symbol  lub x, jeżeli wartość funkcji jest
nieokreślona.
Przykład przedstawienia funkcji czterech zmiennych za pomocą tablic
Karnaugha:
Funkcja zupełna funkcja niezupełna
00 01 11 10 x x 00 01 11 10 x x
3 4 3 4
00 0 1 0 0 00 0 1 0
çÅ‚
0 1 3 2 0 1 2
3
01 0 0 1 0 01 1 0
çÅ‚ çÅ‚
4 5 7 6 7 6
4 5
11 0 1 1 1 11 1 1 1
çÅ‚
5
12 13 15 14 12 13 15 14
10 0 0 1 0 10 0 0
çÅ‚ çÅ‚
8 9 11 10 9 10
8 11
x x x x
1 2 1 2
Każda kratka tablicy Karnaugha odpowiada kombinacji (wektorowi) zmiennych.
Można więc powiedzieć że kombinacja tych zmiennych tworzy adres kratki.
Kratki są ponumerowane, przy czym jak już pokazano numer (i) jest liczbą
dziesiętną odpowiadającą kombinacji zmiennych (wektorowi
zerojedynkowemu) traktowanej jako liczba dwójkowa. W poszczególnych
kratkach są wpisane  obok numerów  wartości funkcji (tj. 0 lub 1)
przyjmowane przez funkcję dla tej kombinacji, symbol  lub x, jeżeli funkcja
nie jest określona. Można też powiedzieć, że kratka o numerze i zawierająca 1
odpowiada iloczynowi pełnemu P w kanonicznej postaci sumy dla danej
i
funkcji. Natomiast kratka o numerze i zawierająca 0 odpowiada sumie pełnej S
i
w kanonicznej postaci iloczynu.
Diagram Veitcha jest tworem analogicznym do tablicy Karnaugha; różni
się sposobem opisu tablicy. Można powiedzieć, że tablica Karnaugha ma opis
analityczny, a diagram Veitcha ma opis rysunkowy.
Zasada tworzenia diagramu Veitcha:
1) sumie wszystkich pełnych iloczynów (równej jedności) albo iloczynowi
wszystkich pełnych sum (równej zeru) odpowiada powierzchnia całego
kwadratu (prostokÄ…ta);
2) każdej zmiennej odpowiada połowa powierzchni kwadratu; druga połowa
odpowiada tej zmiennej zanegowanej; powierzchnie odpowiadajÄ…ce
dwom różnym zmiennym nie mogą być identyczne;
3) każdemu iloczynowi P odpowiada kratka (mały kwadrat) stanowiący
j
wspólną powierzchnię powierzchni odpowiadających zmiennym (prostym
lub zanegowanym), które występują w tym iloczynie; ta sama kratka
odpowiada sumie S .
j
Dla przykładu iloczynowi x x
1 2 3
x
= P6 dla trzech zmiennych odpowiada
kratka stanowiąca wspólną część  połowy x1 ,  połowy x2 i  połowy nie x3 ;
1 2 3
x x x
ta sama kratka odpowiada pełnej sumie + + = S6 (oczywiście S6 =
6 1 2 3
P x x x
). Inaczej - sumie + + odpowiada kratka stanowiąca wspólną
część  połowy x1 ,  połowy x2 i  połowy nie x3 ; należy tu zwrócić uwagę
na odmiennÄ… konwencjÄ™ przy przyporzÄ…dkowywaniu kratek
odpowiadających pełnym sumom.
Tablice Karnaugha i diagramy Veitcha dla:
- dwóch zmiennych
Tablice Karnaugha Diagramy Veitcha
x
2
0 1 x
2
6
0 0 1 0 1
1 2 3 x 2 3
1
x
1
- trzech zmiennych
Tablice Karnaugha Diagramy Veitcha
x
2
00 01 11 10 x x
2 3
0 0 1 3 2 0 1 3 2
1 4 5 7 6 x 4 5 7 6
1
x
1
x
3
Inny wariant
x
3
0 1 x
3
00 0 1 0 1
01 2 3 2 3
x
2
11 6 7 6 7
x
1
10 4 5 4 5
x x
1 2
- czterech zmiennych
x
3
00 01 11 10 x x
2 3
00 0 1 3 2 0 1 3 2
01 4 5 7 6 4 5 7 6
x
2
11 12 13 15 14 12 13 15 14
x
1
10 8 9 11 10 8 9 11 10
7
x x
1 2
x
4
Inny wariant
000 001 011 010 110 111 101 100 x x x
2 3 4
0 0 1 3 2 6 7 5 4
1 8 9 11 10 14 15 13 12
x
1
0 1 x
4
000 0 1
001 2 3
011 6 7
010 4 5
110 12 13
111 14 15
101 10 11
100 8 9
x x x
1 2 3
- pięciu zmiennych
000 001 011 010 110 111 101 100 x x x
3 4 5
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
8
10 16 17 19 18 22 23 21 20
x x
1 2
Inny wariant
00 01 11 10 x x
4 5
000 0 1 3 2
001 4 5 7 6
011 12 13 15 14
010 8 9 11 10
110 24 25 27 26
111 28 29 31 30
101 20 21 23 22
100 16 17 19 18
x x x
1 2 3
- sześciu zmiennych
000 001 011 010 110 111 101 100 x x x
4 5 6
000 0 1 3 2 6 7 5 4
001 8 9 11 10 14 15 13 12
011 24 25 27 26 30 31 29 28
010 16 17 19 18 22 23 21 20
110 48 49 51 50 54 55 53 52
111 56 57 59 58 62 63 61 60
101 40 41 43 42 46 47 45 44
9
100 32 33 35 34 38 39 37 36
x x x
1 2 3
x
4
x x
6 6
0 1 3 2 6 7 5 4
8 9 11 10 14 15 13 12
x
3
24 25 27 26 30 31 29 28
x
2
16 17 19 18 22 23 21 20
48 49 51 50 54 55 53 52
x
2
56 57 59 58 62 63 61 60
x x
1 3
40 41 43 42 46 47 45 44
32 33 35 34 38 39 37 36
x x
5 5
Tablice Karnaugha i diagramy Veitcha mają następujące zastosowania:
1) przedstawienie funkcji logicznej
2) wyznaczenie negacji
3) sprowadzenie formuł logicznych do postaci kanonicznej
4) uproszczenie formuł logicznych
5) synteza funkcji logicznych
Punktem wyjścia do minimalizacji jest najczęściej funkcja zadana tablicą
prawdy lub tablicą Karnaugha, lub w postaci zbiorów f 1 i f 0. Odpowiada to
oczywiście kanonicznej postaci sumy lub iloczynu; jednak operowanie tymi
wyrażeniami jest w praktyce niewygodne zwłaszcza dla funkcji niezupełnych.
Minimalizacja formuły logicznej przedstawionej w postaci sumy iloczynów
(nie koniecznie pełnych) za pomocą diagramów Veitcha sprowadza się do
następujących czynności:
10
1) Przedstawienie formuły za pomocą diagramu Veitcha (jeżeli jest to
potrzebne).
2) Wyznaczenie prostych implikantów przez sklejenie możliwie jak
największych grup (par, czwórek, ósemek, ...) kratek zawierających
jedynki bÄ…dz
też jedynki i krzyżyki według podanych reguł
W diagramie dwóch, trzech, czterech zmiennych sklejać można
a) pary kratek przylegające do siebie  wewnętrznie (np. 9-11 lub 14-
10 na wykresie czterech zmiennych) lub  zewnętrzne (np. 8-0 lub
8-10)
b)  kwadraty wewnętrzne (np. 9-11-15-13) lub zewnętrzne (np. 9-8-
1-0, 8-10-0-2
c) pary wierszy lub kolumn przylegających do siebie wewnętrznie lub
zewnętrznie.
W diagramach pięciu lub sześciu zmiennych można sklejać grupy
kratek leżące symetrycznie względem osi symetrii w dwóch
częściach diagramu (np. dla pięciu zmiennych), z których każda jest
diagramem składowym (np. dla czterech zmiennych); dla pięciu
zmiennych można np. skleić kratki 5 i 7 z kratkami 21 i 23.
3) Wybranie niektórych grup z grup otrzymanych w p. 2 oraz
pojedynczych kratek (zawierających jedynki), które nie mogły być
sklejone, zgodnie z następującymi zasadami:
a) każda jedynka musi być co najmniej jeden raz reprezentowana w
zbirze wybranych grup
b) liczba wybranych grup powinna być możliwie jak najmniejsza
Suma iloczynów odpowiadających wybranym grupom stanowi
formułę minimalną równoważną formule pierwotnej.
Punkt 3 omawianej procedury odpowiada drugiej części procedury
Quine a. W przypadkach bardziej złożonych może być celowe dokonanie
pierwszej części minimalizacji metodą Veitcha, a drugiej Quine a z użyciem
tablicy implikantów.
Przykład: należy podać formuły minimalne dla funkcji f i f podanych w
1 2
tablicach
00 01 11 10 x x 00 01 11 10 x x
3 4 3 4
00 0 1 0 0 00 0 1 0
çÅ‚
0 1 3 2 0 1 2
3
01 0 0 1 0 01 1 0
çÅ‚ çÅ‚
4 5 7 6 7 6
4 5
11 0 1 1 1 11 1 1 1
çÅ‚
12 13 15 14 13 15 14
12
10 0 0 1 0 10 0 0
çÅ‚ çÅ‚
11
8 9 11 10 8 9 11 10
x x x x
1 2 1 2
Otrzymujemy:
00 01 11 10 x x 00 01 11 10 x x
3 4 3 4
00 0 1 0 0 00 0 1 0
çÅ‚
0 1 3 2 0 1 2
3
01 0 0 1 0 01 1 0
çÅ‚ çÅ‚
4 5 7 6 7 6
4 5
11 0 1 1 1 11 1 1 1
çÅ‚
12 13 15 14 13 15 14
12
10 0 0 1 0 10 0 0
çÅ‚ çÅ‚
8 9 11 10 9 10
8 11
x x x x
1 2 1 2
Wyrażenie minimalne dla funkcji f ma postać
1
F = x x x + x x x + x x x + x x x + x
x x x
1min 1 2 3 1 2 4 1 3 4 2 3 4 1 2 3 4
14-15 13-15 11-15 7-15 1
Liczby pod wyrażeniami oznaczają numery sklejonych kratek. Dla funkcji f
2
będzie to:
F = x x + x x
2min 1 2 1 4
12.13.14.15 1-3-5-7
Należy zwrócić uwagę że użycie kresek do uproszczenia ma istotne znaczenie.
Kreski sklejone z jedynkami  stajÄ… siÄ™ jedynkami. Kreski niesklejane  stajÄ…
się zerami. Tak więc otrzymane wyrażenie interpretowane w pełnym zbiorze
{0, 1}3 odpowiada funkcji zupełnej.
1
= {1, 3, 5, 7, 12, 13, 14, 15}
F
2
0
= {0, 2, 4, 6, 8, 9, 10, 11}
F
2
Natomiast dla funkcji niezupełnej mamy
1
= {1, 7, 13, 14, 15}
F
2
0
= {0, 2, 6, 9, 10}
F
2
Oczywiście
1 1/ 0 0 /
Ä…" Ä…"
F F F F
2 2 2 2
oraz
12
Natomiast wyrażenie F2min odpowiada funkcji f2 w zbiorze jej określoności, tj.
1 0
F F
2 2
dla *"
W wyrażeniach logicznych minimalnych lub częściowo zminimalizowanych
występują także iloczyny niepełne, tj. nie zawierające wszystkich zmiennych.
Takie iloczyny mogą być jednoznacznie powiązane z odpowiednimi wektorami.
Trzeba przyjąć
ej
e1 em
x
x j x
1 m
WL(e1) = ... ...
przy czym
dla e = 0
j j
x
ej
x dla e = 1
j j
=
x
j
1 dla ej = *
Funkcja f może być wtedy zapisana jako
m*
f :
D
{0,1}

m*
{0, 1, *}m
Ä…"
D
przy czym
Przykład:
Korzystając z wprowadzonego aparatu formalnego możemy napisać dla f i f
1 2
e e e e
1 2 3 4
1 1 1 x
1 1 x 1
f = WL-1(F 1 x 1 1
1 1min
x 1 1 1
0 0 0 1
e e e e
1 2 3 4
1 1 x x
f = WL-1(F )
2 2min
0 x x 1
Funkcje f i f przyporządkowują podanym wyżej wektorom wartość 1.
1 2
Przykład:
Funkcja zupełna f (x , x , x , x , x , x ) jest dana w postaci F = {2, 5, 6, 7, 9, 10,
1 2 3 4 5 6 1
11, 13, 14, 15, 16, 18, 20, 22, 24, 25, 26, 27, 28, 30, 41, 43, 48, 52, 54, 55, 56,
57, 59, 60}. Funkcja ta jest podana za pomocÄ… tablicy Karnaugha.
13
000 001 011 010 110 111 101 100 x x x
4 5 6
0 0 0 1 1 1 1 0
000
0 1 3 2 6 7 5 4
0 1 1 1 1 1 1 0
001
8 9 11 10 14 15 13 12
1 1 1 1 1 0 0 1
011
24 25 27 26 30 31 29 28
1 0 0 1 1 0 0 1
010
16 17 19 18 22 23 21 20
1 0 0 0 1 1 0 1
110
48 49 51 50 54 55 53 52
1 1 1 0 0 0 0 1
111
56 57 59 58 62 63 61 60
0 1 1 0 0 0 0 0
101
40 41 43 42 46 47 45 44
0 0 0 0 0 0 0 0
100
32 33 35 34 38 39 37 36
x x x
1 2 3
Wyrażenie minimalne z tablicy Karnaugha ma postać
F (x , x , x , x , x , x ) = x + x + x x + x x +
x x x x x x x
min 1 2 3 4 5 6 1 5 6 2 5 6 3 4 6 1 2 4 6
+ x x x x
x
1 2 3 4 5
Przykład
Należy zminimalizować funkcję f przedstawioną w tabeli, podając minimalną
1
sumę iloczynów i minimalny iloczyn sum. Zastosować tablice Karnaugha.
Funkcja f
1
i x x x f
1 3 1
2
14
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
Po sklejeniu jedynek otrzymujemy
00 01 11 10 x x
2 3
0 0 1 0
0
0 1 3 2
0 1 1 1
1
4 5 7 6
x
1
Otrzymujemy: F = x x + x x + x x
1 1 2 2 3 3 1
6-7 3-7 5-7
Natomiast sklejenie zer
00 01 11 10 x x
2 3
0 0 1 0
0
0 1 3 2
0 1 1 1
1
4 5 7 6
x
1
prowadzi do par kratek 0-1, 0-2, 0-4, co odpowiada operacjom na wektorach
)#
000*# *)# 001*# = )# 00x*# x + x
1 2
000 010 = 0x0 x + x
)# *# )# *#
1 3
*)# *#
000 100 = x00 x + x
)# *# )# *#
2 3
*)# *#
Otrzymujemy w wyniku sklejenia podane wyżej wektory i odpowiadające im
sumy (inna konwencja niż dla iloczynów). Ostatecznie
F = (x + x )(x + x )(x + x )
1 1 2 2 3 3 1
15
Tablice Karnaugha i diagramy Veitcha znajdujÄ… zastosowanie nie tylko do
minimalizacji.
Przykład:
Funkcję f zapisaną za pomocą formuły F = x x + x x + x należy przedstawić w
1 2 2 3 3
kanonicznej postaci sumy, stosujÄ…c diagram Veitcha. Jest to zagadnienie
odwrotne do minimalizacji.
x
3
0 1 1 0
0 1 3 2
0 1 1 1
x
1
4 5 7 6
x
2
Otrzymujemy F = P + P + P + P + P
1 3 5 6 7
Przykład
Funkcję f zapisaną za pomocą formuły F = (x + x )(x + x ) należy
1 2 2 3
przedstawić w kanonicznej postaci iloczynu, stosując diagram Veitcha.
x
3
0 0 1 1
0 1 3 2
0 1 1 1
x
1
4 5 7 6
x
2
Otrzymujemy F = S S S
0 1 4
Przedstawione metody minimalizacji wyrażeń logicznych nadają się dla
niezbyt dużej liczby zmiennych  w przypadku tablic Karnaugha praktycznie
do 6. Metoda Quine a-McCluskeya daje tu nieco większe możliwości, ale
staje się mało efektywna w przypadku tzw. funkcji słabookreślnych, dla
których zbiór Dm jest małą częścią zbioru {0, 1}m. Znane są metody [20], [3],
umożliwiające wyznaczenie wyrażeń minimalnych i zminimalizowanych (tj.
16
nieoptymalnych) także dla funkcji słabookreślnych. Istnieją też metody
umożliwiające minimalizację zespołów wyrażeń logicznych.
17


Wyszukiwarka