Prolog durch eine ansteigende Folge von Versionen, die also mehr und mehr Features mit reinnehmen,

einfach mal hier kurz intuitiv näher bringen. Die tieferen Grundlagen des Ganzen, die kommen dann nächstes Mal.

Also, knappe Überschrift Prolog. Da sind ja auch Aufgaben jetzt auf dem neuesten Zettel zu drauf.

Die Aufgaben laufen insbesondere darauf hinaus, dass man sich in die tatsächliche Benutzung von Prolog einliest.

Da gibt es also ein relativ gut nachzuvollziehendes Tutorial, was also auf den alten GLOLOB-Homepages noch draufsteht.

Da müssen wir uns jetzt mal anstrengen, dass wir es auf den neuen auch verlinken, aber man findet es auf jeden Fall auf den alten,

von einem Herrn Fuchs aus der Schweiz. Das sieht man insbesondere daran, dass die Zuchtverbindungen, die da gesucht werden,

alle irgendwie von Zürich nach Bern und so was laufen. Nichtsdestotrotz kann man das also relativ gut verwenden,

um sich mit der Bedienung seines Systems erst einmal vertraut zu machen.

Hier eben alles erst einmal auf Papier, bzw. auf Tafel. Okay, alles klar. Nun geht es hoffentlich.

Also zum einen die Deklaration logischer Zusammenhänge und zum anderen Anfragen nach deren Konsequenzen.

Ja, und wir gucken uns das an anhand einer Version 0, mit der man wirklich noch nicht allzu viel anfangen kann,

aber vielleicht das Prinzip versteht. Und zwar lebt Version 0 in der Logik, die wir schon kennen,

eben schlicht und einfach in der Aussagenlogik. Dazu zwei Definitionen, oder eine, die wir, also eine Definition,

die zwei Begriffe definiert. Zum einen eine Klausel, das kennen wir ja nun schon, also eine Menge von Literalen,

sagen wir D, ist definiert, wenn, ach so, das können wir jetzt, machen wir gleich in eins,

ist definiert, bzw. zweite Definition eine Zielklausel, wenn, ja, jetzt diese beiden Begriffe hängen einfach nur

am Zählen der positiven Literale in D. Und zwar sagen wir D sei definiert, wenn D genau ein positives Literal enthält.

Und die zweite Definition, die steht jetzt hier in Klammern, kommt jetzt auch die Definition hier,

also der Begriff steht in Klammern, die entsprechende Definition steht in Klammern, also es ist eine Zielklausel,

wenn D kein positives Literal enthält. Das ist jetzt erstmal, ja, also im Prinzip ist das einfach eine Einschränkung

von Aussagenlogik. Wir reden also insgesamt nur über solche Klauseln, die höchstens ein positives Literal enthalten.

Wenn wir jetzt nicht über Logikprogrammierung reden, sondern weiter über Logik, haben diese Tiere auch einen Namen,

die heißen Hornklausel, nach einem Herrn Horn, und zwar gibt es positive Hornklausel, das sind genau die definiten Klauseln,

und es gibt beliebige Hornklauseln, das sind Dinge, die höchstens ein positives Literal enthalten, also entweder

definite Klauseln oder Zielklauseln sind. Warum ist diese Einschränkung auf ein positives Literal nun bedeutsam?

Das merkt man dann, wenn man versucht, Logeleien zu lösen, ein Knots knozelt nicht und dergleichen,

was man halt im Zeitmagazin oder in der Süddeutschen so findet, wenn man das mal nachguckt, die Dinger, die gibt es in leicht und in schwer.

Und das, was diese Dinger nun gerade genau schwer macht, ist, dass es meistens gegeben eine Anzahl Voraussetzungen

zwei Möglichkeiten gibt, die dann folgen können oder noch mehr.

Ja, wie schreibt sich denn eine Klausel? Eine Klausel, wenn wir jetzt mal keine Einschränkungen machen,

also sagen wir mal, das Ding hat die Form nicht a1 bis und so weiter bis nicht aj oder sowas,

und dann kommt hier, das sind die Negativen, und dann kommen hier positive, sagen wir b1 bis bk oder sowas.

Ja, wenn wir dieses Ding jetzt mal in etwas lesbare Schreibweise übersetzen, dann ist das nichts anderes als eine Implikation,

nämlich die Implikation der Konjunktion, andersrum die Implikation der Konjunktion,

nein, Entschuldigung, der Disjunktion a la bj, a la bi haben wir noch als Buchstab über, also i gleich 1 bis k.

Und hier eine Implikation dieses Dings aus der Konjunktion jetzt positiv a la ap, wobei p gleich 1 bis j ist.

So, das ist also eine lesbare Schreibweise dieser Klausel, das heißt, da sehen wir also, wenn eine bestimmte Anzahl Voraussetzungen vorliegt,

von a1 bis aj, dann können wir schließen, eine von mehreren Möglichkeiten b1 bis bk.

So, wenn wir das jetzt hier auf definite Klauseln einschränken, dann können wir nicht eine von mehreren Möglichkeiten schließen, sondern genau eine.

Und wenn wir uns jetzt unser Zeiträtsel wieder vorstellen, dann wissen wir, dass, was weiß ich, wenn das Haus des betreffenden Herrn Roth ist

und auf der linken Straßenseite liegt, er dann gerne Fisch isst oder so was, und wir müssen uns nicht überlegen,

ob es jetzt der Fall ist, dass er gerne Fisch isst oder abends Hockey spielt oder so was, sondern es liegt genau eine Möglichkeit vor.

Damit wird das Schließen eben deutlich einfacher, und es ist genau diese Verzweigung, die eben das Sat-Problem NP-H macht.

Das sieht man daran letztlich, dass das 3-Sat-Problem NP-H ist, und der Grund ist genau, dass das 3-Sat-Problem das hier zulässt.

Was ist das 3-Sat-Problem? Das 3-Sat-Problem ist das Erfüllbarkeitsproblem für konjunktive Normalformen, in denen die Klauseln alle höchstens drei Literale haben.

Höchstens drei ist aber schon schlimm genug. Es gibt folgende Formeln von Klauseln mit drei Literalen, das ist aber dieses hier.

Nicht A und B und C, also ich sage, A und B und C können nicht zusammen auftauchen, das wäre noch in Ordnung, das ist also eine Zielklausel.

Dann gibt es A und B impliziert C, das ist auch harmlos. Was aber nicht mehr harmlos ist, ist dieses hier, A impliziert B oder C.

Letzte Form wäre dann A oder B oder C, das ist noch schlimmer.