Dowód nie wprost


Original: http://zimmer.csufresno.edu/~larryc/proofs/proofs.contradict.html
Copyright: Larry W. Cusick

W dowód przez sprzeczność zakładamy, wraz z hipotez, logiczne zaprzeczenie wyniku chcemy udowodnić, a następnie dotrzeć do pewnego rodzaju sprzeczności. Oznacza to, że jeśli chcemy udowodnić “Jeśli P, to Q”, zakładamy, P i Q. Nie sprzeczność docieramy mogą być niektóre wnioski sprzeczne jedno z naszych założeń, czy coś oczywiście nieprawdziwych, jak 1 = 0. Przeczytaj dowód irracjonalności pierwiastka kwadratowego z 2 we wprowadzaniu na przykład.

Oto kilka przykładów.
Nieskończenie wiele liczb pierwszych
Jednym z pierwszych dowodów przez sprzeczność jest następujący klejnot nadana Euklidesa.

Twierdzenie. Istnieje nieskończenie wiele liczb pierwszych.

Dowód. Załóżmy przeciwnie, że istnieje tylko skończenie wiele liczb pierwszych, a wszystkie z nich są wymienione w następujący sposób: i P1 P2 …, pn. Rozważmy liczbę q = p1p2 … pn + 1.? Liczba q jest albo główny lub kompozytu. Jeśli podzielić cały wyszczególniony pi Primes do q, nie spowoduje resztę z 1 dla każdego i = 1, 2, …, n. Tak więc, q nie może być złożony. Wnioskujemy, że q jest liczbą pierwszą, a nie wśród liczb pierwszych wymienionych powyżej, sprzeczne z naszym założeniem, że wszystkie liczby pierwsze są w p1 lista, P2 …, pn.
q

Dowód nie wprost jest często stosowany gdy chcesz udowodnić niemożność czegoś. Można zakładać, że jest możliwe, a następnie dotrzeć sprzeczność. W poniższych przykładach używamy tego pojęcia, aby udowodnić niemożność niektórych rodzajów rozwiązań pewnych równań.
Przykład: Równanie diofantycznych
Diofantycznych równanie jest równaniem, dla których szukacie całkowite rozwiązania. Na przykład tak zwanych trójek pitagorejskich (x, y, z) są dodatnie całkowite rozwiązania równania x2 + y2 = z2. Oto kolejny.

Twierdzenie. Brak pozytywnych całkowite rozwiązania tego równania diofantycznych X2 – y2 = 1.

Dowód. (Dowód przez sprzeczność.) Załóżmy przeciwnie, że istnieje rozwiązanie (x, y) gdzie x i y są liczbami całkowitymi dodatnimi. Jeśli tak jest, możemy czynnik lewej: x2 – y2 = (xy) (x + y) = 1. Ponieważ x i y są liczbami całkowitymi, wynika, że albo xy = 1 i x + y = 1 lub xy = -1 oraz x + y = -1. W pierwszym przypadku możemy dodać dwa równania, aby uzyskać x = 1, y = 0, sprzeczne z naszym założeniem, że x i y są pozytywne. Drugi przypadek jest podobny, coraz x = -1 i y = 0, ponownie sprzeczne z naszym założeniem.
q
Przykład: Rational Roots
Jest wzór na rozwiązanie ogólne równania sześciennego x3 + b 2 cx + d = 0, to jest bardziej skomplikowane niż qaudratic równania. Ale w tym przykładzie, chcemy udowodnić, nie ma racjonalnego korzenia do danego równania sześciennego bez spojrzeć na wzorze ogólnym sześcienny.

Twierdzenie. Nie ma żadnych racjonalnych rozwiązań liczby do równania x3 + x + 1 = 0.

Dowód. (Dowód przez sprzeczność.) Załóżmy przeciwnie istnieje liczba wymierna p / q, w zmniejszonym formacie, z P nie równa się zeru, że spełnia równanie. Następnie mamy p3/q3 + p / q + 1 = 0. Po pomnożeniu każdej strony równania przez Q3, dostajemy równanie

p3 + p q2 + q3 = 0

Istnieją trzy przypadki, które należy rozważyć. (1) Jeżeli p i q są zarówno nieparzyste, następnie lewa strona powyższego równania jest nieparzysta. Ale zero nie jest dziwne, który pozostawia nam sprzeczność. (2) Jeżeli p jest nawet i q jest nieparzyste, to lewa strona jest dziwne, znowu sprzeczność. (3) Jeżeli p jest nieparzysta i q jest nawet, mamy tę samą sprzeczność. Czwarta sprawa – p i q nawet nawet – nie jest posssible bo założyliśmy, że p / q jest w ograniczonej formie. To kończy dowód.
q
Converse z twierdzenia
Converse z “Jeśli P, to Q” jest twierdzenie “Jeśli Q, to P”. Na przykład, converse “Jeśli to jest mój samochód, to czerwony” “Jeśli samochód jest czerwony, to jego moja.” Powinno być jasne, z tym przykładzie, że nie ma gwarancji, że odwrotnie prawdziwego stement jest prawdą.

Dowód nie wprost jest często najbardziej naturalny sposób udowodnić converse już udowodnił twierdzenia.
Converse z twierdzenia Pitagorasa
Twierdzenie Pitagorasa mówi nam, że w trójkąta prostokątnego, istnieje prosta zależność pomiędzy tymi dwoma długości nóg (A i B) i długości przeciwprostokątnej, c, z trójkąta prostokątnego: a2 + b2 = c2. Być może nie wiesz, że odwrót.

Converse twierdzenia Pythagporean. Jeśli (niezerowe) trzy długość boku trójkąta – A, B i C – spełniać a2 + b2 = stosunek c2, to trójkąt jest trójkąt prostokątny. (Załóżmy, że twierdzenie Pitagorasa zostało już udowodnione.)

Dowód. (Dowód przez sprzeczność.) Załóżmy, że trójkąt nie jest trójkąt prostokątny. Oznaczyć wierzchołki A, B i C jak na zdjęciu. (Istnieją dwa możliwościach miary kąta C: mniej niż 90 stopni ust zdjęcie po lewej) lub większym niż 90 stopni (po prawej zdjęcie)).

Wybudować linię pionową płytę segmentu jak na obrazku poniżej.Przez twierdzenie Pitagorasa, BD2 = a2 + b2 = c2, a więc BD = c. Mamy więc równoramienny trójkąty ACD i Abd. Wynika z tego, że mamy przystających kątach CDA znaku = CAD i BDA = DAB. Ale to w sprzeczności z widocznych nierówności (patrz zdjęcie) BDA <CDA = CAD <DAB (zdjęcie po lewej) lub DAB <CAD = CDA <BDA (prawe zdjęcie).
q
ćwiczenia
Użyj metody dowodu nie wprost udowodnić każdy z następujących czynności.

Pierwiastek sześcienny z 2 jest irracjonalna.

Brak pozytywnych całkowite rozwiązania tego równania diofantycznych X2 – y2 = 10.

Nie ma żadnego racjonalnego rozwiązania liczbę do równania x5 + x4 + x3 + x2 + 1 = 0.

Jeśli jest liczbą wymierną, a b jest liczbą niewymierną, to a + b jest liczbą niewymierną.

Comments are closed.