[MaLo] Blatt 4 Aufgabe 2 und 3

[Purzelbaum]

Hallo Leute,

in der Hoffnung dass es noch hilfsbereite Informatiker aus Aachen gibt...
Benötige die Lösung der 2. und 3. Aufgabe des 4. Übungsblattes in MaLo. (Per PN wäre empfehlenswert, sonst meckert gleich wieder der Lehrstuhl rum)

Wenn mir zumindest keiner damit helfen kann, dann eventuell wie bei der 3 b) die Resolutionsmethode für die Sequenz auszusehen hat.
Mir ist die Resolutionsmethode nur für eine Formel in KNF klar. Hier weiß ich nicht wie sie auszusehen hat.

Dankeschön.

[Farmosch]

glaub bei der 3b musst du die linke seite mit der negation der rechten vereinigen, bin mir aber net 100% sicher grade ^^

[MartinL]

Eigentlich gibts hier immer hilfsbereite Informatiker. Es werden nur irgendwie in letzter Zeit nur noch Musterlösungen angefragt und kaum einzelne Fragen gestellt. Musterlösungen haben halt kaum Leute. Fragen beantworten können da n paar mehr Leute.

Da es ja auch nicht mehr um Punkte geht die du sammeln brauchst kann ich auch eigentlich ruhigen Gewissens hier antworten.

Zur 2
a)
Enthält eine Klauselmenge keine Positiven Formeln enthalten alle Klauseln negative Literale. Alles auf 0 setzen erfüllt also Scheinbar die Klauselmenge.

b)
Naja wie normale Resolution nur mit der zusätzlichen oben genannten Regel. Siehe Skript. Man muss auch hier die leere Klausel ableiten können.

c)
Die Operationen die in der P-Resolution sind bilden eine Teilmenge der Operationen der normalen Resolution. Somit folgt die Korrektheit aus der Korrektheit der normalen Resolution.

d) weis ich nicht so spontan. Gibts aber ja einen Hinweis für die Vorgehensweise.

Zur 3

Die 3a) soll man (in meinen Augen) so lösen, dass man einfach mal alle möglichen boolschen Kombinationen für die Variablen einsetzt und guckt ob die Sequenz stimmt.
Also ob wenn die Formeln vor dem => erfüllt sind immer mindestens eine der hinteren erfüllt ist.
(i) ist würd ich sagen falsch, (ii) gilt

die b) geht so in der Art wie Farmosch schon sagte. Idee dahinter ist folgende. Die Sequenz ist gültig, wenn es nicht sein kann, dass die beiden Formeln auf der linken Seite wahr sind, die auf der rechten aber falsch ist. Wenn also linke Seite und (nicht rechte Seite) unerfüllbar ist, ist die Sequenz gültig. Du kannst/musst die Formel ja in KNF bringen.

c) kann man mit Fallunterscheidungen machen. Man nimmt einfach mal an die linke Seite unten gilt und zeigt dann mit den Sequenzen oben, dass auch die rechte Seite der Sequenz unten erfüllt wird. Wenn du dazu genauere Fragen hast kannst du das ja auch nochmal separat fragen.

Gruß,

Martin