Dowód warunkowy

Dowód warunkowy to dowód , który przybiera formę twierdzenia warunku i udowodnienia, że poprzednik warunku warunkowego koniecznie prowadzi do następnika .

Przegląd

Zakładany poprzednik dowodu warunkowego nazywany jest założeniem dowodu warunkowego ( CPA ). Zatem celem dowodu warunkowego jest wykazanie, że gdyby CPA było prawdziwe, to z konieczności wynika pożądany wniosek . Ważność dowodu warunkowego nie wymaga, aby CPA było prawdziwe, a jedynie, że gdyby było prawdziwe , prowadziłoby do następnika.

Dowody warunkowe mają ogromne znaczenie w matematyce . Istnieją dowody warunkowe łączące kilka nieudowodnionych w inny sposób przypuszczeń , tak że dowód jednej hipotezy może natychmiast implikować ważność kilku innych. O wiele łatwiej jest pokazać prawdziwość twierdzenia wynikającego z innego twierdzenia niż udowodnić je niezależnie.

Słynną siecią dowodów warunkowych jest NP-zupełna klasa teorii złożoności. Istnieje wiele interesujących zadań (patrz Lista problemów NP-zupełnych ) i chociaż nie wiadomo, czy dla któregokolwiek z nich istnieje rozwiązanie w czasie wielomianowym, wiadomo, że jeśli takie rozwiązanie istnieje dla niektórych z nich, jeden istnieje dla nich wszystkich. Podobnie hipoteza Riemanna ma wiele konsekwencji, które zostały już udowodnione.

Logika symboliczna

Jako przykład dowodu warunkowego w logice symbolicznej załóżmy, że chcemy udowodnić A → C (jeśli A, to C) z dwóch pierwszych przesłanek poniżej:

1.	A → B	(„Jeśli A, to B”)
2.	B → C	(„Jeśli B, to C”)

3.	A	(warunkowe założenie dowodowe, „Załóżmy, że A jest prawdziwe”)
4.	B	(wynika z wierszy 1 i 3, modus ponens ; „Jeśli A to B; A, więc B”)
5.	C	(wynika z wierszy 2 i 4, modus ponens ; „Jeśli B to C; B, więc C”)
6.	A → C	(wynika z wierszy 3–5, dowód warunkowy; „Jeśli A, to C”)

Zobacz też

Robert L. Causey, Logika, zbiory i rekurencja , Jones i Barlett, 2006.
Dov M. Gabbay, Franz Guenthner (red.), Podręcznik logiki filozoficznej , tom 8, Springer, 2002.