Algorytm Quine'a-McCluskey'a

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):

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

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 log₃ (2³²) - 1 = 19 zmiennymi. 20-elementową wariację trójelementowego zbioru da się zapisać na 32 bitach.

F₁ =