• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Dowód - matematyka

    Przeczytaj także...
    Dowód niekonstruktywny - rodzaj dowodu matematycznego istnienia pewnych obiektów (zbiorów, liczb, figur geometrycznych o pewnych własnościach), zwykle nie wprost, w którym wykazuje się, że nieprawdziwość tezy twierdzenia prowadziłaby do sprzeczności, z czego wyciąga się wniosek o jej spełnieniu (a więc istnieniu rozpatrywanego rodzaju obiektów) bez podania jakiegokolwiek sposobu ich konstruowania.Lemat – w matematyce twierdzenie pomocnicze, którego głównym zastosowaniem jest uproszczenie dowodów innych, bardziej istotnych twierdzeń. Formalnie jednak każdy lemat jest pełnoprawnym twierdzeniem, a zaklasyfikowanie pewnego twierdzenia jako lematu wynika jedynie ze sposobu jego użycia w innym, obszerniejszym kontekście. Często zdarzało się, że lemat zyskiwał sobie o wiele większe znaczenie od pierwotnego, znajdując szersze zastosowanie i stając się w zasadzie samodzielnym twierdzeniem, którego nazwa wynika z uwarunkowań historycznych.
    Język w logice matematycznej to pewien zbiór symboli, przy użyciu których można tworzyć bardziej złożone wyrażenia (na przykład formuły, zdania) według ściśle określonych reguł syntaktycznych. Przyjmuje się, że w danym języku L mogą występować (w dowolnej ilości) symbole funkcyjne, relacyjne oraz symbole stałych. Zdania napisane przy użyciu języków tego typu wystarczają do opisu większości własności dowolnych struktur matematycznych oraz do wyrażenia twierdzeń mówiących o tych strukturach.

    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 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ść), c.b.d.o. (co było do okazania) lub podobnym.

    Aksjomat wyboru (ozn. AC od ang. Axiom of Choice) – jeden z aksjomatów teorii mnogości mówiący o możliwości skonstruowania zbioru (nazywanego selektorem) zawierającego dokładnie po jednym elemencie z każdego zbioru należącego do rodziny niepustych zbiorów rozłącznych.Hipoteza continuum (skr. CH, od ang. continuum hypothesis) – postawiona przez Georga Cantora hipoteza teorii mnogości dotycząca mocy zbiorów liczb naturalnych i liczb rzeczywistych.

    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 , gdzie jest całkowite; suma dwóch liczb parzystych wynosi , 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ć spośród 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 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 ma pierwiastek rzeczywisty, zauważmy, że przyjmuje on wartość ujemną dla i dodatnią dla . Ponieważ jest funkcją ciągłą, z twierdzenia Cauchy'ego wynika, że wielomian ma miejsce zerowe w przedziale . 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.

    Aksjomat (postulat, pewnik) (gr. αξιωμα [aksíoma] – godność, pewność, oczywistość) – jedno z podstawowych pojęć logiki matematycznej. Od czasów Euklidesa uznawano, że aksjomaty to zdania przyjmowane za prawdziwe, których nie dowodzi się w obrębie danej teorii matematycznej. We współczesnej matematyce definicja aksjomatu jest nieco inna:Dowód wprost, dowód zwyczajny lub klasyczny, to inna od dowodu nie wprost forma dowodzenia w systemie założeniowym rachunku zdań, w której prawdziwość tezy dowodzi się bezpośrednio poprzez dedukcję - z założeń twierdzenia i aksjomatów teorii (ustalonych reguł).

    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 jest aksjomatem lub jest wnioskiem z przesłanek (gdzie ) wyprowadzonym przez zastosowanie przyjętej reguły dedukcyjnej.

    Dedukcja to rodzaj rozumowania logicznego, mającego na celu dojście do określonego wniosku na podstawie założonego wcześniej zbioru przesłanek. Rozumowanie dedukcyjne w odróżnieniu od rozumowania indukcyjnego jest w całości zawarte wewnątrz swoich założeń, to znaczy nie wymaga tworzenia nowych twierdzeń czy pojęć, lecz jest tylko prostym wyciąganiem wniosków. Jeśli jest przeprowadzone poprawnie, zaś zbiór przesłanek nie zawiera zdań fałszywych, to wnioski wyciągnięte w wyniku rozumowania dedukcyjnego są nieodparcie prawdziwe i nie można ich zasadnie zakwestionować.W matematyce, termin indukcja matematyczna używany jest na określenie szczególnej metody dowodzenia twierdzeń (w najbardziej typowych przypadkach o liczbach naturalnych), ale także jest on używany na oznaczenie konstrukcji pewnych obiektów.

    Jeżeli dany ciąg jest dowodem formalnym przy zbiorze aksjomatów to mówi się, że jest to dowód formalny dla z oraz że da się dowieść z

    Łańcuch Eulera (droga Eulera, ścieżka Eulera, szlak Eulera) to taka ścieżka w grafie, która przechodzi przez każdą jego krawędź dokładnie raz. Jeżeli w danym grafie możliwe jest utworzenie takiej drogi, to jest on nazywany grafem półeulerowskim.Forsing (ang. forcing) – metoda dowodzenia niesprzeczności i niezależności zdań teorii mnogości względem aksjomatów Zermelo-Fraenkela.

    Zobacz też[]

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



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    q.e.d. – skrót od łacińskiego zwrotu Quod erat demonstrandum (co było do udowodnienia). Najpowszechniej stosowanymi polskimi odpowiednikami są skróty c.n.d. ("czego należało dowieść"), c.b.d.u. ("co było do udowodnienia"), c.b.d.o. ("co było do okazania") oraz c.k.d. ("co kończy dowód").
    Dowód nie wprost (dowód apagogiczny, dowód sokratejski, łac. reductio ad absurdum - sprowadzenie do sprzeczności), to forma dowodu logicznego, w którym z założenia o nieprawdziwości tezy wyprowadza się sprzeczność ze zdaniem prawdziwym (założenie nieprawdziwości twierdzenia prowadzi do sprzeczności), co pozwala przyjąć że zaprzeczenie tezy jest fałszywe, a sama teza prawdziwa. Inaczej sposób dowodzenia twierdzeń przez wykazanie sprzeczności między zaprzeczeniem dowodzonej tezy a przyjętymi założeniami.
    Twierdzenie o czterech barwach – dla każdego skończonego grafu planarnego ( V , E ) {displaystyle left(V,E ight)} istnieje funkcja k : V → { k 1 , k 2 , k 3 , k 4 } {displaystyle k:,V ightarrow left{k_{1},k_{2},k_{3},k_{4} ight}} , taka że ∀ { v 1 , v 2 } ∈ E ( k ( v 1 ) ≠ k ( v 2 ) ) {displaystyle forall _{{v_{1},v_{2}}in E}left(k(v_{1}) eq k(v_{2}) ight)} , czyli możliwe jest przypisanie każdemu z jego wierzchołków jednej z czterech liczb 1, 2, 3 i 4 w taki sposób, aby żadne sąsiednie wierzchołki nie miały przyporządkowanej tej samej liczby. Jest to jeden z najsłynniejszych problemów matematycznych.
    Indukcja matematyczna – metoda dowodzenia twierdzeń o prawdziwości nieskończonej liczby stwierdzeń oraz definiowania rekurencyjnego (zob. osobna sekcja). W najbardziej typowych przypadkach dotyczą one liczb naturalnych.
    W logice matematycznej teorią nazywamy niesprzeczny zbiór zdań. Dokładniej, niech T będzie zbiorem zdań zapisanych w pewnym języku L. Wtedy T jest teorią, jeśli nie istnieje zdanie napisane w języku L takie że T dowodzi zarówno tego zdania, jak i jego zaprzeczenia. Zbiór zdań T dowodzi zdania X, jeśli można przeprowadzić formalny dowód zdania X przy użyciu zdań ze zbioru T oraz aksjomatów i reguł dowodzenia klasycznego rachunku logicznego.
    Heurystyka (gr. heuresis – odnaleźć, odkryć, heureka – znalazłem) - w informatyce metoda znajdowania rozwiązań, dla której nie ma gwarancji znalezienia rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązań tych używa się np. wtedy, gdy pełny algorytm jest z przyczyn technicznych zbyt kosztowny lub gdy jest nieznany (np. przy przewidywaniu pogody lub przy wykrywaniu niektórych zagrożeń komputerowych, takich jak wirusy lub robaki). Metody używa się też często do znajdowania rozwiązań przybliżonych, na podstawie których później wylicza się ostateczny rezultat pełnym algorytmem. To ostatnie zastosowanie szczególnie dotyczy przypadków, gdy heurystyka jest wykorzystywana do nakierowywania pełnego algorytmu ku optymalnemu rozwiązaniu, aby zmniejszyć czas działania programu w typowym przypadku bez poświęcania jakości rozwiązania (np. algorytm A*).
    Problem stopu – zagadnienie algorytmiczne odpowiadające dla danego algorytmu na pytanie, czy realizujący go program zatrzyma się (w skończonym czasie); pytanie może dotyczyć konkretnych danych wejściowych albo wszystkich możliwych. O programie, który zatrzymuje się dla wszystkich możliwych danych mówi się, że ma własność stopu.

    Reklama