Logik

 

Ich wollte zunächst eine kleine Abhandlung über die mathematische Logik schreiben. Eine Abhandlung für die Kinder. Etwas wie "Logik den Kindern erzählt". Heute glaube ich, dass ein illustriertes Buch sie mehr interessieren könnte. Sein Titel: "Das letzte Zeichen". Logik wird oft als schwierig betrachtet, weil zu abstrakt. Es gibt aber zwei Sachen, die Teenager begeistern könnten: Die Magie der Symbole und das Resolutionsprinzip. Natürlich anstelle die traditionellen mathematischen Symbole zu benutzen und Formeln wie P(a, f(b)) zu verwenden, würden Icons ermöglichen, das Lesen zu vereinfachen. Das scheint gut möglich zu sein mit Konstanten-, Variablen-, Funktions-Symbolen und sogar mit Prädikatsymbolen. So könnte man zum Beispiel schreiben: 

      (jeanne, paul )  für den Ausdruck P(a, f(b)).
 

Die Benutzung von Klauseln anstelle von Sätzen würde ermöglichen, das Problem der booleschen Operatoren, der Quantoren und der Gruppensymbole zu lösen. So wäre es nicht mehr notwendig, umständliche Sätze wie x [P(x) [y P(f(x,y))]] zu schreiben.

Klauseln sind sowieso den richtigen Ansatz, um Inferenz und Resolution zu erklären und die langweilige Beschreibung der Skolemisierung zu vermeiden. Ich bin fast davon überzeugt, dass Teenager die Beweistechnik verstehen und die Magie der leeren Klausel entdecken können. Allein die Unifikation könnte eine gewisse Schwierigkeit darstellen. 

Nun das Drehbuch. Ann (14), Alice (13) und Paul (11) sind Freunde. Sie gehen in der gleichen Schulklasse. Ann ist für Mathematik begabt. Alice zieht Kunst vor. Paulfast der Bruder von Ann. Es gibt auch ein alter Magier in der Geschichte, Mr. M. (M. wie Mandrake), der in der Nachbarschaft lebt. Eines Tages erhält Ann eine seltsame Botschaft, mit nur einem Satz:
 

                        ¬☺(x,y)∨¬☀(x,z)∨♡(y,z)

Sie kann nichts damit anfangen und legt sie beiseite. Dann kommen andere, genauso geheimnisvolle Meldungen, wo Ann nur ihr Name und die von Paul und Alice erkennen kann:

                         (Ann, Paul)

                        (Ann, Alice)

 Ohne weiter zu denken, speichert sie die Meldungen im gleichen Ordner. Dann passiert etwas ganz seltsames: bei jeder neuankommender Meldung ändern sich die anderen selbständig. Manche verschwinden komplett. Es ist als ob die Sätze ein eigenes Leben hätten! Es ist zum Fürchten. Da gehen die Freunde zu Mr. M. und bitten sie ihm um Hilfe. Er schreibt einen neuen Satz und sagt ihnen: legen sie ihn mit den anderen und sagen sie mir was geschehen ist. Hier ist der Satz, den er geschrieben hat:

                         ¬♡(Paul, Alice)

Am anderen Tag eröffnen die Freunde den Ordner: alle Meldungen sind verschwunden. Nur noch ein Zeichen bleibt übrig: Der Letzte Zeichen, der wie ein Quadrat aussieht:

                       

 Die Freunde sind ratlos. Sie bitten Mr. M. alles zu erzählen. Mr. M. lächelt und antwortet: ich wusste doch, dass Paul in Alice verliebt war...

Von nun an gehen die Kinder so oft wie möglich Mr. M. besuchen und entdecken so, dass Symbole nicht das gleiche sind wie ihre Interpretation, dass es Universalregeln gibt, mit welchen man Symbole handhaben kann (unabhängig ihrer Interpretationsdomäne) und dass es ein wundervolles Prinzip existiert, das Resolutionsprinzip, mit welchem man einen Satz ausgehend von einer Menge von Axiomen beweisen kann.

Die Symbole und ihre Interpretation 

Betrachten wir zuerst die Konstantensymbole. Sie bezeichnen einzelne Entitäten wie "Paul" oder "1". Sofort am Anfang muss man die Tatsache betonen, dass "Paul" nur ein Symbol ist, für welches man eine Interpretationsdomäne definieren muss. Natürlich kann man das Symbol " mit der Person Paul assoziieren. Aber man könnte auch "Paul" mit einem Hund verknüpfen. Das ist die berühmte Unterscheidung, die Frege zwischen Sinn und Bedeutung macht. Die Person Paul ist die Bedeutung des Wortes, während das Symbol "Paul" dessen Sinn ist. Die Interpretationsdomäne muss auf jedem Fall explizit sein. Sonst jeder von uns hätte das Recht, jedem Symbol eine andere, persönliche Interpretation zu geben. 

Das gleiche gilt für Funktions- und Prädikatsymbole. So kann man Funktionssymbole wie "mutter_von" oder "plus" benutzen, um abstrakte Symbole zu vermeiden. Der Term mutter_von(Paul), projiziert auf das Konstantensymbol "Anna", wird besser verstanden als f(a) projiziert auf b. Aber es muss nochmals wiederholt werden: man darf nicht vergessen, dass wir uns in einer Meta-Welt befinden, die nur die Repräsentation einer realen Welt ist. Der atomer Satz verheiratet(mutter_von(Paul), Robert) ist eine andere Art zu schreiben P(f(a),b), mit einer Interpretation in einer Welt, wo Paul und  Robert sind Personen und die Mutter von Paul mit Robert verheiratet ist. 

Die Quantoren  (für alle) und (es existiert) mit Variablensymbolen ermöglichen allgemeine Aussagen wie:

    x   y (x y)  : alle lieben alle (jeder liebt jeden)

    x   ∃y (x y):  jeder liebt mindestens eine Person

    ∀x [ mensch(x) ⇒ sterblich(x)]   : alle Menschen sind sterblich

Diese Beispiele stammen aus der Interpretationsdomäne der Personen. Ein weiteres Beispiel in der Domäne der Zahlen: 

    x [gerade(x) [y gerade(multiplikation(x,y))]]  : multipliziert man eine gerade Zahl (gerade(x)) mit einer beliebigen Zahl, dann erhält man eine gerade Zahl.

Es wurde bewiesen, dass alle Sätze als Klauseln umgeschrieben werden können, nachdem alle Quantoren eliminiert wurden. 

Zum Beispiel x [ mensch(x) sterblich(x)] kann  ¬mensch(x)  sterblich(x) neu geschrieben werden. Im folgenden werden wir nur Klauseln betrachten.

 
Die leere Klausel

 Betrachten wir zwei Klauseln f1 and f2 , wo f2 die Negierung von f1 ist. In diesem Fall der Inkonsistenz sagt man, dass man die leere Klausel  inferieren kann. Die leere Klausel ist sehr wichtig, denn um zu zeigen, dass eine Aussage wahr ist, besagt das Resolutionsprinzip, dass es genügt zu zeigen, dass die Negierung der Aussage inkonsistent mit der Menge der Annahmen (der Axiome) ist. In anderen Worten: Es genügt zu zeigen, dass man die leere Klausel aus der Menge der Klauseln inferieren kann, die die Axiome und die Negierung der Aussage darstellen.

 
Substitution und Unifikation

Jetzt wird es leider ein wenig formal. 
Eine Substitution s ist eine Assoziation von Variablen mit Termen.

Zum Beispiel s = { x a, y f(z) }.

Die Anwendung einer Substitution s auf eine Klausel f  ( f= a1 a2 ... ak ) , fs, ist die Klausel, die man erhält, wenn jedes Vorkommen einer Variable der Substitution s durch den assoziierten Term ersetzt wird.

Betrachtet man nun zwei atomare Sätze a und b (also auf Terme angewandte Prädikatsymbole), dann sagt man dass a und b unifizierbar sind, wenn es Substitutionen sA und sB gibt, so dass  asA = bsB.

Beispiele:

 P(a,z) ist unifizierbar mit P(z, b) dank der Substitution s:  sA = { z b} und sB = { z a} weil asA = bsB =  P(a,b).

 P(f(x),w) ist unifizierbar mit P(z,z) dank der Substitution sA = { w f(x) } und sB = { z f(x)} weil asA = bsB =  P( f(x) , f(x) ).

 P(f(x),x) ist nicht unifizierbar mit P(z,z).


Inferenzregeln

 Es gibt zwei Inferenzregeln: 

Regel 1 (factoring): sei f die Klausel a1 a2 ... ak . Seien ai und aj zwei Literals, die beide entweder positiv oder negativ sind und s eine  Substitution, so dass ai et aj unifizierbar sind. Dann kann man inferieren (f - aj)s .

Beispiel: aus  P(a, x) P(y, b) Q(x, y, c) kann man P(a, b) Q(b, a, c) inferieren, weil P(a, x) et P(y, b) unifizierbar sind, dank s = { x b , y a }.

Regel 2 (resolution) : Sei f1 die Klausel a1 a2 ... ak und f2 die Klausel b1 b2 ... bm . 

Nehmen wir an, dass  ai = g et bj =  ¬d.  g und d sind Atome und g unifiziert d dank den Substitutionen sA et sB. Dann kann man inferieren ( f1 - ai )sA ∨ ( f2 - bj )sB  .  

Beispiel: Aus f1 = P(a, b) Q( b , c) und f2 = ¬ P (x, y) R(x, y) kann man inferieren  Q ( b , c) R ( a, b), weil P(a, b) et P(x , y) unifizierbar sind, dank s = { x b , y a } .

 

Das Resolutionsprinzip

Um eine Klausel f zu beweisen, ausgehend von einer Menge von Axiomen, die als Klauseln umgeschrieben wurden:    

Schritt 1:  Union G U { ¬ f} realisieren

Schritt 2: Regeln 1 und  2 anwenden, um neue Klauseln zu erzeugen. Wenn am Ende die leere Klausel inferiert wurde, dann ist f beweisbar ausgehend von G. Sonst ist f nicht beweisbar.

 

Logik den Kindern erzählt

Sowas wird Mister M. unseren Freunden erzählen können. Natürlich wird er nicht so formal sein. Aber einige gut ausgewählte Beispiele werden ihm ermöglichen, die wichtigsten Konzepte zu erläutern.

A propos: Du hast bestimmt erraten: Die Symbole ☺, ☀, ♡ entsprechen in unserer Interpretationsdomäne bruder_von, freund_von und verliebt_mit...

 

Frege

 

   Prolog                                                                                                                                                  Impressum