Metoda Quine'a-McCluskeya

Metoda Quine'a-McCluskeya to sposób minimalizacji funkcji boolowskich. Daje rezultaty identyczne do metody tablic Karnaugh, ale w przeciwieństwie do niej, dużo łatwiej daje się zaimplementować na komputerze.

[edytuj] Algorytm

Proces minimalizacji rozpoczynamy od uporządkowania zbiorów iloczynów zupełnych funkcji w taki sposób, aby poszczególne grupy zawierały iloczyny zupełne o takiej samej liczbie jedynek. Następnie porównujemy każdą kombinację należącą do danej grupy z każdą kombinacją należącą do grupy następnej. Jeżeli porównywane kombinacje różnią się od siebie tylko na jednej pozycji, to łączymy je w nową kombinację, wpisując w rozróżniające je miejsce znak "–".

Kontynuując procedurę łączenia, usuwamy powtarzające się kombinacje; kończymy gdy nie ma możliwości dokonania dalszych łączeń. Każda kombinacja nie podlegająca dalszemu łączeniu jest nazywana implikantem prostym.

Następnie tworzymy tabelę, w której wiersze odpowiadają otrzymanym implikantom prostym, a kolumny wszystkim prawdziwym iloczynom zupełnym, przedstawionym w definicji funkcji. Analizując tabelę stawiamy znak "x" w tych polach, które leżą na przecięciu kolumny reprezentującej dany iloczyn pełny (w postaci liczby dziesiętnej) oraz wiersza odpowiadającego implikantowi prostemu, który ów iloczyn pełny zawiera.

Uproszczona funkcja, równoważna funkcji minimalizowanej, może być otrzymana w postaci sumy wybranych implikantów prostych. Wybór implikantów prostych jest przeprowadzany tak, aby pokrywały one wszystkie rozważane iloczyny pełne.

[edytuj] Złożoność

Wprawdzie dla funkcji powyżej czterech zmiennych metoda Quine'a-McCluskeya jest bardziej wygodna niż metoda Karnaugh, jednak zakres jej zastosowań także jest ograniczony, ponieważ problem który rozwiązuje jest NP-trudny: czas działania algorytmu rośnie wykładniczo z rozmiarem zadania. Pokazano, że dla n zmiennych liczba implikantów prostych funkcji ma ograniczenie górne 3ⁿ/n.

Funkcje o wielu zmiennych redukuje się więc metodami heurystycznymi, które nie gwarantują znalezienia minimum. Wśród nich faktycznym standardem jest metoda Espresso.