Metoda Quine’a-McCluskeya
Metoda Quine’a-McCluskeya jest techniką minimalizacji funkcji boolowskich, opracowaną przez Willarda Van Ormana Quine’a i Edwarda J. McCluskeya. Oferuje wyniki porównywalne z metodą tablic Karnaugh, ale jest łatwiejsza do zaimplementowania komputerowo.
Algorytm
Minimalizacja zaczyna się od uporządkowania zbiorów iloczynów funkcji według liczby jedynek. Następnie porównuje się kombinacje w danej grupie z tymi w grupie następnej. Jeśli różnią się tylko na jednej pozycji, łączy się je w nową kombinację, oznaczając różniącą się pozycję znakiem „–”. Proces ten powtarza się, aż do wyczerpania możliwości dalszego łączenia. Kombinacje, które nie mogą być już łączone, nazywa się implikantami prostymi.
Później tworzy się tabelę, gdzie wiersze reprezentują implikanty proste, a kolumny prawdziwe iloczyny funkcji. W tabeli oznacza się „x” w polach, które reprezentują implikanty i ich odpowiadające iloczyny.
Ostateczna uproszczona funkcja jest sumą wybranych implikantów prostych, które pokrywają wszystkie iloczyny pełne.
Podobieństwo do metody tablic Karnaugha
Obie metody są teoretycznie identyczne, organizując grupy w sposób analogiczny. Quine’a-McCluskeya bazuje na podejściu tekstowym, podczas gdy metoda Karnaugha ma charakter graficzny. Wybór implikantów prostych w obu metodach jest analogiczny.
Złożoność
Chociaż metoda Quine’a-McCluskeya jest bardziej wygodna dla funkcji z większą liczbą zmiennych, jej zastosowanie jest ograniczone, ponieważ problem minimalizacji jest NP-trudny. Czas działania algorytmu rośnie wykładniczo z liczbą zmiennych. Dla funkcji z n zmiennymi liczba implikantów prostych ma górne ograniczenie 3n/n. W praktyce dla wielu zmiennych używa się metod heurystycznych, takich jak metoda Espresso.
Przykład
Rozważmy tablicę prawdy funkcji czterech zmiennych:
Funkcja przyjmuje wartość 1 dla 4, 8, 10, 11, 12 i 15, a niezdefiniowana jest dla 9 i 14. Można przedstawić ją jako:
Optymalizacja
Aby zoptymalizować funkcję, budujemy tablicę iloczynów zupełnych i łączymy je w pary różniące się jedną pozycją, oznaczając różnice znakiem „–”. Implikanty, które nie mogą być połączone, zaznaczamy gwiazdką jako implikanty proste.
Krok 2: Wybór implikantów prostych
Tworzymy tabelę z implikantami prostymi jako wierszami oraz iloczynami jako kolumnami. Wybieramy istotne implikanty, które pokrywają kolumny z jednym znakiem „x”. W przypadku, gdy istotne implikanty nie pokrywają wszystkich iloczynów, stosujemy metodę Petricka. Ostateczne rozwiązania mogą mieć różne formy, na przykład:
lub
