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
StartseiteMatheForenAussagenlogikNotation, Tautologie(?)
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Aussagenlogik" - Notation, Tautologie(?)
Notation, Tautologie(?) < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Notation, Tautologie(?): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:01 Fr 15.04.2016
Autor: impliziteFunktion

Aufgabe
Zeigen Sie:

Seien [mm] $\varphi,\psi$ [/mm] beliebige Formeln (der Sprache der Aussagenlogik). Dann gilt

[mm] $\varphi\vDash\psi$ [/mm] gdw. [mm] $\vDash \varphi\to\psi$ [/mm]

Hallo,

ich habe eine Frage zu der Notation [mm] $\vDash\varphi\to\psi$. [/mm]

Dabei meint [mm] $\varphi\vDash\psi$, [/mm] dass [mm] $\psi$ [/mm] logisch aus [mm] $\varphi$ [/mm] folgt.

Leider wird jedoch die Notation [mm] $\vDash\varphi\to\psi$ [/mm] im Skript nicht erklärt.

Ist damit vielleicht gemeint, dass [mm] $\varphi\vDash\psi$ [/mm] gdw.  [mm] $\emptyset\vDash\varphi\to\psi$, [/mm] also letzteres eine Tautologie ist?

Vielleicht weiß jemand von euch eine Antwort.
Vielen Dank im voraus.

        
Bezug
Notation, Tautologie(?): Antwort
Status: (Antwort) fertig Status 
Datum: 09:49 Sa 16.04.2016
Autor: hippias

Es ist genau so wie Du sagst.

Bezug
                
Bezug
Notation, Tautologie(?): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:47 Sa 16.04.2016
Autor: impliziteFunktion

Danke für die Bestätigung.

Ich hätte dann noch eine Frage zu der Aufgabe an sich.
[mm] $\phi$ [/mm] und [mm] $\psi$ [/mm] sind beliebige Formeln.

Es ist also wohl ein Beweis mittels Induktion über den Formelaufbau.

[mm] $\phi$ [/mm] kann ja die "Formen":

[mm] $A_0$, ($\neg A_0$), (A_0\wedge A_1), (A_0\vee A_1), (A_0\leftrightarrow A_1), (A_0\to A_1)$ Und $\psi$ genau so. Für die Richtung "$\Rightarrow$" müsste ich dann alle Möglichkeiten durchgehen, also $A_0\vDash A_3$ $\neg A_0\vDash A_3$ $(A_0\wedge A_1)\vDash A_3$ $(A_0\vee A_1)\vDash A_3$ $(A_0\leftrightarrow A_1)\vDash A_3$ $(A_0\to A_1)\vDash A_3$ und jeweils gucken ob dann $\phi\to\psi$ eine Tautologie ist. Bei der "$\Leftarrow$"-Richtung sollten jedoch die meisten Fälle einfach raus fallen. Aber das ist hier doch sicherlich nicht von Nöten? [/mm]

Bezug
                        
Bezug
Notation, Tautologie(?): Antwort
Status: (Antwort) fertig Status 
Datum: 17:51 Sa 16.04.2016
Autor: hippias

Eine Induktion über de Formelaufbau ist nicht notwendig. Die Behauptung ergubt sich direkt aus der Definition der Relation [mm] $\models$. [/mm]

Bezug
                                
Bezug
Notation, Tautologie(?): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:44 Sa 16.04.2016
Autor: impliziteFunktion


> Die Behauptung ergubt sich direkt aus der Definition der Relation $ [mm] \models [/mm] $.

Ok, das sehe ich ein.

Mir scheint aber noch irgendetwas unklar zu sein. Denn folgendes verstehe ich nicht:

Wenn ich eine Tautologie habe, dann ist diese unabhängig von der Belegung der Aussagenvariablen wahr.

Es ist etwa die Formel [mm] $(((A_0\leftrightarrow A_1)\vee A_0)\vee A_1)$ eine Tautologie. Die Wahrheitstafel sieht so aus: \begin{tabular}{c c c c c} A_0 & A_1 & A_0\leftrightarrow A_1 &(A_0\leftrightarrow A_1)\vee A_0&(((A_0\leftrightarrow A_1)\vee A_0)\vee A_1) \\ w&w&w&w&w\\ w&f&f&w&w\\ f&w&f&f&w\\ f&f&w&w&w \end{tabular} Die Belegungen sind also "egal". Aber wenn ich aus $\varphi\models\psi$ folgern soll, dass $\models\varphi\to\psi$ gilt, dann muss ich doch auch zeigen, dass die jeweilige Belegung egal ist und am Ende $\varphi\to\psi$ immer wahr wird. Aber $\varphi\models\psi$ gilt doch nur dann, wenn $\psi$ und $\varphi$ unter der Belegung schon wahr waren und ist nicht unabhängig davon, oder verstehe ich hier etwas falsch? [/mm]

Bezug
                                        
Bezug
Notation, Tautologie(?): Antwort
Status: (Antwort) fertig Status 
Datum: 19:10 Sa 16.04.2016
Autor: tobit09

Hallo impliziteFunktion!


> > Die Behauptung ergubt sich direkt aus der Definition der
> Relation [mm]\models [/mm].
>  
> Ok, das sehe ich ein.

Aus meiner Sicht sollte näher ausgeführt werden, WIE die Behauptung aus der Definition der Relation [mm] $\models$ [/mm] folgt.


> Mir scheint aber noch irgendetwas unklar zu sein. Denn
> folgendes verstehe ich nicht:
>  
> Wenn ich eine Tautologie habe, dann ist diese unabhängig
> von der Belegung der Aussagenvariablen wahr.

Ja.

  

> Es ist etwa die Formel [mm](((A_0\leftrightarrow A_1)\vee A_0)\vee A_1)[/mm]
> eine Tautologie.
>  
> Die Wahrheitstafel sieht so aus:
>  
> [mm]\begin{tabular}{c c c c c} A_0 & A_1 & A_0\leftrightarrow A_1 &(A_0\leftrightarrow A_1)\vee A_0&(((A_0\leftrightarrow A_1)\vee A_0)\vee A_1) \\ w&w&w&w&w\\ w&f&f&w&w\\ f&w&f&f&w\\ f&f&w&w&w \end{tabular}[/mm]
>  
> Die Belegungen sind also "egal".
>  
> Aber wenn ich aus [mm]\varphi\models\psi[/mm] folgern soll, dass
> [mm]\models\varphi\to\psi[/mm] gilt, dann muss ich doch auch zeigen,
> dass die jeweilige Belegung egal ist und am Ende
> [mm]\varphi\to\psi[/mm] immer wahr wird.

Ja, zu zeigen ist in dieser Richtung, dass [mm] $\varphi\to\psi$ [/mm] unter jeder Belegung den Wahrheitswert "wahr" erhält.

Sei dazu [mm] $\beta$ [/mm] eine beliebig vorgegebene Belegung.
Unterscheide nun die Fälle [mm] "$\varphi$ [/mm] unter [mm] $\beta$ [/mm] wahr" und [mm] "$\varphi$ [/mm] unter [mm] $\beta$ [/mm] falsch".
Im erstgenannten Fall kannst du die Voraussetzung [mm] $\varphi\models\psi$ [/mm] ins Spiel bringen.


> Aber [mm]\varphi\models\psi[/mm] gilt doch nur dann, wenn [mm]\psi[/mm] und
> [mm]\varphi[/mm] unter der Belegung schon wahr waren und ist nicht
> unabhängig davon, oder verstehe ich hier etwas falsch?

Was meinst du hier mit "DER" Belegung?

Aber in der Tat macht [mm] $\varphi\models\psi$ [/mm] per Definition von [mm] $\models$ [/mm] eine Aussage (nur) über solche Belegungen, unter denen [mm] $\varphi$ [/mm] wahr ist.


Fazit: Ich finde, du hast die kritischste Stelle im Beweis gefunden und zurecht eingehakt. [ok]


Viele Grüße
Tobias

Bezug
                                                
Bezug
Notation, Tautologie(?): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:35 Sa 16.04.2016
Autor: impliziteFunktion


> Sei dazu $ [mm] \beta [/mm] $ eine beliebig vorgegebene Belegung.
> Unterscheide nun die Fälle "$ [mm] \varphi [/mm] $ unter $ [mm] \beta [/mm] $ wahr" und "$ [mm] \varphi [/mm] $ unter $ [mm] \beta [/mm] $ falsch".
> Im erstgenannten Fall kannst du die Voraussetzung $ [mm] \varphi\models\psi [/mm] $ ins Spiel bringen.

Sei [mm] $\beta$ [/mm] also eine beliebige Belegung.

1. Fall: Sei [mm] $\beta(\varphi)=w$, [/mm] da [mm] $\varphi\models\psi [/mm] ist [mm] \beta(\psi)=w, [/mm] wenn [mm] \beta(\varphi)=w. [/mm]

Es ist aber [mm] $\beta(\varphi)=w$ [/mm] angenommen, also gilt auch [mm] $\beta(\psi)=w$. [/mm]

(Irgendwie komisch formuliert, falls es richtig ist...)

2. Fall: Sei [mm] $\beta(\varphi)=f$, [/mm] dann gilt [mm] $\beta(\psi)=w$, [/mm] weil man aus einer falschen Annahme alles folgern kann und [mm] $\varphi\models\psi$ [/mm] gilt.



Bezug
                                                        
Bezug
Notation, Tautologie(?): Antwort
Status: (Antwort) fertig Status 
Datum: 19:54 Sa 16.04.2016
Autor: tobit09


> > Sei dazu [mm]\beta[/mm] eine beliebig vorgegebene Belegung.
> > Unterscheide nun die Fälle "[mm] \varphi[/mm] unter [mm]\beta[/mm] wahr" und
> "[mm] \varphi[/mm] unter [mm]\beta[/mm] falsch".
> > Im erstgenannten Fall kannst du die Voraussetzung
> [mm]\varphi\models\psi[/mm] ins Spiel bringen.
>  
> Sei [mm]\beta[/mm] also eine beliebige Belegung.

Zeigen wollen wir: [mm] $\beta(\varphi\to\psi)=w$. [/mm]


Wie habt ihr [mm] $\beta(\varphi\to\psi)$ [/mm] definiert?


> 1. Fall: Sei [mm]$\beta(\varphi)=w$,[/mm] da [mm]$\varphi\models\psi[/mm] ist
> [mm]\beta(\psi)=w,[/mm] wenn [mm]\beta(\varphi)=w.[/mm]
>  
> Es ist aber [mm]\beta(\varphi)=w[/mm] angenommen, also gilt auch
> [mm]\beta(\psi)=w[/mm].

Ja.


> (Irgendwie komisch formuliert, falls es richtig ist...)

Das stimmt. Ich würde dies so formulieren:

1. Fall: [mm]\beta(\varphi)=w[/mm].
Dann gilt wegen [mm] $\varphi\models\psi$ [/mm] auch [mm] $\beta(\psi)=w$. [/mm]


Der letzte Schritt im 1. Fall fehlt noch:
Wegen [mm] $\beta(\psi)=w$ [/mm] gilt auch [mm] $\beta(\varphi\to\psi)=w$. [/mm]


> 2. Fall: Sei [mm]\beta(\varphi)=f[/mm], dann gilt [mm]\beta(\psi)=w[/mm],

Nein, [mm] $\beta(\psi)=w$ [/mm] muss nicht gelten.


> weil man aus einer falschen Annahme alles folgern kann und
> [mm]\varphi\models\psi[/mm] gilt.

Wenn du in einer Situation sowohl eine Aussage als auch ihr Gegenteil beweisen kannst, kannst du in dieser (widersprüchlichen) Situation alles folgern.
Eine solche Konstellation liegt hier jedoch nicht vor.
(Aus [mm] $\beta(\varphi)=f$ [/mm] kannst du nicht alles folgern. Dazu bräuchtest du zusätzlich die Annahme [mm] $\beta(\varphi)=w$.) [/mm]


2. Fall: [mm] $\beta(\varphi)=f$. [/mm]
Dann folgt direkt (ohne Verwendung von [mm] $\varphi\models\psi$) [/mm] wie gewünscht [mm] $\beta(\varphi\to\psi)=w$. [/mm]

Bezug
                                                                
Bezug
Notation, Tautologie(?): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:12 Sa 16.04.2016
Autor: impliziteFunktion


> Wie habt ihr $ [mm] \beta(\varphi\to\psi) [/mm] $ definiert?

[mm] $\beta(\varphi\to\psi)=f$ [/mm] gdw. [mm] $\beta(\varphi)=w$ [/mm] und [mm] $\beta(\psi)=f$ [/mm]

[mm] $\beta(\varphi\to\psi)=w$ [/mm] sonst.

Ok, dann folgt der 2. Fall tatsächlich direkt, weil [mm] $\beta(\phi)=f$ [/mm] nach Voraussetzung und dann gilt [mm] $\beta(\varphi\to\psi)=w$ [/mm] nach obiger Definition.

Die Rückrichtung müsste dann so funktionieren:

Es gelte [mm] $\models\varphi\to\psi$, [/mm] daher [mm] $\beta(\varphi\to\psi)=w$ [/mm] für alle Belegungen [mm] $\beta$. [/mm]

Dann gilt nicht [mm] $\beta(\varphi)=w$ [/mm] und [mm] $\beta(\psi)=f$. [/mm]
Und somit [mm] $\varphi\models\psi$ [/mm]


Bezug
                                                                        
Bezug
Notation, Tautologie(?): Antwort
Status: (Antwort) fertig Status 
Datum: 20:26 Sa 16.04.2016
Autor: tobit09


> > Wie habt ihr [mm]\beta(\varphi\to\psi)[/mm] definiert?
>
> [mm]\beta(\varphi\to\psi)=f[/mm] gdw. [mm]\beta(\varphi)=w[/mm] und
> [mm]\beta(\psi)=f[/mm]
>  
> [mm]\beta(\varphi\to\psi)=w[/mm] sonst.

Danke.


> Ok, dann folgt der 2. Fall tatsächlich direkt, weil
> [mm]\beta(\phi)=f[/mm] nach Voraussetzung und dann gilt
> [mm]\beta(\varphi\to\psi)=w[/mm] nach obiger Definition.

Ja.


> Die Rückrichtung müsste dann so funktionieren:
>  
> Es gelte [mm]\models\varphi\to\psi[/mm], daher
> [mm]\beta(\varphi\to\psi)=w[/mm] für alle Belegungen [mm]\beta[/mm].

Ja.


> Dann gilt nicht [mm]\beta(\varphi)=w[/mm] und [mm]\beta(\psi)=f[/mm].

(Klarer formuliert:
Für jede Belegung [mm] $\beta$ [/mm] gilt nicht [ [mm] $\beta(\varphi)=w$ [/mm] und [mm] $\beta(\psi)=f$ [/mm] ].)


> Und somit [mm]\varphi\models\psi[/mm]

Denn:
Sei [mm] $\beta$ [/mm] eine Belegung mit [mm] $\beta(\varphi)=w$. [/mm]
Zu zeigen ist [mm] $\beta(\psi)=w$. [/mm]
Anderenfalls wäre [mm] $\beta(\psi)=f$ [/mm] und damit [mm] $\beta(\varphi\to\psi)=f$ [/mm] im Widerspruch zu [mm] $\beta(\varphi\to\psi)=w$ [/mm] (Letzteres wegen [mm] $\models\varphi\to\psi$). [/mm]

Bezug
                                                                                
Bezug
Notation, Tautologie(?): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:35 Sa 16.04.2016
Autor: impliziteFunktion

Vielen Dank für die Hilfe.

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


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