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

Dodane 4308 bajtów ,  10 lat temu
m
Wycofano edycje użytkownika 62.87.179.164 (dyskusja). Autor przywróconej wersji to Luckas-bot.
Znacznik: usuwanie dużej ilości tekstu (filtr nadużyć)
m (Wycofano edycje użytkownika 62.87.179.164 (dyskusja). Autor przywróconej wersji to Luckas-bot.)
'''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.
 
== Metody dowodu ==
1. Dowód wprost
O ile nie istnieje żaden wyczerpujący podział dowodów, można wyróżnić niektóre metody używane w dowodach:
2. Dowód nie wprost
* '''[[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 ==
32 970

edycji