Algorytm ekspansji

Algorytm ekspansji – ważny element metody Espresso, która jest używana do minimalizacji funkcji boolowskich. Jednakże używany samodzielnie również prowadzi do znalezienia minimalnej realizacji zadanej funkcji boolowskiej.

Algorytm ekspansji działa na zbiorach F i R (patrz Zapis funkcji boolowskiej w artykule Funkcja boolowska). Jego idea polega na maksymalnym powiększeniu kostek zbioru F. Ograniczeniem są tu kostki ze zbioru R.

Algorytm

Działanie algorytmu przebiega następująco:

1. Wyznaczenie macierzy blokujących B(k_i, R) dla k_i∈F.
2. Wyznaczenie implikantów prostych funkcji f=(F, R).
3. Wyznaczenie zbioru implikantów prostych pokrywających wszystkie kostki k_i.

Macierze blokujące

Macierz blokującą B(k_i, R) tworzy się negując $j$-te kolumny macierzy R przy czym $j$-te elementy kostki k_i są jedynkami. Przykładowo:

${\begin{matrix}k_{1}={\begin{Bmatrix}0&0&0&1&0\end{Bmatrix}}\\[1ex]R={\begin{Bmatrix}1&0&0&0&1\\1&0&1&0&1\\0&1&0&0&1\end{Bmatrix}}\quad B_{1}={\begin{Bmatrix}1&0&0&1&1\\1&0&1&1&1\\0&1&0&1&1\end{Bmatrix}}\\[1ex]{\text{zanegowana kolumna}}-4\end{matrix}}$

Należy wyznaczyć macierz blokującą dla każdej kostki ze zbioru F.

Wyznaczenie implikantów prostych

Dla danej kostki k_i wyznaczamy ekspansje k⁺(L,k_i). Jeśli L jest minimalnym pokryciem kolumnowym macierzy blokującej, to k⁺ jest implikantem prostym funkcji f.

Należy zatem znaleźć minimalne pokrycia kolumnowe macierzy B_i. Dla macierzy B₁, wyznaczonej powyżej, minimalnymi pokryciami kolumnowymi są $L{=}\{4\}$ i $L{=}\{5\}.$ Zauważmy, że istnieje też pokrycie $L{=}\{1,2\},$ ale nie jest to pokrycie minimalne.

Kostkę k⁺(L,k) wyznacza się następująco:

$k^{+}(L,k)=\left\{{\begin{aligned}&k_{j},&&{\mbox{gdy }}j\in L\\&**,&&{\mbox{w pozostalych przypadkach}}\end{aligned}}\right.$

Zatem: $k^{+}(\{4\},k_{1})=(***1*)=x_{4}.$

Końcowy krok

Gdy mamy już wyznaczone wszystkie implikanty proste, należy wyznaczyć taki ich podzbiór, który pokrywa wszystkie kostki k_i ze zbioru F. Suma tych implikantów będzie minimalną realizacją zadanej funkcji f(F, R).