0 Daumen
344 Aufrufe

Aufgabe:

Tautologie von α := (¬a ∨ b) ∧ (c ⇒ a) ∨ ¬a beweisen

Ich weiß wenn man es in logikrechner angibt dass es keine tautologie ist aber wie beweist man es?

Avatar von

1 Antwort

+1 Daumen
dass es keine tautologie ist aber wie beweist man es?

Man gibt eine Belegung an, die die Formel falsch macht.

Avatar von 105 k 🚀

ja und wie ?

Zum Beispiel indem man alle Belegungen ausprobiert. Das sind nur 8 Stück, die man gut in eine Wahrheitstabelle packen kann:

a
b
c
(¬a ∨ b) ∧ (c ⇒ a) ∨ ¬a
f
f
f

f
f
w

f
w
f

f
w
w

w
f
f

w
f
w

w
w
f

w
w
w

kann man es auch ohne Warheitstabelle beweisen ?

Die Wahrheitstabelle ist nicht Teil des Beweises.

Der Beweis besteht wirklich nur darin - wie ich in meiner Antwort schon erwähnt habe - eine Belegung anzugeben, die die Formel falsch macht. Dass die Formel durch diese Belegung tatsächlich falsch wird, könnte man noch durch eine Rechnung verdeutlichen. Aber andere Belegungen sind für den Beweis vollkommen irrelevant.

Die Wahrheitstabelle dient dazu, eine geeignete Belegung zu finden.

Natürlich könnte man sich überlegen, wenn die Formel falsch sein soll, dann muß aufgrund der Eigenschaften der Verknüpfung ∨ die Teilformel ¬a falsch sein, also muss a wahr sein. Mit so einer Überlegung hat man schon die Hälfte der Belegungen als ungeeignet eliminiert. Aber letztendlich hat man dadurch auch nichts anderes gemacht, als die Wahrheitstabelle auszufüllen (auch wenn das nur im Kopf passiert ist, und nicht auf dem Papier).

Anstelle einer Wahrheitstabelle kann man ein Kalkül verwenden, zum Beispiel das Resolutionskalkül. Ich vermute aber, das kommt im Lehrplan etwas später.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community