Beweisführung der Übung im Skript

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Beweisführung der Übung im Skript

Beitrag von patrix » 19. Aug 2010 20:34

Hallo zusammen,
ich habe ein Problem bei der Beweisführung der Übung 6.8 und 6.10.
Übung 6.8:
Weisen Sie die Korrektheit der modus ponens Regel nach.
(Anmerkung: Sematisch ist es einfach: Wenn ich eine Geleichung habe in der auf beiden seiten eine identische Menge vorhaden ist, so kann man auch beide Mengen etfernen ohne das Ergebnis zu verfälschen. Aber wie zeige ich das Formal???)

Übung 6.10:
Zeigen sie die Korrektheit folgender Doppelnegationsregeln:
Welcher dieser Regeln lassen sich durch direkte Simulation in SK, welche in SK+ (SK mit modus ponens) simulieren, welche auch hier nicht?
(Anmerkung: Ich hätte jetzt gesagt, dass alle durch direkte Simulation in SK zu Beweisen sind?)

Danke und viele Grüße

Patrick

kartzow
Mausschubser
Mausschubser
Beiträge: 55
Registriert: 8. Apr 2010 14:12

Re: Beweisführung der Übung im Skript

Beitrag von kartzow » 23. Aug 2010 08:24

Hallo,

die Korrektheit einer Regel muss man natuerlich mit einem semantischen Beweis zeigen.
Allerdings befuerchte ich aufgrund deiner Anmerkung, dass dir nicht ganz klar ist, wie man eine solche Aussage semantisch beweist.
Insbesondere verstehe ich nicht, wo in einem solchen Beweis Gleichungen auftreten. Und das man Mengen aus Mengengleichungen (?) auf beiden Seiten einfach entfernen kann, ist im allgemeinen auch Quatsch.

Wenn du eine sinnvolle Antwort auf deine Frage haben moechtest, solltest du etwas genauer beschreiben, was du dir zu der Aufgabe bereits ueberlegt hast.

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Re: Beweisführung der Übung im Skript

Beitrag von patrix » 25. Aug 2010 23:54

Hallo nochmal,
Bei Übung 6.8 wäre meine Argumentation die Folgende:
Weisen Sie die Korrektheit der modus ponens Regel nach.
angenommen es gibt die zwei folgenden Sequenzen:
\(\Gamma\vdash\varphi\) und \(\Gamma\!\,'\!\,,\varphi\vdash\Delta\)
Dann wäre die Zusammengeführte Sequenz:
\(\Gamma\!\,,\Gamma\!\,'\!\,,\varphi\vdash\varphi\!\,,\Delta\)
Nun bekommt man durch die Ableitungsregel \(\left(\neg L\right)\) folgende Formel:
\(\Gamma\!\,,\Gamma\!\,'\!\,,\varphi\!\,,\neg\varphi\vdash\Delta\)
Da ja eine Sequenz \(\Gamma\vdash\Delta\) als allgemeingültig gilt, wenn \(\wedge\Gamma\models\vee\Delta\) allgemeingülltig ist kann man also \(\!\,,\varphi\!\,,\neg\varphi\) entfernen ohne unkorrekt in Bezug auf Allgemeingültigkeit zu werden.

Bei Übung 6.10 hätte ich genaus durch Ableitungen argumentier und festgestellt, dass ich nur Akbleitungen in SK benötig.

Vielen Dank schonmal für Deine mühe

Patrick

franzose
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 146
Registriert: 9. Okt 2009 00:08

Re: Beweisführung der Übung im Skript

Beitrag von franzose » 26. Aug 2010 01:40

patrix hat geschrieben:...............
Dann wäre die Zusammengeführte Sequenz:
\(\Gamma\!\,,\Gamma\!\,'\!\,,\varphi\vdash\Delta\!\,,\varphi\)
Nun bekommt man durch die Ableitungsregel \(\left(\neg L\right)\) folgende Formel:
\(\Gamma\!\,,\Gamma\!\,'\!\,,\varphi\!\,,\neg\varphi\vdash\Delta\)
Da ja eine Sequenz \(\Gamma\vdash\Delta\) als allgemeingültig gilt, wenn \(\wedge\Gamma\models\vee\Delta\) allgemeingülltig ist kann man also \(\!\,,\varphi\!\,,\neg\varphi\) entfernen ohne unkorrekt in Bezug auf Allgemeingültigkeit zu werden.
die Argumentation verstehe ich nicht, denn du musst ja alle Teilformeln auf der linken Seite wahr machen, aber \(\!\,\varphi\!\,,\neg\varphi\) kann man doch gar nicht gleichzeitig wahr machen? und was ist die "zusammengeführte Sequenz" gabs da sowas?


zu Deiner Frage: ich glaube bei einem semantischen Beweis darf man nicht einfach die Ableitungsregeln anwenden, denn hier hättest du ja nur syntaktisch argumentiert (oder reicht das doch aufgrund der Korrektheit und Vollständigkeit?)

ich hätte einen semantischen Beweis eher so gemacht:

man weiß (Allgemeingültigkeit) dass jede Interpretation die \(\Gamma\) wahr macht immer \(\varphi\) wahr macht und jede Interpretation die \(\Gamma\!\,'\) und \(\varphi\) wahr macht, macht immer \(\Delta\) wahr.

wenn jetzt eine Interpretation \(\Gamma\) und \(\Gamma\!\,'\) wahr macht, dann macht sie auch \(\varphi\) wahr und somit auch \(\Delta\).

kartzow
Mausschubser
Mausschubser
Beiträge: 55
Registriert: 8. Apr 2010 14:12

Re: Beweisführung der Übung im Skript

Beitrag von kartzow » 26. Aug 2010 08:01

Hallo!

Die Argumentation von franzose ist korrekt.

Patrix, du kannst \(\varphi, \neg\varphi\) nicht einfach aus den Vorraussetzungen streichen, damit triffst du eine staerkere Aussage.

Im allgemeinen ist \(a \wedge b \Rightarrow c\) eine schwaechere Aussage als \(a \Rightarrow c\)

In deinem Fall hat \(\Gamma,\varphi,\neg\varphi\) keine Modelle, also ist eine beliebige Sequenz mit dieser linken Seite allgemeiengueltig.
Aber natuerlich sind nicht alle Sequenzen, bei denen links \(\Gamma\) steht allgemeingueltig!

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Re: Beweisführung der Übung im Skript

Beitrag von patrix » 26. Aug 2010 09:57

Ah O.K. jetzt hat es geschnaggelt!

Vielen Dank und Grüße Patrick

Antworten

Zurück zu „Archiv“