Widerspurchsbeweis als logische Formel?
Hallo liebe Community,
ich beschäftige mich immer noch mit dem Thema Aussagenlogik und will erneut eine Verständnisfrage stellen. Ich probiere gerade den indirekten Beweis oder auch Beweis durch Widerspruch zu verstehen.
Meinem Verständnis nach funktioniert der Widerspruchsbeweis wie folgt:
Man nimmt eine Aussage S und negiert diese. Der Widerspruchsbeweis funktioniert nur wenn die negierte Aussage S den Wahrheitswert falsch hat. Wenn die negierte Aussage von S den Wahrheitswert falsch hat, dann kann man die negierte Aussage S nocheinmal negieren.
Dadurch, dass die doppelt negierte Aussage von S eindeutig wahr ist, und die doppelte Negation von S wieder S ergibt hat man dadurch bewiesen, dass S wahr ist.
Ansich habe ich das Gefühl, dass ich es teilweise verstanden habe, aber ich habe es noch nicht in der Gänze verstanden.
Ich möchte die ganze Zeit den Beweis durch Widerspruch als logische Formel aufstellen und dann wollte ich probieren diese logische Formel, formal zu beweisen. Mit vielleicht einer Wahrheitswertetabelle.
Das habe ich auch schon irgendwie ein bisschen ausprobiert und hatte folgendes:
Nur irgendwie habe ich diese Wahrheitswertetabelle erstellt ohne mir im klaren zu sein, was ich da so wirklich mache. Ich habe meiner Meinung nach immer noch keine logische Formel für den Beweis durch Widerspruch.
Also meine expliziten Fragen sind:- Was ist die logische Formel des Beweises durch Widerspruch.
- Ergibt meine Wahrheitswertetabelle Sinn im Bezug auf den Beweis durch Widerspruch?
- Wenn meine Wahrheitswertetabelle Sinn ergibt, kann mir jemand kurz zusammenfassen warum diese Wahrheitswertetabelle Sinn ergibt?
Anmerkung zu der letzten Frage: Ich bin halt ein bisschen verwirrt im allgemeinen, da ich nicht weiß wie ich damit umgehen soll falls die Aussage S falsch ist. Weil dann funktioniert ja der Beweis durch Widerspruch eigentlich nicht, weil ich dann die Negation von S nicht zu einem Widerspruch bringen kann, oder?
3 Antworten
Also im Wesentlichen funktioniert der Widerspruchsbeweis ja so:
Zu zeigen: A
Angenommen, A wäre nicht wahr. Dann gilt ¬A. Aber aus ¬A folgt eine falsche Aussage. Darum kann ¬A nicht wahr sein. Ergo ist A wahr.
Die eigentliche Idee lautet daher meines Erachtens:
A <=> (¬A => false)
Es ist die Grundidee. Eine sauberere Formulierung findest du z.B. hier
Okay vielen Dank! Die saubere Formulierung geht aber leider über meine Kenntnisse erstmal hinaus, da muss ich mich glaube ich noch ein wenig weiter mit der Materie beschäftigen um die zu verstehen.
Aber ansich ist das was du geschrieben hast, ja schon passend für mich.
Weil es ist ja die logische Formel von:
Zeige, dass aus ¬A eine falsche Aussage folgt.
Dann muss A wahr sein
Und das ist ja der Beweis durch Widerspruch.
Wenn ich nun die logische Formel beweisen möchte, dann würde ich das jetzt mittels Wahrheitswertetabelle machen.
Das habe ich gerade gemacht und für deine gegebene Formel kommt immer wahr raus. Aber was mich immer noch ein bisschen verwirrt ist, ist der Fakt, dass die Wahrheitswertetabelle für deine Formel komplett gleich zu meiner Wahrheitswertetabelle mit der doppelten Negation von A ist.
Ich habe das mit der doppelten Negation von A halt bei meiner Recherche im Internet gefunden und bin mir jetzt nicht sicher, inwiefern das wichtig ist oder ob ich das komplett weglassen kann.
Hier einmal der Link mit der Wahrheitswertetabelle:
Dass die Tabellen identisch sind, ist nicht so verwunderlich. Wegen
(A => B) <=> (¬A v B)
ist (¬A => false) <=> (¬¬A v false). Deswegen ist
¬A => false nichts anderes als ¬¬A.
Der Grund, aus dem ich den Link angebracht hab, ist dass man den Widerspruchsbeweis in dieser reinen Form A <=> (¬A => false) quasi nie verwendet.
Wenn ich z.B. beweisen will, dass es nicht regnet, könnte ich ein Argument bringen wie:
"Es kann nicht regnen. Denn würde es regnen, dann wäre die Straße nass. Aber wie man deutlich sieht, ist die Straße nicht nass!".
Aber die Aussage "Die Straße ist nass" muss nicht immer eine falsche Aussage sein (sie ist an sich keine Antinomie). In einer anderen Welt könnte die Straße durchaus nass sein. Daher gilt mein Beweis nur, wenn zusätzlich angenommen wird, dass die Straße nicht nass ist.
Die logischen Formeln die ich jetzt bereits gefunden/formuliert habe sind diese:
Diese habe ich alle mit Wahrheitwertetabelle bewiesen. Ich bin jetzt zu dem Schluss gekommen, dass diese Aussagen alle logisch äquivalent zueinander sind. Bedeutet, dass das ich zum beweisen des Beweises durch Widerspruch einfach eine der Aussagen nehmen kann und diese mittels Wahrheitswertetabelle beweise und dann habe ich den Beweis durch Widerspruch bewiesen?
Dass alle Formeln äquivalent sind, ist klar: Es sind ja alles Tautologien.
Es kommt ein bisschen drauf an, wie du den Beweis durch Widerspruch betrachtest. Die zweite Formulierung ist vermutlich am deutlichsten:
Ich nehme ¬A an, führe es zum Widerspruch und beweise somit die Aussage A.
Die erste Formulierung ist zwar an sich dasselbe in grün (weil ¬¬A äquivalent zu A ist), aber typischerweise wollen wir keine negierten Aussagen beweisen (bzw. wir schreiben die zu zeigende Aussage in positiver Form auf).
Die letzte Formulierung [meine Version] besagt zusätzlich, dass wenn A gilt, ¬A zum Widerspruch führt. Das ist zwar korrekt, aber für den eigentlichen Widerspruchsbeweis eine unnötige Eigenschaft, da wir zum Beweis von A ja nicht annehmen, dass A wahr ist ;)
In der mathematischen Logik (hier in der "natürlichen" Minimallogik) hat der Widerspruchsbeweis prinzipiell die Form
wobei das umgedrehte T für das Falsum, also die konstant falsche Aussage steht.
Auf Deutsch: Impliziert A eine falsche Aussage, muss A falsch sein.
Intuitiv stimmt das mit dem überein, was du geschrieben hast. Man zeigt beim Widerspruchsbeweis, dass "nicht A" nicht gelten kann. Zusammen mit dem Bivalenzprinzip ergibt sich daraus, dass A gilt.
Die Wahrheitstabelle zeigt im Wesentlichen, dass "nicht nicht A" dasselbe ist wie A (wobei es tatsächlich ein nicht selbstverständlicher Luxus der Aussagenlogik ist, dass A aus "nicht nicht A" herleitbar ist).
Der Widerspruchsbeweis funktioniert aber auch für falsche Aussagen - man nimmt dann eben an, dass sie wahr sind und zeigt, dass das einen Widerspruch impliziert.
Vielen Dank für deine Antwort.
Also denkst du es wäre formal besser, wenn ich deine Formel nehmen würde und die mittels einer Wahrheitswertetabelle beweisen würde, anstatt irgendwas mit der doppelten Negation von A zu machen.
Weil um ehrlich zu sein verstehe ich zwar ansich den Sachverhalt, dass aus der doppelten Negation von A wieder A herleitbar ist usw., aber um den Beweis durch Widerspruch zu beweisen, verwirrt mich das mit der doppelten Negation ein bisschen.
Also wenn ich einfach deine Formel mittels Wahrheitswertetabelle beweise, dann habe ich den Beweis durch Widerspruch bewiesen oder?
Was ich außerdem verwirrend finde ist, dass es anscheinend mehrere logische Formeln für den Beweis durch Widerspruch gibt.
Du hast nun diese logische Formel für den Beweis durch Widerspruch vorgeschlagen und wenn ich diese mit Wahrheitswertetabelle beweise, dann funktioniert das auch, also man hat halt immer den Wahrheitswert "wahr" für deine Formel.
Aber genauso, hat man für diese logische Formel für den Beweis durch Widerspruch immer den Wahrheitswert "wahr". Also ist diese Formel ja auch wieder bewiesen und somit anscheinend korrekt.
A <=> (¬A => false)
Und meine Sache mit der doppelten Negation von S hat auch überall den Wahrheitswert "wahr" und ist somit bewiesen.
Also meine Formel würde ich schonmal nicht nehmen, weil da dass mit dem Wahrheitswert falsch nicht so wirklich integriert ist. Aber von den beiden oberen Formeln, welche soll ich da nehmen? Oder ist das egal?
Ich verstehe dein Ziel noch nicht ganz. Auf welchem Niveau möchtest du was beweisen? Du wirkst nicht so als würdest du tatsächlich formal sauber in irgendeinem logischen Kalkül schließen wollen?
Ich beschäftige mich halt nur so aus Neugierde damit und bin deswegen noch nicht wirklich tief in diesem Thema drin.
Ansich ist mein Ziel einfach nur eine logische Formel zu finden, die den Beweis durch Widerspruch beschreibt und diese Formel möchte ich dann mit einer Wahrheitswertetabelle beweisen.
Ich weiß nicht was mir das bringt. Ich habe einfach nur angefangen darüber nachzudenken wie man sowas macht und dann wollte ich das herausfinden.
Jetzt bin ich dem ganzen ja schonmal etwas näher gekommen.
Ich habe logische Formeln gefunden die den Beweis durch Widerspruch beschreiben (siehe die zwei Formeln oben, also das mit der doppelten Negation lassen wir erstmal einfach außen vor).
Ja und mehr möchte ich nicht machen.
Also einfach aus dem Beweis durch Widerspruch:
Zeige, dass aus ¬A eine falsche Aussage folgt.
Dann muss A wahr sein.
Eine logische Formel formulieren und diese möchte ich dann beweisen.
Das wars, das ist für keine Komplexe Aufgabe oder sowas gedacht, ich habe halt einfach nur über den Beweis gelesen und mir dann diese Frage gestellt.
Ich brauche die Formel für nichts ansich. Ich brauche die nur um die zu beweisen. Ist halt jetzt in keinem größeren Kontext oder so.
Die logischen Formeln die ich jetzt bereits gefunden/formuliert habe sind diese:
Diese habe ich alle mit Wahrheitwertetabelle bewiesen. Ich bin jetzt zu dem Schluss gekommen, dass diese Aussagen alle logisch äquivalent zueinander sind. Bedeutet, dass das ich zum beweisen des Beweises durch Widerspruch einfach eine der Aussagen nehmen kann und diese mittels Wahrheitswertetabelle beweise und dann habe ich den Beweis durch Widerspruch bewiesen?
Hallo,
bei einem Widerspruchsbeweis stellst Du eine gegenteilige Behauptung auf und versuchst sie zu beweisen.
Führt dieser Beweis zu einem Widerspruch, folgt daraus, daß die gegenteilige Behauptung falsch ist und demnach die eigentliche Behauptung richtig sein mußt.
Wenn Du durch Widerspruch beweisen willst, daß aus NICHT NICHT A A folgt, behauptest Du, daß aus NICHT NICHT A NICHT A folgt und zeigst, daß der Beweis dieser Behauptung zu einem Widerspruch führt.
Herzliche Grüße,
Willy
Vielen Dank!
Aber meine eigentliche Absicht war, den Beweis durch Widerspruch insgesamt zu beweisen. Also sozusagen durch logische Verknüpfungen zu beweisen, dass der Widerspruchsbeweis funktioniert.
Und ich habe halt probiert das mit dieser doppelten Negation zu beweisen.
Aus der anderen Antwort habe ich jetzt als logische Formel für den Beweis durch Widerspruch folgendes erhalten:
A <=> (¬A => false)
Falls dies wirklich die logische Formel für Beweis durch Widerspruch ist (meiner Meinung nach ergibt, die Formel schon Sinn), dann würde ich jetzt einfach probieren mittels Wahrheitswertetabelle diese Formel zu beweisen und dann habe ich bewiesen, dass der Beweis durch Widerspruch funktioniert oder?
Das mit der doppelten Negation von A habe ich halt bei meiner Recherche irgendwo gelesen und habe gedacht, dass man auch das benötigt um den Beweis durch Widerspruch zu beweisen.
Die logischen Formeln die ich jetzt bereits gefunden/formuliert habe sind diese:
Diese habe ich alle mit Wahrheitwertetabelle bewiesen. Ich bin jetzt zu dem Schluss gekommen, dass diese Aussagen alle logisch äquivalent zueinander sind. Bedeutet, dass das ich zum beweisen des Beweises durch Widerspruch einfach eine der Aussagen nehmen kann und diese mittels Wahrheitswertetabelle beweise und dann habe ich den Beweis durch Widerspruch bewiesen?
Du mußt zeigen, daß die Behauptung, die das Gegenteil von dem behauptet, das eigentlich bewiesen werden soll, zu einem Widerspruch führt.
Wenn Du beweisen willst, daß aus A B folgt, behauptest Du, daß aus A nicht B folgt, versuchst das zu beweisen und zeigst, daß der Beweis zu einem Widerspruch führt.
Wenn Du durch Widerspruch beweisen sollst, daß die 3 eine ungerade Zahl ist, behauptest Du, die 3 sei eine gerade Zahl und zeigst, daß der Beweis dieser (falschen) Behauptung zu einem Widerspruch führt und daß die 3 daher keine gerade Zahl sein kann und folglich ungerade sein muß.
Ja das verstehe ich ja. Aber ich will nichts mit dem Beweis durch Widerspruch beweisen. Ich will den Beweis durch Widerspruch ansich beweisen.
Ich weiß nicht, anscheinend verstehe ich irgendwas komplett falsch oder so, aber ansich hätte man doch meinen letzten Kommentar einfach mit einem Ja oder einem Nein beantworten können. Und vielleicht noch eine kurze Erklärung warum entweder Ja oder warum Nein.
Wahrscheinlich verstehe ich das Thema im allgemeinen nicht, aber das was du geschrieben hast verstehe ich. Ich weiß wie man eine Aussage mittels Beweis durch Widerspruch beweist, aber ich weiß nicht wie ich den Beweis durch Widerspruch beweise.
So der Beweis durch Widerspruch ist ja wie folgt aufgebaut:
Zeige, dass aus ¬A eine falsche Aussage folgt.
Dann muss A wahr sein.
Das ist der Beweis durch Widerspruch. Diese zwei Sätze habe ich jetzt durch logische Formeln beschrieben. Insgesamt, habe ich drei logische Formeln erarbeitet (siehe anderes Kommentar von mir). Diese drei Formeln sind meiner Meinung nach logisch äquivalent zueinander.
Jetzt möchte ich halt eine dieser logischen Formeln beweisen, mittels Wahrheitswertetabelle. Nun stellt sich mir aber die Frage, ist es egal welche der Formeln ich beweise, oder nicht?
Also ist A <=> (nicht A => false) sozusagen die logische Formel des Beweises durch Widerspruch?