6.4 Übertragung der Operationen

Sei $n$ die Anzahl der Grundobjekte, $w$ die Anzahl der allgemeinen Prämissen, $v$ die Anzahl der partikulären Prämissen. Dann bestehen die $2^{n}$ Einträge des Arrays oder der linearen Liste, die das Venn-Diagramm repräsentiert, jeweils aus Bit-Vektoren der Länge $w+v$.

$$V_{j} = (~x_{1}~x_{2}~\ldots~x_{w}~x_{w+1}~\ldots~x_{w+v}~)~~~~~~~j \in \{0, \ldots 2^{n}-1\}$$

$x_{i}$ ist dabei ein Flag, welches im gesetzten Zustand, abhängig von der Position im Bit-Vektor entweder eine Schraffierung oder eine Sternung anzeigt.

Auf den Vektoren sind bitweise ,,Boolesche`` UND-, ODER- und NICHT-Operationen definiert. $V_{M}$ ist der 1-Vektor, $V_{W}$ ist der 0-Vektor. $V_{aM}$ ist der Vektor, in dem nur die ersten $w$ Flags gesetzt sind. $V_{pM}$ ist der Vektor, in dem nur die letzten $v$ Flags gesetzt sind.

6.4.1 Streichen

Das Schraffieren einer Zelle im Venn-Diagramm entspricht dem Setzen eines ,,Schraffierungsflags`` in dem Eintrag mit der der Zelle entsprechenden Nummer.

$a \sqsubseteq b$ entspricht $a \sqcap \overline{b} = 0$, d.h. $a \sqcap \overline{b}$ ist zu schraffieren, d.h. in den Einträgen mit den Nummern ${G^{n}_{a} \cap G^{n}_{\overline{b}}}$ wird das entsprechende Schraffierungsflag gesetzt.

$a \sqsubseteq \overline{b}$ entspricht $a \sqcap b = 0$, d.h. $a \sqcap b$ ist zu schraffieren, d.h. in den Einträgen mit den Nummern ${G^{n}_{a} \cap G^{n}_{b}}$ wird das entsprechende Schraffierungsflag gesetzt.

$\overline{a} \sqsubseteq b$ entspricht $\overline{a} \sqcap \overline{b} = 0$, d.h. $\overline{a} \sqcap \overline{b}$ ist zu schraffieren, d.h. in den Einträgen mit den Nummern ${G^{n}_{\overline{a}} \cap G^{n}_{\overline{b}}}$ wird das entsprechende Schraffierungsflag gesetzt.

$\overline{a} \sqsubseteq \overline{b}$ entspricht $\overline{a} \sqcap b = 0$, d.h. $\overline{a} \sqcap b$ ist zu schraffieren, d.h. in den Einträgen mit den Nummern ${G^{n}_{\overline{a}} \cap G^{n}_{b}}$ wird das entsprechende Schraffierungsflag gesetzt.

Für jede Prämisse, die eine Halbordnung enthält, ist in den Einträgen des Venn-Diagramms ein eigenes Schraffierungsflag vorhanden. Dieses ist zunächst nicht notwendig, wird uns später aber erlauben, festzustellen, welche Prämisse(n) eine Zelle schraffiert hat(haben).

Der Aufwand ist $w \cdot O(N)$, also $O(N)$ wenn $N$ die Größe der Liste (im folgenden Eingabemenge genannt) ist, die das Venn-Diagramm repräsentiert.

6.4.2 ,,Sternen``

Das Sternen einer Zelle im Venn-Diagramm entspricht dem Setzen eines ,,Sternungsflags`` in dem Eintrag mit der der Zelle entsprechenden Nummer.

$a \not\sqsubseteq b$ entspricht $a \sqcap \overline{b} \not = 0$, d.h. $a \sqcap \overline{b}$ ist zu sternen, d.h. in den Einträgen mit den Nummern ${G^{n}_{a} \cap G^{n}_{\overline{b}}}$ wird das entsprechende Sternungsflag gesetzt.

$a \not\sqsubseteq \overline{b}$ entspricht $a \sqcap b \not = 0$, d.h. $a \sqcap b$ ist zu sternen, d.h. in den Einträgen mit den Nummern ${G^{n}_{a} \cap G^{n}_{b}}$ wird das entsprechende Sternungsflag gesetzt.

$\overline{a} \not\sqsubseteq b$ entspricht $\overline{a} \sqcap \overline{b} \not = 0$, d.h. $\overline{a} \sqcap \overline{b}$ ist zu sternen, d.h. in den Einträgen mit den Nummern ${G^{n}_{\overline{a}} \cap G^{n}_{\overline{b}}}$ wird das entsprechende Sternungsflag gesetzt.

$\overline{a} \not\sqsubseteq \overline{b}$ entspricht $\overline{a} \sqcap b \not = 0$, d.h. $\overline{a} \sqcap b$ ist zu sternen, d.h. in den Einträgen mit den Nummern ${G^{n}_{\overline{a}} \cap G^{n}_{b}}$ wird das entsprechende Sternungsflag gesetzt.

Bei der Sternung ist es ganz klar, daß jede Prämisse, die eine verneinte Halbordnung enthält, in den Einträgen des Venn-Diagramms ein eigenes Sternungsflag haben muß, denn man muß ja die Sternsorten für den Konklusionentest unterscheiden können.

Der Aufwand ist $v \cdot O(N)$, also $O(N)$ wenn $N$ die Größe der Eingabemenge ist.

6.4.3 Testen von vermuteten Folgerungen

Der Konklusionentest ist nach den obigen Vorbereitungen natürlich ganz einfach:

1.

Die vermutete Folgerung ist eine Halbordnung. Dann wird zunächst berechnet, welche Zellen des Diagrammes schraffiert sein müssten. Danach wird geprüft, ob in jedem der betroffenen Einträge mindestens ein Schraffierungsflag gesetzt ist. Ist dieses der Fall, so FOLGT die vermutete Folgerung, sonst FOLGT sie NICHT.

Sei $N$ die Anzahl der abzutestenden Zellen. Dann ist der Laufzeitaufwand $O(N)$.

2.

Die vermutete Folgerung ist eine negierte Halbordnung. Dann muß unter Umständen für jede Sternsorte geprüft werden, ob mindestens eine der betroffenen Zellen mit einem Sternungsflag dieser Sternsorte versehen ist, und diese Sternsorte außerhalb der durch die vermutete Folgerung betroffenen Zellen nicht vorkommt, bzw. falls sie vorkommt, daß diese Zellen auch schraffiert sind. Ist dieses der Fall, dann FOLGT die vermutete Folgerung. Kann keine der Sternsorten diese Bedingungen erfüllen, so FOLGT die vermutete Folgerung NICHT.

Da schlimmstenfalls jede Zelle des Diagrammes für jede partikuläre Prämisse getestet werden muß, ist die Laufzeit $v \cdot O(N) = O(N)$, wobei $v$ die Anzahl der partikulären Prämissen ist.