semantische Korrektheit < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:45 Do 25.05.2017 | | Autor: | Austinn |
Hallo Zusammen,
Seien ϕ und ψ AL-Formeln und Γ,∆ ⊆ AL endlich. Ich muss semantisch, d.h. indem ich über Interpretationen argumentiere, zeigen, dass die folgende Regel korrekt
ist.
[mm] \bruch{\neg \varphi \vdash \neg \psi}{ \psi \vdash \varphi}
[/mm]
Ich habe Probleme, die Korrektheit dieser Regel zu zeigen. Ich weiß nicht nicht wie man semantisch bzw. über Interpretationen dies beweisen kann.
Kann mir jemand in einfachen Worten erklären, wie das zu beweisen wäre?
Dafür wäre ich sehr dankbar!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:14 Fr 26.05.2017 | | Autor: | tobit09 |
Hallo Austinn!
> Seien ϕ und ψ AL-Formeln und Γ,∆ ⊆ AL endlich. Ich
> muss semantisch, d.h. indem ich über Interpretationen
> argumentiere, zeigen, dass die folgende Regel korrekt
> ist.
> [mm]\bruch{\neg \varphi \vdash \neg \psi}{ \psi \vdash \varphi}[/mm]
>
> Ich habe Probleme, die Korrektheit dieser Regel zu zeigen.
> Ich weiß nicht nicht wie man semantisch bzw. über
> Interpretationen dies beweisen kann.
Ich gehe davon aus, dass du also die semantischen Bedeutungen von [mm] $\psi\vdash\varphi$ [/mm] und [mm] $\neg\varphi\vdash\neg\psi$ [/mm] verwenden sollst.
Was bedeutet z.B. [mm] $\psi\vdash\varphi$ [/mm] semantisch?
(Ich kenne eure genauen Notationen nicht, daher überprüfe kritisch, ob folgendes zu euren Notationen passt und gib gegebenenfalls eure Formulierung der semantischen Bedeutung von [mm] $\psi\vdash\varphi$ [/mm] an.)
Es bedeutet: Alle Belegungen [mm] $\beta$, [/mm] die [mm] $\psi$ [/mm] erfüllen, erfüllen auch [mm] $\varphi$.
[/mm]
Entsprechend bedeutet [mm] $\neg\varphi\vdash\neg\psi$: [/mm] Alle Belegungen [mm] $\beta$, [/mm] die [mm] $\neg\varphi$ [/mm] erfüllen, erfüllen auch [mm] $\neg\psi$.
[/mm]
Um nun die Korrektheit der Regel zu zeigen, nimm an dass [mm] $\neg\varphi\vdash\neg\psi$ [/mm] zutrifft.
Zu zeigen ist, dass dann auch [mm] $\psi\vdash\varphi$ [/mm] zutrifft.
Sei also [mm] $\beta$ [/mm] eine beliebige Belegung, die [mm] $\psi$ [/mm] erfüllt.
Zu zeigen ist, dass [mm] $\beta$ [/mm] auch [mm] $\varphi$ [/mm] erfüllt.
Angenommen, [mm] $\beta$ [/mm] erfüllt nicht die Formel [mm] $\varphi$.
[/mm]
Dann erfüllt [mm] $\beta$ [/mm] die Formel [mm] $\neg\varphi$.
[/mm]
Bringe nun [mm] $\neg\varphi\vdash\neg\psi$ [/mm] ins Spiel, um zum gewünschten Widerspruch zu gelangen!
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:10 So 28.05.2017 | | Autor: | Austinn |
Hallo Tobias,
ich verstehe leider die Intuition dahinter nicht und hoffe, dass du es mir genauer erklären könntest. Und du liegst mit deiner Vermutung richtig. Wir müssen also zeigen: Ist die Sequenz [mm] \neg\varphi\vdash\neg\psi [/mm] allgemeingültig, so auch die Sequenz [mm] \psi\vdash\varphi.
[/mm]
Als Beispiel Beweis für dich zum verstehen habe ich im Bild-Anhang eine Musterlösung zu einer anderen Regel.
Ich freue mich auf deine Antwort.
[Externes Bild http:///picload.org/view/riapaccr/seq.png.html]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:35 So 28.05.2017 | | Autor: | tobit09 |
Gut, dass du die Beispiel-Musterlösung gepostet hast.
In der Tat verwendet ihr ein paar Begriffe anders als ich sie kenne.
Sehe ich es richtig, dass eure Notationen ungefähr zu den Folien unter ![[]](/images/popup.gif) https://www3.mathematik.tu-darmstadt.de/evs/e/23/947/966.html passen, insbesondere zu den dort verlinkten Folien "FGdI2Foliensatz1.pdf" und "FGdI2Foliensatz3.pdf"?
Unter dieser Annahme schreibe meine ursprüngliche Antwort nochmal neu:
Was bedeutet z.B. " $ [mm] \psi\vdash\varphi [/mm] $ ist allgemeingültig"?
Es bedeutet: Für alle Interpretationen [mm] $\mathfrak{I}$ [/mm] mit [mm] $\mathfrak{I}\models\psi [/mm] $ gilt auch $ [mm] \mathfrak{I}\models\varphi [/mm] $.
Entsprechend bedeutet " $ [mm] \neg\varphi\vdash\neg\psi [/mm] $ ist allgemeingültig": Für alle Interpretationen [mm] $\mathfrak{I}$ [/mm] mit [mm] $\mathfrak{I}\models \neg\varphi [/mm] $ gilt auch [mm] $\mathfrak{I}\models \neg\psi [/mm] $.
Um nun die Korrektheit der Regel zu zeigen, nimm an dass $ [mm] \neg\varphi\vdash\neg\psi [/mm] $ allgemeingültig ist.
Zu zeigen ist, dass dann auch $ [mm] \psi\vdash\varphi [/mm] $ allgemeingültig ist.
Sei also $ [mm] \mathfrak{I}$ [/mm] eine beliebige Interpretation, für die [mm] $\mathfrak{I}\models \psi$ [/mm] gilt.
Zu zeigen ist, dass dann auch [mm] $\mathfrak{I}\models\varphi [/mm] $ gilt.
Angenommen NICHT [mm] $\mathfrak{I}\models\varphi$, [/mm] also [mm] $\mathfrak{I}(\varphi)=0$.
[/mm]
Dann gilt [mm] $\mathfrak{I}( \neg\varphi )=1-\mathfrak{I}(\varphi)=1$, [/mm] also [mm] $\mathfrak{I}\models\neg\varphi$. [/mm]
Bringe nun die Allgemeingültigkeit von $ [mm] \neg\varphi\vdash\neg\psi [/mm] $ ins Spiel, um zum gewünschten Widerspruch zu gelangen!
Zu deiner Frage nach der Intuition:
Auf die Intuition wovon bezieht sich deine Frage?
Geht es um einen bestimmten Begriff?
Oder geht es um die Frage, warum ich so vorgehe?
Oder ist ein gewisser Schritt unklar (z.B. warum etwas bestimmtes zu zeigen ist)?
Oder geht es um die Frage, warum eine solche Schlussregel anschaulich plausibel ist?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:47 Mo 29.05.2017 | | Autor: | Austinn |
Hallo Tobias,
vielen Dank für deine Mühen
So ist unsere Notation.
Ich sehe, dass ich auch etwas Hintergrundinformationen.
Was bedeutet : [mm] \neg\varphi\vdash\neg\psi [/mm] ist allgemeingültig. Für alle Interpretationen [mm] \mathfrak{I} [/mm] mit [mm] \mathfrak{I}\models\psi [/mm] gilt auch [mm] \mathfrak{I}\models\varphi. [/mm]
Unter "allgemeingültig" stelle ich mir Wahrheitstabellen vor, wobei jede Zeile w sein muss.
Und was bedeutet deine Annahme: Angenommen NICHT [mm] \mathfrak{I}\models\varphi [/mm] , also [mm] \mathfrak{I}(\varphi)=0. [/mm]
Dann gilt [mm] \mathfrak{I}( \neg\varphi )=1-\mathfrak{I}(\varphi)=1, [/mm] also [mm] \mathfrak{I}\models\neg\varphi. [/mm]
Und auch weiß ich nicht, wie ich die Allgemeingültigkeit von [mm] \neg\varphi\vdash\neg\psi [/mm] ins Spiel, um zum gewünschten Widerspruch zu gelangen.
Danke nochmal.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:46 Di 30.05.2017 | | Autor: | tobit09 |
> So ist unsere Notation.
Gut.
Leider kann ich aus dem Folgenden nicht wirklich herauslesen, was dir genau unklar ist.
> Ich sehe, dass ich auch etwas Hintergrundinformationen.
?
> Was bedeutet : [mm]\neg\varphi\vdash\neg\psi[/mm] ist
> allgemeingültig.
Das habe ich doch in meiner vorherigen Antwort explizit geschrieben.
> Für alle Interpretationen [mm]\mathfrak{I}[/mm]
> mit [mm]\mathfrak{I}\models\psi[/mm] gilt auch
> [mm]\mathfrak{I}\models\varphi.[/mm]
Das ist die Definition von [mm] "$\psi\vdash\varphi$ [/mm] ist allgemeingültig".
Was möchtest du damit aussagen oder fragen?
> Unter "allgemeingültig" stelle ich mir Wahrheitstabellen
> vor, wobei jede Zeile w sein muss.
Die Allgemeingültigkeit einer Formel kannst du dir in der Tat so vorstellen.
Hier geht es aber um etwas anderes:
"Die Sequenz [mm] $\psi\vdash\varphi$ [/mm] ist allgemeingültig" ist eine Sprechweise für die Aussage "Für alle Interpretationen [mm] $\mathfrak{I}$ [/mm] mit [mm] $\mathfrak{I}\models\psi$ [/mm] gilt auch [mm] $\mathfrak{I}\models\varphi$".
[/mm]
Allgemeingültigkeit von Formeln und Allgemeingültigkeit von Sequenzen sind zwei verschiedene Dinge.
> Und was bedeutet deine Annahme: Angenommen NICHT
> [mm]\mathfrak{I}\models\varphi[/mm] , also [mm]\mathfrak{I}(\varphi)=0.[/mm]
> Dann gilt [mm]\mathfrak{I}( \neg\varphi )=1-\mathfrak{I}(\varphi)=1,[/mm]
> also [mm]\mathfrak{I}\models\neg\varphi.[/mm]
Du zitierst hier einen recht großen Abschnitt meines Textes, so dass mir nicht klar ist, was innerhalb dieses Abschnittes unklar für dich ist.
Geht es um die Frage, warum ich die Annahme "nicht [mm] $\mathfrak{I}\models\varphi$" [/mm] ins Spiel bringe?
Oder geht es um die Bedeutung von [mm] $\mathfrak{I}\models\varphi$?
[/mm]
Oder ist an der weiteren von dir zitierten Argumentation etwas unklar? Wenn ja: Was?
> Und auch weiß ich nicht, wie ich die Allgemeingültigkeit
> von [mm]\neg\varphi\vdash\neg\psi[/mm] ins Spiel, um zum
> gewünschten Widerspruch zu gelangen.
Was bedeutet noch einmal die Allgemeingültigkeit der Sequenz [mm] $\neg\varphi\vdash\neg\psi$?
[/mm]
(Das habe ich ja in meiner vorherigen Antwort erläutert.)
Zur Erinnerung: Wir sind in unserem Beweis gerade in der Situation [mm] $\mathfrak{I}\models\neg\varphi$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:39 Di 06.06.2017 | | Autor: | Austinn |
> Allgemeingültigkeit von Formeln und Allgemeingültigkeit von Sequenzen sind zwei verschiedene Dinge.
Was sind denn die Unterschiede bzw. wie unterscheide ich diese beiden von einander?
Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:49 Mi 07.06.2017 | | Autor: | tobit09 |
> > Allgemeingültigkeit von Formeln und Allgemeingültigkeit
> von Sequenzen sind zwei verschiedene Dinge.
>
> Was sind denn die Unterschiede bzw. wie unterscheide ich
> diese beiden von einander?
Wenn du irgendwo die Aussage "die Formel [mm] $\varphi$ [/mm] ist allgemeingültig" oder die Zeichenfolge [mm] \models\varphi [/mm] für eine Formel [mm] $\varphi$ [/mm] siehst, ist die Allgemeingültigkeit der FORMEL [mm] $\varphi$ [/mm] gemeint, d.h. gemeint ist: "Für alle Interpretationen [mm] $\mathfrak{I}$ [/mm] gilt [mm] $\mathfrak{I}\models\varphi$.".
[/mm]
Wenn du irgendwo die Aussage "die Sequenz [mm] $\varphi\vdash\psi$ [/mm] ist allgemeingültig" oder kurz [mm] "$\varphi\vdash\psi$ [/mm] allgemeingültig" siehst, ist die Allgemeingültigkeit der SEQUENZ [mm] $\varphi\vdash\psi$ [/mm] gemeint, d.h. gemeint ist: "Für alle Interpretationen [mm] $\mathfrak{I}$ [/mm] mit [mm] $\mathfrak{I}\models\varphi$ [/mm] gilt auch [mm] $\mathfrak{I}\models\psi$."
[/mm]
Erste Quelle für das Studium der Definitionen sollte deine Vorlesungsmitschrift bzw. dein Skript sein. Das Nachfragen im Matheraum kann dieses Studium nicht ersetzen (aber ergänzen).
|
|
|
|
