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 Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

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
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAussagenlogikNotation, Tautologie(?)
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
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.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]