Dowód (matematyka)

Zobacz też: inne znaczenia słowa „dowód”.

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 ${\displaystyle 2k,}$ gdzie ${\displaystyle k}$ jest całkowite; suma dwóch liczb parzystych wynosi ${\displaystyle 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 ${\displaystyle {\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 ${\displaystyle n,k\geqslant 1}$ zachodzi ${\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k}}+{\tbinom {n-1}{k-1}}.}$ Wyobraźmy sobie, że mamy wybrać ${\displaystyle k}$ spośród ${\displaystyle n}$ osób. Możemy to zrobić na ${\displaystyle {\tbinom {n}{k}}}$ sposobów. Możemy wyróżnić jedną z osób, nazwijmy ją X. Jeżeli wybierzemy X-a, to pozostanie nam ${\displaystyle {\tbinom {n-1}{k-1}}}$ sposobów na wybranie pozostałych osób. Jeżeli nie wybierzemy X-a, to pozostanie nam ${\displaystyle {\tbinom {n-1}{k}}}$ sposobów. Te możliwości są wyczerpujące i rozłączne; zatem ${\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k}}+{\tbinom {n-1}{k-1}}.}$

• 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 ${\displaystyle 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 ${\displaystyle x^{3}-8}$ ma pierwiastek rzeczywisty, zauważmy, że przyjmuje on wartość ujemną dla ${\displaystyle x=0}$ i dodatnią dla ${\displaystyle x=100.}$ Ponieważ ${\displaystyle y=x^{3}-8}$ jest funkcją ciągłą, z twierdzenia Cauchy’ego wynika, że wielomian ma miejsce zerowe w przedziale ${\displaystyle (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)^[1];
2. rola wyjaśniająca (pozwala znaleźć powód dla którego dane twierdzenie jest prawdziwe)^[1];
3. rola wyjaśniająca (pozwala uzyskać społeczną aprobatę)^[1];
4. rola systemacyzacyjna (pozwala uporządkować różne wyniki zgodnie z systemem głównych pojęć i twierdzeń)^[1];
5. rola komunikacyjna (pozwala przekazywać innym gotowe wyniki i obserwacje)^[1];
6. rola estetyczna (pozwala dane rozumowanie zapisać w sposób elegancki i klarowny)^[1];
7. rola satysfakcjonująca (pozwala odczuć satysfakcję, radość, dumę i uczucie odniesienia sukcesu po skutecznym przeprowadzeniu dowodu)^[1];
8. rola transferowa (pozwala zachować techniki dowodowe, które mogą okazać się przydatne w dowodzeniu lub zrozumieniu innych twierdzeń)^[1].

Dowód formalny

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

Jeżeli dany ciąg ${\displaystyle p_{1},p_{2},\dots ,p_{n}}$ jest dowodem formalnym przy zbiorze aksjomatów ${\displaystyle A,}$ to mówi się, że jest to dowód formalny dla ${\displaystyle p_{n}}$ z ${\displaystyle A}$ oraz że ${\displaystyle p_{n}}$ da się dowieść z ${\displaystyle A.}$

Dowodem formuły ${\displaystyle A,}$ w oparciu o zbiór formuł ${\displaystyle X}$ nazywamy każdy skończony ciąg formuł ${\displaystyle D_{1},D_{2},D_{3},\dots ,D_{n}}$ taki, że ${\displaystyle D_{n}=A}$ (czyli ostatnia formuła w tym ciągu jest identyczna z formułą dowodzoną) oraz dla każdego wskaźnika ${\displaystyle k<}$ ${\displaystyle n}$ spełniony jest przynajmniej jeden z nastepujących warunków:

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

Zobacz też

Zobacz hasło dowód w Wikisłowniku

• automatyczne dowodzenie twierdzeń
• teoria dowodu

Przypisy

Linki zewnętrzne

• MarcusM. Giaquinto MarcusM., The Epistemology of Visual Thinking in Mathematics, [w:] Stanford Encyclopedia of Philosophy, CSLI, Stanford University, 2 października 2015, ISSN 1095-5054 [dostęp 2018-08-07]  (ang.). (Epistemologia myślenia wzrokowego w matematyce) – artykuł m.in. o dowodach graficznych