Was ist die explizite Begründung hinter dem Beweis durch Widerspruch?

Es scheint mehrere sich überschneidende Bedenken in Ihrem Problem mit dem Beweis durch Widerspruch zu geben.

1. Sie haben einen Einwand gegen die Wahrheitstabelle wegen materieller Implikation:

Ich habe mich jedoch nie mit dem Argument zufrieden gegeben, dass zwei falsche Behauptungen eine wahre Implikation erzeugen. Welche guten Gründe gibt es, dem zuzustimmen?

2. Sie scheinen Beweis durch Widerspruch falsch zu verstehen:

1. Zeigen Sie, dass p -> q, wobei "->" die Bedingung ist. 2. Zeigen Sie, dass q falsch ist. 3. Leiten Sie aus einer Wahrheitstabelle ab, dass p falsch sein muss.

Ich beginne mit dem zweiten Thema. Ich würde sagen, eine bessere Definition des Beweises durch Widerspruch lautet wie folgt:

1. Gegeben P, A
2. Gegeben P, nicht A
3. Ergo, gegeben P, A & nicht A
4. Also nicht P wegen Widerspruch, wenn P

Dies hängt in gewisser Weise mit materiellen Implikationen zusammen, wie Sie zu Recht bemerken. Aber hier geht es nicht wirklich darum zu beweisen, dass A falsch ist – es geht darum zu beweisen, dass A und nicht A gleichzeitig wahr sind. Da dies jedoch mit Standardlogiken unmöglich ist, müssen wir uns geirrt haben, P zu akzeptieren, also nicht P.

Um auf das Thema Standardlogik zurückzukommen, können wir Ihre Bedenken hinsichtlich der materiellen Implikation teilweise ansprechen. Es gibt drei grundlegende Regeln, denen die klassische Logik folgt:

1. Gesetz der Identität - wir müssen jedes Mal dasselbe mit demselben meinen. (Wir können die Bedeutung von Variablen und Begriffen nicht mitten im Argument ändern).
2. Gesetz der ausgeschlossenen Mitte - jeder Satz, den wir ansprechen, muss entweder wahr oder falsch sein (und nur einer von beiden in dieser Bedeutung von oder).
3. Gesetz der Widerspruchsfreiheit – wir können nicht akzeptieren, dass sowohl A als auch sein Gegenteil (nicht A) gleichzeitig wahr sind.

Wir können das auch kurz ausdrücken:

1. A = A
2. Für jedes A wahr oder falsch
3. nicht (A und nicht A)

Materielle Implikation ist ein logischer Operator, der mit zwei Begriffen arbeitet und in dieser Welt lebt. Sein Zweck ist es, mit Bedingungen zu arbeiten, dh Stellen, an denen der Wert einer Variablen von einer anderen abhängt. Da wir 2 Variablen haben, die (per Regel kann 2 jeweils zwei Werte haben), haben wir vier Möglichkeiten.

Für A -> B,

1. A ist wahr und B ist wahr
2. A ist wahr und B ist falsch
3. A ist falsch und B ist wahr
4. A ist falsch und B ist falsch

Was Implikation tut, ist zu testen, ob die Implikation gilt. Daher akzeptieren wir, dass es gilt (siehe die gesamte Implikation als wahr), wenn A wahr ist und B wahr ist. Wir sollten auch sehen können, dass die Implikation falsch ist, wenn A wahr ist, aber B falsch ist.

Die Situation ist etwas komplizierter und verwirrender, wenn A falsch ist (wenn wir „wenn, dann“ denken, anstatt es einfach als Operator zu akzeptieren). Zuletzt war die Erklärung, die ich in meinen Kursen gegeben habe, wie folgt:

Wenn A falsch ist, haben wir keine Möglichkeit zu prüfen, ob die Implikation direkt gilt oder nicht. Aber angesichts der drei Gesetze (insbesondere 2) müssen wir dies entweder für wahr oder falsch erklären. Da wir die Implikation nicht widerlegt haben, bleibt sie für unsere Zwecke wahr.

Aber die Sache ist die, wir brauchen das nicht speziell für den Widerspruchsbeweis, weil wir beim Widerspruchsbeweis gezeigt haben, dass eine Annahme P zu einem Widerspruch führt. Und Widersprüche sind nach der dritten Regel nicht akzeptabel. Ergo muss die Annahme selbst zurückgewiesen werden.

Der Beweis durch Widerspruch im Allgemeinen ist nicht auf die Verwendung von Bedingung beschränkt .

In der Logik ist der Beweis durch Widerspruch eine Form des Beweises und insbesondere eine Form des indirekten Beweises, der die Wahrheit oder Gültigkeit einer Aussage feststellt, indem er zeigt, dass die Falschheit der Aussage einen Widerspruch implizieren würde .

Was benötigt wird, ist das Konzept der logischen Implikation oder logischen Konsequenz .

Dieses Konzept ist der Kern aller Logik. Es wurde zuerst von Aristolte eindeutig identifiziert :

Die gesamte Logik des Aristoteles dreht sich um einen Begriff: die Deduktion ( sullogismos ). [...] Was ist denn ein Abzug? Aristoteles sagt:

Eine Deduktion ist eine Rede ( logos ), bei der sich, nachdem gewisse Dinge angenommen wurden, notwendigerweise etwas anderes als die angenommenen ergibt, weil sie so sind. ( Frühere Analytik I.2, 24b18–20)

Jedes der „angenommenen Dinge“ ist eine Prämisse ( Protasis ) des Arguments, und was „Ergebnisse der Notwendigkeit“ sind, ist die Schlussfolgerung ( Sumperasma ).

Der Kern dieser Definition ist der Begriff „Ergebnis der Notwendigkeit“. Dies entspricht einer modernen Vorstellung von logischer Konsequenz : X ergibt sich zwangsläufig aus Y und Z , wenn es unmöglich wäre, dass X falsch ist, wenn Y und Z wahr sind. Wir könnten dies daher als eine allgemeine Definition von „gültigem Argument“ auffassen.

Ein gültiges Argument ist also ein Argument, das aus wahren Prämissen eine wahre Schlussfolgerung ableitet.

Wenn wir aus der Menge der Prämissen Γ ∪ {A} etwas Falsches ableiten , wie einen Widerspruch mittels der Regeln der Logik, müssen wir schließen, dass mindestens eine der Prämissen falsch ist , denn nach der Definition der logischen Konsequenz :

wenn alle Prämissen wahr sind, dann gilt zwangsläufig auch die Konklusion .

Daraus schließen wir, dass die Aussage A für den Widerspruch "verantwortlich" ist und dass die verbleibende Prämissenmenge Γ die Negation von A impliziert , also ¬ A .

In Ihrem Beispiel, wenn wir bewiesen haben

P → Q ,

dann gehen wir wie folgt vor:

1) nehme P an

2) leite ¬ Q ab ;

nach modus ponens leiten wir aus P → Q und 1) auch ab:

3) F

Jetzt haben wir den Widerspruch und müssen daraus schließen, dass unsere anfängliche Annahme P falsch ist , dh

4) ¬P .

Anders ausgedrückt, wenn P → Q und P → ¬ Q , unter Verwendung der Tautologie : (P → Q) → ((P → ¬ Q) → ¬P) , durch zweimalige Anwendung von modus ponens schließen wir mit ¬ P , dass läuft darauf hinaus zu sagen:

¬ P ist logische Konsequenz von P → Q und P → ¬ Q .

In Symbolen:

P → Q, P → ¬ Q ⊨ ¬ P

Die explizite Begründung für einen Widerspruchsbeweis sind die beiden Gesetze

"non (non A) = A" und "If A => B and B false, then A false"

Diese Gesetze gelten in der Aussagenlogik. Die wahrheitsfähige Methode beweist den zweiten Hauptsatz.

Ein Widerspruchsbeweis wendet diese Gesetze folgendermaßen an: Um zu beweisen, dass ein Satz „A“ wahr ist, nimmt man im Gegenteil an, dass „A“ falsch ist. dh "nicht A" wahr. Aus dieser Annahme leitet man in einem oder mehreren Schritten eine bestimmte Aussage „B“ ab, die man als falsch nachweist. Nun impliziert "non A => B" und "B" false "non A" false, also "A" true.

Die Methode, die Sie beschreiben, ist nicht "Beweis durch Widerspruch", sondern heißt "Beweis des Kontrapositivs" - symbolisch ausgedrückt als ¬q ⇒ ¬p . Diese Aussage ist logisch äquivalent zu p ⇒ q . Es ist wichtig zu verstehen, dass es bei diesen beiden Methoden darum geht, die materielle Implikation p ⇒ q zu beweisen , nicht (wiederhole nicht ) die Wahrheit von p oder q , wie Sie in Ihren Kommentaren annehmen.

Wie funktioniert das? Die Aussage p ⇒ q ist wahr, es sei denn, p kann wahr sein, während q falsch ist. [1]

Bei der von Ihnen beschriebenen Methode zum Beweis des Kontrapositivs geht man davon aus, dass q falsch ist, und zeigt, dass dies impliziert, dass p falsch sein muss. Das bedeutet, dass wir niemals p wahr und q falsch haben können, also kann man folgern, dass p ⇒ q gemäß [1] .

Bei der Methode des Widerspruchsbeweises nimmt man an, dass p ⇒ q falsch ist, also p wahr und q falsch (im Gegensatz zu [1] ) und zeigt, dass diese Annahme zu einem Widerspruch führt, woraus sich schließen lässt, dass p niemals wahr sein kann und q falsch. Dies ist gleichbedeutend mit der Aussage p ⇒ q , da eine materielle Implikation nur dann falsch ist, wenn es möglich ist, p wahr und q falsch zu machen.

Ihre Kommentare zu diesen Strategien setzen voraus, dass wir wissen, dass p ⇒ q wahr ist, und wir dann die Wahrheitswerte von p und q ableiten . Dies ist bei keiner der Beweismethoden richtig - durch Widerspruch oder durch Kontraposition. Der Sinn dieser Methoden besteht darin, die Wahrheit von p ⇒ q zu beweisen .

BEARBEITEN

Zu Ihren Kommentaren (unten):

1. Wie können wir die materielle Implikation beweisen, ohne zuerst festzustellen, was die Wahrheitswerte von p und q sein müssen?

Beide dieser Methoden funktionieren, indem sie die relevanten Wahrheitswerte annehmen . Beim Beweis des Kontrapositivs nehmen wir an, dass q falsch ist und zeigen, dass uns dies zwingt zu akzeptieren, dass auch p falsch sein muss. Hier ist ein Beispiel für einen Beweis des Kontrapositivs:

( Anmerkung: Ich werde ein Beispiel für ein informelles Argument geben, da es einfacher ist, nachzuvollziehen, wie die Methoden funktionieren. )

BEISPIEL: Angenommen, n ist eine positive ganze Zahl und wir möchten dies beweisen:

• Wenn n ² gerade ist, dann ist n gerade.

Um die Methode des Beweises des Kontrapositivs anzuwenden , würden wir annehmen, dass die Aussage q (= n ist gerade) falsch ist und zeigen, dass eine notwendige Konsequenz dieser Annahme ist, dass p (= n ² ist gerade) ebenfalls falsch sein muss.

Nehmen Sie dazu an, dass n nicht gerade ist. Dann können wir n als 2k+1 für eine positive ganze Zahl k schreiben . Also n ² = ( 2k+1 ) ² . Wenn wir diesen Ausdruck erweitern und die Terme gruppieren, können wir dies schreiben als n ² = 4(k ² + k)+1 . Da 4(k ² + k)+1 nicht gerade ist (da es nicht durch 2 teilbar ist), haben wir gezeigt, dass die Annahme, dass n nicht gerade ist, uns zu dem Schluss zwingt, dass n ² nicht gerade ist. Damit haben wir bewiesen „Wenn n ungerade ist, dann ist n ²ist ungerade" oder äquivalent "Wenn n ² gerade ist, dann ist n gerade." Dh, ¬ q ⇒ ¬p , was äquivalent zu p ⇒ q ist .

Um die Methode des Widerspruchsbeweises zu verwenden , würden wir annehmen, dass p ⇒ q falsch ist und einen Widerspruch ableiten. Wenn p ⇒ q falsch ist, dann gibt es eine positive ganze Zahl n, so dass n ² gerade, aber n ungerade ist. Aber wenn n ungerade ist, dann müssen wir nach dem gleichen Argument, das in unserem Beispiel zum Beweis des Kontrapositivs verwendet wird, n ² auch ungerade haben. Dies widerspricht unserer Annahme, dass p ⇒ q falsch ist und wir daraus schließen können, dass p ⇒ q wahr sein muss.

2. Können Sie anhand der Methode zum Beweis des Kontrapositivs erklären, warum wir zeigen können, dass p falsch ist, indem wir annehmen, dass q falsch ist, ohne die Wahrheitstabelle zu verwenden? Oder wird das verwendet, um dies festzustellen?

Ich glaube, dass meine Ausführungen zu Frage 1 auch diese Frage beantworten. Das Beispiel, das ich gegeben habe, ist offensichtlich ein informelles Argument, das jedoch leicht formalisiert werden kann.

Nach meinem Verständnis besteht der Beweis durch Widerspruch aus den folgenden Schritten. 1. Zeigen Sie, dass p -> q, wobei "->" die Bedingung ist. 2. Zeigen Sie, dass q falsch ist. 3. Leiten Sie aus einer Wahrheitstabelle ab, dass p falsch sein muss.

Sie beschreiben den Modus Tollens, nicht den Beweis durch Widerspruch.

Wenn wir die Wahrheit der Bedingung auf die Wahrheit von p und q stützen, wie können wir dann wissen, dass die Bedingung wahr ist, bevor wir wissen, ob sowohl p als auch q wahr sind?

Die Annahme in der symbolischen Logik ist, dass wir wissen/glauben, dass die Bedingung (oder eine andere Prämisse) aus irgendeinem Grund außerhalb der symbolischen Logik wahr ist. Vielleicht glauben Sie, dass die Implikation selbstverständlich ist oder durch wissenschaftliche Beweise gut belegt ist. Es liegt sicherlich nicht daran, dass Sie den Wahrheitswert von p und q kennen.

Das einzige Szenario, das dieses Ergebnis erzeugt, ist dasjenige, bei dem p ebenfalls falsch ist. Ich habe mich jedoch nie mit dem Argument zufrieden gegeben, dass zwei falsche Behauptungen eine wahre Implikation erzeugen. Welche guten Gründe gibt es, dem zuzustimmen?

Erstens ändert dies nichts an der Begründung für modus tollens. Wenn falsch -> falsch entweder falsch oder unbestimmt wäre, wäre wahr -> falsch immer noch falsch. Da q falsch ist, bleibt nur die Option, dass p falsch ist.

So wie ich es sehe, sollten Sie sich den materiellen Konditional nicht als Äquivalent zu unserem natürlichen Sprachkonzept der Implikation vorstellen. Unser natürlichsprachlicher Begriff der Implikation ähnelt eher dem Konzept der Prädikatenlogik:

(x)(Ax -> Bx)

Dies besagt, dass für alle x, wenn Ax wahr ist, Bx wahr ist. Es ist trivialerweise wahr, wenn Ax falsch ist, aber wenn Ax wahr ist, dann muss auch Bx wahr sein.

Betrachten Sie den Satz: Wenn ich der Präsident bin, sind Sie der Papst. Keine der Behauptungen ist wahr, aber es scheint falsch zu behaupten, dass die Implikation wahr ist, weil ich als Präsident Sie nicht zum Papst machen würde. Aber was wir wirklich meinen, ist so etwas wie: In allen möglichen Welten, in denen ich der Präsident bin, bist du der Papst.

Die Logik erster Ordnung ist insofern nett, als es mehrere Möglichkeiten gibt, darüber nachzudenken, die alle identische Ergebnisse liefern.

Wenn Γ ein Satz von Formeln und P eine Formel ist, ist die Notation

Γ ⊢ P

syntaktische Folgerung genannt , ist die Behauptung, dass es einen deduktiven Beweis von P gibt, indem die Formeln in Γ als Hypothesen verwendet werden. zB Konjunktionseinführung ist das Axiom

P, Q ⊢ P ∧ Q

Eine Formulierung des Widerspruchsbeweises ist

Γ, P ⊢ Q
Γ, P ⊢ ¬Q
therefore
Γ ⊢ ¬P

Einige Versionen der Logik haben ein Symbol ⊥, das "Widerspruch" bedeutet, in diesem Fall würden wir dies wahrscheinlich stattdessen als formulieren

Γ, P ⊢ ⊥
therefore
Γ ⊢ ¬P

Solche Beweisformen können oft verwendet werden

P, ¬P ⊢ ⊥

Der Konditional kann als Mittel betrachtet werden, um den Begriff der Folgerung in eine Aussageform umzuwandeln; speziell

Γ, P ⊢ Q      if and only if      Γ ⊢ P → Q

Dann, anstatt mit dem Begriff der Folgerung zu arbeiten, manipuliert man stattdessen Sätze. zB modus ponens

P, P → Q ⊢ Q

aber wir könnten es stattdessen als Tautologie sehen

⊢ (P ∧ (P → Q)) → Q

Ebenso können wir Beweis durch Widerspruch umformulieren als

(P → Q), (P → ¬Q) ⊢ ¬P

oder als Tautologie

⊢ ((P → Q) ∧ (P → ¬Q)) → ¬P

Mit dem Widerspruchszeichen könnten wir das auch so formulieren

⊢ (P → ⊥) → ¬P

Es gibt eine andere Notation

Γ ⊨ P

wird als semantische Bindung bezeichnet . Da wir hier von Aussagenlogik sprechen, ist eine Möglichkeit, dies zu definieren, die Behauptung, dass jede Wahrheitsbewertung, die jede Aussage in Γ wahr macht, auch P wahr macht.

(Eine Wahrheitsbewertung ist einfach eine Auswahl des Wahrheitswerts für jede atomare Aussage und die Berechnung der Wahrheit komplexerer Aussagen durch Verwendung der entsprechenden booleschen Operatoren für Wahrheitswerte.)

Zum Beispiel können wir beweisen

P ⊨ P ∨ Q

durch Wahrheitstabellen – das heißt, indem überprüft wird, ob jede Zeile der Wahrheitstabelle P = trueauch hat P ∨ Q = true.

Wir möchten, dass sich die Implikation genauso verhält: zum Beispiel

Γ, P ⊨ Q      if and only if      Γ ⊨ P → Q

Beachte, dass die Behauptung P⊨Q identisch ist mit

Es ist unmöglich, Wahrheitswerte so zuzuweisen, dass P wahr und Q falsch wird

Folglich müssen die Zeilen in der Wahrheitstabelle, die für falsch sind, P→Qgenau die Zeilen sein, in denen Pwahr und Qfalsch ist – nicht mehr und nicht weniger.

Dann sind das Magische an der Aussagenlogik (und an der Logik erster Ordnung) der Vollständigkeitssatz und der Korrektheitssatz, die zusammen sagen

Γ ⊢ P      if and only if      Γ ⊨ P

Das ist es also, was wir tun, wenn wir Wahrheitswerte betrachten – wir führen Berechnungen und Tabellen von Wahrheitswerten durch, um semantische Folgerungen herauszuarbeiten, und verwenden dieses Theorem, um syntaktische Folgerungen zu bestimmen.

Beweis durch Widerspruch ist eine INDIREKTE Beweismethode: Sie fügen die Negation dessen, was Sie beweisen möchten, bedingt zu Ihren Prämissen in einem Unterbeweis hinzu und zeigen, dass dies zu einem Widerspruch mit einem vorherigen Schritt Ihres Beweises führt. Sie können also klassisch schlussfolgern, dass das, was Sie beweisen wollten, wahr sein muss. Nicht alle Logiken unterstützen diese Form der Argumentation - ich zum Beispiel intuitionistische Logiken nicht, da sie die uneingeschränkte logische Äquivalenz zwischen der Wahrheit einer Aussage und der Verneinung dieser Aussage als falsch akzeptieren.

Wenn ich mit hoher Geschwindigkeit in einen Laternenpfahl lief, blutete meine Nase. Meine Nase blutet nicht. Daher bin ich nicht in einen Laternenpfahl gelaufen.

Sie haben gefragt: "Wenn wir die Wahrheit der Bedingung auf die Wahrheit von p und q stützen, wie können wir dann wissen, dass die Bedingung wahr ist, bevor wir wissen, ob sowohl p als auch q wahr sind?"

Im Beispiel sind p und q beide falsch. Ich bin nicht gegen den Laternenpfahl gelaufen, meine Nase blutet nicht. Aber die Bedingung ist wahr . p -> q ist in drei von vier Fällen wahr: Wenn p und q beide falsch sind, wenn sie beide wahr sind, und wenn p falsch ist, aber q wahr ist. Sie ist nur dann falsch, wenn p wahr und q falsch ist.