Bedingter Nachweis - Conditional proof
Ein bedingter Beweis ist ein Beweis , der die Form der Behauptung eines Bedingten annimmt und beweist, dass der Vorläufer des Bedingten notwendigerweise zum Konsequenz führt .
Überblick
Der angenommene Vorläufer eines bedingten Beweises wird als bedingte Beweisannahme ( CPA ) bezeichnet. Somit besteht das Ziel eines bedingten Beweises darin zu zeigen, dass, wenn der CPA wahr wäre, die gewünschte Schlussfolgerung notwendigerweise folgt . Die Gültigkeit eines bedingten Beweises setzt nicht voraus, dass der CPA wahr ist, sondern nur, dass er, wenn er wahr wäre, zum Konsequenz führen würde.
Bedingte Beweise sind in der Mathematik von großer Bedeutung . Bedingte Beweise existieren, die mehrere ansonsten unbewiesene Vermutungen verbinden , so dass ein Beweis einer Vermutung sofort die Gültigkeit mehrerer anderer implizieren kann. Es kann viel einfacher sein, die Wahrheit einer Aussage aus einer anderen Aussage zu zeigen, als sie unabhängig zu beweisen.
Ein berühmtes Netzwerk bedingter Beweise ist die NP-vollständige Klasse der Komplexitätstheorie. Es gibt eine große Anzahl interessanter Aufgaben (siehe Liste der NP-vollständigen Probleme ), und obwohl nicht bekannt ist, ob für irgendeine von ihnen eine Lösung in polynomieller Zeit existiert, ist bekannt, dass, falls eine solche Lösung für einige von ihnen existiert, für alle existiert einer. Ebenso hat die Riemann-Hypothese viele bereits bewiesene Konsequenzen.
Symbolische Logik
Als Beispiel für einen bedingten Beweis in der symbolischen Logik nehmen wir an, wir wollen A → C (wenn A, dann C) aus den ersten beiden Prämissen unten beweisen:
| 1. | A → B | ("Wenn A, dann B") |
| 2. | B → C | ("Wenn B, dann C") |
|
|
||
| 3. | EIN | (bedingte Beweisannahme, "Angenommen, A ist wahr") |
| 4. | B | (folgt aus Zeile 1 und 3, modus ponens ; "Wenn A dann B; A, also B") |
| 5. | C | (folgt aus Zeile 2 und 4, modus ponens ; "Wenn B, dann C; B, also C") |
| 6. | A → C | (folgt aus Zeile 3–5, bedingter Beweis; "Wenn A, dann C") |
Siehe auch
Verweise
- Robert L. Causey, Logik, Mengen und Rekursion , Jones und Barlett, 2006.
- Dov M. Gabbay, Franz Guenthner (Hrsg.), Handbuch der philosophischen Logik , Band 8, Springer, 2002.