matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAussagenlogiksemantische Korrektheit
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Aussagenlogik" - semantische Korrektheit
semantische Korrektheit < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

semantische Korrektheit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!

        
Bezug
semantische Korrektheit: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
semantische Korrektheit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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]

Bezug
                        
Bezug
semantische Korrektheit: Antwort
Status: (Antwort) fertig Status 
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 []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?

Bezug
                                
Bezug
semantische Korrektheit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.


Bezug
                                        
Bezug
semantische Korrektheit: Antwort
Status: (Antwort) fertig Status 
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]

Bezug
                                                
Bezug
semantische Korrektheit: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!



Bezug
                                                        
Bezug
semantische Korrektheit: Antwort
Status: (Antwort) fertig Status 
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).

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]