Minimalizacja funkcji boolowskich

Minimalizacja funkcji boolowskich polega na znalezieniu dla danej funkcji formuły minimalnej, która jest jak najmniej skomplikowana.

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.

Zobacz też

• funkcja boolowska
• logika rozmyta
• logika wielowartościowa