Minimalizacja funkcji boolowskich
Z Wikipedii, wolnej encyclopedia
Minimalizacja funkcji boolowskich polega na znalezieniu dla danej funkcji formuły minimalnej, która jest jak najmniej skomplikowana.
Ten artykuł od 2012-11 wymaga zweryfikowania podanych informacji. |
Przy porównywaniu stopnia skomplikowania reguł wprowadza się pojęcie współczynnika skomplikowania.
Dla funkcji boolowskiej zapisanej przy pomocy kanonicznej postaci sumy, współczynnik skomplikowania jest równy sumie liczby mnożeń i sumie liczby dodawań.
Tradycyjne metody takie jak metoda Karnaugha, metoda Quine’a-McCluskeya, metoda iteracyjnego konsensusu czy metoda Espresso (oparta na algorytmie ekspansji) bazują na generowaniu pokryć przy pomocy jak najmniejszej liczby implikantów prostych.
W przypadku funkcji opisanych na przestrzeniach wielowartościowych mamy do czynienia z minimalizacją liczby reguł.
W syntezie logicznej, minimalizację funkcji boolowskich stosuje się w celu zredukowania liczby potrzebnych zasobów (bramek logicznych, bloków bramek) do realizacji danej funkcji. W tym procesie nie mniej skuteczne okazują się także dekompozycja funkcji boolowskich i redukcja argumentów.