TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 84

Man zeige, dass es sich bei dem logischen Ausdruck

[(B ∨ C) ∧ (B → ¬A) ∧ A] → C

um eine Tautologie bzw. bei dem Ausdruck

(A → C) ∧ (C → B) ∧ A ∧ ¬B

um eine Kontradiktion handelt.

Hilfreiches

Das Beispiel lässt sich auch mit einer Wahrheitstafel lösen, auch wenn diese sicher etwas groß ausfallen wird.

Lösungsvorschlag von Friday

a)

Lösung durch indirekten Beweis:

Wir nehmen an es handelt sich um keine Tautologie und führen diese Aussage zum Widerspruch.

Damit also der Ausdruck falsch ist, muss bei der Implikation der erste Wert wahr sein und der Zweite falsch.

Somit können wir für C = f einsetzen:

[(B ∨ f) ∧ (B → ¬A) ∧ A] → f

[B ∧ (B → ¬A) ∧ A] → f

Nun kann jedoch leicht erkann werden (oder mit einer Wahrheitstabelle gezeigt werden), dass der Ausdruck [B ∧ (B → ¬A) ∧ A] nie

erfüllt werden kann, also eine Kontraktion ist.

Das führt jetzt zu dem Widerspruch der Annahme, dass der ursprüngliche Ausdruck falsch werden kann und somit ist die

Tautologie bewiesen.

b)

Lösung durch indirekten Beweis:

Wir nehmen an die Aussage ist erfüllbar.

So ist leicht zu erkennen dass für A = w und B = f eingesetzt werden muss:

(w → C) ∧ (C → f) ∧ w ∧ ¬(f)

(w → C) ∧ (C → f) ∧ w ∧ w

Aus dem linkesten Term (w → C) ist erkennbar dass für C=w stimmen muss:

(w → w) ∧ (w → f) ∧ w ∧ w

Jetzt erkennen wir dass die zweite Implikation falsch ist, wodurch der gesamte Term falsch ist.

Dies führt zu dem Wiederspruch, dass die Aussage erfüllt werden kann und die Kontadiktion ist bewiesen.

PS: Ich bin mir nicht sicher ob mein Lösungsvorschlag so richtig ist, aber es ist hoffentlich besser als eine leere Seite.