Übungsblatt 1, Aufgabe 2

[wichtel]

Heyho,

Wiedereinmal eine Unsicherheit ob das ausreichend ist - beim Beispiel 2:

Man soll zeigen, dass eine Hinzunahme eines Phi zu einer Wissensbasis ausschließt, dass das Nicht-Phi aus der Wissensbasis abgeleitet werden kann (contradiction theorem).
Eigentlich ist das "logisch" - aber wie schreibt man das formell genau hin? Oder reicht eine informelle Begründung?

Was wir bis jetzt haben: Wir haben ein I gewählt, das sowohl Modell für W als auch Modell für Phi ist; dann zeigen wir, dass W entails (not Phi) nicht gelten kann, weil I ja ein Modell für W ist, aber kein Modell für (not Phi). Stimmt das überhaupt? Wenn I ein Modell für Phi ist, ist I automatisch kein Modell für (not Phi)?

Wer diesen Absatz lesen kann ohne dass sein Hirn durch die fünffache Verneinung zu Matsch wird, dem gratuliere ich herzlich

[/brainfuck]

Liebe Grüße,
Wichtel

[_gerald_]

Mach fuer beide Seiten einen Beweis durch Widerspruch: nimm einfach fuer jede Richtung an, dass die Aussage nicht gilt. Dann kannst du ja per def. von entailment argumentieren, dass du einen Widerspruch bekommst. Und ja, das mit dem not phi stimmt; jedoch wuerd ich mich nicht darauf berufen, weil der Beweis von dem mindestens genau so leicht/schwer ist wie von dem contradiction theorem selbst

[ag01]

Ist das Verwenden vom Deduktions Theorem bei dem Beweis zulässig?
Dann wäre das relativ einfach zu Argumentieren.

[_gerald_]

Zulaessig sicher, aber zu was? Das geht so schon in 3 Zeilen

[wichtel]

Danke! Ich glaub wir haben's jetzt.

[weblexx]

Wir haben ein I gewählt, das sowohl Modell für W als auch Modell für Phi ist; dann zeigen wir, dass W entails (not Phi) nicht gelten kann, weil I ja ein Modell für W ist, aber kein Modell für (not Phi)

hab ich auch so:
W |= phi iff I |= phi for all models I of W
W |= not phi iff I |= not phi for all models I of W
-> das kann ja nur ein widerspruch sein?! reicht das aus?

[_gerald_]

Versteh nicht, warum ihr immer die iff-Ketten habt.

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.

Andere Richtung geht aehnlich.

[Ravu al Hemio]

Ist die leere Menge aber nicht zufällig Teilmenge jeder Menge?

EDIT: Ja, ist aber für den Beweis irrelevant.

[0828834]

kann ich da nicht einfach eine Wahrheitstabelle aufschreiben. Für die Formel W ^ {o} (linke Formel der Angabe) und -W v -O (rechte Formel der Angabe umgeformt) und zeigen, dass bei allen Fällen in denen False für (W^{o}) rauskommt eben True für (-W v -O) rauskommt und umgekehrt. Wäre das genug?

[Ravu al Hemio]

Glaub ich kaum, denn W ist eine Wissensbasis und keine aussagenlogische Formel. Das erschwert eine Aussage des Typs "W ist falsch".

[ManuelM]

Das ist ja der ganze Sinn bei Prädikatenlogik.

[HereBeDragons]

Glaub ich kaum, denn W ist eine Wissensbasis und keine aussagenlogische Formel. Das erschwert eine Aussage des Typs "W ist falsch".

Da muss ich dich korrigieren: das Contradiction Theorem hat mit Wissensbasen nichts zu tun (und selbst, wenns so wäre: Wissensbasen sind aussagenlogische Formeln). Das CT gilt für logische (aus prädikatenlogische) Formeln. Man muss zwar eventuell eine Interpretation, eine Variablenzuweisung und eine Domäne angeben, aber letzten Endes ergibt jede Formel entweder "true" oder "false".

[_gerald_]

Da muss ich dich korrigieren: das Contradiction Theorem hat mit Wissensbasen nichts zu tun (und selbst, wenns so wäre: Wissensbasen sind aussagenlogische Formeln). Das CT gilt für logische (aus prädikatenlogische) Formeln. Man muss zwar eventuell eine Interpretation, eine Variablenzuweisung und eine Domäne angeben, aber letzten Endes ergibt jede Formel entweder "true" oder "false".

Ravu hat schon Recht. Er mit mein Wissensbasis eine Menge von Formeln. Hier in KBS ist Wissensbasis immer synonym fuer eine Menge von Formeln (nur halt die Operationen darauf koennen speziell sein). Das W auf der linken Seite ist auf Metaebene, da kannst nicht einfach eine Wahrheitstafel machen. Zwar gibt es auch fuer Mengen von Formeln den Begriff des Modells, etc., jedoch kannst du hier keine Wahrheitstafel anwenden, da du nicht alle Modelle von W kennst bzw. keine Aussagen darueber machen kannst.

[0828834]

aber W muss doch im Endeffekt immer Wahr oder Falsch sein.... oder was bleibt sonst noch übrig?

[_gerald_]

Sicher muss es wahr oder falsch sein. Aber was kannst du ueber den Zusammenhang von W und phi sagen? Wie aendert sich der Wahrheitswert von W, wenn du ein prop. Atom aenderst? Um die Wahrheitstabelle aufzustellen, muesstest du alle Atome kennen, kennst du aber nicht.

[Free]

Also wenn ich das richtig verstanden habe, um eine Richtung zu beweisen treffe ich eine Annahme auf der rechten Seite die laut dem zu beweisenden Satz falsch ist und zeige dass dann die linke Seite nicht mehr haltbar ist.

Darf ich beliebige Annahmen auf der rechten Seite treffen, also könnte ich sagen "W |= phi" - oder aber: "W nicht-|= nicht-phi" (W nicht-entails nicht-phi) ?

Und gehe ich richtig in der Annahme dass "W vereinigt {phi}" genau dann unsatisfiable ist wenn kein Modell für W existiert das auch ein Modell von phi ist?

[_gerald_]

Einen Beweis einer Aequivalenz kannst du auf verschiedene Arten machen. Die gelaeufigsten sind:

1. Zeige zuerst A -> B, dann B -> A

Wegen (A -> B) && (B -> A <-> A equiv B ist das gerechtfertigt.

2. Zeige zuerst A -> B, dann not A -> not B. Das ist auch wegen einer entsprechenden Aequivalenz gerechtfertigt.

Um eine Implikation A -> B zu zeigen, kannst du einen direkten Beweis machen oder eben einen indirekten.

Und gehe ich richtig in der Annahme dass "W vereinigt {phi}" genau dann unsatisfiable ist wenn kein Modell für W existiert das auch ein Modell von phi ist?

Ja. Das ist die direkte Def. eines Modells einer Formelmenge. Eine Interpretation I einer Menge W von Formeln ist genau dann Modell von W, wenn I ein Modell fuer alle phi in W ist.

[Free]

Einen Beweis einer Aequivalenz kannst du auf verschiedene Arten machen. Die gelaeufigsten sind:

1. Zeige zuerst A -> B, dann B -> A

Wegen (A -> B) && (B -> A <-> A equiv B ist das gerechtfertigt.

2. Zeige zuerst A -> B, dann not A -> not B. Das ist auch wegen einer entsprechenden Aequivalenz gerechtfertigt.

Um eine Implikation A -> B zu zeigen, kannst du einen direkten Beweis machen oder eben einen indirekten.

Vielen Dank für die Antwort!

Das mit der Äquivalenz war mir schon halbwegs klar, zumindest die erste Variante. Nur wie ich eben genau einen direkten oder indirekten Beweis einer Richtung mache nicht. Ich wollte den Beweis zum Deduktionstheorem imitieren, ich hab den jetzt nochmal angeschaut und nehme an dass das so geht:

Um A -> B zu zeigen zeige ich !A -> !B.

Dh. in unserem Fall ich negiere "W |= !phi" und dann "W vereinigt {phi} is unsatisfiable" - nur was heißt die Negation in diesen Fällen? Heißt Negation ich negiere das "Entails" zu "not Entails" oder das "!phi" zu "phi"? Und das unsatisfiable wird zu satisfiable oder aber das {phi} zu {!phi}?

[_gerald_]

Um A -> B zu zeigen, zeigst du !B -> !A

dh. du nimmst das gegenteilige zur Annahme an. Wenn du dann !A herleiten kannst, dann hast du gezeigt, dass wenn nicht B gilt, dann kann auch nur nicht A gelten. Daraus folgt logisch, dass wenn A gilt, muss auch B gelten.

[Free]

Um A -> B zu zeigen, zeigst du !B -> !A

dh. du nimmst das gegenteilige zur Annahme an. Wenn du dann !A herleiten kannst, dann hast du gezeigt, dass wenn nicht B gilt, dann kann auch nur nicht A gelten. Daraus folgt logisch, dass wenn A gilt, muss auch B gelten.

Ja sorry ich hab mich verschrieben, ich meinte natürlich !B -> !A so wie in der Vorlesung gezeigt. Aber ich weiß immer noch nicht was "gegenteilige Annahme" bedeutet. Ich nehme jetzt einfach mal an dass das unsatisfiable zu satisfiable wird und das Entails zu Not Entails. Danke nochmal!

[_gerald_]

Das gegenteilige zur Annahme ist einfach das !A.

Z.B.

is unsat.

!A ist dann, dass eben _nicht_ gilt. Daraus kannst du dann leicht !B herleiten (d.h. W + {not phi} ist sat)

[plan_rich]

Das gegenteilige zur Annahme ist einfach das !A.

Z.B.

is unsat.
!A ist dann, dass eben _nicht_ gilt. Daraus kannst du dann leicht !B herleiten (d.h. W + {not phi} ist sat)

sollte A nicht eher so sein (sehe negation vor phi)?

und B:
is unsat.

Je öfter ich diesen Thread durchlese desto weniger versteh ich das Ganze.
Mir ist klar das !B -> !A zum Beweis verwendet werden kann.

Was mir nicht klar ist:

1. Ist !(C models D) dasselbe wie C does_not_model D?
2. !(W u { phi } is unsat) <==> W u { phi } is sat <==> |= W u { phi }

[_gerald_]

A stimmt schon so, is aber auch wurst. Diesen Beweis kannst du auch direkt fuehren. Da gehen beide sachen.

1. Ist !(C models D) dasselbe wie C does_not_model D?

Das ist keine wohlgeformte Formel. Das ergib keinen Sinn. ! ist Objektsprache, models ist Metasprache. Die zwei darfst ned mixen.

[plan_rich]

Wie negiere ich dann zb [tex]B := W |= \neg \phi[\tex] ? Um mit !B beim Beweis zu beginnen?

[_gerald_]

Du nimmst einfach an es gilt nicht. Du musst kein "Zeichen" fuer deine Negation fuer den Beweis haben. Nimm einfach an, die Aussage gilt nicht.

[plan_rich]

Im Beweis 'Proof of the Deduction Theorem' wird das aber genauso gemacht. Um A iff B zu beweisen schliesse von not B auf not A.

=> Assume |/= phi -> psi ... (|/= soll das durchgestrichene |= sein)

[_gerald_]

Ja, aber das ist nicht das objektsprachen not. Das |/= heisst einfach, dass es _nicht_ gilt. Das kannst du in nat. Sprache genauso hinschreiben. Da brauchst nicht irgendeine Formelsprache.

[Crush]

Versteh nicht, warum ihr immer die iff-Ketten habt.

Angenommen W |= phi, dann gilt Mod(W) ist eine Teilmenge von Mod(phi). Angenommen W + {not phi} haette ein Modell. Dann muesste auch phi + {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.

Andere Richtung geht aehnlich.

Danke für diese Hilfe, hat mir sehr geholfen. Die andere Richtung hätte ich so argumentiert:

Annahme: W + { phi } ist erfüllbar. Also ist Mod(W) geschnitten mit Mod(phi) keine leere Menge.
Angenommen W |= not phi dann wäre Mod(W) eine Teilmenge von Mod(not phi) was zu einem Widerspruch führt da Mod(phi) geschnitten mit Mod(not phi) leer ist.

Passt das so? Hab immer noch das Gefühl dass ich i-wo einen Denkfehler habe.

lg Simon

[testsieger]

//edit - hat sich erledigt

[testsieger]

Gibts eigentlich schon Rückmeldungen aus der Übung?

[0828834]

darf man sich eigentlich bei anderen gruppen in die übung dazu setzen?

[thrau]

darf man sich eigentlich bei anderen gruppen in die übung dazu setzen?

darfst natürlich nicht.

[thrau]

Angenommen W |= phi, dann gilt Mod(W) ist eine Teilmenge von Mod(phi). Angenommen W + {not phi} haette ein Modell. Dann muesste auch phi + {not phi} ein Modell haben (da ja Mod(W) eine Teilmenge von Mod(phi) ist).

Den Schritt versteh ich noch nicht ganz.

Weil unerfüllbar ist, muss für ein Modell existieren (trivial)

und wegen der Annahme, dass muss gelten, okay.

aber wieso folgt daraus, dass ein Modell haben muss?

[_gerald_]

Zeichne dir ein Venn-Diagramm auf. Dann siehst du, dass wenn Mod(W) teilmengevon Mod(phi) und Mod(W) geschnitten Mod(not phi) nicht leer ist, dann muesste auch Mod(phi) geschnitten Mod(not phi) nicht leer sein.

[thrau]

danke! also das venn diagramm wird mir nichts bringen , aber die erklärung ist auf jeden fall so schlüssiger.

und was mich jetzt dank kollegen noch irritiert: "Angenommen W |= phi", das ist ja für einen indirekten beweis nicht die gegenteilige annahme von "W |= not phi"

[_gerald_]

Ja da hast du Recht, das ist nicht die gegenteilige annahme. Tipp: mach fuer die Richtung lefttoright einen direkten Beweis (wie gesagt bei diesem Beweis sind so halbwegs alle Beweisarten gleich "aufwaendig")