Aussagenlogische Formel (Not H -> Not G) - (G -> H) ist Tautologie. Beweis?

Question

Aufgabe:

Es sei \( \operatorname{Var}_{A L} \) eine Menge von Aussagevariablen und es sei For \( { }_{A L} \) die Menge aller aussagenlogischen Formeln über \( \operatorname{Var}_{A L} \). Beweisen Sie, dass für alle \( G, H \in F o r_{A L} \) die aussagenlogische Formel
\( (\neg H \rightarrow \neg G) \rightarrow(G \rightarrow H) \)
eine Tautologie ist. Verwenden Sie nicht das aussagenlogische Kalkül, sondern arbeiten Sie mit der Definition der Auswertung von aussagenlogischen Formeln und den boolschen Funktionen.

Ansatz/Problem:

Ich habe eine Wahrheitstabelle aufgestellt, diese ausgewertet und für die letzte Spalte meiner Tabelle nur wahr erhalten, demnach liegt also eine Tautologie vor. Kann ich das so für diese Aufgabe machen oder muss ich das ganze anders beweisen?

Comments

Wenn du in der Spalte mit der Überschrift (Not H -> Not G) - (G -> H)  überall "wahr" hast, hast du "ausgewertet" und damit so bewiesen, wie die das hier beschreiben.

Answer 1

Antwort mit KI erzeugt

Aussagenlogischer Tautologiebeweis

Für die von dir beschriebene Formel \((\neg H \rightarrow \neg G) \rightarrow (G \rightarrow H)\) lässt sich sowohl eine Wahrheitstabelle als auch ein formaler Beweis anführen, um ihre Tautologie zu bestätigen. Der formale Beweis ohne Verwendung des aussagenlogischen Kalküls, sondern durch Rückführung auf die Definitionen und die boolschen Funktionen, sieht wie folgt aus:

Zu beweisen ist, dass für alle Aussagevariablen \(G, H\) die Formel \((\neg H \rightarrow \neg G) \rightarrow (G \rightarrow H)\) immer wahr ist, unabhängig von der Wahrheitswertbelegung von \(G\) und \(H\).

Ansatz über die Definitionen der Implikation und Negation:

Die Implikation \(A \rightarrow B\) ist genau dann falsch, wenn \(A\) wahr und \(B\) falsch ist. In allen anderen Fällen ist die Implikation wahr.

Die Negation \(\neg A\) kehrt den Wahrheitswert von \(A\) um.

Beweisführung:

1. Betrachten wir zuerst die linke Seite der Hauptimplikation \((\neg H \rightarrow \neg G)\):

- Diese ist wahr, wenn \(H\) wahr ist (denn dann ist \(\neg H\) falsch und somit die Implikation wahr unabhängig vom Wahrheitswert von \(\neg G\)).
- Sie ist auch wahr, wenn \(G\) ebenfalls wahr ist (denn dann ist \(\neg G\) falsch, und die Implikation wird wahr, weil ein falscher Satz nicht aus einem anderen folgen kann).
- Die einzig schwierige Situation ist, wenn \(H\) falsch und \(G\) wahr ist, weil dann \(\neg H\) wahr und \(\neg G\) falsch ist. Aber in diesem Fall würde die rechte Seite der Hauptimplikation \((G \rightarrow H)\) falsch, was unserer Behauptung widerspricht, dass die gesamte Formel eine Tautologie ist. Glücklicherweise wird dies durch die Struktur der Implikation aufgefangen, wie im nächsten Schritt gezeigt.

2. Die rechte Seite der Hauptimplikation \((G \rightarrow H)\) ist:

- Falsch, wenn \(G\) wahr und \(H\) falsch ist. In jedem anderen Fall ist diese wahr.

3. Die Kombination beider Teile im Kontext der Hauptimplikation \((\neg H \rightarrow \neg G) \rightarrow (G \rightarrow H)\) zeigt:

- Wenn der linke Teil wahr ist (was in den meisten Fällen so ist, wie besprochen), und der rechte Teil ebenfalls wahr ist (was auch in den meisten Fällen der Wahrheit entspricht, außer wenn \(G\) wahr und \(H\) falsch ist), dann ist die gesamte Formel wahr.
- Das einzige potenzielle Problem entsteht, wenn der linke Teil wahr und der rechte Teil falsch ist. Aber aufgrund der Natur der Implikation (\(A \rightarrow B\) wahr, wenn \(A\) falsch ist), ist die Formel auch in diesem Fall wahr, da die Implikation als Ganzes wahr ist, wenn der Prämisse falsch ist.

Daher haben wir demonstriert, basierend auf den Eigenschaften der boolschen Funktionen, dass die Formel \((\neg H \rightarrow \neg G) \rightarrow (G \rightarrow H)\) in jedem möglichen Fall wahr ist, was bedeutet, dass sie eine Tautologie ist.

Dieser Ansatz ist komplementär zur Auswertung mittels Wahrheitstabelle, bietet jedoch einen tieferen Einblick in die strukturellen Gründe dafür, dass die Formel immer wahr ist.