Metoda Quine'a-McCluskeya
Z Wikipedii
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 pełnych funkcji w taki sposób, aby poszczególne grupy zawierały iloczyny peł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 "-".
Kontunuują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 peł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.
