Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Beweisen in Aussagenlogik

Beweisen in Aussagenlogik

Universität / Fachhochschule

Sonstiges

Tags: Sonstig

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
sopch

sopch aktiv_icon

18:54 Uhr, 26.10.2017

Antworten
Hallo,

ich habe leider immer Probleme beim formulieren von Beweisen.
Zum Beispiel möchte ich gerne beweisen, dass:

G und H immer genau dann semantisch äquivalent sind, wenn (G⇔H) gültig ist.

Ich darf (G⇔H) als gegeben ansehen oder?
Ja aber dann ist ja klar das G gültig und H gültig ⇒G≡H

Aber das wird ja wohl nicht genügen.
Wenn ich mir die Definitionen von semantische Äquivalenz, semantischen Klassen und Gültigkeit bzw. Tautologie angucke verstehe ich sie, aber wie argumentiere ich z.B. in diesem Zusammenhang.

Mich würden grundsätzliche Tipps wirklich brennend interessieren was das Beweisen und Zeigen anbelangt.

Beste Grüße
sopch

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Online-Nachhilfe in Mathematik
Antwort
tobit

tobit aktiv_icon

20:10 Uhr, 26.10.2017

Antworten
Hallo sopch!


Ich nehme mal an, G und H sollen Formeln der Aussagenlogik sein?

Eine Schwierigkeit dabei, dir gut zu helfen, liegt darin, dass die Notationen und Definitionen nicht ganz einheitlich gehandhabt werden.
Lies deshalb alles Folgende sehr kritisch und passe es an eure Notationen an.
Falls ihr ein öffentlich zugängliches Skript im Internet habt, wäre es toll, wenn du den Link posten könntest, damit ich mich an eure Versionen anpassen kann.

Ich schlage nun nicht den kürzesten und elegantesten, sondern den naheliegendsten Beweis vor.


Zu zeigen ist eine "genau-dann-wenn-Aussage".
Dafür zeigt man üblicherweise beide Richtungen => und <= nacheinander.
(Übliche Strategie für den Nachweis von "genau-dann-wenn-Aussagen".)

Du hast nun mit der Richtung <= begonnen.
Dafür dürfen wir in der Tat annehmen, dass G⇔H gültig ist und müssen zeigen, dass G und H semantisch äquivalent sind.
(Übliche Strategie für den Nachweis von Implikationen, d.h. "wenn-dann-Aussagen".)

Deine Annahme, dass aus "G⇔H gültig" bereits "G und H jeweils gültig" folge, ist falsch.

Nach Definition der semantischen Äquivalenz müssen wir zeigen:
Für alle Belegungen β gilt G[β]=H[β].

Sei also eine Belegung β beliebig vorgegeben.
Zeigen müssen wir G[β]=H[β].
(Übliche Strategie für den Nachweis von "für-alle-Aussagen".)

Nun wenden wir die Definition der Gültigkeit auf die Formel G⇔H an:
Da G⇔H gültig ist, gilt insbesondere für unsere Belegung β die Gleichheit (G⇔H)[β]=w.
(Übliche Strategie für das Ausnutzen von "für-alle-Aussagen".)

Nun gilt nach Definition von (G⇔H)[β] genau dann (G⇔H)[β]=w, wenn G[β]=H[β].

Zusammengenommen haben wir also in der Tat G[β]=H[β] und damit <= gezeigt.


Passt das halbwegs zu euren Notationen und Definitionen?
Wenn nicht und kein Skript zugänglich ist, bitte ich dich, eure entsprechenden Definitionen zu posten.

Sobald dies geklärt ist, kannst du ja mal die Richtung => probieren.


Viele Grüße
Tobias
sopch

sopch aktiv_icon

22:31 Uhr, 26.10.2017

Antworten
Danke dass du dir die Zeit nimmst.

Genau, G und H sollen Formeln der Aussagenlogik sein.
Leider ist das Skript nicht online, aber ich kann deine Notation sehr gut in unsere übertragen.
Anstatt von Belegungen arbeiten wir mit Interpretationen f(G)=f(H).

Ok also zeigen muss ich das:

(G⇔H)⇒G≡H

Dabei ist (G⇔H) gültig gegeben.

Definition einer gültigen semantischen Klasse:

f(G)=w für alle zu G passenden Interpretationen f

In dem Fall: f(G⇔H)=w für alle zu (G⇔H) passenden Interpretationen f

So jetzt könnte ich weiter grübeln wie ich (G⇔H) weiter definiere oder ich gucke mir erstmal
G≡H an.

Definition semantischer Äquivalenz:

f(G)=f(H)

Da ich f(G⇔H)=w gegeben habe, muss auch für f(G) und f(H) gelten dass sie den gleichen Wahrheitswert haben.

⇒f(G)=f(H)

Ich habe deine Hilfestellung studiert und nochmal versucht es in meine eigenen Worte bzw. Gedankenkanäle zu fassen.
Wäre das so dann richtig (was ja keine Kunst ist da ich es ja trotzdem im Grunde von dir abgeschrieben ist)

In die andere Richtung hieße dann:

-(G≡H)⇒-(G⇔H)?
Antwort
tobit

tobit aktiv_icon

22:47 Uhr, 26.10.2017

Antworten
Sieht soweit gut aus!


In der Definition der semantischen Äquivalenz fehlt noch die Angabe "für alle zu G und H passenden Interpretationen f".

Bei deiner Formulierung der anderen Richtung fehlt noch das Wort "gültig" in der hinteren Klammer.


Einfacher ist es, nicht mit Negationen zu arbeiten.

Zeige also für die Richtung =>:
Wenn G und H semantisch äquivalent sind, ist die Formel G⇔H gültig.
sopch

sopch aktiv_icon

23:18 Uhr, 26.10.2017

Antworten
G≡H ist gegeben

Laut Äquivalenzdef. gilt G≡H⇔f(G)=f(H) für jede Interpretation der atomaren Formeln

(G⇔H) ist gültig

Laut Def. der Gültigkeit von sem. Klassen gilt: f(G)=w für alle zu G passenden f
⇒f(G⇔H)=w
⇒ Wenn f(G)=w dann ist auch f(H)=w und wenn f(H)=w dann auch f(G)=w
⇒f(G)=f(H) für jede Interpretation der atom. Formeln
⇒G≡H

So würde ich das dann zeigen.
Hast du vielleicht noch einen Tipp woran ich erkenne, wenn sich eine strukturelle Induktion als Beweismethode anbietet?

Danke für deine Hilfe tobit
Antwort
tobit

tobit aktiv_icon

23:47 Uhr, 26.10.2017

Antworten
" G≡H ist gegeben

Laut Äquivalenzdef. gilt G≡H⇔f(G)=f(H) für jede Interpretation der atomaren Formeln "

Ja.


Zu zeigen:

" (G⇔H) ist gültig "


" Laut Def. der Gültigkeit von sem. Klassen gilt: f(G)=w für alle zu G passenden f "

Das ist die Definition von "G gültig".
Hier geht es um "G⇔H gültig".
Und auch das gilt nicht einfach, sondern das wollen wir bei dieser Richtung zeigen.

" ⇒f(G⇔H)=w "

Warum?

Wenn du dies für alle Interpretationen f der atomaren Formeln zeigst, hast du wie gewünscht die Gültigkeit von G⇔H bewiesen und bist mit dieser Richtung fertig.


" ⇒ Wenn f(G)=w dann ist auch f(H)=w und wenn f(H)=w dann auch f(G)=w
⇒f(G)=f(H) für jede Interpretation der atom. Formeln
⇒G≡H "

Dass G≡H gilt, hast du doch ganz zu Anfang dieser Richtung bereits angenommen.


Irgendwie scheinst du falsch herum argumentiert zu haben.

Bei der Richtung => ist G≡H gegeben und die Gültigkeit von G⇔H zu zeigen.



" Hast du vielleicht noch einen Tipp woran ich erkenne, wenn sich eine strukturelle Induktion als Beweismethode anbietet? "

Strukturelle Induktion eignet sich, um eine Aussage über alle Aussagenlogischen Formeln (oder alle Objekte eines anderen induktiv definierten Begriffes) zu zeigen.

Die hier besprochene Aufgabe war ein Beispiel für eine Aussage über alle Aussagenlogischen Formeln G und H, für die wir keine strukturelle Induktion brauchten.

Man kann zunächst probieren, ob man ohne strukturelle Induktion auskommt; wenn man dann auf eine Stelle stößt, bei der man die Behauptung gerne schon auf eine "Teilformel" anwenden würde, deutet dies darauf hin, dass möglicherweise strukturelle Induktion weiterhelfen könnte.

Letztlich hilft Erfahrung, die man anhand von Beispielaufgaben und Ausprobieren verschiedener Ansätze erhält, vermutlich mehr als allgemeine Erklärungsversuche zu dem Thema.
Antwort
tobit

tobit aktiv_icon

04:52 Uhr, 27.10.2017

Antworten
Dankenswerterweise liegt mir nun das Skript vor.

Den Begriff der Semantischen Klasse benötigen wir bei dieser Aufgabe nicht.

Die Formel (G↔H) ist definiert als Abkürzung für die Formel ((¬G∨H)∧(G∨¬H).

Daher muss ich meinen Beweis der Richtung <= anpassen:


Sei (G↔H) gültig.
Zu zeigen ist die semantische Äquivalenz von G und H.

Sei also f eine Interpretation.
Zu zeigen ist f(G)=f(H).

Da ((¬G∨H)∧(G∨¬H) gültig ist, gilt f(((¬G∨H)∧(G∨¬H))=W.

Nach der Definition "Semantik der Aussagenlogik II" aus dem Skript (die ich im Folgenden immer wieder ohne explizite Erwähnung anwende) folgt f(¬G∨H)=f(G∨¬H)=W.

Wir unterscheiden nun die Fälle f(G)=W und f(G)=F.

Im Fall f(G)=W haben wir nach wegen f(¬G∨H)=W auch f(H)=W (womit wie gewünscht f(G)=W=f(H) folgt):
Wäre nämlich f(H)=F, so wäre wegen f(¬G)=F auch f(¬G∨H)=F.

Im Fall f(G)=F haben wir wegen f(G∨¬H)=W auch f(¬H)=W (und damit wie gewünscht f(G)=F=f(H)):
Wäre nämlich f(¬H)=F, so wäre auch f(G∨¬H)=F.


Der Beweis wird also durch eure komplexere Definition von (G↔H) etwas komplizierter.
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.