Loading AI tools
Z Wikipedii, wolnej encyklopedii
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:
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.
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:
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).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.