TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Übungen SS12/Blatt 1 - Beispiel 2

Give a semantic proof for the contradiction theorem:

$W\cup {\phi }$ is unsatisfiable iff $W\models \neg \phi$

Lösungsvorschlag

Angenommen W |= phi, dann gilt Mod(W) ist eine Teilmenge von Mod(phi).

Angenommen W + {not phi} haette ein Modell. 
Dann muesste auch phi geschnitten {not phi} ein Modell haben (da ja Mod(W) eine Teilmenge von Mod(phi) ist). 
Da aber sicherlich Mod(phi) geschnitten Mod(not phi) = emptyset ist, kann W + {not phi} kein Modell haben, dh. es ist unerfuellbar.

Der Lösungsansatz ist, wie wir gestern im Forum schon kurz angeschnitten haben, glaub ich nicht richtig, weil für einen Indirekten Beweis $W\models \phi$ keine gegenteilige Annahme von $W\models \neg \phi$ ist. --thomas 13:39, 18. Apr. 2012 (CEST)

Links

• f.thread:92960
• Zwei verschiedene Lösungsansätze: http://cs-wwwarchiv.cs.unibas.ch/lehre/fs10/cs205/uebungen/loesung8.pdf