Verfahren nach Quine und McCluskey

Das Verfahren nach Quine und McCluskey (QMCV, nach Willard Van Orman Quine und Edward J. McCluskey) ist eine Methode, um Boolesche Funktionen zu minimieren. Der Kern des Verfahrens wurde bereits von Quine vollständig beschrieben. Die Verfeinerungen von McCluskey betreffen im Wesentlichen die praktische algorithmische Durchführbarkeit. Die Minimierung ist u. a. deshalb wichtig, weil dadurch die hardwaretechnische Realisierung einfacher und daher kostengünstiger wird. Der Vorteil dieses Verfahrens ist, dass es sich verhältnismäßig leicht in ein Computerprogramm fassen und so mittels eines Computers ausführen lässt. Das Verfahren benötigt im schlechtesten Fall exponentielle Laufzeit, um eine minimale Lösung zu finden. Das Verfahren findet immer eine minimale Lösung, es ist jedoch möglich, dass es noch andere (gleichwertige) Lösungen gibt, die nicht gefunden werden. Da das zugrunde liegende Problem NP-vollständig ist, gibt es unter der Annahme, dass P ≠ NP gilt, kein in diesem Sinne effizientes Verfahren. Das Verfahren bezieht sich zunächst nur auf Funktionsdarstellungen in kanonischer disjunktiver Normalform (KDNF). Ausdrücke in konjunktiver Normalform (KNF) lassen sich jedoch ohne weiteres über die Verneinung der betrachteten Funktion zunächst in eine DNF umwandeln, dann wie unten beschrieben minimieren und schließlich durch erneute Verneinung in eine KNF zurücktransformieren.