Künstliche Intelligenz und das Entweder – Oder (XOR)

1) Das Entweder – Oder (XOR)

„Entweder bin ich Hier oder ich bin Dort.“  Der Satz gilt eigentlich immer. Oder formal verkürzt:  Hier XOR Dort. Das Entweder – Oder bzw. das XOR  (exklusives Oder) postuliert eine Fundamentalordnung in unserem Leben. Das ist auch so in der Kriminalistik, wenn einer behauptet „ich war Dort und nicht Hier am Orte der Tat“. Das nennt man ein   Alibi. Das Ausfüllen eines Wahlzettels mit  genau einem Kreuzchen in einem Kreis ist ja auch ein Entweder – Oder bzw. ein XOR. Folge man dem nicht, ist die Wahl ungültig.

Logisch wird das XOR,  mit A und B als Aussagen, unter anderem wie folgt gefasst:

A XOR B =  (A ∨ B) ∧¬ ( A ∧ B)

In Worten mit den Symbolen ∨ als „Oder“ , ∧ als „Und“ ,  ¬ als „Nicht“ :

A XOR B   ist gleich (=)     (A Oder B) und  Nicht beide also  (A Und B).

Eine Wahrheitstabelle XOR  für 1 = wahr und 0 =falsch  sieht wie folgt aus:

Wenn A und B unterschiedlich sind, dann wird auf ‘wahr‘ erkannt, bei Gleichheit ist XOR  dann ‚falsch‘

Wichtig ist zu wissen, dass  A XOR A, also das Entweder – Oder mit sich selbst, ist immer falsch oder 0. Denn das geht nicht: wenn nur A da ist, gibt es kein Entweder – Oder, es gibt gar keine Alternative. Also:

A  XOR A  =  0

Das so dargestellte  XOR als Entweder – Oder ist klassisch, aber leider ungeeignet, wenn mehr als zwei Variablen zur Debatte stehen,  also wenn  A, B, C, D, …. , meinetwegen das ganze Alphabet hinunter gefragt wird.

Was machen wir nun?  Wir greifen in die Kiste  XOR – Trick und da   geht es  wie folgt:

Wenn ich einen bestimmten Wert z. B.  ein D  aus einer Folge heraus profilieren will, dann gilt:

XOR – Trick =   A XOR B  XOR  C  XOR D    XOR    ( A XOR B  XOR  C) =  D .

Bis auf D sind alle doppelt also eliminierbar. Das fehlende D (the missing D) in der anfragenden  Liste in der Klammer  rechts  führt dazu,  dass das D in der befragten Liste herausprofiliert wird. Das ist genau das, was wir wünschen. Das Problem nennt man auch „One out of many“.

XOR  war ein Stolperstein in der KI – Entwicklung .  Das XOR  ist halt  eine zusammengesetzte,  eine komplexe Verbindung. Die  beim XOR benutzten Verbindungs-Teile  „Und“ ∧, „Oder“ ∨, „Nicht“ ¬ sind  hingegen elementar.

 

1.1) XOR und Variantenstücklisten

Noch bedeutender wird das Entweder – Oder, das XOR, wenn wir an Variantenstücklisten z.B. im  Automobilbau denken. Es  werden Stücklisten (bill of material) oder Teileverzeichnisse (part lists) für Milliarden unterschiedlicher Exemplare eines Autotyps erzeugt und verwaltet.  Es stehen  z.B. Fragen zur Debatte, ob entweder  ein Auto mit  80 PS oder mit  120 PS  ausgewählt werden soll. Um eine Auto wunschgemäß zu konfigurieren, muss eine große Vielzahl, sagen wir Hunderte solcher XOR- Situationen abgeklärt werden. Wir lieben heute große Zahlen. In der Literatur wird in der Autobus-Produktion von  über  10100 Varianten berichtet. Diese „unmenschlich“, riesige Zahl kommt durch Kombination  zustande, wenn wir 100 XOR’s  mit jeweils 10 Variationsmöglichkeiten pro XOR in einer Stückliste annehmen, dann führt das zu 10100 Möglichkeiten. Das ist bei Autobussen offensichtlich der Fall ist.  Da wir Nebenbedingungen berücksichtigen müssen, weil einige Kombinationen technisch nicht gehen, ist die wirkliche Zahl der Kombinationen kleiner.

Abb. 1 zeigt eine  Variantenstückliste  für leider nur vier Varianten. Die Pfeile  zwischen den Knoten  bedeuten  „geht- ein- in“ und dann  mit der angefügten  Zahl.

Abb. 1:  Eine Variantenstückliste

Man muss sich den Zusammenbau der Teile von unten, den Einzelteilen, über Baugruppen nach  oben, den Fertigteilen vorstellen.

Man unterscheidet grundsätzlich zwischen Muss- und Kann-Varianten. In Kann-Varianten, die  im Abb. 1   über das  XOR 2 erzeugt werden, gibt es ein Leerteil als die Darstellung von „Nichts“  oder „Null“ oder „heiße Luft“ mit dem Sonderzeichen  Λ. K in Abb. 1 ist ein Knoten für ein zusammengebautes Teil. Man nennt den Knoten  auch Konjunktionsknoten ∧. Abb. 1 zeigt wissenschaftlich gesprochen  auch eine mereologische Struktur (vom Griechischen μεροζ = Teil). Mereologie ist die Lehre von  Teil-Ganze Relationen.

Die 22  =  4 Varianten im Bild (zwei Muss- und zwei Kann-Varianten) sind leicht  zu erkennen:

r, g, v,  f        r, g, v, Λ    r, g, z, f       r, g, z, Λ

r und g werden Gleichteile genannt, weil sie in allen Varianten vorkommen.

Würden wir in Abb.1  beliebig viele  und nicht bloß zwei Eingänge annehmen,  müssten wir statt XOR  den oben behandelten XOR – Trick eintragen.

Wenn wir einen historischen Blick auf die Entwicklung der neuronalen Netze in der KI werfen, dann war  das weite Feld der Stücklisten  lange nicht behandelbar, weil ein XOR  neuronal nicht dargestellt werden konnte. Logisch ist das XOR, sprachlich das Entweder – Oder, kein besonderes Problem. Es ist halt nur einer von 24 = 16 weiteren Junktoren wie die Verbindungsoperation in der klassischen Aussagenlogik genannt werden. XOR fristet in der Logik leider  ein Kümmerdasein, nicht aber in vielen technischen Anwendungen, wie z.B. bei Variantenstücklisten oder in der Schaltwerktechnik oder in der Klassifikation von Begriffen.

1.2) OR und die Klassifikation von Begriffen

Wir tragen eine Klassifikation von Begriffen  an einem Beispiel vor, das von Smith/Smith  veröffentlicht wurde. (J.M. Smith / D.C.P. Smith:“ Database Abstractions, Aggregation and Generalization“, ACM Transaction on Database Systems, Vol.2. No.1, June 1977) .

Bei Smith/ Smith  ist „Fahrzeuge“  der zu klassifizierende Begriff.

Abb. 2:   Tabelle der Gesamtklasse „Fahrzeuge“

Abb. 3:  Motor-Fahrzeuge und Luft-Fahrzeuge als Unterklasse

Die mit einem Pfeil versehenen Spalten heißen Klassifikatoren. „Medium“ und „Antrieb“ sind demnach Klassifikatoren. Die Menge {Land-Fz, Luft-Fz, Wasser-Fz} ist eine Klassifikation nach dem Klassifikator „Medium“. Die Elemente einer Menge heißen Klassifikations-Merkmale. Land-Fz ist z.B. ein Klassifikations-Merkmal.

Es gibt Vorschriften für die Klassifikations- Merkmale. Sie müssen disjunkt oder getrennt (elementfremd) sein  Wir waren im Frühjahr 1945 noch im Kriege überrascht, als die Amerikaner mit sogenannten Amphibien-Fahrzeugen den Rhein leicht überquerten. Das waren  Fahrzeuge, die sowohl auf Land wie auch im Wasser operieren können. Brücken über den Rhein  brauchten die Amis nicht, sie fuhren einfach rüber. Am leichtesten wird das Problem der nicht disjunkten Klassifikationsmerkmale dadurch gelöst, indem man ein separates Merkmal einführt, in unserem Falle „ Amphibien-Fz“.

Wenn beide Klassifikationen nach „Medium“ und „Antrieb“ parallel vorgenommen  werden sollen, spricht man von einer Parallel-Klassifikation. Im Gegensatz dazu steht die hintereinander geschaltete Klassifikation, z.B. erst nach dem Klassifikator „Medium“ und dann nach dem Klassifikator „ Antrieb“.

Abb. 4:   Die Klassifikation

Die disjunkten Mengen der Klassifikatoren  „Antrieb, „ Medium“, „Motor“ und „Lifting“ interessieren uns im Rahmen einer XOR- Untersuchung und ihren Anwendungen. Natürlich gelten   in unserer Abkürzung folgende  Auswahlen  unter den Klassifikations – Merkmalen:

Antrieb:   Wind  XOR  Motor XOR  Mensch

Medium:   Land  XOR  Luft  XOR  Wasser

Motor:   Rotary  XOR  Düsen  XOR  Raketen

Lifting:  plane  XOR  heliocopter

Jetzt haben wir es wieder: Das Auswahlproblem wie bei den Variantenstücklisten, und das XOR ist wieder eine logische Grundoperation.