Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Also, wir haben noch ein paar Tanz für die Leute, die gestern nicht da waren oder eine

Niete gezogen haben. Wir beschäftigen uns im Moment mit Logiken, Logiken als Repräsentationen

der Welt für einen Agenten und zwar solche Repräsentationen, dass man Folgerungen daraus

ziehen kann aus dem Wissen, was repräsentiert ist und dadurch neues Wissen aus altem Wissen

herleiten kann. Dinge, die ich nicht sehe als Agent, vielleicht weil ich nicht hingeguckt

habe, aber die ich erschließen kann aus Wissen, was ich bereits habe. Und in diesem Fall haben

wir eine Logik, die besteht, das ist die Aussagenlogik, die einfachste aller Logiken und wir verwenden

eine Inferenzprozedur, die besonders effizient ist, die Davis Putnam, Logamon und noch wer,

wie hieß er? Mensch, ich kenne ihn persönlich, es ist egal. Loveland, genau. Die möchte

ich nochmal in Erinnerung rufen. Wir werden uns heute im Wesentlichen damit beschäftigen,

wie wir dieser Prozedur, Closelarning beibringen werden, also lernen aus gescheiterten Versuchen,

einfach damit wir nicht alles mehrfach machen müssen. Und die Prozedur ist sehr einfach,

wir fangen an mit einer Klauselmenge, Disjunktion aus Literalen, hier haben wir eine wunderbare

Zweierklausel, da haben wir eine Einerklausel, nochmal eine Zweierklausel und am Anfang

eine Dreierklausel und wir wechseln zwei Prozesse miteinander ab. Der eine ist deterministisch

oder mehr oder weniger deterministisch, das ist das Unit Propagation, da gucken wir uns

die Einerklauseln an, sehen, dass die uns zwingen einen bestimmten Wahrheitswert in

der Belegung zu vergeben, also die einzige Möglichkeit, wie ich R true erfüllen kann,

ist indem ich R true mache. Und das kann man jetzt propagieren, Unit heißt eben Einerklausel,

Propagation heißt propagieren, nämlich wenn ich weiß, dass R wahr wird, dann weiß ich,

dass ich hier wahr falsch kriege und wahr falsch kann ich nie erfüllen, deswegen kann

ich das literal weglassen und mich auf die anderen konzentrieren. Das heißt, ich kann

andererseits, wenn ich R wahr mache, das kommt nur einmal vor, ist egal, dann bleiben mir

diese drei Zweierklauseln übrig, das heißt insbesondere, ich kann Unit Propagation nicht

weitermachen. Sehr häufig ist es so, dass ich durch Unit Propagation neue Units erzeuge

und dann immer das weiter rippeln kann, das habe ich zum Beispiel in diesem hier, ich

habe hier eine Einerklausel S, die kann ich propagieren, dann kriege ich eine Einerklausel

Q, dann propagiere ich weiter, habe eine Einerklausel R, dann kann ich hier nochmal zwei Einerklauseln,

die kann ich miteinander propagieren und kriege die leere Klausel, das hätten wir immer

am liebsten, schwuppsdiwupps, deterministisch, alles einmal durch, hier wissen wir, wir haben

nur einen Ast, der kommt, der läuft in eine leere Klausel, wir wissen, das ganze Biest

ist unerfüllbar. Hier ist es anders, hier hat Unit Propagation aufgehört, weil wir

keine Units mehr haben und jetzt müssen wir etwas anderes machen. Jetzt machen wir Fallunterscheidung,

wir suchen uns eine Variable aus, P in diesem Fall und dann untersuchen wir zwei Fälle,

entweder kann P false werden, dann laufen wir per Unit Propagation auf eine leere Klausel

oder P wird wahr, dann kriegen wir Q false, aber können damit keine leere Klausel erzeugen,

das heißt wir haben hier einen erfüllbaren Ast. Wie im Tablo müssen wir für Unerfüllbarkeit

alle Äste unerfüllbar machen und müssen sozusagen den ganzen Baum hier durchsuchen,

das ist die Basisprozedur, die kann man sehr effizient implementieren und das ist im Moment

die beste Prozedur, die wir haben. Aber man kann ihn natürlich ärgern, das Problem ist

NP-vollständig, das heißt es muss Möglichkeiten geben, die ihn irgendwie eine exponentielle

Suche zu jagen, das haben wir hier mal mit einem ganz konkreten Beispiel gemacht und

da hat man hier alle diese Biester, wir laufen jedes Mal in eine Unerfüllbarkeit, das sind

alles letztlich in Suchtermini Fails, das heißt irgendwann nachdem wir alle 100 Variablen

durchgearbeitet haben, wir haben hier unten zwei hochhundert Blätter, das sieht ein bisschen

weniger aus, ist es aber nicht, und finden dann tatsächlich, müssen dann in den anderen

durchgehen. Und wenn man sich das überlegt und das ist das Zentrum, Zentrale was wir

heute machen wollen ist, man macht immer wieder das Gleiche, zwei hoch 98 mal machen wir diesen

Baum, gucken wir uns zwei hoch 98 mal an, ist eine ganze Menge Arbeit und wir wissen natürlich