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.

AlgorytmEdytuj

Działanie algorytmu przebiega następująco:

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

Macierze blokująceEdytuj

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

 

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

Wyznaczenie implikantów prostychEdytuj

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ą   i   Zauważmy, że istnieje też pokrycie   ale nie jest to pokrycie minimalne.

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

 

Zatem:  

Końcowy krokEdytuj

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