Dowód – w matematyce 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 nie speł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ść) 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 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 zachodzi . Wyobraźmy sobie, że mamy wybrać k spośród n osób. Możemy to zrobić na sposobów. Możemy wyróżnić jedną z osób, nazwijmy ją X. Jeżeli wybierzemy X-a, to pozostanie nam sposobów na wybranie pozostałych osób. Jeżeli nie wybierzemy X-a, to pozostanie nam sposobów. Te możliwości są wyczerpujące i rozłączne; zatem .

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³ − 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³ − 8 ma pierwiastek rzeczywisty, zauważmy, że przyjmuje on wartość ujemną dla x = 0 i dodatnią dla x = 100. Ponieważ y = x³ − 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 pomocniczne, tzw. lematy .

Dowód formalny

W teorii sformalizowanej dowód przyjmuje ścisłą formę tak zwanego dowodu formalnego, który jest skończonym ciągiem wyrażeń ustalonego języka sformalizowanego, takim że dla każdego i = 1,...,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 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.

Zobacz też

• automatyczne dowodzenie twierdzeń
• teoria dowodu
• dowód formuły zdaniowej w oparciu o zbiór aksjomatów klasycznego rachunku predykatów