Podręcznik

Zadaniem procedury COMPLEMENT (uzupełnienie) jest obliczenie zbioru D, tj. zbioru wszystkich nieokreśloności funkcji opisanej zbiorami F i R. Zbiór ten jest wykorzystywany między innymi w procedurze pokrycia, a jego zwarta specyfikacja jest bardzo istotna z punktu widzenia złożoności obliczeń. Potrzebę obliczania D wyjaśnia dobrze przykład funkcji boolowskiej o 30 argumentach, opisanej tablicą prawdy o 200 wierszach (wektorach). Otóż zbiór wszystkich nieokreśloności takiej funkcji ma liczność 2³⁰ – 200, a więc bezpośrednia specyfikacja odpowiedniego D staje się niemal nierealna.

Procedura uzupełniania polega na iteracyjnym rozkładzie zbioru kostek reprezentującego funkcję f na kofaktory. Kofaktory te są obliczane tak długo, aż odpowiada­jące im zbiory kostek staną się „łatwe” do obliczenia ich uzupełnienia. Proces kończy „scalanie” wyników cząstkowych. Podstawą takiego postępowania jest spostrzeżenie, że uzupełnienie funkcji reprezentowanej rozkładem Shannona:

$f=x_jf_{x_j}+{\bar{x}}_jf_{{\bar{x}}_j}$

można wyznaczyć obliczając najpierw ko faktory $f_{x_j}$ oraz $f_{{\bar{x}}_j}$, a następnie ich uzupełnienie, czyli [1]:

$\bar{f}=x_j{\bar{f}}_{x_j}+{\bar{x}}_j{\bar{f}}_{{\bar{x}}_j}$          (2-4)

Zatem $\bar{f}$ powstaje w wyniku „scalenia” wyników cząstkowych, tj. ${\bar{f}}_{x_j}$ oraz ${\bar{f}}_{{\bar{x}}_j}$.

W przypadku, gdy wynikiem rozkładu Shannona jest jednorodny zbiór kostek, obliczenia przejmuje procedura UNATE_COMPLEMENT, spełniająca rolę procedury wyznaczającej uzupełnienie funkcji jednorodnej. Wynika to z faktu, że dla funkcji monotonicznych, a w szczególności dla:

            a) monotonicznie rosnącej w punkcie x_j,

            b) monotonicznie malejącej w punkcie x_j,

uzupełnienie (2-4) upraszcza się do następujących wzorów [1]:

            $\bar{F}={{\bar{x}}_j{\bar{F}}_{{\bar{x}}_j}+}_\ {\bar{F}}_{x_j}$                                                                                             (2-5a)

            $\bar{F}={x_j{\bar{F}}_{x_j}+}_\ {\bar{F}}_{{\bar{x}}_j}$                                                                                             (2-5b)

Łatwo to wykazać, gdyż na przykład dla (5-6a) mamy, że $F_{x_j}F_{\bar{x}_j}$ a więc, korzystając z implikacji $\boldsymbol{A} \supseteq \boldsymbol{B} \Rightarrow \boldsymbol{A} \cap \boldsymbol{B} =\boldsymbol{B}$, uzyskujemy:

            $F=x_jF_{x_j}+{\bar{x}}_jF_{{\bar{x}}_j}=x_jF_{x_j}+F_{{\bar{x}}_j}=F_{x_j}\left(x_j+F_{{\bar{x}}_j}\right)$

czyli:

            $\bar{F}={\bar{x}}_j{\bar{F}}_{{\bar{x}}_j}+{\bar{F}}_{x_j}$

            Obliczenie uzupełnienia funkcji jednorodnej rozpoczynamy od wyznaczania zero-jedyn­kowej macierzy M funkcji jednorodnej danej macierzy F.

            Przeliczenie macierzy F na macierz M przeprowadzamy według następujacego schematu:

            M[i, j] = 0, jeżeli F[i, j] = *,

            M[i, j] = 1, jeżeli F[i, j] = 1    lub  F[i, j] = 0.

            Transformacja taka jest jednoznaczna, gdyż macierz F z założenia jest jednorodna (w żadnej z jej kolumn nie występują jednocześnie zera i jedynki). Następnie wyliczany jest wektor V, w którym „zapamiętuje się” polaryzacje zmiennych występujące w każdej kolumnie. Na przykład, zakładając macierz F o postaci:

            $\boldsymbol{F} =\left[\begin{matrix} 0\\ \ast \\ 0 \end{matrix}\begin{matrix} 1\\ \ast \\ \ast \end{matrix}\begin{matrix} \ast \\ 1\\ 1 \end{matrix}\begin{matrix} 0\\ \ast \\ \ast \end{matrix}\right]$

otrzymamy macierz:

            $\boldsymbol{M} =\left[\begin{matrix} 1\\ 0\\ 1 \end{matrix}\begin{matrix} 1\\ 0\\ 0 \end{matrix}\begin{matrix} 0\\ 1\\ 1 \end{matrix}\begin{matrix} 0\\ 0\\ 0 \end{matrix}\right]$

oraz wektor $V=\left[0110\right]$

Otrzymaną macierz M będziemy rozkładać rekursywnie (stosując rozkład Shannona), aż do wystąpienia szczególnych postaci uzyskanych kofaktorów.

Obliczenie kofaktorów otrzymanej macierzy M rozpoczynamy od wyboru zmiennej do rozkładu. Odpowiedni wybór zmiennej ma istotne znaczenie dla redukcji obliczeń. Wybór zmiennej przeprowadzamy według następującego algorytmu:

1) wybieramy kostkę (wiersz macierzy M) z największą liczbą zer,

2) w wybranej kostce wybieramy zmienne, które mają jedynkę w tej kostce,

3) spośród wybranych w punkcie 2) zmiennych wybieramy tę, która ma najwięcej jedynek w swojej kolumnie.

Postępowanie to uzasadniamy następująco. Otóż obliczenie kofaktora powoduje ustawienie na zero kolumny odpowiadającej wybranej zmiennej. Zatem wybranie zmiennej według powyższego algorytmu i obliczenie kofaktora ustawi na zero kolumny, które mają największą liczbę jedynek (p. 3). Ułatwi to uzyskanie sytuacji, w której w kofaktorze będzie wiersz samych zer (p. 1), odpowiadający tautologii.

Kofaktory macierzy M obliczamy według następującego schematu.

            Kofaktor jedynkowy macierzy M względem zmiennej x_j  otrzymujemy przez ustawienie wszystkich pozycji j-tej kolumny macierzy M na zera. Inaczej mówiąc, kofaktor jedynkowy jest przepisaniem macierzy M z „ustawieniem j-tej kolumny na zero”.

            Kofaktor zerowy macierzy M względem zmiennej x_j otrzymujemy przez wypisanie z M tych kostek (wierszy), w których zmienna x_j  przyjmuje wartość zero.

            Powyższy sposób obliczania kofaktorów jest bezpośrednią konsekwencją definicji kofaktora [2.8].

            Na przykład dla macierzy M:

            $\boldsymbol{M} =\left[\begin{matrix} 1\\ 0\\ 1 \end{matrix}\begin{matrix} 1\\ 0\\ 0 \end{matrix}\begin{matrix} 0\\ 1\\ 1 \end{matrix}\begin{matrix} 0\\ 0\\ 0 \end{matrix}\right]$

wybór zmiennej x₃ prowadzi do kofaktorów:

$\boldsymbol{M} =\left[\begin{matrix} 1\\ 0\\ 1 \end{matrix}\begin{matrix} 1\\ 0\\ 0 \end{matrix}\begin{matrix} 0\\ 0\\ 0 \end{matrix}\begin{matrix} 1\\ 0\\ 0 \end{matrix}\right] \ dla\ x_{3} =1$

oraz wektor $\left[1101\right]$ dla x₃ = 0

            Następnym etapem obliczeń jest próba uzupełnienia otrzymanych kofaktorów. W szczególności, jeżeli którykolwiek z kofaktorów zawiera wiersz samych zer, to należy go usunąć, gdyż uzupełnienie takiego kofaktora jest zbiorem pustym.

            Proces rozkładu na kofaktory prowadzimy rekursywnie, tzn. otrzymane kofaktory rozkładamy według tej samej zasady, aż do uzyskania kofaktorów, które zawierają tylko jedną kostkę (wiersz). Warto dodać, że jeżeli na którymś z poziomów rekursji w kolumnie odpowiadającej wybranej zmiennej są tylko jedynki, to kofaktor zerowy takiej macierzy jest pusty.

Rys. 2.13. Rozkład funkcji F z przykładu 2.16

Po obliczeniu uzupełnień na poszczególnych „piętrach” rozkładu możemy przystąpić do scalania poszczególnych wyników. Scalanie przeprowa­dzamy zgodnie z przetrans­formowanym do notacji M wzorem (2-5):

            F = x_j × F₀ + F₁.

Znaczy to, że jeżeli otrzymany kofaktor był zerowy (ozn. F₀), to mnożymy go przez odpowiednie x_j i dodajemy, a jeżeli był jedynkowy (ozn. F₁), to tylko dodajemy. Czyli (dla ${\bar{x}}_4$):

$\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix} =\begin{bmatrix} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1 \end{bmatrix}$

oraz dla $x_4{\bar{x}}_3{\bar{x}}_1$;  kolejne obliczenia są następujące:

            [ 1 0 0 0 ] + f

            [ 1 0 0 0 ] · [ 0 0 1 0 ] = 1 0 1 0.

Ostatni wynik należy dodać do wyniku uzyskanego dla ${\bar{x}}_4$):, czyli:

$\begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{bmatrix} +\begin{bmatrix} 1 & 0 & 1 & 0 \end{bmatrix}$

Łącząc wreszcie wyniki cząstkowe, uzyskujemy $\bar{\boldsymbol{M}}$, która po transformacji według wektora v prowadzi do $\bar{\boldsymbol{F}}$:

$\overline{\boldsymbol{M}} =\begin{bmatrix} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 \end{bmatrix}\xrightarrow{V}\overline{\boldsymbol{F}} =\begin{bmatrix} 1 & * & * & 1\\ * & 0 & * & 1\\ 1 & * & 0 & * \end{bmatrix}$

Otrzymana macierz $\bar{\boldsymbol{F}}$ jest uzupełnieniem jednorodnej funkcji F. W ten sposób, mając funkcję rozłożoną na funkcje jednorodne, łatwo można obliczyć uzupełnienie każdej z nich.