Algorytm ekspansji

Ten artykuł od 2024-08 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Google Books • Google Scholar • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Algorytm ekspansji – 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.

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.

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

${\displaystyle {\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.

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ą ${\displaystyle L{=}\{4\}}$ i ${\displaystyle L{=}\{5\}.}$ Zauważmy, że istnieje też pokrycie ${\displaystyle L{=}\{1,2\},}$ ale nie jest to pokrycie minimalne.

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

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

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

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).