Dowód (matematyka)

Dowód – wykazanie, że pewne zdanie jest prawdziwe. Dowód należy odróżnić od empirycznego lub heurystycznego rozumowania. Każdy krok dowodu musi jasno wynikać z poprzednich lub być przyjętym aksjomatem; rozumowanie niespełniające tego warunku nie jest dowodem. Ostatni krok dowodu to udowodnione zdanie, które w ten sposób staje się twierdzeniem danej teorii. Zwyczajowo koniec dowodu oznacza się skrótem q.e.d. (quod erat demonstrandum), c.n.d. (co należało dowieść), c.b.d.o. (co było do okazania) lub podobnym.

Metody dowodu

O ile nie istnieje żaden wyczerpujący podział dowodów, można wyróżnić niektóre metody używane w dowodach:

• Dowód wprost polegający na przyjęciu założeń i bezpośrednim wykazaniu tezy. Przykład: udowodnimy, że suma dwóch liczb parzystych jest liczbą parzystą. Wiemy, że liczby parzyste to takie, które można zapisać w postaci $2k,$ gdzie $k$ jest całkowite; suma dwóch liczb parzystych wynosi $2k+2l=2(k+l),$ co jest również liczbą parzystą, c.n.d.
• Dowód nie wprost (dowód apagogiczny) polegający na przyjęciu, że twierdzenie jest fałszywe i wykazaniu, że dochodzi się do niedorzeczności. Przykładem może być dowód niewymierności pierwiastka z dwóch: załóżmy, że $\sqrt{2}$ jest liczbą wymierną, jednak to założenie prowadzi do sprzeczności.
• Dowód kombinatoryczny to specyficzny rodzaj dowodu używany przy tożsamościach kombinatorycznych, zwykle polegający na policzeniu możliwości ustawień na dwa sposoby. Przykład: Udowodnimy, że dla $n,k⩾1$ zachodzi $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k})+(\genfrac{}{}{0ex}{}{n-1}{k-1}).$ Wyobraźmy sobie, że mamy wybrać $k$ spośród $n$ osób. Możemy to zrobić na $(\genfrac{}{}{0ex}{}{n}{k})$ sposobów. Możemy wyróżnić jedną z osób, nazwijmy ją X. Jeżeli wybierzemy X-a, to pozostanie nam $(\genfrac{}{}{0ex}{}{n-1}{k-1})$ sposobów na wybranie pozostałych osób. Jeżeli nie wybierzemy X-a, to pozostanie nam $(\genfrac{}{}{0ex}{}{n-1}{k})$ sposobów. Te możliwości są wyczerpujące i rozłączne; zatem $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k})+(\genfrac{}{}{0ex}{}{n-1}{k-1}).$

Geometryczny dowód twierdzenia Pitagorasa

• Dowód geometryczny polega na wykorzystaniu metod geometrii, takich jak przystawanie i podobieństwo figur. Dowody geometryczne mogą być wykorzystywane również poza geometrią (patrz geometryczny dowód niewymierności pierwiastka z 2)
• Dowód indukcyjny to dowód wykorzystujący zasadę indukcji matematycznej.
• Metoda przekątniowa to rodzaj rozumowania używany w dowodach, że nie istnieje pewien obiekt. Przykłady twierdzeń, które można udowodnić w ten sposób: zbiór liczb rzeczywistych nie jest przeliczalny, twierdzenie Cantora, nierozwiązywalność problemu stopu.
• Użycie wspomagania komputerowego, np. dowód twierdzenia o czterech barwach. Takie dowody wzbudzają kontrowersje, gdyż niemożliwe jest zweryfikowanie ich przez człowieka. Innym przykładem użycia komputerów jest rozproszony projekt Seventeen or Bust sprawdzający potencjalnych kandydatów na liczby Sierpińskiego.
• Dowód niezależności to dowód, że pewnego zdania nie można udowodnić. Przykładem jest dowód niezależności hipotezy continuum, wykorzystujący forsing.
• Dowód konstruktywny to dowód polegający na znalezieniu pewnego obiektu spełniającego wymagane założenia. Przykład: aby udowodnić, że wielomian $x^3-8$ ma pierwiastek rzeczywisty, wystarczy zauważyć, że jest nim liczba 2. Aby udowodnić, że każdy graf spójny zawierający co najwyżej dwa wierzchołki stopnia nieparzystego ma drogę Eulera, można podać algorytm znajdujący ją.
• Dowód niekonstruktywny to dowód polegający na wykazaniu, że istnieje obiekt spełniający założenia, jednak bez konstrukcji. Przykład: aby udowodnić, że wielomian $x^3-8$ ma pierwiastek rzeczywisty, zauważmy, że przyjmuje on wartość ujemną dla $x=0$ i dodatnią dla $x=100.$ Ponieważ $y=x^3-8$ jest funkcją ciągłą, z twierdzenia Cauchy’ego wynika, że wielomian ma miejsce zerowe w przedziale $(0,100).$ Innym przykładem jest wykorzystanie zasady szufladkowej Dirichleta.
• Dowód nieefektywny to dowód wykorzystujący aksjomat wyboru.

W złożonych, wielostopniowych dowodach wykorzystuje się twierdzenia pomocnicze, tzw. lematy.

Rola dowodu matematycznego

Dowód matematyczny może przyjmować następujące role:

1. rola weryfikacyjna (pozwala stwierdzić poprawność hipotezy);
2. rola wyjaśniająca (pozwala znaleźć powód dla którego dane twierdzenie jest prawdziwe);
3. rola wyjaśniająca (pozwala uzyskać społeczną aprobatę);
4. rola systemacyzacyjna (pozwala uporządkować różne wyniki zgodnie z systemem głównych pojęć i twierdzeń);
5. rola komunikacyjna (pozwala przekazywać innym gotowe wyniki i obserwacje);
6. rola estetyczna (pozwala dane rozumowanie zapisać w sposób elegancki i klarowny);
7. rola satysfakcjonująca (pozwala odczuć satysfakcję, radość, dumę i uczucie odniesienia sukcesu po skutecznym przeprowadzeniu dowodu);
8. rola transferowa (pozwala zachować techniki dowodowe, które mogą okazać się przydatne w dowodzeniu lub zrozumieniu innych twierdzeń).

Dowód formalny

W teorii sformalizowanej dowód przyjmuje ścisłą formę tak zwanego dowodu formalnego, który jest skończonym ciągiem wyrażeń $p_1,p_2,\dots ,p_n$ ustalonego języka sformalizowanego, takim że dla każdego $i=1,\dots ,n:p_i$ jest aksjomatem lub $p_i$ jest wnioskiem z przesłanek $p_j,p_k$ (gdzie $j,k<i$) wyprowadzonym przez zastosowanie przyjętej reguły dedukcyjnej.

Jeżeli dany ciąg $p_1,p_2,\dots ,p_n$ jest dowodem formalnym przy zbiorze aksjomatów $A,$ to mówi się, że jest to dowód formalny dla $p_n$ z $A$ oraz że $p_n$ da się dowieść z $A.$

Dowodem formuły $A,$ w oparciu o zbiór formuł $X$ nazywamy każdy skończony ciąg formuł $D_1,D_2,D_3,\dots ,D_n$ taki, że $D_n=A$ (czyli ostatnia formuła w tym ciągu jest identyczna z formułą dowodzoną) oraz dla każdego wskaźnika $k<$ $n$ spełniony jest przynajmniej jeden z następujących warunków:

• $D_k\in$$X$ (czyli formuła $D_k$ może być wzięta ze zbioru, w oparciu o który dowód jest prowadzony);
• istnieją: wskaźnik $j<$ $k$, formuła $B$ oraz wskaźnik $i$ takie, że $D_k=S(B,p_i,D_j)$ (czyli $D_k$ powstaje z pewnej wcześniejszej formuły $D_j$ przez zastosowanie reguły podstawiania);
• istnieją takie $i,j$, że $i<k,j<k$ oraz $D_j=⌜D_i\to D_k⌝$ (czyli $D_k$ podstaje z pewnych wcześniejszych formuł $D_i$ oraz $D_j$ przez zastosowanie reguły odrywania reguły odrywania)

Zobacz też

• automatyczne dowodzenie twierdzeń
• teoria dowodu

Linki zewnętrzne

• Szablon:Otwarty dostęp Wiktor Bartol, O dowodzeniu, Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej (MiNI PW), kanał „Archipelag Matematyki” na YouTube, 15 września 2017 [dostęp 2024-09-04].
• Szablon:SEP – artykuł m.in. o dowodach graficznych
• Szablon:Otwarty dostęp Roman Murawski, On a Proof in Mathematics, Centrum Kopernika Badań Interdyscyplinarnych – Uniwersytet Jagielloński, kanał „Copernicus” na YouTube, 13 marca 2012 [dostęp 2024-09-04].