Algorytm ekspansji
Z Wikipedii
Algorytm ekspansji to ważny element metody Espresso, która jest używana do minimalizacji funkcji boolowskich. Jednakże używany samodzielnie również prowadzi do znalezienia minimalej 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.
Spis treści |
[edytuj] Algorytm
Działanie algorymtmu przebiega następująco:
- Wyznaczenie macierzy blokujących B(ki, R) dla ki∈F.
- Wyznaczenie implikantów prostych funkcji f=(F, R)
- Wyznaczenie zbioru implikantów prostych pokrywających wszystkie kostki ki
[edytuj] Macierze blokujące
Macierz blokującą B(ki, R) tworzy się. negując j-te kolumny macierzy R przy czym j-te elementy kostki ki są jedynkami. Przykładowo:
-
- zanegowana kolumna - 4
Należy wyznaczyć macierz blokującą dla każdej kostki ze zbioru F.
[edytuj] Wyznaczenie implikantów prostych
Dla danej kostki ki wyznaczamy ekspansje k+(L,ki). 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 Bi. Dla macierzy B1, 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:
Zatem:
k + ({4},k1) = ( * * * 1 * ) = x4
[edytuj] Końcowy krok
Gdy mamy już wyznaczone wszystkie implikanty proste, należy wyznaczyć taki ich podzbiór, który pokrywa wszystkie kostki ki ze zbioru F. Suma tych implikantów będzie minimalną realizacją zadanej funkcji f(F, R).
