Podręcznik: Metoda systematyczna

4. Metody minimalizacji funkcji boolowskich

4.2. Metoda systematyczna

W metodzie systematycznej zbiór wektorów (w ogólności kostek), dla których funkcja f = 1 oznacza się F. Natomiast zbiór tych wektorów (kostek), dla których funkcja f = 0 oznacza się R.

W tabl. 2.21 przedstawiono tablicę prawdy funkcji boolowskiej 7-argumentowej. Funkcję tę w dalszej części wykładu oznaczać będziemy EXTL. Wektory zbioru F oznaczono symbolami k₁, …, k₅.

Tablica 2.21

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	f
	1	0	0	0	1	0	1	0
	1	0	1	1	1	1	0	0
	1	1	0	1	1	1	0	0
	1	1	1	0	1	1	1	0
k₁	0	1	0	0	1	0	1	1
k₂	1	0	0	0	1	1	0	1
k₃	1	0	1	0	0	0	0	1
k₄	1	0	1	0	1	1	0	1
k₅	1	1	1	0	1	0	1	1

Metoda systematyczna jest procesem działającym na kostkach zbiorów F i R, a jej celem jest uzyskanie dla danej k Î F kostki k' tak dużej, jak to tylko możliwe (tzn. z możliwie dużą liczbą pozycji o wartości *) i nie pokrywającej żadnego wektora zbioru R. W swoich obliczeniach metoda ta wykorzystuje tzw. macierz blokującą B.

Macierzą blokującą (kostkę k) nazywać będziemy macierz:

B(k,R) = [b_ij], 1 £ i £ ÷R÷, 1 £ j £ n,

w której każdy element b_ij Î {0,1} jest definiowany następująco:

b_ij = 1, jeśli k_j = 1 oraz r_ij = 0 lub k_j = 0 oraz r_ij = 1;

b_ij = 0, w pozostałych przypadkach.

W przypadku funkcji opisanej wektorami binarnymi macierz blokująca dla danej kostki k Î F powstaje z macierzy R przez zanegowanie tych kolumn R, których pozycje są wyznaczone przez pozycje jedynek w kostce k Î F.

Wyznaczymy macierz blokującą dla f = (F, R) zadanej w tablicy 2.21 i kostki k₂. Jak wynika z tej tablicy, zbiory F i R są opisane macierzami:

$\boldsymbol{F} =\begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}$

$\boldsymbol{R} =\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 0 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 0 & 1 & 1 & 1 \end{bmatrix}$

Skoro k₂ = (1000110), to dla uzyskania B wystarczy w macierzy R „zanegować” kolumny pierwszą, piątą i szóstą. Zatem B(k₂, R):

$\begin{matrix} & \begin{array}{ c c c c c c c } 1 & 2 & 3 & 4 & 5 & 6 & 7 \end{array}\\ \boldsymbol{B} = & \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{bmatrix} \end{matrix}$

Pokryciem kolumnowym macierzy B = [b_ij], i $\in$ {1, …, w}, j $\in$ {1, …, n} jest zbiór L $\subseteq$ {1, …, n} taki, że dla każdego i $\in$ {1, …, w} istnieje j $\in$ L, dla którego b_ij = 1.

Pokrycie kolumnowe jest pokryciem, w którym elementami pokrywanymi są wiersze B, a pokrywającymi – kolumny tej macierzy. Jednak brak formalnych elementów pokrywanych i pokrywających skłania do wprowadzenia nazwy „pokrycie kolumnowe”.

Obliczenia pokrycia kolumnowego omówimy na przykładzie macierzy blokującej wyznaczonej dla kostki k₂ funkcji z poprzedniego przykładu.

Oznaczając kolumny macierzy B kolejno L₁ do L₇ zapisujemy poszczególne wiersze tej macierzy oznaczeniami tych kolumn, które w danym wierszu mają „1”. Na przykład wiersz pierwszy zapiszemy L₆, L₇, drugi L₃, L₄, itd. Traktując kolumny L_i jako zmienne boolowskie tworzymy iloczyn sum kolumn poszczególnych wierszy:

(L₆ + L₇) (L₃ + L₄) (L₂ + L₄) (L₂ + L₃ + L₇)

Następnie iloczyn sum przekształcamy do wyrażenia boolowskiego typu suma iloczynów:

(L₄ + L₂)(L₄ + L₃)(L₇ + L₆)(L₇ + L₂ + L₃) = (L₄ + L₂L₃)(L₇ + L₆(L₂ + L₃)) = (L₄ + L₂L₃)(L₇ + L₂L₆ + L₃L₆) =

= L₄L₇ + L₂L₄L₆ + L₃L₄L₆ + L₂L₃L₇ + L₂L₃L₆

Składniki tego wyrażenia reprezentują zbiory minimalnego pokrycia kolumnowego:

{L4, L7}, {L2, L4, L6}, {L3, L4, L6}, {L2, L3, L7}, {L2, L3, L6}

Macierz blokująca B(k,R) pozwala wyznaczyć uogólnioną kostkę k oznaczaną k⁺(L, k) w sposób następujący:

$k^{+}( L,k) =\begin{cases} k_{j}\text{, gdy} \ j\in L\\ *\text{, w pozostałych przypadkach} \end{cases}$

Uogólnioną kostkę k⁺(L, k) nazywa się również ekspansją kostki k, co oznacza, że wszystkie składowe kostki k należące do L nie ulegają zmianie, natomiast składowe nie należące do L przyjmują wartość *.

Można wykazać, że k⁺(L, k) jest implikantem funkcji f = (F, R). W szczególności k⁺(L, k) jest implikantem prostym, gdy L jest minimalnym pokryciem kolumnowym macierzy B(k, R). Wykorzystując pojęcie macierzy blokującej można obliczyć implikanty proste dla poszczególnych kostek zbioru F.

Kontynuujemy obliczenia dla macierzy blokującej B = B(k₂, R) z przykładu 2.10.

Zbiór L = {4,7} jest pokryciem kolumnowym B, a więc $k^+\left(L,k\right)=\left(\ast\ast\ast0\ast\ast0\right)$ , czyli implikantem F jest ${\bar{x}}_4{\bar{x}}_7$ . Natomiast dla L = {2,4,6} (inne pokrycie kolumnowe) $k^+\left(L,k\right)=\left(\ast0\ast0\ast1\ast\right)={\bar{x}}_2{\bar{x}}_4x_6$ . Postępując podobnie dla pozostałych pokryć kolumnowych można uzyskać następujący zbiór implikantów prostych funkcji f generowanych przez kostkę k₂:

${\bar{x}}_4{\bar{x}}_7,{\bar{x}}_2{\bar{x}}_4x_6,.{\bar{x}}_3{\bar{x}}_4x_6,.\ {\bar{x}}_2{\bar{x}}_3{\bar{x}}_7,.\ {\bar{x}}_2{\bar{x}}_3x_6$

Każdy z obliczonych w ten sposób implikantów może zastąpić (często mówimy pokrywa) wiele innych kostek pierwotnych funkcji f, gdzie relację pokrycia definiujemy następująco:

K Í K’ (K’ pokrywa K) wtedy i tylko wtedy, gdy $k_i=k_i^\prime\ lub\ k_i=\ast\$ dla każdego i, 1 £ i £ n,

gdzie: K = (k₁, …, k_n) i $K^\prime=\left(k_1^\prime,\ldots,k_n^\prime\right),$

Na przykład obliczony wyżej implikant pokrywa kostki k₂, k₃, k_4,co zapisujemy formalnie:

$\ {\bar{x}}_4{\bar{x}}_7$ Ê k₂, k₃, k₄.

Relacja pokrycia dla kostek i sposób postępowania omówiony w przykładzie 2.12 nasuwa pomysł systematycznej metody obliczania minimalnych realizacji funkcji boolowskich.

Kolejne etapy takiej metody są następujące.

Dla każdej k_inależącej do zbioru F obliczyć macierz blokującą.
Wyznaczyć wszystkie minimalne pokrycia kolumnowe tej macierzy.
Wyznaczyć wszystkie implikanty proste.
Obliczyć sumę zbiorów implikantów prostych generowanych przez poszczególne kostki.
Z tak utworzonego zbioru wszystkich implikantów prostych usunąć implikanty powtarzające się.
Spośród obliczonych implikantów prostych wyselekcjonować minimalny podzbiór implikantów pokrywający wszystkie kostki zbioru F.

Niezależnie jednak od metody ograniczania liczności zbioru implikantów prostych proces ich selekcji wykonuje się za pośrednictwem tzw. tablicy implikantów prostych.

Tablica implikantów prostych jest to tablica elementów binarnych 0 lub 1, o liczbie wierszy równej liczbie kostek zbioru F oraz liczbie kolumn równej liczbie wyznaczonych implikantów prostych funkcji f.

Tablicę implikantów prostych konstruujemy w następujący sposób. Jeśli implikant I_j pokrywa kostkę k_i, to na przecięciu wiersza k_i z kolumną I_j piszemy 1, w przeciwnym przypadku piszemy 0.

Utworzymy tablicę implikantów prostych dla funkcji f podanej w tabl. 2.21. W tym celu obliczamy minimalne (i o najmniejszej liczności) pokrycia kolumnowe dla każdej kostki zbioru F tej funkcji. Oznaczając przez J_i implikanty generowane przez kostkę k_i uzyskujemy kolejno:

$J_1={\bar{x}}_1$ $J_3={\bar{x}}_5$ $J_5=x_2{\bar{x}}_6$ oraz $x_3{\bar{x}}_6$

${J_2=\bar{x}}_4{\bar{x}}_7$ ${J_4=\bar{x}}_4{\bar{x}}_7$

Usuwając implikanty powtarzające się ostateczną listę implikantów prostych zapisujemy jak następuje:

$I_1={\bar{x}}_1$ $I_3={\bar{x}}_5$ $I_5=x_3{\bar{x}}_6$

${I_2=\bar{x}}_4{\bar{x}}_7$ ${I_4=x}_2{\bar{x}}_6$

Na tej podstawie dla każdego obliczonego wyżej implikanta (ale interpretowanego jako kostka) wyznaczamy wszystkie kostki zbioru F pokrywane przez ten implikant. Przykładowo:

$I_1={\bar{x}}_1\supseteq\ k_1$

${I_2=\bar{x}}_4{\bar{x}}_7\supseteq\ k_2,k_3,k_4$

${I_4=x}_2{\bar{x}}_6\supseteq\ k_1,k_5$

Tablicę implikantów prostych dla funkcji f pokazano w tabl. 2.22.

Tablica 2.22

	I₁	I₂	I₃	I₄	I₅
k₁	1	0	0	1	0
k₂	0	1	0	0	0
k₃	0	1	1	0	1
k₄	0	1	0	0	0
k₅	0	0	0	1	1

Tablica implikantów prostych umożliwia wybór (selekcję) takiego minimalnego zbioru implikantów, który pokrywa wszystkie kostki funkcji pierwotnej.

Minimalny zbiór implikantów prostych reprezentujących funkcję f można wyznaczyć obliczając minimalne pokrycie kolumnowe tablicy implikantów prostych. W tym celu tworzymy wyrażenie CNF,

I₂ (I₁ + I₄) (I₂ + I₃ + I₅) (I₄ + I₅), które po oczywistych uproszczeniach zamieniamy na DNF: I₂I₄+ I₁I₂I₅

Zatem minimalne pokrycie tworzą implikanty I₂, I₄. Czyli,

$f={\bar{x}}_4{\bar{x}}_7+x_2{\bar{x}}_6$

Obliczeniem decydującym o eksplozji kombinatorycznej zadania minimalizacji funkcji boolowskiej jest obliczenie wszystkich pokryć kolumnowych tablicy implikantów prostych. O złożoności tego problemu decyduje szybko rosnąca (ze wzrostem liczby argumentów) liczność rodziny tych implikantów.

Otóż w przypadku funkcji z tablicy 2.21 liczba wszystkich implikantów jest 5: tym samym odpowiednia tablica implikantów (tabl. 2.22) ma 5 kolumn. W rezultacie obliczenie minimalnych pokryć kolumnowych tej tablicy można wykonać „ręcznie” – jest widoczne „gołym okiem”. Ale nie zawsze tak musi być. Zjawisko występującej w tym problemie złożoności obliczeniowej lepiej wyjaśni następny przykład, którego wyniki obliczono programem InstantRS.

Dla funkcji podanej w standardzie typu pla (tabl. 2.23) zbiór implikantów jest następujący:

I1 = !x6!x7

I2 = !x7x8

I3 = x2x3

I4 = x3x4

I5 = x3!x5

I6 = x3x6

I7 = x3!x7

I8 = x3!x8

I9 = x1x4

I10 = x2x4

I11 = x4!x5

I12 = x4x6

I13 = x4!x7

I14 = x4!x8

I15 = x2!x7

I16 = x6x8

I17 = !x1x2

I18 = x2x5

I19 = !x6!x8

Tablica 2.23

. type fr

.i 8

.o1

.p12

11000110 0

00000100 0

10101011 0

10000100 0

10001110 0

11000011 0

00011011 0

00000001 1

11110100 1

11010111 1

01001111 1

11000010 1

zatem do obliczenia wszystkich minimalnych pokryć kolumnowych (tabl. 2.24) trzeba formalnie obliczyć wyrażenie typu DNF dla następującego wyrażenia w postaci CNF:

I19(I1 + I2)(I3 + I4 +…..+ I15)(I9 + I10 + I11 + I12 + I16)(I16 + I17 + I18).

Tablica 2.24

#	I1	I2	I3	I4	I5	I6	I7	I8	I9	I10	I11	I12	I13	I14	I15	I16	I17	I18	I19
c1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
c2	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0	0	0	0
c3	0	0	0	0	0	0	0	0	1	1	1	1	0	0	0	1	0	0	0
c4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0
c5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

Nie jest to zadanie proste i zawiera minimalne pokrycia kolumnowe reprezentujące 42 rozwiązania, czyli 42 minimalne reprezentacje funkcji z Tabl. 2.23, przykładowo:

01] !x6!x7 + x2x3 + x6x8 + !x6!x8

02] !x6!x7 + x3x4 + x6x8 + !x6!x8

03] !x6!x7 + x3!x5 + x6x8 + !x6!x8

04] !x6!x7 + x3x6 + x6x8 + !x6!x8

05] !x6!x7 + x3!x7 + x6x8 + !x6!x8

06] !x6!x7 + x3!x8 + x6x8 + !x6!x8

………………………………………………….

41] !x7x8 + x4!x5 + x2x5 + !x6!x8

42] !x7x8 + x4x6 + x2x5 + !x6!x8

Można się zatem spodziewać eksplozji kombinatorycznej, której rezultat dla funkcji Kaz podanej w Tabl. 2.25 prowadzi do wniosku, że w tym przypadku liczba wszystkich minimalnych implikantów jest 416, co uniemożliwia systematyczne obliczenie minimalnych wyrażeń boolowskich tej funkcji.

Ograniczenia w stosowaniu systematycznego algorytmu obliczania pokrycia kolumnowego spowodowały potrzebę użycia szybkich, heurystycznych algorytmów redukcji tablic boolowskich. Opracowane zostały dwa algorytmy iteracyjne: MaxCol i MinRow.

Algorytm MaxCol wykorzystuje strategię, w której dla uzyskania minimalnego pokrycia kolumnowego najbardziej istotne są kolumny macierzy, które zawierają największą liczbę jedynek.

Postępowanie w algorytmie MaxCol

Policzenie wystąpień wartości 1 w każdej kolumnie
Zapisanie kolumny z największą liczbą 1 – jeżeli jest kilka kolumn o tej samej liczbie 1, arbitralnie wybrana zostaje ta z mniejszym indeksem
Usunięcie wszystkich wierszy, dla których w wybranej kolumnie znajduje się wartość 1
Jeżeli macierz nie jest pusta (zawiera elementy), następuje powrót do kroku 1.
Zwrot zapisanych kolumn

Algorytm MinRow opiera swoje iteracyjne działanie analizowaniu wierszy o najmniejszej ilości jedynek.

Tablica 2.25

.type fr

.i 21

.o 1

.p 31

100110010110011111101 1

111011111011110111100 1

001010101000111100000 1

001001101100110110001 1

100110010011011001101 1

100101100100110110011 1

001100100111010011011 1

001101100011011011001 1

110110010011001001101 1

100110110011010010011 1

110011011011010001100 1

010001010000001100111 0

100110101011111110100 0

111001111011110011000 0

101101011100010111100 0

110110000001010100000 0

110110110111100010111 0

110000100011110010001 0

001001000101111101101 0

100100011111100110110 0

100011000110011011110 0

110101000110101100001 0

110110001101101100111 0

010000111001000000001 0

001001100101111110000 0

100100111111001110010 0

000010001110001101101 0

101000010100001110000 0

101000110101010011111 0

Kroki algorytmu MinRow

Policzenie wystąpień wartości 1 w każdym wierszu
Wybranie wierszy z najmniejszą liczbą wystąpień 1
Policzenie wystąpień wartości 1 w kolumnach, dla których dowolny wybrany w kroku 2. wiersz ma wartość 1
Zapisanie kolumny z największą liczbą 1 wśród tych z kroku 3. – jeżeli jest kilka kolumn o tej samej liczbie 1, arbitralnie wybrana zostaje ta z mniejszym indeksem

Strategię MinRow do obliczania minimalnego zbioru implikantów zastosowano w programie Hummingbird. Skuteczność tej strategii potwierdza wynik minimalizacji funkcji Kaz (Tabl. 2.25):

F = x4!x13x21 + x7!x15x16 + !x4!x17!x21

Warto zauważyć, że minimalizacja tej funkcji programem Espresso wcale nie jest lepsza:

F = !x2x14!x19x21 + !x8!x11!x12 + x5x8!x20

#	I1	I2	I3	I4	I5	I6	I7	I8	I9	I10	I11	I12	I13	I14	I15	I16	I17	I18	I19
c1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
c2	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0	0	0	0
c3	0	0	0	0	0	0	0	0	1	1	1	1	0	0	0	1	0	0	0
c4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0
c5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

#	I1	I2	I3	I4	I5	I6	I7	I8	I9	I10	I11	I12	I13	I14	I15	I16	I17	I18	I19
c1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
c2	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0	0	0	0
c3	0	0	0	0	0	0	0	0	1	1	1	1	0	0	0	1	0	0	0
c4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0
c5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

#	I1	I2	I3	I4	I5	I6	I7	I8	I9	I10	I11	I12	I13	I14	I15	I16	I17	I18	I19
c1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
c2	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0	0	0	0
c3	0	0	0	0	0	0	0	0	1	1	1	1	0	0	0	1	0	0	0
c4	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0
c5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1