Metoda Quine'a-McCluskeya

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Metoda Quine'a-McCluskeya – sposób minimalizacji funkcji boolowskich opracowany przez Willarda Van Ormana Quine'a i Edwarda J. McCluskeya. Daje rezultaty identyczne do metody tablic Karnaugh, ale w przeciwieństwie do niej, dużo łatwiej daje się zaimplementować na komputerze.

Algorytm[edytuj | edytuj kod]

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.

Podobieństwo do metody tablic Karnaugha[edytuj | edytuj kod]

Z teoretycznego punktu widzenia, metoda Quine'a-McCluskeya i metoda tablic Karnaugh są identyczne. Wystarczy zauważyć, że w kolejnych krokach metody Quine'a-McCluskeya organizujemy grupy odpowiednio 1,2,4,8... elementowe, tak samo jak zakreślamy możliwie największe grupy w metodzie tablic Karnaugh. Następnie wybieramy takie implikanty proste, które pokrywają nam wszystkie iloczyny pełne, tak samo jak w metodzie Karnaugh upewniamy się, że zakreślone grupy pokrywają nam wszystkie konieczne pola. Można zatem odnieść wrażenie, że mechanizm działania jest ten sam, tyle że metoda tablic Karnaugha jest "graficzna", natomiast metoda Quine'a-McCluskeya jest "tekstowa". Praktyka pokazuje, która metoda jest wygodniejsza w wybranej sytuacji.

Złożoność[edytuj | edytuj kod]

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 3n/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.

Zobacz też[edytuj | edytuj kod]