powrót do strony głównej >>

Algorytm Quine'a-McCluskey'a

Copyright © 2004   Robert Nowotniak

Minimalizacja formuł boolowskich jest przydatna w wielu zastosowaniach, także poza elektroniką i elektrotechniką. Algorytm Quine'a-McCluskey'a pozwala na otrzymanie najprostszego wzoru, który wyraża dowolną funkcję logiczną ({0, 1}m → {0, 1}). Inne metody rozwiązywania tego problemu, tablice Karnaugha i diagramy Veitcha, są trudniejsze do przedstawienia w postaci algorytmicznej, a w praktyce pozwalają minimalizować funkcje co najwyżej sześciu zmiennych - dla większej liczby konieczne byłoby użycie wielu wielowymarowych, nakładających się tablic.


Wpisz wzór formuły boolowskiej (przykład):
F1 =

Zamiast wzoru możesz podać wartości funkcji dla wszystkich argumentów.

Ilość zmiennych:

Algorytm polega na podziale argumentów (wektorów), dla których funkcja przyjmuje wartości prawdziwe na grupy biorąc pod uwagę ilość jedynek. Następnie stosuje się jedną z dwu równoważności (reguły sklejania):

A*x + A*x' = A
(A + x)(A + x') = A

Po zakończeniu każdego cyklu wektory, które nie zostały sklejone z żadnym innym, dodaje się do zbioru implikantów formuły wyjściowej. G jest implikantem F, gdy w(G → F) = 1. Jeśli nie można dokonać już więcej sklejeń, przechodzi się do wyboru implikantów prostych, czyli najmniejszego podzbioru, z którego sumy wynika formuła. Używa się tabelki, w której kolumny oznaczają pełne iloczyny formuły, a wiersze implikanty. Należy znaleźć najmniejszą liczbę wierszy, z których alternatywy logicznej wynika cała początkowa formuła.


Program przyjmuje wzory w postaci napisów o następującej składni:

WZÓR     ::= SKŁADNIK { '+' SKŁADNIK }
SKŁADNIK ::= CZYNNIK { [ '*' ] CZYNNIK }
CZYNNIK  ::= (LICZBA | ZMIENNA | '(' WZÓR ')') { ''' }

Jeśli chcesz, możesz pobrać kod źródłowy w języku C. Pozwala minimalizować formuły boolowskie dla wyrażeń z log3 (232) - 1 = 19 zmiennymi. 20-elementową wariację trójelementowego zbioru da się zapisać na 32 bitach.


Copyright © Robert Nowotniak
29 maja 2004