Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 27

Jedynym sposobem ustalenia prawdziwości lub fałszywości zdania matematycznego jest przeprowadzenie dowodu matematycznego. Niestety znalezienie dowodu nie zawsze jest łatwe. Zadania tego nie można zredukować do prostego zestawu reguł lub procedur. W trakcie lektury tego podręcznika Czytelnik nieraz będzie musiał przedstawiać dowody różnych twierdzeń. Nie należy jednak zawczasu się martwić! Wprawdzie nikt nie znalazł uniwersalnego przepisu na tworzenie dowodów, ale istnieje kilka ogólnych pomocnych strategii.

Należy uważnie przeczytać zdanie, które chcemy udowodnić. Czy na pewno rozumiemy całą notację? Warto przepisać to zdanie własnymi słowami. Podzielić je na części i rozważyć każdą z nich oddzielnie.

Niekiedy części zdania złożonego nie są od razu oczywiste. Jedno z często występujących zdań złożonych jest postaci „P wtedy i tylko wtedy, gdy Q”, gdzie P i Q to zdania matematyczne. Zapis ten jest skrótem dla zdania dwuczęściowego. Pierwszą częścią jest „P tylko wtedy gdy Q”, oznaczające: jeśli P jest prawdziwe, wówczas Q też jest prawdziwe, co zapisujemy jako P ⇒ Q. Druga część to „P, jeśli Q”, co oznacza: jeśli Q jest prawdziwe, wówczas P też jest prawdziwe, zapisywane jako P Ü Q. Pierwsza z tych części ma kierunek w jedną stronę oryginalnego stwierdzenia, zaś druga to kierunek w drugą stronę. „P wtedy i tylko wtedy, gdy Q” zapisujemy jako P ⇔ Q. Aby dowieść twierdzenia w tej postaci, konieczne jest przeprowadzenie dowodu w obu kierunkach. Często jeden z tych kierunków jest łatwiejszy do udowodnienia niż drugi.

Inny typ zdania złożonego polega na stwierdzeniu, że dwa zbiory A i B są równe. Pierwsza część głosi, że A jest podzbiorem B, zaś druga stwierdza, że B jest podzbiorem A. Stąd jedną z typowych metod dowodzenia, że A = B, polega na wykazaniu, że każdy element A jest również elementem B, a następnie, że każdy element B jest też elementem A.

Wreszcie gdy próbujemy udowodnić jakieś zdanie lub jego część, trzeba próbować uzyskać intuicyjne „wewnętrzne” poczucie, dlaczego powinno być ono prawdziwe. Szczególnie pomocne może tu być eksperymentowanie z przykładami. Jeśli zdanie głosi, że wszystkie obiekty określonego typu mają pewną własność, to można wybrać kilka obiektów tego typu i sprawdzić, czy rzeczywiście mają tę własność. W kolejnym kroku można spróbować znaleźć obiekt, który nie będzie spełniać tego warunku, co nazywamy kontrprzykładem. Jeśli zdanie jest rzeczywiście prawdziwe, nie będziemy w stanie znaleźć kontrprzykładu. Dostrzeżenie, w którym miejscu pojawiają się trudności przy próbach znalezienia kontrprzykładu, może pomóc w zrozumieniu, dlaczego to stwierdzenie jest prawdziwe.

Przykład 0.19

Załóżmy, że chcemy udowodnić stwierdzenie, że dla każdego grafu G suma stopni wszystkich wierzchołków tego grafu jest liczbą parzystą.

Najpierw wybieramy kilka grafów i sprawdzamy to stwierdzenie w działaniu. Oto dwa przykłady:

Następnie próbujemy znaleźć kontrprzykład; inaczej mówiąc, szukamy grafu, w którym suma ta będzie liczbą nieparzystą.

Czy można już zauważyć, że stwierdzenie to jest prawdziwe, i jak tego dowieść?

■

Jeśli utkniemy na ciągłych próbach udowodnienia jakiegoś zdania, warto spróbować czegoś łatwiejszego. Można spróbować dowieść szczególnego przypadku stwierdzenia. Na przykład, jeśli próbujemy dowieść, że jakaś własność jest prawdą dla każdego k > 0, najpierw spróbujmy dowieść tego dla k = 1. Jeśli to się uda, próbujemy dla k = 2 i tak dalej, aż uchwycimy bardziej ogólny przypadek. Jeśli wybrany przypadek szczególny okazuje się trudny do udowodnienia, można spróbować innego przypadku szczególnego, a być może nawet szczególnego przypadku tego szczególnego przypadku.

Na koniec, gdy jesteśmy już przekonani, że znaleźliśmy dowód, musimy go odpowiednio zapisać. Dobrze napisany dowód to ciąg zdań, z których każde wynika w drodze prostego rozumowania z poprzednich zdań. Staranne pisanie dowodu jest rzeczą ważną zarówno dlatego, że pozwala czytelnikowi go zrozumieć, jak i dlatego, że pozwala się upewnić, że jest on wolny od błędów.

Oto kilka wskazówek pomagających w tworzeniu dobrych dowodów.

 Bądź cierpliwy. Znajdowanie dowodów zajmuje czas. Jeśli nie widzisz od razu, jak coś udowodnić, nie martw się. Badacze niekiedy pracują tygodniami lub nawet latami nad pojedynczymi dowodami.

 Wróć do zadania za jakiś czas. Przyjrzyj się zdaniu, które chcesz udowodnić, pomyśl trochę nad nim, zostaw je, po czym wróć kilka minut lub godzin później. Daj szansę popracować nieświadomej intuicyjnej części swojego umysłu.

 Bądź schludny. Gdy budujesz intuicję na temat zdania, które chcesz udowodnić, używaj prostych, jasnych rysunków i notatek. Chcesz stworzyć wgląd w naturę problemu, a niechlujstwo w tym przeszkadza. Co więcej, gdy piszesz rozwiązanie, które ma przeczytać ktoś inny, to schludność także tej osobie pomoże w zrozumieniu.

 Bądź zwięzły. Pomaga to w wyrażaniu ważnych myśli bez grzęźnięcia w szczegółach. Dobra notacja matematyczna pomaga w zwięzłym przedstawianiu pomysłów. Trzeba jednak zadbać o to, aby pisząc dowód, przedstawić rozumowanie wystarczająco dokładnie, tak aby czytelnik mógł szybko pojąć, co chcesz powiedzieć.

W ramach ćwiczenia dowiedziemy jednego z praw DeMorgana.

Twierdzenie 0.20

Dla dowolnych dwóch zbiorów A i B, A ∪ B = A ∩ B.

Na początek, czy sens tego twierdzenia jest jasny? Jeśli nie rozumiesz znaczenia symboli ∪ lub ∩ albo kreski u góry, zajrzyj do omówienia na stronie 4.

Aby dowieść tego twierdzenia, musimy pokazać, że zbiory A ∪ B oraz A ∩ B są równe. Przypomnijmy, że równość zbiorów możemy udowodnić, pokazując, że każdy element jednego zbioru jest również elementem drugiego zbioru, i vice versa. Przed przeczytaniem dowodu zamieszczonego dalej warto rozważyć kilka przykładów, a następnie spróbować samodzielnie przeprowadzić dowód.

Dowód Twierdzenie to głosi, że dwa zbiory, A ∪ B oraz A ∩ B, są równe. Udowodnimy tę tezę, pokazując, że każdy element jednego ze zbiorów jest również elementem drugiego, i odwrotnie.

Załóżmy, że x jest elementem zbioru A È B. Z definicji dopełnienia zbiorów wynika, że x nie należy do A ∪ B. Tym samym z definicji sumy zbiorów x nie jest ani elementem A, ani elementem B. Innymi słowy, x należy do A i x należy do B. Stąd z definicji przecięcia zbiorów otrzymujemy, że x należy do A ∩ B.

Aby udowodnić twierdzenie w przeciwnym kierunku, załóżmy, że x należy do A ∩ B. Oznacza to, że x należy zarówno do A, jak i do B. Wynika stąd, że x nie należy do A i że x nie należy do B, a tym samym nie należy do sumy tych zbiorów. Stąd x należy do dopełnienia sumy tych zbiorów; innymi słowy, x należy do A ∪ B, co kończy dowód twierdzenia.

Udowodnijmy teraz stwierdzenie z przykładu 0.19.

Twierdzenie 0.21

Dla każdego grafu G suma stopni wszystkich wierzchołków G jest liczbą parzystą.

Dowód Każda krawędź w G jest połączona z dwoma wierzchołkami. Każda krawędź wnosi 1 do stopnia każdego wierzchołka, z którym jest połączona. Tym samym każda krawędź dodaje 2 do sumy stopni wszystkich węzłów. Zatem jeśli G zawiera e krawędzi, to suma stopni wszystkich wierzchołków G wynosi 2e, czyli jest liczbą parzystą.