Teil der zentralen Verarbeitungen meines Logikübergangs ist ein aussagenlogischer Optimierer, der eine recht schnelle heuristische Variante des Quine-McCluskey-Algorithmus benützt. Dieses Verfahren bildet zu einer gegebenen KDNF eine äquivalente DNF, die höchstens ebenso lang (meistens aber viiieeel kürzer) ist.

Angewandt wird die Quine-McCluskey-Optimierung vor allem im Bereich der digitalen Schaltungstechnik, wo es sich bisweilen zuträgt, dass zu einem gegebenen Wahrheitswertverlauf eine möglichst einfache aussagenlogische Realisierung gesucht wird. Aus dieser Herkunft erklärt es sich, dass der Optimierer im Gegensatz zu den anderen Verarbeitungen des Logikübergangs in zwei Versionen vorliegt: Einer gewöhnlichen, die wie die anderen Verarbeitungen arbeitet und aussagenlogische Ausdrücke entgegennimmt; und einer tabellenbasierten, die auf eine Menge von Wahrheitswertzuordnungen angewendet wird, unter denen die Schaltung den Wahrheitswert wahr liefern soll.

Gewöhnlicher Optimierer

Der gewöhnliche Quine-McCluskey-Optimierer ist, äh, gewöhnlich. Er erwartet ebenso wie die anderen Verarbeitungen des Logikübergangs eine Aussage im Eingabebereich, reduziert sie und zeigt das Ergebnis der Vereinfachung an.

Ein Beispiel hierzu

Um die Aussage (A & B & ~C) v (A & ~B & D) v (A & ~B) zu reduzieren, gehen Sie wie folgt vor:

  1. Geben Sie sie die Aussage (A & B & ~C) v (A & ~B & D) v (A & ~B) im Eingabebereich ein.
  2. Wählen Sie die Verarbeitungsart "Quine-McCluskey" (niiicht "Quine-McCluskey mit Tabelle")
  3. Starten Sie durch Wahl von "Verarbeitung" den Optimierungslauf. Der Optimierer reduziert die Aussage zu A & ~B v A & ~C".

Um das Beispiel selbst zu versuchen, wählen Sie dasda.

Tabellenbasierte Optimierung

Der tabellenbasierte Optimierer verarbeitet im Gegensatz zu den anderen Verarbeitungen keine Aussage, sondern eine Liste von Wahrheitswertzuordnungen, unter denen die Schaltung den Wahrheitswert wahr liefern soll. Ein Beispiel mag des Gesagten Verständnis befördern:

Ein Beispiel, als das hilfreicher kein Beispiel gedacht werden kann

Ausgangspunkt des Beispiels ist, dass Sie eine möglichst einfache Aussage finden möchten, die folgenden Wahrheitswertverlauf aufweist: 

  A B C  |  
  -------+--------
  1 1 1  |  1
  1 1 0  |  0
  1 0 1  |  0
  1 0 0  |  0
  0 1 1  |  1
  0 1 0  |  1
  0 0 1  |  1
  0 0 0  |  1

Also: Möchten Sie eine möglichst einfache Aussage mit diesem Wahrheitswertverlauf finden!

Diese Aussage ist in der ersten, fünften, sechsten, siebenten und achten Zeile wahr. Mit anderen Worten sind die Bewertungen, die diese Aussage wahrmachen, die Folgenden: 

  A B C
  -----
  1 1 1
  0 1 1
  0 1 0
  0 0 1
  0 0 0

Diese Bewertungen sind es, die dem Quine-McCluskey-Optimierer vorgelegt werden müssen. Jede wahr machende Bewertung muss als eine Zeile eingegeben werden, ermangelnd jeglicher führender, abschließender oder sonstiger Leerzeichen. So muss z.B. die erste Bewertung als 111 eingegeben werden, die zweite als 011 und so weiter.

Es muss sohin die Anwenderin folgenden Text im Eingabebereich des Logikübergangs eingeben: 

  111
  011
  010
  001
  000

Verschließen Sie Ihre Aufmerksamkeit bitte nicht vor der Tatsache, dass diese Zuordnungsmenge als die KDNF einer zu optimierenden Aussage interpretiert werden kann: (A & B & C) v (~A & B & C) v (~A & B & ~C) v (~A & ~B & C) v (~A & ~B & ~C). Dies ist die KDNF, die der erste Absatz erwähnt und zu der das Verfahren eine äquivalente DNF bildet.

Nach einer kleinen Denkpause liefert der Optimierer eine Aussage, die der solcherart eingegebenen KDNF äquivalent, dabei aber zumeist kürzer als diese ist. Im Beispiel liefert das Verfahren die Aussage b & c v ~a. Obwohl sie nicht wirklich kürzer ist als A->(B&C), ist sie doch um ein Erhebliches kompakter als die KDNF, die am Beginn der Verarbeitung stand. Hinzu kommt, dass sie in ihrer Eigenschaft als DNF strukturell einfacher ist als A->(B&C) und sich einfacher mit Standardschaltungen verwirklichen lässt.

Wenn Sie dieses Beispiel selbst versuchen möchten: Wählen Sie dasda.