1

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

1

=

x

1

x

2

x

3

x

+

x

1

x

2

x

3

x

4

+

x

1

x

2

x

3

x

4

+

x

1

x

2

x

3

x

4

+ x

1

x

2

x

3

x

4

+ x

1

x

2

x

3

x

4

+ x

1

x

2

x

3

x

4

+

+

x

1

x

2

x

3

x

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

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.

3

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

1

x

2

x

3

+ x

1

x

2

x

3

= x

1

x

2

.

Formułę G

1

nazywamy prostym implikantem formuły F, gdy G

1

jest

implikantem formuły F oraz gdy nie istnieje formuła G

2

taka, że

(G

1

→ G

2

) = 1 oraz (G

2

→ 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

1

x

2

x

3

+ x

1

x

2

x

3

+

+

x

1

x

2

x

3

wszystkie trzy iloczyny pełne są implikantami, a iloczyny x

1

x

2,

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 g

1

. G jest wtedy implikantem F, jeżeli g

1

⊆

f

1

, czyli

zbiór jedynek G zawiera się w zbiorze jedynek F.
Poszukiwana

formuła minimalna F

2

równoważna formule początkowej F

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

1

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

1

x

3

= G

1

(2,3,6,7);

x

2

x

3

= G

2

(6,7,14,15);

4

x

1

x

2

= G

3

(12,13,14,15)

Oznacza to, że np. implikant x

1,

x

3

powstał w wyniku połączenia pełnych

iloczynów o indeksach 2, 3, 6, 7. Selekcję wykonujemy, korzystając z tablicy
implikantów prostych.

x

1

x

3

2, 3, 6, 7

x

2

x

3

6, 7, 14, 15

x

1

x

2

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 F

2

=

x

1

x

3

+ x

1

x

2

. Współczynnik skomplikowania dla F

1

i F

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

1

= x

1

x

2

x

3

+ x

1

x

2

x

3

+

x

1

x

2

x

3

z dodatkowymi warunkami

x

1

x

2

x

3

= x

1

x

2

x

3

= 0

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

φφ

5

0

6

7

x

2

x

3

0,4

x

1

4, 5, 6, 7

Otrzymujemy F

2

= x

1

+

x

2

x

3

. Formule F

1

bez warunków dodatkowych

odpowiada formuła F

3

= x

1

x

2

+

x

1

x

2

x

3

Współczynniki skomplikowania dla F

1

,

F

2

, F

3

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 2

m

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

3

x

4

00 01 11 10 x

3

x

4

00 0

0

1

1

0

3

0

2

00

0

0

1

1

⎯

3

0

2

01 0

4

0

5

1

7

0

6

01

⎯

4

⎯

5

1

7

0

6

11 0

12

1

13

1

15

1

14

11

⎯

12

1

13

1

15

1

14

10 0 0 1 0

10

⎯

0

⎯

0

6

8 9 11 10

8

9

11 10

x

1

x

2

x

1

x

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

i

w kanonicznej postaci sumy dla danej

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

j

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 S

j

.

Dla przykładu iloczynowi x

1

x

2

x

3

= P

6

dla trzech zmiennych odpowiada

kratka stanowiąca wspólną część „połowy x

1

”, „połowy x

2

” i „połowy nie

x

3

”; ta sama kratka odpowiada pełnej sumie

x

1

+

x

2

+

x

3

= S

6

(oczywiście

S

6

=

P

6

). Inaczej - sumie

x

1

+

x

2

+

x

3

odpowiada kratka stanowiąca

wspólną część „połowy x

1

”, „połowy x

2

” i „połowy nie x

3

”; 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

0 0 1

0 1

1 2 3

x

1

2 3

7

x

1

- trzech zmiennych

Tablice

Karnaugha Diagramy

Veitcha

x

2

00 01 11 10

x

2

x

3

0

0 1 3 2

0 1 3 2

1

4 5 7 6

x

1

4 5 7 6

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

1

x

2

- czterech zmiennych

x

3

00 01 11 10 x

2

x

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

x

1

x

2

x

4

8

Inny wariant

000 001 011 010 110 111 101 100 x

2

x

3

x

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

1

x

2

x

3

- pięciu zmiennych

000 001 011 010 110 111 101 100

x

3

x

4

x

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

10

16 17 19 18 22 23 21 20

x

1

x

2

9

Inny wariant

00 01 11 10 x

4

x

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

1

x

2

x

3

- sześciu zmiennych

000 001 011 010 110 111 101 100 x

4

x

5

x

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

100 32 33 35 34 38 39 37 36

10

x

1

x

2

x

3

x

4

x

6

x

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

1

x

3

40 41 43 42 46 47 45 44

32 33 35 34 38 39 37 36

x

5

x

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:

1) Przedstawienie formuły za pomocą diagramu Veitcha (jeżeli jest to

potrzebne).

11

2) Wyznaczenie prostych implikantów przez sklejenie możliwie jak

największych grup (par, czwórek, ósemek, ...) kratek zawierających
jedynki bądź 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

1

i f

2

podanych w

tablicach

00 01 11 10 x

3

x

4

00 01 11 10 x

3

x

4

00 0

0

1

1

0

3

0

2

00

0

0

1

1

⎯

3

0

2

01 0

4

0

5

1

7

0

6

01

⎯

4

⎯

5

1

7

0

6

11 0

12

1

13

1

15

1

14

11

⎯

12

1

13

1

15

1

14

10 0

8

0

9

1

11

0

10

10

⎯

8

0

9

⎯

11

0

10

x

1

x

2

x

1

x

2

12

Otrzymujemy:

00 01 11 10 x

3

x

4

00 01 11 10 x

3

x

4

00 0

0

1

1

0

3

0

2

00

0

0

1

1

⎯

3

0

2

01 0

4

0

5

1

7

0

6

01

⎯

4

⎯

5

1

7

0

6

11 0

12

1

13

1

15

1

14

11

⎯

12

1

13

1

15

1

14

10 0

8

0

9

1

11

0

10

10

⎯

8

0

9

⎯

11

0

10

x

1

x

2

x

1

x

2

Wyrażenie minimalne dla funkcji f

1

ma postać

F

1min

= x

1

x

2

x

3

+ x

1

x

2

x

4

+ x

1

x

3

x

4

+ x

2

x

3

x

4

+

x

1

x

2

x

3

x

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

2min

= x

1

x

2

+

x

1

x

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.

F

1

2

= {1, 3, 5, 7, 12, 13, 14, 15}

F

0
2

= {0, 2, 4, 6, 8, 9, 10, 11}

Natomiast dla funkcji niezupełnej mamy

F

1

2

= {1, 7, 13, 14, 15}

F

0
2

= {0, 2, 6, 9, 10}

Oczywiście

F

1

2

⊆

F

/

1

2

oraz

F

0
2

⊆

F

/

0
2

Natomiast wyrażenie F

2min

odpowiada funkcji f

2

w zbiorze jej określoności, tj.

dla

F

1

2

∪

F

0
2

W wyrażeniach logicznych minimalnych lub częściowo zminimalizowanych
występują także iloczyny niepełne, tj. nie zawierające wszystkich zmiennych.

13

Takie iloczyny mogą być jednoznacznie powiązane z odpowiednimi wektorami.
Trzeba przyjąć

WL(e

1

) =

x

e1

1

...

x

ej

j

...

x

em

m

przy czym

x

j

dla e

j

= 0

x

ej

j

= x

j

dla e

j

= 1

1 dla e

j

= *

Funkcja f może być wtedy zapisana jako

f :

D

m*

→ {0,1}

przy czym

D

m*

⊆

{0, 1, *}

m

Przykład:
Korzystając z wprowadzonego aparatu formalnego możemy napisać dla f

1

i f

2

e

1

e

2

e

3

e

4

1 1 1 x

1 1 x 1

f

1

= WL

-1

(F

1min

1 x 1 1

x 1 1 1

0 0 0 1

e

1

e

2

e

3

e

4

1 1 x x

f

2

= WL

-1

(F

2min

)

0 x x 1

Funkcje f

1

i f

2

przyporządkowują podanym wyżej wektorom wartość 1.

Przykład:
Funkcja zupełna f (x

1

, x

2

, x

3

, x

4

, x

5

, x

6

) jest dana w postaci F

1

= {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.

14

000 001 011 010 110 111 101 100 x

4

x

5

x

6

000

0

0

0

1

0

3

1

2

1

6

1

7

1

5

0

4

001

0

8

1

9

1

11

1

10

1

14

1

15

1

13

0

12

011

1

24

1

25

1

27

1

26

1

30

0

31

0

29

1

28

010

1

16

0

17

0

19

1

18

1

22

0

23

0

21

1

20

110

1

48

0

49

0

51

0

50

1

54

1

55

0

53

1

52

111

1

56

1

57

1

59

0

58

0

62

0

63

0

61

1

60

101

0

40

1

41

1

43

0

42

0

46

0

47

0

45

0

44

100

0

32

0

33

0

35

0

34

0

38

0

39

0

37

0

36

x

1

x

2

x

3

Wyrażenie minimalne z tablicy Karnaugha ma postać

F

min

(x

1

, x

2

, x

3

, x

4

, x

5

, x

6

) =

x

1

x

5

x

6

+ x

2

x

5

x

6

+ x

3

x

4

x

6

+

x

1

x

2

x

4

x

6

+

+ x

1

x

2

x

3

x

4

x

5

Przykład
Należy zminimalizować funkcję f

1

przedstawioną w tabeli, podając minimalną

sumę iloczynów i minimalny iloczyn sum. Zastosować tablice Karnaugha.
Funkcja f

1

i x

1

x

2

x

3

f

1

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

15

Po sklejeniu jedynek otrzymujemy

00 01 11 10 x

2

x

3

0

0

0

0

1

1

3

0

2

1

0

4

1

5

1

7

1

6

x

1

Otrzymujemy: F

1

= x

1

x

2

+ x

2

x

3

+ x

3

x

1

6-7 3-7 5-7

Natomiast sklejenie zer

00 01 11 10 x

2

x

3

0 0

0

0

1

1

3

0

2

1

0

4

1

5

1

7

1

6

x

1

prowadzi do par kratek 0-1, 0-2, 0-4, co odpowiada operacjom na wektorach

〈

000

〉

*

〈

001

〉

=

〈

00x

〉 →

x

1

+ x

2

〈

000

〉

*

〈

010

〉

=

〈

0x0

〉 →

x

1

+ x

3

〈

000

〉

*

〈

100

〉

=

〈

x00

〉 →

x

2

+ x

3

Otrzymujemy w wyniku sklejenia podane wyżej wektory i odpowiadające im
sumy (inna konwencja niż dla iloczynów). Ostatecznie

F

1

= (x

1

+ x

2

)(x

2

+ x

3

)(x

3

+ x

1

)

Tablice Karnaugha i diagramy Veitcha znajdują zastosowanie nie tylko do
minimalizacji.
Przykład:
Funkcję f zapisaną za pomocą formuły F = x

1

x

2

+ x

2

x

3

+ x

3

należy przedstawić w

kanonicznej postaci sumy, stosując diagram Veitcha. Jest to zagadnienie
odwrotne do minimalizacji.

16

x

3

0

0

1

1

1

3

0

2

x

1

0

4

1

5

1

7

1

6

x

2

Otrzymujemy F = P

1

+ P

3

+ P

5

+ P

6

+ P

7

Przykład
Funkcję f zapisaną za pomocą formuły F = (x

1

+ x

2

)(x

2

+ x

3

) należy

przedstawić w kanonicznej postaci iloczynu, stosując diagram Veitcha.

x

3

0

0

0

1

1

3

1

2

x

1

0

4

1

5

1

7

1

6

x

2

Otrzymujemy F = S

0

S

1

S

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 D

m

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