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:
F1 = x x x3 x + x x x3 x4 + x x2 x3 x + x x2 x3 x4 + x1 x2 x x + x1 x2 x x4 + x1 x2 x3 x +
1 2 1 2 1 4 1 3 4 3 4
+ x1 x2 x3 x4
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
1
2. Szeregujemy te kombinacje według liczby jedynek. Otrzymujemy w ten
sposób grupy n = 0, 1, 2 ... jedynek
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
różniące się symbolem Ć. Wykorzystujemy tu związek xy +x y =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 x1x2 x + x1x2x3 = x1x2 .
3
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 x1x2 x + x1x2x3 +
3
+ x x x
x x x
wszystkie trzy iloczyny pełne są implikantami, a iloczyny x1x2, 1 2 3
1 2 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 F2 równoważna formule początkowej F1
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 F1 były reprezentowane w wybranych implikantach
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 x3 = G1(2,3,6,7); x2x3 = G2(6,7,14,15);
1
3
x1x2 = G3(12,13,14,15)
Oznacza to, że np. implikant x1,x3 powstał w wyniku połączenia pełnych
iloczynów o indeksach 2, 3, 6, 7. Selekcję wykonujemy, korzystając z tablicy
implikantów prostych.
2, 3, 6, 7
x x3
1
x2x3 6, 7, 14, 15
x1x2 12, 13, 14, 15
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 F2 = x x3 + x1x2 . Współczynnik skomplikowania dla F1 i F2
1
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: F1 = x1x2x3 + x1x2 x + x x x z dodatkowymi warunkami
3 1 2 3
x1 x x3 = x1 x x = 0
2 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, 5, 6, 7, 1ĆĆ
4
0 6 7
0,4
x 2 x 3
x1 4, 5, 6, 7
Otrzymujemy F2 = x1 + x x . Formule F1 bez warunków dodatkowych
2 3
odpowiada formuła F3 = x1x2 + x x x Współczynniki skomplikowania dla F1,
1 2 3
F2, F3 wynoszą odpowiednio 12, 5, 7.
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 x3x4 00 01 11 10 x3x4
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
Ż# Ż#
5
8 9 11 10 8 9 11 10
x1x2 x1x2
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 Pi w kanonicznej postaci sumy dla danej
funkcji. Natomiast kratka o numerze i zawierająca 0 odpowiada sumie pełnej Si
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 Pj odpowiada kratka (mały kwadrat) stanowiący
wspólną powierzchnię powierzchni odpowiadających zmiennym (prostym
lub zanegowanym), które występują w tym iloczynie; ta sama kratka
odpowiada sumie Sj.
Dla przykładu iloczynowi x1x2 x
= P6 dla trzech zmiennych odpowiada
3
kratka stanowiąca wspólną część  połowy x1 ,  połowy x2 i  połowy nie
x x x
x3 ; ta sama kratka odpowiada pełnej sumie + + = S6 (oczywiście
1 2 3
P x x x
S6 = ). Inaczej - sumie + + odpowiada kratka stanowiąca
6 1 2 3
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
x2
0 1 x2
0 0 1 0 1
1 2 3 x1 2 3
6
x1
- trzech zmiennych
Tablice Karnaugha Diagramy Veitcha
x2
00 01 11 10 x2x3
0 0 1 3 2 0 1 3 2
1 4 5 7 6 x1 4 5 7 6
x1
x3
Inny wariant
x3
0 1 x3
00 0 1 0 1
01 2 3 2 3
x2
11 6 7 6 7
x1
10 4 5 4 5
x1 x2
- czterech zmiennych
x3
00 01 11 10 x2x3
00 0 1 3 2 0 1 3 2
01 4 5 7 6 4 5 7 6
x2
11 12 13 15 14 12 13 15 14
x1
10 8 9 11 10 8 9 11 10
x1 x2
x4
7
Inny wariant
000 001 011 010 110 111 101 100 x2x3 x4
0 0 1 3 2 6 7 5 4
1 8 9 11 10 14 15 13 12
x1
0 1 x4
000 0 1
001 2 3
011 6 7
010 4 5
110 12 13
111 14 15
101 10 11
100 8 9
x1 x2x3
- pięciu zmiennych
000 001 011 010 110 111 101 100 x3x4x5
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
x1 x2
8
Inny wariant
00 01 11 10 x4x5
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
x1 x2x3
- sześciu zmiennych
000 001 011 010 110 111 101 100 x4x5 x6
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
100 32 33 35 34 38 39 37 36
9
x1 x2x3
x4
x6 x6
0 1 3 2 6 7 5 4
8 9 11 10 14 15 13 12
x3
24 25 27 26 30 31 29 28
x2
16 17 19 18 22 23 21 20
48 49 51 50 54 55 53 52
x2
56 57 59 58 62 63 61 60
x1 x3
40 41 43 42 46 47 45 44
32 33 35 34 38 39 37 36
x5 x5
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ą
1 0
prawdy lub tablicą Karnaugha, lub w postaci zbiorów f i f . 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:
1) Przedstawienie formuły za pomocą diagramu Veitcha (jeżeli jest to
potrzebne).
10
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 f1 i f2 podanych w
tablicach
00 01 11 10 x3x4 00 01 11 10 x3x4
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
x1x2 x1x2
11
Otrzymujemy:
00 01 11 10 x3x4 00 01 11 10 x3x4
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
x1x2 x1x2
Wyrażenie minimalne dla funkcji f1 ma postać
F1min = x1x2x3 + x1x2x4 + x1x3x4 + x2x3x4 + x x x x4
1 2 3
14-15 13-15 11-15 7-15 1
Liczby pod wyrażeniami oznaczają numery sklejonych kratek. Dla funkcji f2
będzie to:
F2min = x1x2 + x x4
1
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
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.
12
Takie iloczyny mogą być jednoznacznie powiązane z odpowiednimi wektorami.
Trzeba przyjąć
e1 ej em
x x x
1 j m
WL(e1) = ... ...
przy czym
x dla ej = 0
j
ej
x
j
xj dla ej = 1
=
1 dla ej = *
Funkcja f może być wtedy zapisana jako
m*
f : {0,1}
D
m*
ą" {0, 1, *}m
D
przy czym
Przykład:
Korzystając z wprowadzonego aparatu formalnego możemy napisać dla f1 i f2
e1 e2 e3 e4
1 1 1 x
1 1 x 1
f1 = WL-1(F1min 1 x 1 1
x 1 1 1
0 0 0 1
e1 e2 e3 e4
1 1 x x
f2 = WL-1(F2min)
0 x x 1
Funkcje f1 i f2 przyporządkowują podanym wyżej wektorom wartość 1.
Przykład:
Funkcja zupełna f (x1, x2, x3, x4, x5, x6) jest dana w postaci F1 = {2, 5, 6, 7, 9, 10,
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 x4x5 x6
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
x1 x2x3
Wyrażenie minimalne z tablicy Karnaugha ma postać
Fmin (x1, x2, x3, x4, x5, x6) = x x5 x + x2 x x + x3 x x6 + x x x4x6 +
1 6 5 6 4 1 2
+ x1x2 x x4x5
3
Przykład
Należy zminimalizować funkcję f1 przedstawioną w tabeli, podając minimalną
sumę iloczynów i minimalny iloczyn sum. Zastosować tablice Karnaugha.
Funkcja f1
i x1 x2 x3 f1
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
14
Po sklejeniu jedynek otrzymujemy
00 01 11 10 x2x3
0 0 1 0
0
0 1 3 2
0 1 1 1
1
4 5 7 6
x1
Otrzymujemy: F1 = x1x2 + x2x3 + x3x1
6-7 3-7 5-7
Natomiast sklejenie zer
00 01 11 10 x2x3
0 0 0 1 0
0 1 3 2
0 1 1 1
1
4 5 7 6
x1
prowadzi do par kratek 0-1, 0-2, 0-4, co odpowiada operacjom na wektorach
)# 000*# *)# 001*# = )# 00x*# x1 + x2
)# 000*# )# 010*# = )# 0x0*# x1 + x3
*
)# 000*# 100*# = )# x00*# x2 + x3
*)#
Otrzymujemy w wyniku sklejenia podane wyżej wektory i odpowiadające im
sumy (inna konwencja niż dla iloczynów). Ostatecznie
F1 = (x1 + x2)(x2 + x3)(x3 + x1)
Tablice Karnaugha i diagramy Veitcha znajdują zastosowanie nie tylko do
minimalizacji.
Przykład:
Funkcję f zapisaną za pomocą formuły F = x1x2 + x2x3 + x3 należy przedstawić w
kanonicznej postaci sumy, stosując diagram Veitcha. Jest to zagadnienie
odwrotne do minimalizacji.
15
x3
0 1 1 0
0 1 3 2
0 1 1 1
x1
4 5 7 6
x2
Otrzymujemy F = P1 + P3 + P5 + P6 + P7
Przykład
Funkcję f zapisaną za pomocą formuły F = (x1 + x2)(x2 + x3) należy
przedstawić w kanonicznej postaci iloczynu, stosując diagram Veitcha.
x3
0 0 1 1
0 1 3 2
0 1 1 1
x1
4 5 7 6
x2
Otrzymujemy F = S0S1S4
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.
nieoptymalnych) także dla funkcji słabookreślnych. Istnieją też metody
umożliwiające minimalizację zespołów wyrażeń logicznych.
www.lmsite.prv.pl
16