Die Aufgabe: Beweise oder widerlege folgende Behauptung: Ist (A–>B) erfüllbar und B keine Tautologie, so ist A erfüllbar. Ich habe da erst mal folgende Aussagen-„Formel“ für erstellt:
((A–>B)^B^NichtB)–>A
Die Überprüfung mit der Wahrheitstabelle zeigte erst einmal, dass das ganze eine Tautologie ist (also in allen 4 Fällen wahr). Ein Beweis ist das leider noch nicht.
Wie beweise ich das. Geht es mit dem Implikations-Beweisverfahren? Ich habe aber absolut keinen Ansatz.
Die Aufgabe: Beweise oder widerlege folgende Behauptung: Ist
(A–>B) erfüllbar und B keine Tautologie, so ist A
erfüllbar.
Ich habe da erst mal folgende Aussagen-„Formel“ für
erstellt:
((A–>B)^B^NichtB)–>A
Die Überprüfung mit der Wahrheitstabelle zeigte erst einmal,
dass das ganze eine Tautologie ist (also in allen 4 Fällen
wahr). Ein Beweis ist das leider noch nicht.
Wieso denn nicht? Eine Wahrheitstabelle listet doch alle möglichen Kombinationen der „Eingangszustände“ auf. Das gilt als Beweis! (Was anderes kann ja gar nicht mehr passieren.)
Wie beweise ich das. Geht es mit dem
Implikations-Beweisverfahren? Ich habe aber absolut keinen
Ansatz.
Das klappt auch, wenn man weiß, daß aus etwas Falschem immer etwas Wahres folgt. Nun ist B^nichtB immer falsch, so daß die
Prämisse (A–>B)^B^NichtB) laut dem Assoziativgesetz für ^ ebenfalls falsch wird.
Eine Wahrheitstabelle listet doch alle
möglichen Kombinationen der „Eingangszustände“ auf. Das gilt
als Beweis! (Was anderes kann ja gar nicht mehr passieren.)
Nur muss man sich vergewissern, dass die Wahrheitstabelle auch zu dem passt, was zu beweisen war.
Die Aufgabe: Beweise oder widerlege folgende Behauptung: Ist
(A–>B) erfüllbar und B keine Tautologie, so ist A
erfüllbar.
Ich habe da erst mal folgende Aussagen-„Formel“ für
erstellt:
((A–>B)^B^NichtB)–>A
„B ist keine Tautologie“ bedeutet (B / ¬B), d.h. zu betrachten wäre die Formel
(A -> B) /\ (B / ¬B) -> A
(A -> B) /\ W -> A
(A -> B) -> A
Dies wird falsch für A=F (unabhängig von B), also ist die Behauptung kein allgemeingültiger Satz.
Ich bin anderer Meinung. Folgendes Zitat soll verdeutlichen, dass „B ist keine Tautologie“ bedeutet:
(B/\NichtB), denn du hast EINE Tautologie beschrieben, da (B oder NichtB) immer wahr ist.
Definition 4.5
Ein logischer Ausdruck heißt Tautologie , wenn er
für jede Substitution seiner Variablen durch wahr
oder falsch den Wert wahr
ergibt. Entsprechend heißt ein logischer Ausdruck Widerspruch, wenn er für jede Substitution seiner
Variablen den Wert falsch hat.
Die Aussage A/NichtA
ist eine Tautologie:
Sie ist immer wahr. Ein Beispiel aus dem
täglichen Leben: „Wenn der Hahn kräht auf dem Mist,
ändert sich das Wetter oder es bleibt wie es ist.“ sieht
formal so aus: A–>(B/NichtB) und weil die rechte
Seite dieser Implikation eine Tautologie ist, ist die ganze Aussage
eine Tautologie.
Die Aussage A/\NichtA ist ein Widerspruch.
Ich bin anderer Meinung. Folgendes Zitat soll verdeutlichen,
dass „B ist keine Tautologie“ bedeutet:
(B/\NichtB), denn du hast EINE Tautologie beschrieben, da (B
oder NichtB) immer wahr ist.
Da hast Du vollkommen recht.
Definition 4.5
Ein logischer Ausdruck heißt Tautologie , wenn er
für jede Substitution seiner Variablen durch wahr
oder falsch den Wert wahr
ergibt.
So steht’s in jedem Lehrbuch.
Ein Beispiel aus dem
täglichen Leben: „Wenn der Hahn kräht auf dem Mist,
ändert sich das Wetter oder es bleibt wie es ist.“ sieht
formal so aus: A–>(B/NichtB) und weil die rechte
Seite dieser Implikation eine Tautologie ist, ist die ganze
Aussage eine Tautologie.
Da mußte ich auch erst etwas nachdenken, aber Du hast vollkommen recht. Die Subjunktion A --> C würde ja nur für A=w und C=f gesamt den Wert f liefern, was in Deinem Beispiel nicht sein kann. Da hab’ ich auch wieder was dazugelernt. Danke
Zu Recht. (war schon spät und so… *herausred*…)
Okay, Murks, stimmt nicht, vergessen wirs. Ich hatte den glorreichen Gedanken "Tautologie -> Wahr — keine Tautologie -> kann auch falsch sein -> Wahr oder Falsch. Naja.
Die Aussage A/\NichtA ist ein Widerspruch.
„keine Tautologie“ ist aber nicht gleichbedeutend mit „Widersprüchlich“!
Die Behauptung macht Annahmen über die Ausdrücke A und B, deshalb kann ich das nicht auf eine Formel abbilden, die sich auf der gleichen Bedeutungsebene wie A und B befindet. Wenn ich die Behauptung formalisieren will, brauche ich etwas, das eine Ebene höher angesiedelt ist.
Die Aussage „B ist keine Tautologie“ läßt sich nicht in eine aussagenlogische Formel umwandeln, die nur ebendieses B verwendet. Wir müssen die Aussagenlogik überhaupt verlassen. Ich könnte natürlich ein Aussagensymbol C definieren mit C := „B ist keine Tautologie“, aber das hilft nicht wirklich weiter. Beim Formalisieren benötigen wir (oder ich jedenfalls) Quantoren und Prädikate:
(1) „B ist keine Tautologie“ heißt, es ex. eine Belegung α, so dass B unter der Belegung α (bezeichnet als B[α]) falsch ist.
(2) „(A -> B) ist erfüllbar“ heißt, es ex. eine Belegung β, so dass (A[β] -> B[β]) wahr ist.
Weder (1) noch (2) schließt aus, dass A[β] für jedes β falsch ist.