Dowód (matematyka): Różnice pomiędzy wersjami

[wersja przejrzana]

[wersja nieprzejrzana]

Usunięta treść Dodana treść

Jednokolumnowy

Wersja z 17:24, 19 sty 2011

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.

1. Dowód wprost 2. Dowód nie wprost

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},\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ż

Szablon:Link FA Szablon:Link FA

@@ Linia 1: / Linia 1: @@
 '''Dowód''' – w matematyce wykazanie, że pewne zdanie jest prawdziwe. Dowód należy odróżnić od empirycznego lub [[heurystyka (informatyka)|heurystycznego]] rozumowania. Każdy krok dowodu musi jasno wynikać z poprzednich lub być przyjętym [[aksjomat]]em; 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 [[teoria (logika)|teorii]]. Zwyczajowo koniec dowodu oznacza się skrótem [[QED|q.e.d]] (quod erat demonstrandum), c.n.d. (co należało dowieść) lub podobnym.
+. Dowód wprost
-== Metody dowodu ==
+. Dowód nie wprost
-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 <math>2k</math>, gdzie <math>k</math> jest całkowite; suma dwóch liczb parzystych wynosi <math>2k+2l=2(k+l)</math>, 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 <math>\sqrt{2}</math> 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 <math>n,k \geqslant 1</math> zachodzi <math>\tbinom{n}{k}=\tbinom{n-1}{k} + \tbinom{n-1}{k-1}</math>. Wyobraźmy sobie, że mamy wybrać <math>k</math> spośród <math>n</math> osób. Możemy to zrobić na <math>\tbinom{n}{k}</math> sposobów. Możemy wyróżnić jedną z osób, nazwijmy ją X. Jeżeli wybierzemy X-a, to pozostanie nam <math>\tbinom{n-1}{k-1}</math> sposobów na wybranie pozostałych osób. Jeżeli nie wybierzemy X-a, to pozostanie nam <math>\tbinom{n-1}{k}</math> sposobów. Te możliwości są wyczerpujące i rozłączne; zatem <math>\tbinom{n}{k}=\tbinom{n-1}{k} + \tbinom{n-1}{k-1}</math>.
-[[Plik:Pythagorean proof.svg|thumb|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 [[dowód niewymierności pierwiastka z dwóch#Dowód geometryczny|geometryczny dowód niewymierności pierwiastka z 2]])
-* '''[[Dowód indukcyjny]]''' to dowód wykorzystujący zasadę [[indukcja matematyczna|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ść [[problem stopu|problemu stopu]].
-* Użycie wspomagania komputerowego, np. dowód [[twierdzenie o czterech barwach|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 [[hipoteza continuum|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 <math>x^3-8</math> 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 [[droga Eulera|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 <math>x^3-8</math> ma pierwiastek rzeczywisty, zauważmy, że przyjmuje on wartość ujemną dla <math>x=0</math> i dodatnią dla <math>x=100</math>. Ponieważ <math>y=x^3-8</math> jest funkcją ciągłą, z [[twierdzenie Darboux#Twierdzenie Cauchy'ego|twierdzenia Cauchy'ego]] wynika, że wielomian ma miejsce zerowe w przedziale <math>(0,100)</math>. Innym przykładem jest wykorzystanie [[zasada szufladkowa Dirichleta|zasady szufladkowej Dirichleta]].
-* '''Dowód nieefektywny''' to dowód wykorzystujący [[aksjomat wyboru]].
-W złożonych, wielostopniowych dowodach wykorzystuje się twierdzenia pomocniczne, tzw. [[lemat]]y.
 == Dowód formalny ==