7.3 Die Deduktion

Eine andere Frage, die man sich im Zusammenhang mit logischen Systemen stellt, ist die Frage, was alles aus den vorgegeben Prämissen folgt. Dieser Vorgang wird im allgemeinen ,,Deduktion`` genannt.

Auch deduktive Fragen können mit Venn-Diagrammen behandelt werden, denn nach dem Eintrag aller bekannten Prämissen in das Diagramm steht auch alles darin, was aus den Prämissen folgt. Die Frage ist natürlich, in welcher Form und in welchem Umfang man diese Informationen ausliest. Eine vollständige Ausgabe aller in dem Diagramm enthaltenen Informationen würde einen erheblichen Umfang annehmen, außerdem wäre viel redundante Information enthalten von der Art $a \cdot b \sqsubseteq a$.

Für das Programm wurde daher eine ,,quasi vollständige`` Ausgabe gewählt, d.h. die Ausgabe kann relativ einfach ( durch einfachste verbandstheoretische Regeln ) vervollständigt werden, wenn man sich die Zeit dazu nehmen will. Um diese ,,quasi vollständige`` Ausgabe zu erreichen, werden die Zellen, die durch allgemeine Prämissen gestrichen wurden, in einer Menge zusammengenommen und dann soweit wie möglich zusammengefaßt (Generierung der Primimplikanten). Ebenso werden die nicht gestrichenen Zellen jeder einzelnen partikulären Prämisse zusammengefaßt.

Der bekannteste Zusammenfassungsalgorithmus zur Erzeugung von Primimplikanten ist der Algorithmus von Quine/McCluskey. Er basiert auf der Regel $a \sqcap b \sqsubseteq 0, a \sqcap \overline{b} \sqsubseteq 0 \vdash a \sqsubseteq 0$, einer einfachen Anwendung von (A5).

Das Venn-Diagramm liefert die Minterme als Zellennummern, mit denen der Algorithmus startet. Jedoch reicht ein Bit nun nicht mehr zur Kodierung der Verhältnisse eines Grundobjekts aus, denn man muß neben dem negierten wie dem unnegierten Auftreten auch noch kodieren können, daß das Grundobjekt sowohl negiert als auch unnegiert auftritt, und daher gemäß obiger Regel eliminiert werden kann.

Eine mögliche Lösung ist die Kodierung in zwei Zahlen: Zu Beginn sind beide Zahlen gleich und entsprechen der Zellennummer. Nach Elimination eines Grundobjekts steht in der ersten Zahl eine 0 und in der zweiten eine 1. Diese Elimination kann erfolgen, wenn sich die beiden ersten Zahlen der zu vergleichenden Implikanten nur an einer Stelle unterscheiden und ebenso die beiden zweiten Zahlen nur an dieser Stelle. Lassen sich Implikanten bei einem Durchlauf ( jeder Implikant, der sich möglicherweise an nur einer Stelle von einem anderen Implikanten unterscheidet, wird mit diesem verglichen ) nicht für eine Elimination verwenden, dann sind sie prim und brauchen nicht mehr weiter betrachtet zu werden.

Als Ausgabe erhält man die Menge der Primimplikanten in der Kodierung durch je zwei Zahlen, die sehr einfach als Halbordnungen oder negierte Halbordnungen interpretiert werden können.

Es gibt Implementationen des Quine/McCluskey Algorithmus, die eine Laufzeit von $O(N^{log(3)} \cdot log^{2}(N))$ erreichen, mit $N$ Länge der Eingabe. Das liegt an einer besonders effizienten Speicherung der Implikanten, z.B. in einem 2-3 Baum auf einem 3-wertigen Alphabet. Die vorgestellte Version verwaltet die Implikanten in linearen Listen, ist also nicht ganz so gut.

Hat man viele Implikanten und lassen sich die Prämissen sehr gut zusammenfassen, so ergeben sich aber doch recht lange Laufzeiten für den Quine/McCluskey Algorithmus.

Daher ist noch ein anderer Algorithmus denkbar, der das Zusammenfassen von der anderen Seite her angeht, d.h. er beginnt bei der Prüfung der stärksten Zusammenfassungen und arbeitet sich von dort nach unten vor.

Dabei gibt die Zahl der zusammenzufassenden Zellen bereits eine Schranke an, ab der es sich erst zu testen lohnt, ob die jeweils notwendigen Minterme vorhanden sind. Ist die Schranke erreicht, werden die auf dieser Ebene generierten möglichen Zusammenfassungen getestet, und mit Breitensuche weitergeneriert. Für jede so erzeugte mögliche Zusammenfassung wird überprüft, ob alle für sie notwendigen Minterme vorhanden sind. Wenn ja, wird diese Zusammenfassung ausgegeben. Danach terminiert dieser Ast des Baumes der möglichen Zusammenfassungen, denn er würde immer nur Spezialfälle der bereits gefundenen Zusammenfassung ausgeben. Hier wirkt sich die Wahl der ,,quasi-vollständigen`` Ausgabe aus.

Insgesamt bildet die größte Zahl der in einer Prämisse vorkommenden Grundobjekte eine Schranke für den Grad der zu erzeugenden Zusammenfassungen. Der Algorithmus terminiert daher spätestens auf der Ebene der Minterme, meistens aber schon viel früher. Dabei könnte der Algorithmus im schlimmsten Fall $2^{(2^n)}$ mögliche Zusammenfassungen generieren, nämlich wenn die Eingabe nur aus einem einzigen Minterm besteht und das wäre sehr schlecht.

Der eine Algorithmus ist da gut, wo der andere schlecht ist und umgekehrt. Als statistisch begründete Heuristik hat sich ergeben, den zweiten Algorithmus im Rahmen der Deduktion einzusetzen, sobald mehr als ein Drittel der Zellen des Diagrammes zusammengefaßt werden sollen.