Notation, Tautologie(?) < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| 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.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:49 Sa 16.04.2016 | | Autor: | hippias |
Es ist genau so wie Du sagst.
|
|
|
| |
|
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]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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]
|
|
|
| |
|
> 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]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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]](/images/smileys/ok.gif "[ok]")
Viele Grüße
Tobias
|
|
|
| |
|
> 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.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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]
|
|
|
| |
|
> 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]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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]
|
|
|
| |
|
Vielen Dank für die Hilfe.
|
|
|
|
