Minimalizacja funkcji boolowskich

Ten artykuł od 2012-11 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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.