Dowód (matematyka)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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

Dowód formalny[edytuj | edytuj kod]

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,\ldots,\,p_n 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  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 .

Zobacz też[edytuj | edytuj kod]

Zobacz hasło dowód w Wikisłowniku