Wie kann man wissen, ob A⟹BA⟹BA \impliziert, dass B (eine Implikation) wahr ist, ohne zu wissen, ob BBB (die Konsequenz) wahr ist?

Betrachten Sie die folgenden Aussagen:

$A$: Adam lebt in Boston;$B$: Adam lebt in Massachusetts.

Sie haben Adam noch nie zuvor getroffen, und Sie haben keine Ahnung, ob Aussagen$A$oder$B$sind wahr. Aber Sie wissen, dass die Aussage$A \Rightarrow B$ist wahr. Wenn ich Ihnen jetzt einen Weg vorstelle, um zu beweisen, dass Adam in Boston lebte, könnten Sie vernünftigerweise schlussfolgern, dass er in Massachusetts lebt.

Ich nehme an, Sie würden einer Aussage wie „Wenn es regnet, werden die Straßen nass“ zustimmen, oder?

Nun, bevor Sie der Wahrheit dieser Bedingung zugestimmt haben, haben Sie aus dem Fenster geschaut, um zu sehen, ob es gerade regnet oder nicht, und ob die Straßen gerade nass werden oder nicht? Nein, eindeutig nicht.

Ja, es ist wahr, dass wir oft auf der Grundlage empirischer Beweise zur Wahrheit von Konditionalen gelangen, dh vermutlich auf einer Reihe von Fällen, in denen wir beobachten, dass der Antezedens wahr ist und der Konsequens ebenfalls wahr ist ... und auch Fälle nicht sehen, in denen der Antezedens ist wahr und daraus folgend falsch. Solche Bedingungen werden zwar durch nicht-deduktives Denken, aber durch induktive Verallgemeinerungen oder andere solche Argumente festgelegt. Es gibt hier also keine Zirkularität der Argumentation.

Außerdem werden einige Bedingungen einfach als Teil einer Definition oder eines Axioms behauptet, sodass in diesem Fall Beobachtungen, ob y-Aussagen tatsächlich wahr oder falsch sind, überhaupt nicht verwendet werden.

Außerdem sind Konditionale oft Teil von universellen Aussagen. Das „Wenn es regnet, werden die Straßen nass“ kann man eigentlich auch so sehen: Es ist wirklich eine universelle Aussage über jeden Ort und jede Zeit. Also ist es wirklich das Universelle, das wir entweder auf der Grundlage vieler Beobachtungen aufstellen oder einfach als Axiom behaupten, und so stellen wir die Wahrheit dieses Universellen sicher nicht unter der Bedingung einer einzigen Beobachtung fest, ob der Vordersatz und der Nachsatz wahr oder falsch sind.

Schließlich können wir, sobald Konditionale festgelegt sind, sie einfach verwenden, ohne uns Gedanken darüber machen zu müssen, ob der Antezedens tatsächlich wahr oder falsch ist oder ob die Konsequenz wahr oder falsch ist. In der Praxis gibt es hier also wirklich kein Henne-Ei-Problem.

So wie Sie dachten, dass Mathematik funktioniert, oder besser gesagt, informelle Theorembeweise, so funktioniert es. Die klassische Aussagenlogik ist ein kleines Fragment der Argumentationswerkzeuge, die von typischen informellen Argumenten verwendet werden, und allgemeiner passt ein semantischer Ansatz zur Logik nicht gut zum Beweisprozess, also zur Beweistheorie.

Es gibt zwei breite Ansätze zum Verständnis der (formalen) Logik: einen syntaktischen oder beweistheoretischen Ansatz und einen semantischen oder modelltheoretischen Ansatz.

Die Verwendung von Wahrheitstabellen und Wahrheitsfunktionalen ist ein semantischer Ansatz. Hier interpretieren wir die syntaktischen Formeln in mathematische Objekte und dann, ob die "Wahrheit" einer Aussage eine Eigenschaft des mathematischen Objekts wird, als das sie interpretiert wird. Zum Beispiel können wir die Sätze interpretieren$A$Und$B$als Untermengen$[\![A]\!]$Und$[\![B]\!]$eines Satzes$X$. Fragt ob$A\lor B$"wahr" ist, wird die Aussage, dass$[\![A]\!]\cup[\![B]\!]=X$. Beachten Sie, dass dies nichts damit zu tun hat, ob$A$oder$B$sind philosophisch „wahr“. Die Interpretation der Aussage fragt nur, ob die Vereinigung zweier Mengen gleich einer anderen ist. Das Beweisen oder Widerlegen dieser Aussage erfolgt normalerweise informell, könnte aber auch formal erfolgen, in diesem Fall zB mit der Zermelo-Fraenkel-Mengentheorie. Natürlich können wir diese semantische Aussage nicht genau auf die gleiche Weise beweisen. Dies führt zum anderen Ansatz: der Beweistheorie.

Eine andere Art zu verstehen, was in der Logik vor sich geht, besteht darin, Regeln anzugeben. Hier bleiben die syntaktischen Formeln einfach Syntax. Stattdessen geben wir Regeln an, die diese Formeln transformieren, und wir nennen bestimmte Formeln Axiome. Sätze sind dann alle Formeln, die wir erhalten können, indem wir die Regeln auf die Axiome anwenden. Dies ist viel mehr wie der "mechanische" Prozess, auf den Sie anspielen. In der Tat ist dies das, was Theorembeweisprogramme tun. Die philosophische Idee ist, dass Axiome für Dinge stehen sollen, die "wahr" sind, und die Regeln "Wahrheit bewahren" sollen, aber es ist alles nur Symboldruck. Dabei spielt es für die Regeln keine Rolle, ob die Formeln wahr sind oder nicht oder gar widersprüchlich sind. Für typische Logiken bedeutet aus beweistheoretischer Sicht alle Inkonsistenz, dass alleFormel kann aus den Axiomen durch die Regeln erreicht werden. (Inkonsistenz bedeutet semantisch normalerweise, dass es kein Modell gibt. In anderen Ansätzen zur Semantik kann es bedeuten, dass es nur "triviale" Modelle gibt.) Der eigentliche Beweis ist dann die Folge von (gültigen) Regelanwendungen und wird Ableitung genannt.

Das Beweissystem, das den Studenten normalerweise zuerst präsentiert wird, ist ein Beweissystem im Hilbert-Stil . Das ist ein bisschen schade, da Beweissysteme im Hilbert-Stil nicht sehr benutzerfreundlich zu handhaben sind. Andere Beweissysteme umfassen natürliche Deduktion und den Folgenkalkül . Ich persönlich verwende gerne natürliche Deduktion durch eine Curry-Howard-Linse. Dies führt zu Beweisen mit einer kompakten, einfachen Darstellung, die die Symbolmanipulation einfach macht. (Die Verbindungen zur Berechnung bieten auch viel Intuition, wenn man mit funktionaler Programmierung vertraut ist.) Beispielsweise entspricht eine Verwendung von Modus Ponens nur der Funktionsanwendung. (Aus dieser Perspektive ist der Mangel an Menschenfreundlichkeit von Beweissystemen im Hilbert-Stil offensichtlicher, da sie der kombinatorischen Logik entsprechenwas sehr unangenehm zu programmieren ist.) Natürliche Deduktionsbeweise (wie der Name vermuten lässt) sollten dem Fluss informeller Beweise näher kommen. Sobald Sie eine anständige Menge an Erfahrung mit informellen Beweisen und mit Systemen wie natürlichen Deduktion haben, ist es eigentlich ziemlich einfach, selbst die feinkörnige logische Struktur eines informellen Beweises als Ableitung in einem natürlichen Deduktionssystem "herauszulesen".

Der syntaktische Ansatz bietet eine direkte Antwort auf Ihre Bedenken, den Wahrheitswert von kennen zu müssen$B$den Wahrheitswert kennen$A\Rightarrow B$modus ponens verwenden. Modus ponens ist eine Schlussregel, die einfach besagt, dass, wenn wir eine Ableitung von haben$A$(dh eine Folge gültiger Regelanwendungen) und eine Ableitung von$A\Rightarrow B$, dann können wir eine Ableitung von machen$B$. Ableitung$A\Rightarrow B$muss nicht (und wird normalerweise nicht) voraussetzen, dass bereits eine Ableitung von vorhanden ist$B$. In der Praxis werden die Regeln normalerweise so formuliert, dass sie mit bedingten Formeln arbeiten. Oft werden diese geschrieben wie zB$\varphi,\psi\vdash\chi$(obwohl diese Notation auf verschiedene, aber verwandte Arten verwendet wird), was intuitiv für "es ist beweisbar, dass" stehen soll$\chi$ist wahr, wenn$\varphi$Und$\psi$wahr sind", aber auch hier nur Syntax, die manipuliert wird. Das intuitive Lesen ist nur gerechtfertigt, wenn die Regeln und Axiome es zulassen. Die Verwendung von Bedingungsformeln erleichtert das Einbeziehen von Annahmen erheblich und erleichtert auch das Formulieren der Regeln deutlich einfacher.

Schließlich sind diese beiden Ansätze zur Logik unterschiedlich . Es ist überhaupt nicht a priori klar, dass sie zu demselben Begriff von "Wahrheit" führen. Die Korrektheits- und Vollständigkeits-(Meta-)Theoreme, zB die für FOL , (und die stärkere Vorstellung einer internen Logikwas in die kategoriale Semantik übergeht) sind das, was sie verbindet. Aber Korrektheits- und Vollständigkeitssätze sind (Meta-)Theoreme, die für ein gegebenes Beweissystem und eine gegebene Semantik bewiesen werden müssen. Es ist nicht immer möglich, beides zu beweisen (obwohl normalerweise eine Verletzung der Korrektheit bedeutet, dass Sie etwas sehr Falsches getan haben). Im syntaktischen Ansatz ist ein Beweis eine Ableitung, und daher ist das Überprüfen von Wahrheitstabellen nur ein Non-Sequitur. Selbst wenn die Wahrheitstabellen zeigen, dass eine Formel eine Tautologie ist, liefert Ihnen das keine Ableitung und ist daher syntaktisch unbrauchbar. Der (metalogische) Vollständigkeitsbeweis eines natürlichen Deduktionssystems für die klassische Aussagenlogik in Bezug auf Wahrheitstabellen muss beispielsweise zeigen, wie eine natürliche Deduktionsableitung aufgebaut werden kann, wenn eine Formel gegeben ist und eine Wahrheitstabelle, die die Formel zeigt, gültig ist. Es ist anscheinend ziemlich üblich, dass die syntaktischen und semantischen Herangehensweisen an die Logik erheblich verschmolzen oder zumindest nicht klar getrennt werden, aber dies führt zu viel Verwirrung. (Wenn man zum Beispiel dachte, dass ein Beweis Wahrheitstabellen überprüft, dann machen Solidität und Vollständigkeit nicht einmal Sinn oder erscheinen völlig trivial.)

Wir können tatsächlich beweisen, dass die Implikation$A\implies B$wahr ist, nur das zu wissen$A$ist falsch und überhaupt nichts$B$.

Die einzige Eigenschaft der materiellen Implikation, die wir benötigen, ist die, wenn Sie annehmen$P$und anschließend ableiten können$Q$dann kannst du daraus schließen$P \implies Q$. (Es gelten einige Einschränkungen.)

Satz:

$\neg A \implies [A\implies B]$

Nachweisen:

1. Vermuten$\neg A$

2. Vermuten$A$

3. Angenommen (im Gegenteil).$\neg B$

4. Verbinden Sie (2) und (1), um den Widerspruch zu erhalten$A \land \neg A$

5. Schluß damit$\neg \neg B$aus (3) und (4).

6. Entfernen Sie die doppelte Negation von (5), um zu erhalten$B$.

7. Schluß damit$A\implies B$aus (2) und (6).

8. Schließen Sie, wie erforderlich, dass$\neg A \implies [A\implies B]$aus (1) und (7).

Ebenso können wir auch beweisen:

$A \land B \implies [A\implies B]$

$A \land \neg B \implies \neg [A \implies B]\space$(erfordert auch eine Ablösungsregel)

Auf diese Weise können wir die übliche Wahrheitstabelle für materielle Implikationen rechtfertigen.

Follow-up: Ein anderer Ansatz: Das habe ich bewiesen$[A\implies B] \iff \neg [A \land \neg B]$Verwendung von Ablösungs- und Abzugsregeln. Es wird oft nur als Definition angegeben, was viele Anfänger am Kopf kratzen lässt.$\neg A \implies [A \implies B]$ist eine Folge. Siehe "Wenn Schweine fliegen könnten", heute neu in meinem Mathe-Blog .

Um die konkrete Frage zu beantworten:

wie wir in der Praxis wissen können, dass A⟹B im ersten wahr ist.

Im Allgemeinen haben Sie keine Ahnung, ob die Aussage, dass A materiell B impliziert, WAHR ist oder nicht, wenn Sie mit einer beliebigen Proposition A→B versorgt werden! Das steht zur Debatte!

Wenn Sie einen Beweis schreiben, können Sie jeden Schritt auswählen, den Sie verwenden. Wählen Sie in jedem Schritt A und B aus, für die Sie begründen können, dass A→B wahr ist.

Es gibt Hunderte von allgemein akzeptierten Prinzipien, die Sie als Rechtfertigung verwenden können. Verwenden Sie sie für Schulaufgaben, wenn Sie darauf vertrauen, dass jemand sie bereits geprüft hat. (auch wenn Sie sich nicht sicher sind, was der genaue "Name" ist. Aber wenn Sie zu einem einzelnen Schritt befragt werden, müssen Sie in der Lage sein, dies zu rechtfertigen.)

Allgemeiner:

Der Begriff „Wahrheitstabelle“ ist meiner Meinung nach eine verwirrende und schreckliche Namenswahl.

Schlimmer noch, viele Leute (einschließlich Ausbilder) werden routinemäßig die "Wahrheitstabelle" anführen, die die Beziehung zwischen A , B und A → B als Grund dafür "beweist" , dass A → B WAHR oder FALSCH ist.

Dies zeigt, dass sie NICHT verstehen, wovon sie sprechen.

Das Symbol „ → “, das im Englischen oft als „impliziert“ übersetzt wird, hat in der klassischen Logiksemantik NICHT die gleiche Bedeutung wie das Wort „impliziert“ im Standardenglischen. Das Symbol ist Teil eines Systems, das mathematisch/logische „Objekte“, „Variablen“, „Verknüpfungen“, „Operatoren“ oder „Funktionen“ mit sehr spezifischen Definitionen verwendet. (Ähnlich wie „+“ oder „-“ haben eine bestimmte Definition in der Mathematik.)

Das Symbol „ → “ ist besser definiert als der „materielle Bedingungs-“ oder „materielle Implikations“-Konnektiv/Operator.

" → " ist als Verbindung zwischen zwei anderen "Objekten" definiert und kann als "zwei Eingaben" betrachtet werden. Die Eingänge müssen jeweils mit TRUE oder FALSE ausgewertet werden.

" → " wurde dann DEFINIERT, um EINEN Ausgang zu erzeugen oder aufzulösen, entweder WAHR oder FALSCH.

Die DEFINITION des „ → “-Operators IST die Wahrheitstabelle, auf die so oft verwiesen wird.

Diese obige Tabelle DEFINIERT, wie das „ → “-Symbol, der „Materielle Implikations“- oder „Schlussregel“-Operator/-Verknüpfung, funktioniert.

Warum haben sie es so gewählt? Das ist eine längere Erklärung, und ich behaupte nicht, sie vollständig zu verstehen. Die ersten beiden Zeilen der Tabelle sind intuitiv sinnvoll und gehen Tausende von Jahren auf eine Idee namens Modus Ponens zurück. Die letzten beiden Zeilen der Tabelle? Nun, sie hatten ihre Gründe, und die Definition stimmt mit dem Rest des Systems überein.

( Es ist erwähnenswert , dass, während die dritte Zeile „ A→B “ als WAHR definiert, dies Vacuous Truth genannt wird . Wenn A falsch ist, werden diese Beziehungen in der Praxis NICHT tatsächlich verwendet, um zu rechtfertigen, dass „ B “ WAHR oder sogar WAHR ist dass " A→B " WAHR sein könnte. Wenn A falsch ist, haben Sie im Wesentlichen keine nützlichen Informationen.)

Die klassische Logik definiert auch das Symbol " ⟷ ", das als "Material Biconditional" Connective/Operator bezeichnet wird.

Die Definition von „ ⟷ “ in der folgenden Tabelle entspricht eher dem typischen Verständnis von „impliziert“ im Englischen.

(*) Beispiel für eine Implikation: Wenn ein Snack Zucker enthält, dann ist er süß.

Modus ponens sagt uns, dass wir mit der Prämisse (*) beginnen, und wir wissen auch, dass ein Snack Zucker enthält, dann können wir behaupten, dass der Snack süß sein wird.

Das Beispiel von Wahrheitstabellen und Aussagenlogik verbirgt den größten Teil der Komplexität der eigentlichen Mathematik, die Variablen und Quantifizierer beinhaltet. Anstatt also etwas künstliche Beispiele in der Aussagenlogik zu betrachten, können wir uns natürlichere Beispiele aus der tatsächlichen Mathematik ansehen. Hier ist ein besseres Beispiel für eine Implikation, die wir als wahr beweisen können, obwohl wir nicht wissen, ob die Hypothese wahr oder falsch ist:

Wenn$n$ist dann eine gerade natürliche Zahl$n^2$ist eine gerade natürliche Zahl.

Beweis: Wenn$n$ist dann eine gerade natürliche Zahl$n = 2m$für eine natürliche Zahl$m$. Dann$n^2 = 4m^2 = 2(2m^2)$, So$n^2$ist auch gerade.

In diesem Fall können wir nicht sagen, ob "$n$ist eine gerade natürliche Zahl" wahr oder falsch ist - wir haben keinen spezifischen Wert für$n$. Stattdessen beweisen wir gleichzeitig eine Tatsache über alle natürlichen Zahlen (nämlich, dass wenn sie gerade sind, dann auch ihr Quadrat). Um diese Art von Aussage zu beweisen, „nehmen wir die Hypothese an und beweisen die Schlussfolgerung“ – wir gehen davon aus, dass uns eine ansonsten unbekannte gerade Zahl präsentiert wird$n$, und beweise das$n^2$muss auch gleichmäßig sein.

Die Ausgangspunkte sind unter allem Definitionen. Die Definition einer „gerade Zahl“ erlaubt es uns zu sagen, dass wenn$n$ist dann eine gerade natürliche Zahl$n = 2m$für eine natürliche Zahl$m$. Dies ist bereits eine Implikationsaussage, aber wir "beweisen" sie nicht separat, weil es einfach die Definition von "gerade" ist. In gewissem Sinne beweist der obige Beweis einfach eine kompliziertere Implikation, indem einfachere Implikationen, die bereits bekannt waren, miteinander kombiniert wurden.

Wie könnten wir also Modus Ponens in einem Argument mit unserem Theorem anwenden? Wenn wir diese bestimmte Zahl separat beweisen$C$gerade ist, können wir Modus Ponens und unseren Satz anwenden, um das zu zeigen$C^2$ist auch gerade. Wir müssten ableiten "$C$ist sogar" natürlich getrennt.

• In der formalen Logik

  $$P\to Q$$ ist eine Wahrheitsfunktion ; Ob es also tatsächlich wahr oder falsch ist, hängt von der jeweiligen Kombination von Wahrheitswerten ab$P$Und$Q.$

• Im Kontext der Mathematik die Aussage

  $$P \implies Q$$ (lesen: "$P$impliziert$Q$“) bedeutet nur das$\mathbf{P\to Q}$ ist wahr , dh das$Q$'s Wahrheit ist eine Folge von$P$ist Wahrheit. Deutlich sein:$P \implies Q$sagt nur, dass wenn$P$stimmt dann$Q$muss wahr sein.

  Beachten Sie, dass diese Aussage nur nützlich ist, wenn wir das wissen$P$ist wahr; wenn wir das wissen$P$ist falsch oder weiß nicht$P$Der Wahrheitswert von$P \implies Q$hilft uns nicht, irgendwelche Schlussfolgerungen zu ziehen.

  Viele Sätze in der Mathematik sind von dieser Form. Wenn wir ein solches Theorem anwenden, zitieren wir einige$P \implies Q$Aussage und Annahme/Hypothese (oder Behauptung, basierend auf dem Modell/Szenario) davon$P$wahr ist, dann schließe ich daraus$Q$muss also wahr sein; eine solche Argumentationsform nennt sich Modus Ponens .