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.

Beschreibung des Verfahrens

Prinzip

Das Grundprinzip des Quine-McCluskey-Verfahrens beruht auf der folgenden Eigenschaft von Konjunktionstermen: Unterscheiden sich zwei durch Disjunktion verknüpfte Konjunktionsterme nur durch die Negation einer einzigen Variablen, so kann man diese beiden Terme verschmelzen und dabei die betreffende Variable entfernen. Diese Eigenschaft erklärt sich aus folgendem booleschen Zusammenhang:

$x_{1}\cdot \ldots \cdot x_{i}\cdot \ldots \cdot x_{n}+x_{1}\cdot \ldots \cdot {\overline {x_{i}}}\cdot \ldots \cdot x_{n}$

$=x_{1}\cdot \ldots \cdot (x_{i}+{\overline {x_{i}}})\cdot \ldots \cdot x_{n}$

$=x_{1}\cdot \ldots \cdot x_{i-1}\cdot 1\cdot x_{i+1}\cdot \ldots \cdot x_{n}$

$=x_{1}\cdot \ldots \cdot x_{i-1}\cdot x_{i+1}\cdot \ldots \cdot x_{n}$

In diesem Zusammenhang ist es zweckmäßig, eine Boolesche Funktion unter dem Aspekt der Mengenlehre zu betrachten. (Es werden hier nur vollständig definierte Funktionen berücksichtigt):

• Eine Boolesche Funktion ist als Menge von Konjunktionen aller unabhängigen Variablen darstellbar. Dies entspricht den Funktionswerten der Wahrheitstabelle und ist die Gesamtmenge. Für n unabhängige Variablen beträgt ihre Mächtigkeit $2^{n}$ Elemente.
• Die Elemente werden hierbei auch Elementarkonjunktionen genannt. Dies ist also ein einzelner Funktionswert.
• Diese Menge teilt sich in zwei Teilmengen auf. Ein Teil, welcher die Funktion zur wahren Aussage macht und ein Teil, welcher die Funktion nicht erfüllt. (Bei Verwendung von '0' und '1' also die Teilmenge der '1' und die Teilmenge der '0' in der Wahrheitstabelle).
• Eine Konjunktion ist eine Teilmenge dieser Gesamtmenge. Es gibt $3^{n}$ mögliche Konjunktionen. (inkl. der Gesamtmenge selbst).

Ein Element der Gesamtmenge ist Element einer Konjunktion, wenn die Belegung der in der Konjunktion enthaltenen Variablen mit den entsprechenden Werten des Elements (Elementarkonjunktion) die Konjunktion zur wahren Aussage macht.

Beispiel:

$x_{0}\cdot x_{1}\cdot {\overline {x_{2}}}\in x_{0}\cdot x_{1}$

${\overline {x_{0}}}\cdot x_{1}\cdot {\overline {x_{2}}}\in \!\!\!\!\!/\,x_{0}\cdot x_{1}$

Erstellen der kanonischen disjunktiven Normalform

Das Quine-McCluskey-Verfahren geht nun von einer algebraischen Darstellung der Formel in kanonischer disjunktiver Normalform (KDNF) aus. Eine solche KDNF besteht aus einer Disjunktion von Mintermen. Eine andere Darstellung muss also zuerst in diese Form gebracht werden.

Da in diesem Schritt unter Umständen bis zu $2^{n}$ Terme erzeugt werden, gibt es auch Varianten des Verfahrens, die nur eine DNF (statt einer KDNF) benötigen, wie z. B. die Resolventenmethode.

Ermitteln der Primterme

Alle Minterme werden jetzt nach aufsteigender Klasse sortiert, in einer Tabelle aufgelistet. Die Klasse einer Konjunktion ist die Anzahl der darin vorkommenden nicht negierten Variablen.

Man vergleicht nun alle Minterme benachbarter Klassen daraufhin, ob sie sich paarweise um eine einzige Negation unterscheiden. Ist dies der Fall, so verschmilzt man die beiden Terme zu einem neuen Term (der dann natürlich kein Minterm mehr ist) und trägt ihn in eine zweite Tabelle ein. Die beiden verwendeten Terme werden (z. B. durch Abhaken) gekennzeichnet, sind aber auch weiterhin für Vergleiche heranzuziehen.

Auf die verschmolzenen Terme wendet man das Verfahren rekursiv in mehreren Stufen so lange an, bis keine weiteren Verschmelzungen mehr möglich sind. Es ist darauf zu achten, dass beide Terme (Tabellenzeilen) die gleichen Variablen enthalten. Während dieses Vorganges verbleiben einige Terme, die nicht verschmolzen werden konnten. Diese Terme bezeichnet man als Primterme bzw. Primkonjunktionen.

Hierbei treten ab der zweiten Minimierungsstufe die gleichen Konjunktionen mehrfach auf, sie sind jedoch nur einmal in die neue Tabelle einzutragen.

Erstellen der Primtermtabelle

Es ist durchaus möglich, dass nicht alle Primterme benötigt werden. Um herauszufinden, welche Primterme man unbedingt benötigt, erstellt man eine sogenannte Primtermtabelle. Als Spaltenköpfe der Tabelle werden die Minterme verwendet. Als Zeilenköpfe trägt man die Primterme ein. Die einzelnen Zellen der Tabelle sind also Kreuzungspunkte bestimmter Minterme mit bestimmten Primtermen.

Man trägt nun immer dann eine Markierung in der jeweiligen Zelle ein, wenn der Minterm Element des Primterms ist (s. u.).

Dominanzprüfung

Bei der Dominanzprüfung werden obsolete Zeilen und Spalten ermittelt.

Spaltendominanzprüfung

Die Spalten werden paarweise darauf verglichen, ob nicht eine Spalte existiert, in der die markierten Primterme eine Teilmenge der markierten Primterme der anderen Spalte sind. Ist dies der Fall, so kann die Spalte mit der Obermenge gestrichen werden, denn es müssen alle Konjunktionen erfasst werden und daher ist die Konjunktion mit der Obermenge durch Auswahl der Konjunktion mit der Teilmenge ebenfalls erfasst.

Beispiel:

In einer Tabelle stehen u. A. die beiden Spalten

$K_{a}=P_{1}+P_{2}+P_{4}$

$K_{b}=P_{1}+P_{4}$

Hier kann $K_{a}$ gestrichen werden, weil er $K_{b}$ vollständig dominiert. $K_{a}$ ist daher obsolet und wird ab jetzt nicht mehr berücksichtigt.

Zeilendominanzprüfung

Jetzt vergleicht man die Zeilen (Primterme) der Tabelle paarweise, ob nicht eine Zeile existiert, in denen die markierten Minterme eine Teilmenge der markierten Minterme der anderen Zeile sind. Ist dies der Fall, so kann der Primterm mit der Teilmenge gestrichen werden, denn man kann für jede Markierung des gestrichenen Primterms den anderen Primterm als Ersatz nehmen. Die Relation ist hier also genau umgekehrt als bei der Spaltendominanz.

Beispiel:

In einer Tabelle stehen u. A. die beiden Zeilen

$P_{a}=K_{1}+K_{2}+K_{6}+K_{7}$

$P_{b}=K_{1}+K_{2}$

Hier kann $P_{b}$ gestrichen werden, weil er von $P_{a}$ vollständig dominiert wird. $P_{b}$ ist daher obsolet und wird ab jetzt nicht mehr berücksichtigt.

Diese beiden Prüfungen werden solange abwechselnd wiederholt, bis bei einer Prüfung keine Zeile/Spalte mehr gestrichen werden kann, mindestens jedoch je einmal.

Auswahl der Primterme

Die verbleibenden Primterme muss man jetzt so auswählen, dass alle Minterme abgedeckt werden. Hierfür kann es mehrere (ggf. gleichwertige) Möglichkeiten geben. Man wählt dabei möglichst wenige und kleine Primterme, da man ja eine optimierte Funktion erreichen möchte, die schließlich mit möglichst wenigen Schaltgattern technisch realisiert werden kann.

Beispiel

Es folgt ein Beispiel, um die Methode zu erklären:

Darstellung als kanonische disjunktive Normalform

Wir gehen von einer Booleschen Funktion $f$ mit vier Eingangsvariablen $x_{0}\dots x_{3}$ aus, deren kanonische disjunktive Normalform so aussieht:

$\,f(x_{0},x_{1},x_{2},x_{3})=Y=$

${\begin{matrix}\\{\overline {x_{0}}}*{\overline {x_{1}}}*{\overline {x_{2}}}*{\overline {x_{3}}}\,+\,{x_{0}}*{\overline {x_{1}}}*{\overline {x_{2}}}*{\overline {x_{3}}}\,+\,\\{\overline {x_{0}}}*{\overline {x_{1}}}*{x_{2}}*{\overline {x_{3}}}\,+\,{x_{0}}*{\overline {x_{1}}}*{x_{2}}*{\overline {x_{3}}}\,+\,\\{\overline {x_{0}}}*{x_{1}}*{x_{2}}*{\overline {x_{3}}}\,+\,{x_{0}}*{x_{1}}*{x_{2}}*{\overline {x_{3}}}\,+\,\\{\overline {x_{0}}}*{\overline {x_{1}}}*{\overline {x_{2}}}*{x_{3}}\,+\,{x_{0}}*{\overline {x_{1}}}*{\overline {x_{2}}}*{x_{3}}\,+\,\\{x_{0}}*{x_{1}}*{\overline {x_{2}}}*{x_{3}}\,+\,{x_{0}}*{x_{1}}*{x_{2}}*{x_{3}}\ \ \ \end{matrix}}$

Die Variable $m_{k}$ steht für folgenden Konjunktionsterm, wobei $0\leq k\leq 2^{4}-1$ ist:

Die Zahl $k$ wird als Binärzahl $z_{0}z_{1}z_{2}z_{3}$ geschrieben. Wenn $z_{i}=0$, dann wird die negierte Variable ${\overline {x_{i}}}$ verwendet. Wenn $z_{i}=1$, dann wird die nicht negierte Variable $x_{i}$ verwendet. Daraus wird ein Konjunktionsterm gebildet. Für $k=5=[0101]_{2}$ zum Beispiel ist $m_{5}={x_{0}}\land {\overline {x_{1}}}\land {x_{2}}\land {\overline {x_{3}}}$.

Daraus ergibt sich die Schreibweise

$Y=m_{0}\,+\,m_{1}\,+\,m_{4}\,+\,m_{5}\,+\,m_{6}\,+\,m_{7}\,+\,m_{8}\,+\,m_{9}\,+\,m_{11}\,+\,m_{15}$

Ermitteln der Primterme

Die Auswahltabellen

Die Ausgangstabelle:	Die erste Zusammenfassung ergibt:	Es dürfen nur Zeilen zusammengefasst werden, die die "-" an den gleichen Positionen haben (!). Außerdem tauchen ab der zweiten Zusammenfassung (also in der dritten Tabelle) Konjunktionen doppelt auf, welche aber nur einmal notiert werden.	Dritte Zusammenfassung
Tabelle 1 $m_{x}$ $x_{3}$ $x_{2}$ $x_{1}$ $x_{0}$ OK $m_{0}$ 0 0 0 0 ✓ $m_{1}$ 0 0 0 1 ✓ $m_{4}$ 0 1 0 0 ✓ $m_{8}$ 1 0 0 0 ✓ $m_{5}$ 0 1 0 1 ✓ $m_{6}$ 0 1 1 0 ✓ $m_{9}$ 1 0 0 1 ✓ $m_{7}$ 0 1 1 1 ✓ $m_{11}$ 1 0 1 1 ✓ $m_{15}$ 1 1 1 1 ✓	Tabelle 2 $m_{x}+m_{y}$ $x_{3}$ $x_{2}$ $x_{1}$ $x_{0}$ OK $m_{0}+m_{1}$ 0 0 0 - ✓ $m_{0}+m_{4}$ 0 - 0 0 ✓ $m_{0}+m_{8}$ - 0 0 0 ✓ $m_{1}+m_{5}$ 0 - 0 1 ✓ $m_{1}+m_{9}$ - 0 0 1 ✓ $m_{4}+m_{6}$ 0 1 - 0 ✓ $m_{4}+m_{5}$ 0 1 0 - ✓ $m_{8}+m_{9}$ 1 0 0 - ✓ $m_{5}+m_{7}$ 0 1 - 1 ✓ $m_{6}+m_{7}$ 0 1 1 - ✓ $m_{9}+m_{11}$ 1 0 - 1 P1 $m_{7}+m_{15}$ - 1 1 1 P2 $m_{11}+m_{15}$ 1 - 1 1 P3	Tabelle 3 $m_{w}+m_{x}+m_{y}+m_{z}$ $x_{3}$ $x_{2}$ $x_{1}$ $x_{0}$ OK $m_{0}+m_{1}+m_{4}+m_{5}$ 0 - 0 - P4 $m_{0}+m_{1}+m_{8}+m_{9}$ - 0 0 - P5 $m_{4}+m_{6}+m_{5}+m_{7}$ 0 1 - - P6	Keine weiteren Zusammenfassungen möglich.

Dabei wird jede Zeile einer Klasse mit allen Zeilen der benachbarten Klasse auf Verschmelzbarkeit geprüft. Falls eine Verschmelzung möglich ist, werden die zu verschmelzenden Terme in die nächste Tabelle bzw. in die nächste Zusammenfassung eingetragen. Das genaue Vorgehen, um von der Ausgangstabelle zur ersten Zusammenfassung zu gelangen, kann der folgenden Tabelle entnommen werden:

x	x3	x2	x1	x0	Klasse
0	0	0	0	0	0	(0,1)✓(0,4)✓(0,8)✓	(0 mit 1, 4 und 8 vergleichen)
1	0	0	0	1	1	(0,1)✓	(1,5)✓(1,9)✓			(1 mit 5, 6 und 9 vergleichen)
4	0	1	0	0		(0,4)✓		(4,5)✓(4,6)✓		(4 mit 5, 6 und 9 vergleichen)
8	1	0	0	0		(0,8)✓			(8,9)✓	(8 mit 5, 6 und 9 vergleichen)
5	0	1	0	1	2		(1,5)✓	(4,5)✓		(5,7)✓			(5 mit 7 und 11 vergleichen)
6	0	1	1	0				(4,6)✓			(6,7)✓		(6 mit 7 und 11 vergleichen)
9	1	0	0	1			(1,9)✓		(8,9)✓			(9,11)✓	(9 mit 7 und 11 vergleichen)
7	0	1	1	1	3					(5,7)✓	(6,7)✓		(7,15)✓		(7 mit 15 vergleichen)
11	1	0	1	1								(9,11)✓		(11,15)✓	(11 mit 15 vergleichen)
15	1	1	1	1	4								(7,15)✓	(11,15)✓

Dieses Verfahren wird solange wiederholt, bis keine Verschmelzungen mehr möglich sind. Es ergeben sich im vorliegenden Fall sechs Primterme, die sich im Zuge des Verfahrens nicht verschmelzen lassen. Diese Terme können in verschiedenen Tabellen stehen. Im vorliegenden Fall ergeben sich die Terme, die sich nicht verschmelzen lassen, bzw. die Primimplikanten in den letzten drei Zeilen der Tabellen 2 und 3:

$\,P_{1}=x_{0}*{\overline {x_{2}}}*x_{3}=m_{9}+m_{11}$

$\,P_{2}=x_{0}*x_{1}*x_{2}=m_{7}+m_{15}$

$\,P_{3}=x_{0}*x_{1}*x_{3}=m_{11}+m_{15}$

$\,P_{4}={\overline {x_{1}}}*{\overline {x_{3}}}=m_{0}+m_{1}+m_{4}+m_{5}$

$\,P_{5}={\overline {x_{1}}}*{\overline {x_{2}}}=m_{0}+m_{1}+m_{8}+m_{9}$

$\,P_{6}=x_{2}*{\overline {x_{3}}}=m_{4}+m_{5}+m_{6}+m_{7}$

Erstellen der Primtermtabelle

Die Primtermtabelle sieht so aus:

	$m_{0}$	$m_{1}$	$m_{4}$	$m_{5}$	$m_{6}$	$m_{7}$	$m_{8}$	$m_{9}$	$m_{11}$	$m_{15}$
$P_{1}$								•	•
$P_{2}$						•				•
$P_{3}$									•	•
$P_{4}$	•	•	•	•
$P_{5}$	•	•					•	•
$P_{6}$			•	•	•	•

Dominanzprüfung

Die erste Spaltendominanzprüfung ergibt:

• Streichen von $m_{0}$, $m_{1}$ und $m_{9}$ wegen Spalte $m_{8}$
• Streichen von $m_{4}$, $m_{5}$ und $m_{7}$ wegen Spalte $m_{6}$

Danach sieht die Tabelle so aus:

	$m_{6}$	$m_{8}$	$m_{11}$	$m_{15}$
$P_{1}$			•
$P_{2}$				•
$P_{3}$			•	•
$P_{4}$
$P_{5}$		•
$P_{6}$	•

Die Zeilendominanzprüfung ergibt:

• Streichen von $P_{4}$ (leer).
• Streichen von $P_{2}$ wegen $P_{3}$
• Streichen von $P_{1}$ wegen $P_{3}$

Somit erhält man:

	$m_{6}$	$m_{8}$	$m_{11}$	$m_{15}$
$P_{3}$			•	•
$P_{5}$		•
$P_{6}$	•

Eine Zweite Spaltendominanzprüfung ergibt:

• Streichen von $m_{15}$ wegen $m_{11}$

Ergebnis:

	$m_{6}$	$m_{8}$	$m_{11}$
$P_{3}$			•
$P_{5}$		•
$P_{6}$	•

Eine zweite Zeilendominanzprüfung ergibt keine Streichungen mehr. Damit ist die Dominanzprüfung beendet.

Auswahl der Primterme

Die Auswahl geeigneter Primterme ist hier jetzt sehr einfach, da es nur eine Möglichkeit gibt: Benötigt werden die Primterme $P_{3}$, $P_{5}$ und $P_{6}$.

Verknüpfung der gewählten Primterme

Jetzt müssen die ausgewählten Primterme mittels Disjunktion zur Lösungsgleichung verknüpft werden:

$\,Y=P_{3}\ +P_{5}\ +\ P_{6}$

$\,Y=x_{0}*x_{1}*x_{3}\quad +\quad {\overline {x_{1}}}\ *{\overline {x_{2}}}\quad +\quad x_{2}*{\overline {x_{3}}}$

Anmerkung

Das Problem, eine minimale Anzahl von Primtermen aus der Primtermtabelle auszuwählen, ist NP-vollständig; d. h., für viele Fälle ist kein wesentlich besseres Verfahren bekannt, als alle möglichen Auswahlen auszuprobieren. Deshalb bietet es sich an, das Minimum nur näherungsweise zu bestimmen. Beispielsweise wählt man zuerst die Spalten mit nur einer Markierung aus (diese sind zwingend notwendig), danach sucht man in den Spalten mit wenig Markierungen oder in Zeilen mit vielen Markierungen nach geeigneten Termen.

Das Verfahren hat insbesondere bei höherer Variablenzahl Vorteile gegenüber dem Karnaugh-Veitch-Diagramm (KVD). Als Faustregel gilt: Bis fünf Variablen ist das KVD besser, ab sechs Variablen das QMCV.

Siehe auch

• Karnaugh-Veitch-Diagramm
• Buchberger-Algorithmus
• Disjunktive Normalform
• Konjunktive Normalform

Weblinks

• Wolfgang Kastner, Institut für Rechnergestützte Automation, TU Wien: Grundzüge der Informatik
• Philipps-Universität Marburg: Technische Informatik - Minimierung mit Quine-McCluskey
• Christian Gottschall: Der Quine-McCluskey-Optimierer
• Technische Universität Ilmenau: Ein Applet, das die einzelnen Schritte des Verfahrens demonstriert
• JavaScript-Programm der Universität Marburg