Kalkül Modus Ponens < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:58 Sa 15.11.2014 | | Autor: | Steffi88 |
| Aufgabe | Sei K ein Kalkül der Aussagenlogik, der den Modus Ponens
ϕ, ϕ → ψ / ψ Bruch tut irgendwie nicht....
als Regel enthält und in dem (für alle Formeln ϕ und ψ) ¬ϕ → (ϕ → ψ) beweisbar ist.
Zeigen Sie, dass K genau dann widerspruchsfrei ist, wenn es keine Formel ϕ gibt, sodass ϕ
und ¬ϕ beide K-beweisbar sind. |
Hallo zusammen,
die zweite Kalkül frage, auch hier sitze ich davor und verstehe einfach nicht wie man an solch einen Beweis rangehen muss... Vieleicht fällt hierzu auch jemandem was ein :D
Vielen vielen Dank schonmal!!!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:26 Mo 17.11.2014 | | Autor: | Steffi88 |
hm, kennt sich hier keiner damit aus :D schade.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:46 Di 18.11.2014 | | Autor: | tobit09 |
Hallo Steffi88!
> Sei K ein Kalkül der Aussagenlogik, der den Modus Ponens
> ϕ, ϕ → ψ / ψ Bruch tut irgendwie nicht....
> als Regel enthält und in dem (für alle Formeln ϕ und
> ψ) ¬ϕ → (ϕ → ψ) beweisbar ist.
> Zeigen Sie, dass K genau dann widerspruchsfrei ist, wenn
> es keine Formel ϕ gibt, sodass ϕ
> und ¬ϕ beide K-beweisbar sind.
Wie habt ihr denn definiert, wann ein Kalkül der Aussagenlogik widerspruchsfrei heißt?
Zu zeigen ist eine "genau-dann-wenn-Aussage".
Zeige dazu beide Richtungen nacheinander.
Nimm also zunächst (Hin-Richtung) an, dass $K$ widerspruchsfrei ist (Was bedeutet das?).
Zeige dann, dass es keine Formel [mm] $\Phi$ [/mm] gibt, für die sowohl [mm] $\Phi$ [/mm] als auch [mm] $\neg\Phi$ [/mm] $K$-beweisbar sind.
Wahrscheinlich bietet es sich dazu an, einen Beweis durch Widerspruch zu führen, also anzunehmen, dass es eine Formel [mm] $\Phi$ [/mm] gibt, für die sowohl [mm] $\Phi$ [/mm] als auch [mm] $\neg\Phi$ [/mm] $K$-beweisbar sind.
Zu zeigen ist dann ein Widerspruch (zur Annahme $K$ widerspruchsfrei).
Für die Rück-Richtung ist was anzunehmen und was zu zeigen?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:37 Mi 19.11.2014 | | Autor: | Steffi88 |
Hmm... Habe mich versucht, finde aber keinen wirklichen Ansatz... Normalerweise hat man ja Axiome die man anwenden kann, hier hat man ja eigentlich gar nichts...
Hast du vielleicht noch ein Tipp wie man hier anfängt? Weiss gar nicht wie man hier eine Formel definieren würde... :/
sorryyy
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:55 Mi 19.11.2014 | | Autor: | tobit09 |
> Hmm... Habe mich versucht, finde aber keinen wirklichen
> Ansatz...
Ansatz für das Herausfinden der Definition von "widerspruchsfrei":
In deinen Unterlagen nachschlagen.
Ansatz für den Rahmen der Rück-Richtung:
Formuliere zunächst, wie die Rück-Richtung überhaupt lautet.
Formuliere dann, was du bei der Rück-Richtung als gegeben annehmen kannst und was zu zeigen ist.
> Normalerweise hat man ja Axiome die man anwenden
> kann, hier hat man ja eigentlich gar nichts...
Naja, wir wissen vom Kalkül K immerhin, dass alle Formeln der Gestalt
¬ϕ → (ϕ → ψ)
für Formeln [mm] $\phi$ [/mm] und [mm] $\psi$ [/mm] herleitbar sind und das der Kalkül den Modus Ponens enthält.
> Hast du vielleicht noch ein Tipp wie man hier anfängt?
Den würde ich ja gerne geben!
Aber so lange du mir nicht verrätst, wie ihr definiert habe, wann ein Kalkül widerspruchsfrei heißt, weiß ich nicht, was zu zeigen ist.
Also poste bitte eure entsprechende Definition!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:04 Mi 19.11.2014 | | Autor: | Steffi88 |
also in den unterlagen haben wir nur:
DEFINITION. Der Kalkul K is widerspruchsfrei, falls es eine K-Formel ψ mit nicht |- ψ gibt.
Leider verstehe ich den Ansatz gar nicht :/
Danke nochmal für deine Hilfe!!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:09 Mi 19.11.2014 | | Autor: | Steffi88 |
Kannst du damit was anfangen?
Nun müsste man wahrscheinlich einen Widerspruch oder so finden?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:45 Mi 19.11.2014 | | Autor: | tobit09 |
> Kannst du damit was anfangen?
Ja!
> Nun müsste man wahrscheinlich einen Widerspruch oder so
> finden?
Bist du gerade bei der Hin- oder Rück-Richtung?
Ich wiederhole und ergänze das schon von mir Geschriebene:
> Nimm also zunächst (Hin-Richtung) an, dass $ K $ widerspruchsfrei ist (Was bedeutet das?).
Es existiert also eine Formel [mm] $\psi$, [/mm] die nicht $K$-beweisbar ist.
> Zeige dann, dass es keine Formel $ [mm] \phi [/mm] $ gibt, für die sowohl $ [mm] \phi [/mm] $ als
> auch $ [mm] \neg\phi [/mm] $ $ K $-beweisbar sind.
> Wahrscheinlich bietet es sich dazu an, einen Beweis durch Widerspruch zu
> führen, also anzunehmen, dass es eine Formel $ [mm] \phi [/mm] $ gibt, für die sowohl
> $ [mm] \phi [/mm] $ als auch $ [mm] \neg\phi [/mm] $ $ K $-beweisbar sind.
Tun wir dies.
> Zu zeigen ist dann ein Widerspruch (zur Annahme $ K $ widerspruchsfrei).
Genauer gesagt zeigen wir einen Widerspruch zu [mm] $\psi$ [/mm] nicht $K$-beweisbar, d.h. wir zeigen, dass [mm] $\psi$ [/mm] doch $K$-beweisbar ist.
Nochmal zum Mitschreiben:
Wir haben eine Formel [mm] $\psi$, [/mm] die nicht $K$-beweisbar ist und eine Formel [mm] $\phi$, [/mm] für die sowohl [mm] $\phi$ [/mm] als auch [mm] $\neg\phi$ [/mm] $K$-beweisbar sind.
Zu zeigen ist, dass [mm] $\psi$ [/mm] doch $K$-beweisbar ist.
Nach Voraussetzung ist [mm] $\neg\phi\to(\phi\to\psi)$ [/mm] $K$-beweisbar.
Arbeite nun zweimal mit Modus Ponens.
Zur Rück-Richtung:
Es existiere keine Formel [mm] $\phi$, [/mm] für die sowohl [mm] $\phi$ [/mm] als auch [mm] $\neg\phi$ [/mm] $K$-beweisbar sind (d.h. für jede Formel [mm] $\phi$ [/mm] ist eine der Formeln [mm] $\neg\phi$ [/mm] und [mm] $\phi$ [/mm] nicht $K$-beweisbar).
Zu zeigen ist die Widerspruchsfreiheit von $K$, d.h. die Existenz irgendeiner nicht $K$-beweisbaren Formel.
Siehst du, dass hier nicht viel zu tun ist?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:21 Mi 19.11.2014 | | Autor: | tobit09 |
> also in den unterlagen haben wir nur:
>
> DEFINITION. Der Kalkul K is widerspruchsfrei, falls es eine
> K-Formel ψ mit nicht |- ψ gibt.
Danke! 
Ich versuche gleich mal damit, die Aufgabe zu lösen und melde mich dann wieder.
> Leider verstehe ich den Ansatz gar nicht :/
Wenn du etwas von dem von mir Geschriebenen nicht verstehst, solltest du konkret mit Zitat an der Stelle nachfragen, an der es hakt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:32 Mi 19.11.2014 | | Autor: | Steffi88 |
danke für die viele Hilfe, fühle mich schon ganz doof :)
also:
wir haben $ [mm] \neg\phi\to(\phi\to\psi) [/mm] $ gegeben
der MP besagt: ϕ, ϕ → ψ / ψ
Nun setzten wir quasi [mm] \phi [/mm] zu [mm] \neg\phi [/mm] und bekommen für den MP [mm] \neg\phi [/mm] , [mm] \neg\phi \to(\phi\to\psi) [/mm] mit ψ = [mm] (\phi\to\psi)
[/mm]
nun nochmal MP und es steht nur noch [mm] \psi [/mm] ?
Für die Rückrichtung braucht man nun einen Widerspruch, richtig?
[mm] \phi
[/mm]
[mm] \neg \phi
[/mm]
[mm] \phi [/mm] ->( [mm] \neg\phi->(\phi \wedge \neg\phi))
[/mm]
[mm] \neg\phi->(\phi \wedge \neg\phi)
[/mm]
[mm] \phi \wedge \neg \phi
[/mm]
Das wäre zumindest ein Widerspruch :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:51 Do 20.11.2014 | | Autor: | tobit09 |
> wir haben [mm]\neg\phi\to(\phi\to\psi)[/mm] gegeben
> der MP besagt: ϕ, ϕ → ψ / ψ
>
> Nun setzten wir quasi [mm]\phi[/mm] zu [mm]\neg\phi[/mm] und bekommen für
> den MP [mm]\neg\phi[/mm] , [mm]\neg\phi \to(\phi\to\psi)[/mm] mit ψ =
> [mm](\phi\to\psi)[/mm]
> nun nochmal MP und es steht nur noch [mm]\psi[/mm] ?
Deine Idee stimmt!
Ich würde sie so notieren:
Da [mm] $\neg\phi$ [/mm] und [mm] $\neg\phi\to(\phi\to\psi)$ [/mm] $K$-beweisbar sind, ist gemäß MP auch [mm] $\phi\to\psi$ [/mm] $K$-beweisbar.
Zusammen mit der $K$-Beweisbarkeit von [mm] $\phi$ [/mm] liefert eine erneute Anwendung des MP somit die $K$-Beweisbarkeit von [mm] $\psi$.
[/mm]
> Für die Rückrichtung braucht man nun einen Widerspruch,
> richtig?
Nein. Ein Beweis durch Widerspruch ist nicht nötig.
> [mm]\phi[/mm]
> [mm]\neg \phi[/mm]
> [mm]\phi[/mm] ->( [mm]\neg\phi->(\phi \wedge \neg\phi))[/mm]
>
> [mm]\neg\phi->(\phi \wedge \neg\phi)[/mm]
> [mm]\phi \wedge \neg \phi[/mm]
Ich sehe hier eine Ansammlung von Formeln (wobei ich nicht weiß, welche Formel du mit [mm] $\phi$ [/mm] meinst).
Was soll mit diesen Formeln sein?
> Das wäre zumindest ein Widerspruch :)
Was widerspricht wem?
Ich schrieb zur Rück-Richtung:
> Es existiere keine Formel [mm] $\phi$, [/mm] für die sowohl [mm] $\phi$ [/mm] als auch [mm] $\neg\phi$ [/mm] $K$-beweisbar sind (d.h. für jede Formel [mm] $\phi$ [/mm] ist eine der Formeln [mm] $\neg\phi$ [/mm] und [mm] $\phi$ [/mm] nicht $K$-beweisbar).
> Zu zeigen ist die Widerspruchsfreiheit von $K$, d.h. die Existenz irgendeiner nicht $K$-beweisbaren Formel.
Also:
Wir haben, dass für jede Formel [mm] $\phi$ [/mm] (mindestens) eine der Formeln [mm] $\neg\phi$ [/mm] und [mm] $\phi$ [/mm] nicht $K$-beweisbar ist.
Zu zeigen ist, dass irgendeine nicht $K$-beweisbare Formel existiert.
Kommst du damit weiter?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:17 Do 20.11.2014 | | Autor: | Steffi88 |
[mm] \phi [/mm]
[mm] \neg \phi [/mm] (das wäre ja eine Formel mit [mm] \phi [/mm] und [mm] \neg \phi [/mm] )
[mm] \phi [/mm] ->( $ [mm] \neg\phi->(\phi \wedge \neg\phi)) [/mm] $
[mm] \neg\phi->(\phi \wedge \neg\phi) [/mm] (MP)
[mm] \phi \wedge \neg \phi [/mm] (nochmal MP)
die letzte Zeile kann ja nie wahr sein :(
Dachte das wäre nicht schlecht so :D
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:41 Do 20.11.2014 | | Autor: | tobit09 |
> [mm]\phi[/mm]
Ich weiß immer noch nicht, welche Formel du mit [mm] $\phi$ [/mm] meinst und was du von ihr behauptest.
> [mm]\neg \phi[/mm]
> (das wäre ja eine Formel mit [mm]\phi[/mm]
> und [mm]\neg \phi[/mm] )
Welche Formel meinst du jetzt?
> [mm]\phi[/mm] ->( [mm]\neg\phi->(\phi \wedge \neg\phi))[/mm]
Die letztgenannte Formel hat NICHT genau die Gestalt aus der Voraussetzung, falls du darauf hinaus möchtest.
> [mm]\neg\phi->(\phi \wedge \neg\phi)[/mm]
> (MP)
WENN die Formeln [mm]\phi[/mm] ->( [mm]\neg\phi->(\phi \wedge \neg\phi))[/mm] und [mm] $\phi$ [/mm] beide K-beweisbar ist, dann kannst du mit MP auf die $K$-Beweisbarkeit der von dir gerade genannten Formel schließen.
> [mm]\phi \wedge \neg \phi[/mm]
> (nochmal MP)
WENN [mm] $\neg\phi$ [/mm] und [mm]\neg\phi->(\phi \wedge \neg\phi)[/mm] $K$-beweisbar sind, so auch [mm] $\phi\wedge\neg\phi$ [/mm] gemäß MP.
> die letzte Zeile kann ja nie wahr sein :(
Die Formel wird in der Tat unter keiner Belegung der Aussagenvariablen wahr.
(Ob sie $K$-beweisbar sein kann, weiß ich übrigens nicht.)
> Dachte das wäre nicht schlecht so :D
Was hat eine unter keiner Belegung der Aussagenvariablen wahre Formel mit der Rück-Richtung zu tun?
Also warum soll nach deiner Argumentation aus der Nicht-K-Beweisbarkeit von [mm] $\phi$ [/mm] oder [mm] $\neg\phi$ [/mm] für jede Formel [mm] $\phi$ [/mm] die Widerspruchsfreiheit von $K$ folgen?
Ich schrieb zur Rück-Richtung:
> Wir haben, dass für jede Formel $ [mm] \phi [/mm] $ (mindestens) eine der Formeln $ [mm] \neg\phi [/mm] $ und $ [mm] \phi [/mm] $ nicht $ K $-beweisbar ist.
> Zu zeigen ist, dass irgendeine nicht $ K $-beweisbare Formel existiert.
>
> Kommst du damit weiter?
Du brauchst für diese Richtung weder die Voraussetzung, dass $K$ den Modus Ponens als Regel enthält, noch die Voraussetzung, dass alle Formeln der Gestalt ¬ϕ → (ϕ → ψ) für Formeln [mm] $\phi$ [/mm] und [mm] $\psi$ [/mm] $K$-beweisbar sind.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:36 Do 20.11.2014 | | Autor: | Steffi88 |
ohhhhje... ich verstehe es irgendwie nicht... ich soll einfach irgendeine Formel angeben die nicht K-beweisbar ist? :/
K-Beweisbar ist doch immer anders, je nach Kalkül? Also brauche ich in dem Fall eine Formel die mit MP nicht beweisbar ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:02 Do 20.11.2014 | | Autor: | tobit09 |
> ohhhhje... ich verstehe es irgendwie nicht... ich soll
> einfach irgendeine Formel angeben die nicht K-beweisbar
> ist? :/
Guter Ansatz, um die Existenz einer nicht K-beweisbaren Formel zu beweisen!
Die gesuchte Formel wird aber u.a. von K abhängen.
> K-Beweisbar ist doch immer anders, je nach Kalkül?
So ist es.
> Also
> brauche ich in dem Fall eine Formel die mit MP nicht
> beweisbar ist?
Du brauchst eine Formel, die nicht nur mit MP nicht beweisbar, sondern mit dem ganzen Kalkül $K$ nicht beweisbar ist.
Das Gute ist, dass wir bei der Rück-Richtung ja auch etwas als gegeben hinnehmen dürfen:
> Wir haben, dass für jede Formel $ [mm] \phi [/mm] $ (mindestens) eine der Formeln $ [mm] \neg\phi [/mm] $ und $ [mm] \phi [/mm] $ nicht $ K $-beweisbar ist.
Das sieht doch schon sehr so aus, als gäbe es ganz viele nicht-$K$-beweisbare Formeln, oder?
Dieses Verständnis finde ich wichtiger als den nun folgenden formalen Beweis.
(Mit A meine ich eine Aussagenvariable. Wenn ihr andere Buchstaben dafür verwendet, ersetze A entsprechend!)
Sei [mm] $\phi:=A$ [/mm] die durch die Aussagenvariable $A$ gegebene Formel.
(Diese Wahl ist völlig willkürlich. Ich hätte genauso gut jede andere Formel wählen können.)
Nach Annahme bei der Rück-Richtung ist [mm] $\phi$ [/mm] oder [mm] $\neg\phi$ [/mm] nicht $K$-beweisbar.
1. Fall: [mm] $\phi$ [/mm] ist nicht $K$-beweisbar.
Dann haben wir mit [mm] $\phi$ [/mm] eine nicht $K$-beweisbare Formel gefunden.
Also ist $K$ widerspruchsfrei.
2. Fall: [mm] $\neg\phi$ [/mm] ist nicht $K$-beweisbar.
Dann haben wir mit [mm] $\neg\phi$ [/mm] eine nicht $K$-beweisbare Formel gefunden.
Also ist $K$ widerspruchsfrei.
Somit ist $K$ in allen Fällen wie gewünscht widerspruchsfrei.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:02 Do 20.11.2014 | | Autor: | Steffi88 |
öhhh, da habe ich mal viel zu kompliziert gedacht... Ich habe versucht gleichungen aufzustellen die nicht wahr werden können... :/
aber der eine Satz den du so oft geschriben hast
>
> Das Gute ist, dass wir bei der Rück-Richtung ja auch etwas
> als gegeben hinnehmen dürfen:
>
> > Wir haben, dass für jede Formel [mm]\phi[/mm] (mindestens) eine der
> Formeln [mm]\neg\phi[/mm] und [mm]\phi[/mm] nicht [mm]K [/mm]-beweisbar ist.
> Das sieht doch schon sehr so aus, als gäbe es ganz viele
> nicht-[mm]K[/mm]-beweisbare Formeln, oder?
>
> Dieses Verständnis finde ich wichtiger als den nun
> folgenden formalen Beweis.
>
das macht nun auf einmal soviel Sinn :D Habe echt total an der Lösung vorbei gedacht, das hätte ich glaube ich nicht herausbekommen.
Vielen vielen Dank für deine ganze Geduld die du mit mir hattest!!! Mir hat es wirklich viel geholfen, vorallem vom Verständniss!
|
|
|
|
