Juhuu!!!

Erstmal vielen Dank für die Unterstützung zur Resolution.
Jetzt hab ichs voll geschnallt :-)

Aber nun zum Aufagbenblatt 10 Aufgabe 1:

a) ist eigentlich klar, die Formle ist erfüllbar. Wie prüfe ich allerdings ob sie eine Tautologie ist. Etwa indem ich die gesamte Formel negiere und dann Resolution anwende und wenn ich auf die leere Klauselmenge komme, dann ist es eine Tautologie?

b) ist unerfüllbar richtig?

c) ist die eigentliche Frage.
Nochmal die Klauselmenge:

{(D), (R,-S,-Q), (-D,C), (-Q,S,-I), (-R), (I), (-I,-C,Q,-A)}

Kann man folgendermaßen argumentieren? :

Mit der letzten Menge kann ich nie auf die leere Klausel kommen, da ich nie (A) bekommen werde. also streich ich sie mal dreist.
Das führt aber nun auch dazu, das ich nie ein (Q) haben werde und somit die zweite und vierte Menge auch wegfällt.
Mach ich so weiter, bleibt am Ende nur (D) und (-D,C) über, was ich zu (C) resolvieren kann. Mehr geht nicht, leere Menge gibts nicht, fertig.

Ist das richtig?

Dann bleibt wie in Aufgabe a) nur noch die Frage, wie ich auf Tautologie prüfe.

Bis dann, euer anonymer User.

Zu a) Würde ich mal sagen, habe ich auch so gemacht.

Zu c) Hab ich mir auch schon überlegt, und auch so argumentiert. Bleibt eigentlich "nur noch" die Tautologieprüfung … reicht es da eignetlich, zu begründen, dass man ja nur eine Belegung mit A(R)=1 nehmen muss, somit die Klausel (-R) =0 wird, und somit die ganze Konjunktion (= formel) falsch wird, so dass sie keine Tautologie sein kann?
Oder müssen wir in jedem Fall die KNF bilden und resolvieren? stell ich mir bei der Formel etwas langatmig vor)

Zu a) ich wuerde nicht umbedingt nochmal die Resolution anwenden. Zuerst zeigst du mit Resolution, dass die Formel erfuellbar ist, dann negierst du sie und _dann_ wuerde ich nicht nochmal Resolution anwenden, sondern einfach eine Belegung angeben, die diese negierte Formel wahr macht (damit ist die Formel dann ja kontingent).
Letzteres geht ja sehr schnell, weil du nach der Negation eine Formel hast, die aus mehreren Oder-Verknuepfungen besteht, sobald eine dieser Teilformeln wahr ist, ist das ganze wahr.

b) ja, ist unerfuellbar.

c) Klingt beides gut (bei dem anonymen fehlt noch zu zeigen, dass es keine Tautologie ist). Ich hab's so gemacht, dass ich die Formel erst umgeformt habe, aber das ist so ziemlich das gleiche wie das Weglassen von Klauseln bei euch.
Dann hab' ich die Formeln negiert und eben wieder eine Belegung angegeben, so dass die negierte Formel wahr ist. Damit ist die Formel wieder kontingent. (Das entspricht dem was du gemacht hast, XeXano)

Cheers.

Zu a) ich wuerde nicht umbedingt nochmal die Resolution anwenden. Zuerst zeigst du mit Resolution, dass die Formel erfuellbar ist, dann negierst du sie und _dann_ wuerde ich nicht nochmal Resolution anwenden, sondern einfach eine Belegung angeben, die diese negierte Formel wahr macht (damit ist die Formel dann ja kontingent).
Letzteres geht ja sehr schnell, weil du nach der Negation eine Formel hast, die aus mehreren Oder-Verknuepfungen besteht, sobald eine dieser Teilformeln wahr ist, ist das ganze wahr.

noch schlauer wärs natürlich, einfach eine belegung anzugeben, die die ursprüngliche formel nicht wahr macht ;)



zur begründung von c:

ist zwar nicht formal bewiesen, aber schlüssig, sollte reichen ;)

Stimmt, das ist genauso einfach [img]http://www.fb18.de/gfx/7.gif[/img]
Ich dachte zuerst, erst zu negieren, waere einfacher, aber es ist ja genauso einfach bei der gegebenen Formel aus Und-Verknuepfungen eine Belegung anzugeben, die die Formel falsch macht….