Dane oryginału

Original edition copyright ? 2019 by Harry Lewis and Rachel Zax. Title of English-language original: Essential Discrete Mathematics for Computer Science by Harry Lewis, Rachel Zax, ISBN 978-0-691-17929-2. Polish-language edition ? 2021 by Polish Scientific Publishers PWN Wydawnictwo Naukowe PWN Spółka Akcyjna. All Rights reserved.

Przekład: Piotr Fabijańczyk, Tomasz Lewandowski na zlecenie WITKOM Witold Sikorski

Projekt okładki: INT-Media Dawid Mazur

Wydawca: Wioleta Szczygielska-Dybciak

Redaktor prowadzący: Monika Zabrocka-Kutera

Redaktor: Małgorzata Dąbkowska-Kowalik

Koordynator produkcji: Anna Bączkowska

Skład wersji elektronicznej na zlecenie Wydawnictwo Naukowe PWN Michał Latusek

Konsultant merytoryczny:

dr Adam Malinowski, Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski

Zastrzeżonych nazw firm i produktów użyto w książce wyłącznie w celu identyfikacji.

Książka, którą nabyłeś, jest dziełem twórcy i wydawcy. Prosimy, abyś przestrzegał praw, jakie im przysługują. Jej zawartość możesz udostępnić nieodpłatnie osobom bliskim lub osobiście znanym. Ale nie publikuj jej w internecie. Jeśli cytujesz jej fragmenty, nie zmieniaj ich treści i koniecznie zaznacz, czyje to dzieło. A kopiując jej część, rób to jedynie na użytek osobisty.

Szanujmy cudzą własność i prawo

Więcej na www.legalnakultura.pl

Polska Izba Książki

Copyright ? for the Polish edition by Wydawnictwo Naukowe PWN S.A.

Warszawa 2021

ISBN 978-83-01-21995-6

eBook został przygotowany na podstawie wydania papierowego z 2021r. (Wydanie I)

Warszawa 2021

Wydawnictwo Naukowe PWN SA

02-460 Warszawa, ul. Gottlieba Daimlera 2

tel. 22 69 54 321, faks 22 69 54 288

infolinia 801 33 33 88

e-mail: pwn@pwn.com.pl, reklama@pwn.plwww.pwn.pl

Przypisy

WSTĘP

??? ?? ????? ?? ??? ???? ???????????, ?? ?? ???????.

Ilość jest bądź rozdzielna, bądź ciągła.

- Arystoteles, Kategorie (ok. 350 p.n.e.)

Ten wprowadzający podręcznik traktuje o matematyce dyskretnej, którą informatycy powinni znać, ale z reguły nie uczą się jej na kursach rachunku różniczkowego czy algebry liniowej. Celem naszym jest raczej wiedza szeroka niż głęboka, zaś tak samo jak pojęć czy umiejętności chcemy uczyć odpowiedniego sposobu myślenia.

Podkreślamy wagę sztuki przeprowadzania dowodów w nadziei, że informatycy nauczą się myśleć formalnie i precyzyjnie. Niemal każda formuła i twierdzenie są tu w pełni udowodnione. Tekst ukazuje kumulatywną naturę matematyki. Na przekór szerokiemu zakresowi tematycznemu, wyniki pozornie między sobą niezwiązane w dalszych rozdziałach będą oparte na pojęciach poznanych wcześniej.

Tekst wymaga znajomości matematyki na poziomie wstępu do rachunku różniczkowego, niekiedy używamy też samego rachunku różniczkowego. W rozdziale 21 na temat notacji asymptotycznej używamy granic, ale umieściliśmy tam też krótkie podsumowanie wszystkich potrzebnych podstawowych faktów. Dowody i ćwiczenia wykorzystujące podstawową wiedzę z zakresu pochodnych i całek, w tym zasadę l'Hopitala, można pominąć, nie tracąc ciągłości.

Przyspieszony jednosemestralny kurs na Harvardzie omawia większość materiału zawartego w tej książce. Na taki kurs uczęszczają zazwyczaj studenci pierwszego i drugiego roku, gdyż stanowi on wstęp do kursów na temat teorii obliczeń (automaty, obliczalność, analiza algorytmów). Podręcznik nadaje się również do użytku w szkołach średnich, dla uczniów matematyki lub informatyki zainteresowanych tematami matematycznie dla nich dostępnymi, ale znajdującymi się poza utartym szlakiem programu szkolnego.

Książka napisana została jako seria krótkich rozdziałów, z których każdy mógłby być tematem jednej lub dwóch godzin zajęć. Każdy rozdział kończy się krótkim podsumowaniem i około dziesięcioma zadaniami. Można z nich korzystać na zasadach pracy domowej lub użyć ich jako ćwiczeń do wspólnego rozwiązywania w niewielkich grupkach.

Nauczyciele, którzy wolą nie omawiać wszystkich tematów tu zawartych, mogą skracać książkę na wiele sposobów. Główny nurt książki zawiera rozdziały 1-8 na temat podstawowych pojęć, rozdziały 13-18 na temat grafów skierowanych i nieskierowanych oraz rozdziały 21-25 na temat notacji asymptotycznej i zliczania. Cztery bloki rozdziałów są opcjonalne i mogą być niezależnie włączone lub wyłączone z omawiania według uznania nauczyciela:

- rozdziały 9-12 o logice,

- rozdziały 19-20 o automatach i językach formalnych,

- rozdziały 26-29 o prawdopodobieństwie dyskretnym oraz

- rozdziały 30-31 o arytmetyce modularnej oraz kryptografii.

Ponadto żaden z tych bloków, o ile w ogóle się je omawia, nie musi być przerobiony w całości, ponieważ tylko materiał z późniejszych rozdziałów opiera się na rozdziałach wcześniejszych z tego samego bloku.

Naszym celem było dostarczenie tekstu uniwersalnego w stylistyce, a przez to nadającego się do szerokiego użytku, nie tak ciężkiego jak encyklopedyczny podręcznik. Przez cały czas staraliśmy się uszanować zarówno chęć do nauki studentów, jak i ich ograniczone zasoby czasu, uwagi i pieniędzy.

*

Z podziękowaniami dla zespołu CS20, który tworzą: Deborah Abel, Ben Adlam, Paul Bamberg, Hannah Blumberg, Crystal Chang, Corinne Curcie, Michelle Danoff, Jack Dent, Ruth Fing, Michael Gelbart, Kirk Goff, Gabriel Goldberg, Paul Handorff, Roger Huang, Steve Komarov, Abiola Laniyonu, Nicholas Longenbaugh, Erin Masatsugu, Keenan Monks, Anupa Murali, Eela Nagaraj, Rebecca Nesson, Jenny Nitishinskaya, Sparsh Sah, Maria Stoica, Tom Silver, Francisco Trujillo, Nathaniel Ver Steeg, Helen Wu, Yifan Wu, Charles Zang i Ben Zheng.

dla Alberta Meyera za jego hojną pomoc w początkowych okresie CS20,

a także dla Micheala Sobina, Scotta Josepha, Alexa Silversteina i Noam Wolf za ich krytykę i wsparcie w czasie pisania.

Harry Lewis i Rachel Zax

Rozdział 1Zasada szufladkowa

Skąd wiemy, że program komputerowy generuje trafne wyniki? Skąd wiemy, że dany program zakończy swoje działanie? Jeśli wiemy, czy w końcu się zatrzyma, to czy możemy przewidzieć, czy stanie się to w ciągu sekundy, godziny czy dnia? Intuicja, testy i "działało całkiem dobrze za każdym razem, gdy próbowaliśmy" nie powinny uchodzić za dowód stwierdzenia. Udowodnienie czegokolwiek wymaga formalnej argumentacji, gdzie zaczynamy od zdań, o których wiemy, że są prawdziwe i łączymy poszczególne zdania za pomocą niepodważalnych wniosków logicznych. Oto książka o matematyce używanej do argumentacji na temat działania programów komputerowych.

Matematyka informatyki nie stanowi jakieś specjalnej, oddzielnej dziedziny. Informatycy korzystają z niemal wszystkich gałęzi matematyki, także takich, o których nikt nigdy nie myślał, iż okażą się przydatne, do momentu, gdy rozwój informatyki znalazł dla nich zastosowanie. Tak więc książka ta zawiera rozdziały traktujące między innymi o logice matematycznej, teorii grafów, zliczaniu, teorii liczb i teorii prawdopodobieństwa dyskretnego. Z punktu widzenia tradycyjnego programu nauczania matematyki, lista powyższa zawiera rzeczy wzajemnie nieporównywalne. Wspólną cechą tych tematów jest to, że znajdują one zastosowanie w informatyce. Co więcej, wszystkie wchodzą w skład matematyki dyskretnej, co oznacza, że dotyczą one wielkości zmieniających się skokowo, a nie w sposób ciągły. Są one wyrażane raczej w postaci symboli i struktur niż w postaci liczb. Oczywiście rachunek różniczkowy w informatyce również jest bardzo ważny, ponieważ wspomaga on rozważania na temat wielkości ciągłych. W tej książce jednak rzadko będziemy używać całek i pochodnych.

***

Jedną z najważniejszych umiejętności wykształcanych przez myślenie matematyczne jest sztuka uogólniania. Dla przykładu, zdanie

Nie istnieje trójkąt o bokach długości 1, 2 i 6

jest prawdziwe, ale bardzo szczegółowe (patrz rys. 1.1). Boki o długości 1 i 2 muszą łączyć się z bokiem o długości 6 na obu jego końcach, ale nie są one razem na tyle długie, by potem spotkać się jeszcze w trzecim wierzchołku.

Rysunek 1.1. Czy może istnieć trójkąt o bokach długości 1, 2 i 6?

Bardziej ogólnym stwierdzeniem mogłoby być (patrz rys. 1.2):

Rysunek 1.2. Nie istnieje trójkąt o bokach długości a, b, c jeśli a + b ? c

Nie istnieje trójkąt o bokach mających długości a, b, c, jeśli a, b i c są liczbami takimi, że a + b ? c.

Drugie sformułowanie jest bardziej ogólne, ponieważ możemy wywnioskować pierwsze z drugiego, podstawiając a = 1, b = 2 i c = 6. Dotyczy ono również przypadku niepokazanego na rysunku - gdy a + b = c, tak więc wszystkie trzy "wierzchołki" znajdują się na jednej prostej. Ogólna zasada ma wreszcie tę zaletę, że nie tylko mówi nam, co jest niemożliwe, lecz także dodatkowo to wyjaśnia. Nie istnieje trójkąt 1 - 2 - 6, ponieważ 1 + 2 ? 6.

Tak więc formułujemy stwierdzenia w formie ogólnej z dwóch powodów. Po pierwsze, bardziej ogólne stwierdzenie jest bardziej przydatne: możemy je z powodzeniem zastosować do większej liczby sytuacji. Po drugie, ogólne stwierdzenie ułatwia zrozumienie tego, o co naprawdę chodzi, ponieważ pozbawione jest nieistotnych, rozpraszających szczegółów.

***

Następnym przykładem niech będzie dość prosty scenariusz.

Anna, Batul, Czarek, Deja, Ewelina, Fawwaz, Grzegorz, Hoon rozmawiają ze sobą i dowiadują się, że zarówno Deja, jak i Grzegorz urodzili się we wtorek.

(1.1)

No i co z tego? Gdy weźmiemy dwie dowolne osoby, to mogą być one urodzone w tym samym dniu tygodnia lub nie. A jednak dzieje się tutaj coś, co można uogólnić. Gdy tylko mamy do czynienia z przynajmniej ośmioma ludźmi, pewna para spośród nich musi być urodzona w tym samym dniu tygodnia, ponieważ tydzień ma tylko siedem dni. Pewne zdania, takie jak (1.1), muszą być prawdziwe, być może z innymi imionami i innym dniem tygodnia. Tak więc mamy tu bardziej ogólne stwierdzenie.

W dowolnej grupie ośmiu osób jakaś dwójka z nich urodziła się w tym samym dniu tygodnia.

Nawet to jednak nie jest tak naprawdę ogólne. Ta zbieżność nie ma nic wspólnego z cechami ludzi albo dni tygodnia, z wyjątkiem tego, ile czego jest. Z tego samego powodu, jeśli postawimy osiem filiżanek na siedmiu talerzykach, pewien talerzyk będzie miał na sobie dwie filiżanki. W zasadzie nie ma też nic magicznego w "ósemce" i "siódemce" z wyjątkiem tego, że pierwsza jest większa od drugiej. Jeśli hotel ma 1000 pokoi i 1001 gości, to jeden pokój musi mieścić co najmniej dwoje gości. Jak możemy wyrazić ogólną zasadę obejmującą naraz wszystkie przypadki bez omawiania zbędnych szczegółów któregokolwiek z nich?

Na początek potrzebujemy nowych pojęć. Zbiór jest kolekcją rzeczy, czyli elementów. Elementy należące do danego zbioru nazywamy jego zawartością. Elementy tworzące zawartość zbioru muszą być odrębne, co jest tylko innym sposobem powiedzenia, że wszystkie muszą różnić się między sobą. Tak więc osoby wymienione w (1.1) tworzą zbiór, zaś dni tygodnia tworzą inny zbiór. Niekiedy wypisujemy zawartość danego zbioru w sposób bezpośredni, jako listę w nawiasach klamrowych {}:

L = {Anna, Batul, Czarek, Deja, Ewelina, Fawwaz, Grzegorz, Hoon}

D = {niedziela, poniedziałek, wtorek, środa, czwartek, piątek, sobota}

Kiedy wypisujemy elementy zbioru, kolejność ich zapisania nie ma znaczenia - w każdej innej kolejności tworzą one ten sam zbiór. Zapis x ? X oznacza, że element x należy do zbioru X. Na przykład Czarek ? L, zaś czwartek ? D.

Aby rozmawiać na temat zbiorów, potrzebujemy pewnej podstawowej terminologii dotyczącej liczb. Liczba całkowita to jedna z liczb 0, 1, 2, ... albo -1, -2, ... Liczby rzeczywiste to wszystkie liczby na osi liczbowej, włączając w to wszystkie liczby całkowite oraz wszystkie liczby pomiędzy nimi, takie jak ?, - ?2 czy ?. Dana liczba jest dodatnia, jeśli jest większa od 0, ujemna, jeśli jest mniejsza od 0 i nieujemna, jeśli jest większa lub równa 0.

Na razie będziemy mówić tylko o zbiorach skończonych. Zbiór skończony to taki, którego elementy mogą być (przynajmniej w założeniu) wymienione jeden po drugim. Zbiór skończony ma liczebność albo moc, która jest wyrażana przez liczbę całkowitą nieujemną. Moc zbioru X oznaczamy jako |X|. W przykładzie dotyczącym osób i dni tygodnia, w których się urodzili, |L| = 8, zaś |D| = 7, ponieważ wymieniliśmy osiem osób, a dni w tygodniu jest siedem. Zbiór, który nie jest skończony - na przykład zbiór liczb całkowitych - jest nieskończony. Zbiory nieskończone również mają swoje rozmiary - jest to ciekawy temat, do którego powrócimy w rozdziale 7.

Funkcją z jednego zbioru na drugi nazywamy regułę, według której każdemu elementowi pierwszego zbioru przyporządkowuje się dokładnie jeden element drugiego zbioru. Jeśli f jest funkcją z X na Y, zaś x ? X, to f(x) jest tym elementem Y, który f przyporządkowuje elementowi x. Mówimy o x jako o argumencie funkcji f, zaś f(x) nazywamy wartością f na tym argumencie. Zapis f: X ? Y oznacza, że f jest funkcją ze zbioru X na zbiór Y. Można na przykład zapisać u: L ? D jako oznaczenie funkcji przyporządkowującej każdemu z ośmiu przyjaciół dzień tygodnia, w którym został on urodzony. Jeśli Karol urodził się we wtorek, to u(Karol) = wtorek.

Funkcję f : X ? Y nazywamy niekiedy odwzorowaniem zbioru X na Y, zaś o f mówimy, że odwzorowuje element x ? X na element f(x) ? Y (w podobny sposób jak prawdziwa mapa[1] odwzorowuje punkt na powierzchni za pomocą punktu na kartce papieru).

Wreszcie mamy sposób na wyrażenie ogólnej reguły, jaka rządzi przykładem (1.1)

Jeśli f : X ? Y oraz |X| > |Y|, to istnieją takie elementy x1, x2 ? X, że x1 ? x2 i f(x1) = f(x2).

(1.2)

Twierdzenie (1.2) jest znane jako zasada szufladkowa, gdyż w formie matematycznej wyraża ten zdroworozsądkowy pomysł: jeśli mamy więcej rzeczy niż szufladek i każda rzecz idzie do pewnej szufladki, to któraś szufladka zawiera więcej niż jedną rzecz. Rzeczy są elementami zbioru X, zaś szufladki elementami zbioru Y (patrz rys. 1.3).

Rysunek 1.3. Zasada szufladkowa. Jeśli |X| > |Y|, zaś f jest dowolną funkcją z X na Y, to pewne dwa różne elementy X muszą mieć tę samą wartość funkcji f

Formalny dowód zasady szufladkowej podamy na stronie 39, gdy już wypracujemy odpowiednie narzędzia do przeprowadzania dowodów. Na razie przyjrzyjmy się bliżej powyższemu sformułowaniu zasady szufladkowej w celu lepszego zrozumienia języka matematyki. Oto niektóre z pytań, które moglibyśmy zadać:

1. Czym są X i Y?

Są zbiorami skończonymi. Aby wyrazić się całkowicie jasno, można by rozpocząć zdanie od frazy "Dla dowolnych zbiorów skończonych X i Y", ale założenie, że f jest funkcją z X na Y ma sens tylko jeśli X i Y są zbiorami, zaś z kontekstu wiadomo, że zbiory, o których mowa, są skończone - i dzięki temu wiemy, jak porównywać ich rozmiary.

2. Dlaczego wybraliśmy "x1" i "x2" na nazwy elementów X?

Zasadniczo moglibyśmy wybrać dowolne nazwy zmiennych, "x" i "y" na przykład. Ale używanie wariantów oznaczenia "X" na nazwanie elementów zbioru X sugeruje, że x1 i x2 należą raczej do X niż do Y. Dzięki temu użycie "x1" i "x2" sprawia, że nasze zdanie łatwiej przeczytać i zrozumieć.

3. Czy wyrażenie "takie, że x1 ? x2" było konieczne? Zdanie jest prostsze bez tego i wydaje się, że mówiłoby dokładnie to samo.

Tak, "x1 ? x2" jest konieczne, i nie - zdanie nie mówi tego samego bez niego! Gdybyśmy nie powiedzieli "x1 ? x2", wtedy "x1" i "x2" mogłyby być dwiema nazwami tego samego elementu. Gdybyśmy nie podkreślili, że x1 i x2 mają być różne od siebie, zdanie nie stałoby się przez to fałszywe - tylko trywialne! Oczywiście, jeśli x1 = x2, to f(x1) = f(x2). To jak mówić, że masa Ziemi jest równa masie trzeciej planety od Słońca. Innym sposobem wyrażenia zasady szufladkowej byłoby stwierdzenie, że "istnieją różne od siebie elementy x1, x2 ? X o własności takiej, że f(x1) = f(x2)".

Jeszcze jedną rzecz warto tu podkreślić. Zdanie takie, jak "istnieją różne od siebie elementy x1, x2 ? X o własności takiej, że bla bla bla" nie oznacza, że istnieją dokładnie dwa elementy o takiej własności. Oznacza tylko, że przynajmniej dwa takie elementy istnieją na pewno - być może więcej, ale na pewno nie mniej.

***

Matematycy zawsze poszukują bardziej ogólnych postaci danej reguły, ponieważ wtedy może zostać ona użyta do wyjaśnienia większej liczby rzeczy. Jest na przykład równie oczywiste, że jeśli włożymy 15 rzeczy w 7 szufladek, to w którejś szufladce znajdą się przynajmniej 3 rzeczy - ale nie ma sposobu, by wywnioskować to z zasady szufladkowej w sformułowaniu, w jakim ją tu przedstawiliśmy. Oto bardziej ogólna jej wersja:

Twierdzenie 1.3. Rozszerzona zasada szufladkowa. Dla dowolnych skończonych zbiorów X i Y oraz dowolnej dodatniej liczby całkowitej k takich, że |X| > k - |Y|, jeśli f : X ? Y, to istnieje przynajmniej k + 1 różnych elementów x1, ..., xk+1 ? X takich, że f(x1) = ... = f(xk+1).

Zasada szufladkowa jest szczególnym przypadkiem rozszerzonej zasady szufladkowej, dla którego k = 1.

Użyliśmy tu po raz pierwszy notacji na oznaczenie ciągu, wykorzystując tę samą zmienną z dolnymi indeksami liczbowymi zawartymi w danym przedziale. W tym przypadku xi, gdzie 1 ? i ? k + 1, tworzą ciąg o długości k + 1. Notacja ta jest bardzo wygodna, gdyż umożliwia użycie wyrażeń algebraicznych, takich jak k + 1, w indeksach. W podobny sposób do elementu o numerze 2i ciągu y1, y2, ... możemy odnieść się poprzez oznaczenie y2i.

Minimalną wartość parametru k w rozszerzonej zasadzie szufladkowej zastosowanej do konkretnych zbiorów X i Y można określić, gdy rozmiary X i Y są znane. Aby to obliczenie było przeprowadzone w sposób precyzyjny, należy zastosować odpowiedni zapis.

Liczba całkowita p dzieli inną liczbę całkowitą q, co zapisujemy jako p | q, jeśli ułamek jest liczbą całkowitą - to znaczy można podzielić q przez p bez reszty. Jeśli p nie dzieli q, zapisujemy ten fakt następująco: p  q, np. 3  7. Jeśli x jest dowolną liczbą rzeczywistą, zapis x oznacza największą liczbę całkowitą mniejszą lub równą x (nazywamy to cechą liczby x albo podłogą liczby x). Na przykład Potrzebujemy również notacji oznaczającej tzw. cechę górną: x, czyli sufit liczby x, jest najmniejszą liczbą całkowitą większą lub równą x, na przykład 3,7 = 4.

Z pomocą tej notacji możemy przeformułować rozszerzoną zasadę szufladkową w taki sposób, by określić minimalny rozmiar najbardziej wypełnionych szufladek dla danej liczby rzeczy i szufladek:

Twierdzenie 1.4. Rozszerzona zasada szufladkowa, wersja alternatywna. Niech X i Y będą dowolnymi skończonymi zbiorami i niech f : X ? Y. Istnieje wtedy y ? Y taki, że f(x) = Y dla przynajmniej

wartości x.

Dowód. Niech m = |X| oraz n = |Y|. Jeśli n | m, to jest to przypadek rozszerzonej zasady szufladkowej dla k = m/n = 1 = - 1. Jeśli n m, to mamy znów do czynienia z zasadą szufladkową, gdzie k = - 1, ponieważ jest to największa liczba całkowita mniejsza od .-

***

Te wersje zasady szufladkowej podanej w ogólnej postaci wydają się być skomplikowanym sposobem wyrażenia rzeczy oczywistych. Używamy ich jednak do wyjaśnienia wielu różnorakich zjawisk - gdy tylko da się określić, co tym razem może być "szufladkami", a co "rzeczami w szufladkach". Zakończmy rozdział zastosowaniem w teorii liczb badającej własności liczb całkowitych. Na początek kilka podstawowych faktów.

Jeśli p | q, to p nazywamy dzielnikiem albo czynnikiem q.

Liczba pierwsza to dowolna liczba całkowita większa niż 1, która dzieli się tylko przez 1 i przez samą siebie. Na przykład 7 jest liczbą pierwszą, ponieważ dzieli się tylko przez 7 i 1, jednak 6 nie jest liczbą pierwszą, bo 6 = 2 - 3. Zauważmy, że 1 również nie jest liczbą pierwszą.

Twierdzenie 1.5. Podstawowe twierdzenie arytmetyki. Każdą liczbę całkowitą większą od 1 można w sposób jednoznaczny przedstawić w postaci iloczynu różnych pierwszych w porządku rosnącym i z wykładnikami całkowitymi dodatnimi.

Dowiedziemy tego twierdzenia w rozdziale 4, ale już teraz z niego skorzystamy. Rozkładem na czynniki pierwsze liczby n nazywamy jedyny taki iloczyn

gdzie pi są liczbami pierwszymi w porządku rosnącym, zaś ei są liczbami całkowitymi dodatnimi. Na przykład 180 = 22-32-51 i nie istnieje inny iloczyn równy 180, gdzie p1 < p2 < ... < pk, wszystkie pi są liczbami pierwszymi, zaś ei są wykładnikami całkowitymi.

Rozkład na czynniki pierwsze iloczynu dwóch liczb całkowitych m i n łączy ze sobą rozkłady na czynniki pierwsze m i n - każdy czynnik pierwszy liczby m - n jest czynnikiem pierwszym jednej lub drugiej z tych liczb.

Twierdzenie 1.7. Jeśli m, n i p są liczbami całkowitymi większymi od 1, p jest liczbą pierwszą i p | m - n, to p | m, lub p | n.

Dowód. Na podstawie podstawowego twierdzenia arytmetyki (1.5) istnieje tylko jeden sposób zapisu

(1.6)

gdzie pi są liczbami pierwszymi. Ale p musi być jednym z pi, zaś każde z pi pojawia się w rozkładzie m lub n na czynniki pierwsze.-

Wykładnik liczby pierwszej p w rozkładzie na czynniki pierwsze m - n stanowi sumę wykładników z rozkładów m i n (przyjmując wykładnik 0, jeśli p nie pojawia się w danym rozkładzie). Dla przykładu rozważmy iloczyn 18 - 10 = 180. Mamy:

18 = 21 - 32    (wykładnikami liczb 2, 3, 5 są 1, 2, 0)

10 = 21 - 51    (wykładnikami liczb 2, 3, 5 są 1, 0, 1)

180 = 22 - 32 - 51

= 21+1 - 32+0 - 50+1

Pokolorowaliśmy wykładniki, by wyeksponować, że wykładniki liczb 2, 3, 5 w iloczynie 180 są sumami wykładników liczb pierwszych w rozkładach na czynniki pierwsze dwóch czynników 18 i 10.

Innym ważnym faktem na temat liczb pierwszych jest to, że jest ich nieskończenie wiele.

Twierdzenie 1.8. Istnieją dowolnie wielkie liczby pierwsze.

"Dowolnie wielkie" znaczy, że dla każdego n > 0 istnieje liczba pierwsza większa niż n.

Dowód. Przyjmijmy jakąś wartość k, o której wiemy, że istnieje przynajmniej k liczb pierwszych i niech p1, ..., pk będzie ciągiem k pierwszych liczb pierwszych w porządku rosnącym. (Ponieważ p1 = 2, p2 = 3, p3 = 5, na pewno moglibyśmy przyjąć k = 3). Pokażemy, jak znaleźć liczbę pierwszą większą niż pk. A ponieważ ten proces można powtarzać w nieskończoność, musi istnieć nieskończenie wiele liczb pierwszych.

Rozważmy liczbę N równą zwiększonemu o 1 iloczynowi k początkowych liczb pierwszych:

(1.9)

Dzielenie N przez którąkolwiek z liczb p1, ..., pk dałoby resztę 1. Tak więc N nie ma dzielników pierwszych mniejszych lub równych pk. Zatem N nie jest liczbą pierwszą, ale ma czynnik pierwszy większy od pk albo N jest liczbą pierwszą.-

W przypadku gdy k = 3, N = 2 - 3 - 5 + 1 = 31. Tutaj samo N jest liczbą pierwszą, a w zadaniu 1.11 prosimy o wskazanie przykładu, w którym N nie jest liczbą pierwszą.

Wspólnym dzielnikiem dwóch liczb jest liczba, która dzieli obie z nich. Na przykład 21 i 36 mają wspólne dzielniki 1 i 3, ale 16 i 21 nie mają wspólnych dzielników większych niż 1.

Po przypomnieniu podstaw przyjrzyjmy się przykładowi z teorii liczb, w którym używa się zasady szufladkowej.

Przykład 1.10. Wybierzmy m różnych liczb między 2 a 40 włącznie, gdzie m ? 13. Wtedy przynajmniej dwie z liczb mają wspólny dzielnik większy niż 1.

"Między a i b włącznie" oznacza wszystkie liczby, które są ? a, a także ? b - a, zatem w tym przypadku, włączając zarówno 2, jak i 40.

Rozwiązanie do przykładu. Zauważmy, że istnieje 12 liczb pierwszych mniejszych lub równych 40: 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37 i żadne dwie spośród nich nie mają wspólnego czynnika większego niż 1. Zdefiniujmy P jako zbiór tych 12 liczb pierwszych. (Musieliśmy określić, że m ? 13, ponieważ w przeciwnym razie stwierdzenie byłoby fałszywe dla m = 12, a zbiór P byłby właśnie kontrprzykładem). Rozważmy teraz zbiór X zawierający m liczb w przedziale od 2 do 40 włącznie. Możemy wyobrazić sobie elementy zbioru P jako szufladki, do których wkładamy elementy zbioru X. Aby włożyć coś do szufladki, używamy funkcji f : X? P, gdzie f(x) jest najmniejszą liczbą pierwszą, która dzieli x. Dla przykładu f(16) = 2, f(17) = 17, zaś f(21) = 3. Ponieważ m > 12, to na podstawie zasady szufladkowej, wartości f muszą być równe dla pewnych dwóch różnych elementów X, a zatem przynajmniej dwa elementy X mają wspólny czynnik pierwszy.-

Podsumowanie rozdziału

- Rozumowanie matematyczne skupia się na zasadach ogólnych wyabstrahowanych z poszczególnych przykładów i pozbawionych szczegółów.

- Zbiór jest nieuporządkowaną kolekcją odrębnych rzeczy albo elementów. Elementy danego zbioru tworzą jego zawartość.

- Zbiór jest skończony, jeśli jego elementy mogą zostać wymienione jeden po drugim. Liczba elementów zbioru skończonego X nazywamy jego liczebnością lub mocą oznaczamy jako |X|. Liczebność zbioru jest zawsze nieujemną liczbą całkowitą.

- Funkcją albo odwzorowaniem między dwoma zbiorami nazywamy regułę przyporządkowującą każdemu elementowi pierwszego zbioru jeden element drugiego.

- Zasada szufladkowa głosi, że jeśli X jest zbiorem rzeczy, a Y jest zbiorem szufladek i |X| > |Y|, to każda funkcja przyporządkowująca rzeczy do szufladek wkłada do pewnej szufladki więcej niż jedną rzecz.

- Rozszerzona zasada szufladkowa głosi, że jeśli X jest zbiorem rzeczy, a Y jest zbiorem szufladek i |X| > k|Y|, to każda funkcja przyporządkowująca rzeczy do szufladek wkłada do pewnej szufladki więcej niż k rzeczy.

- Ciąg wyrażeń można zapisać jako powtarzającą się zmienną z różnymi indeksami numerycznymi, tak jak x1, ..., xn. Indeks danego wyrażenia może być wyrażeniem algebraicznym.

- Podstawowe twierdzenie arytmetyki głosi, że każda liczba całkowita dodatnia ma dokładnie jeden rozkład na czynniki pierwsze.

Zadania

1.1. Co oznaczają następujące zapisy?

(a) |{0, 1, 2, 3, 4, 5, 6}|

(b)

(c)

(d) Zbiór dzielników liczby 100.

(e) Zbiór czynników pierwszych liczby 100

1.2. Niech f(n) będzie największym czynnikiem pierwszym liczby n. Czy może się zdarzyć, że x < y, ale f(x) > f(y)? Podaj przykład i wyjaśnij, dlaczego jest to możliwe.

1.3. W jakim przypadku x = x - 1?

1.4. Wyobraźmy sobie kwadrat 9 × 9 przegródek, w każdej z których siedzi jeden gołąb (Mamy więc 81 gołębi w 81 przegródkach - patrz rys. 1.4.) Przypuśćmy, że wszystkie gołębie naraz przemieszczają się do sąsiedniej przegródki - w górę, w dół, w lewo lub prawo. (Gołębie ze skrajnych przegródek nie mogą wyjść z kwadratu). Wykaż, że w pewnej przegródce znajdą się dwa gołębie. Podpowiedź: liczba 9 tylko tu rozprasza. Wypróbuj kilka mniejszych liczb, żeby zobaczyć, co się dzieje.

Rysunek 1.4. W środku każdej przegródki w kwadracie 9 × 9 siedzi jeden gołąb. Wszystkie naraz przemieszczają się o jedno miejsce od aktualnie zajmowanego - w lewo, w prawo, w górę lub w dół. Czy pewna przegródka musi na koniec zawierać dwa gołębie?

1.5. Wykaż, że w dowolnej grupie osób dwie z nich muszą mieć tę samą liczbę przyjaciół w grupie. (Musimy przyjąć tu pewne ważne założenia: nikt nie jest przyjacielem samego siebie, zaś przyjaźń jest symetryczna - jeśli A jest przyjacielem B, to B jest przyjacielem A.)

1.6. Dla danych pięciu dowolnych punktów na sferze wykaż, że cztery z nich muszą znajdować się na tej samej domkniętej półsferze, gdzie "domknięta" oznacza, że półsfera zawiera również ograniczający je okrąg. Wskazówka: Przez dowolne dwa punkty na sferze można przeprowadzić między nimi okrąg wielki, czyli największy okrąg na sferze.

1.7. Wykaż, że dla dowolnej grupy 25 osób trójka z nich musi mieć urodziny w tym samym miesiącu.

1.8. Mamy kolekcję monet o sześciu różnych nominałach: 1, 2, 5, 10, 20 i 50 groszy. Ile monet musi zawierać ta kolekcja, skoro wiemy, że przynajmniej 100 z nich ma ten sam nominał?

1.9. Dwadzieścia pięć osób uczęszcza codziennie na zajęcia jogi na ten samej siłowni, na której odbywa się osiem zajęć jogi dziennie. Każdy z uczestników nosi niebieską, czerwoną albo zieloną bluzkę w czasie ćwiczeń. Wykaż, że dowolnego dnia odbywa się przynajmniej jedna sesja jogi, podczas której dwie osoby noszą bluzki tego samego koloru.

1.10. Wykaż, że jeśli wybierzemy dowolne cztery liczby naturalne z przedziału od 1 do 60 włącznie, to dwie z nich muszą różnić się co najwyżej o 19.

1.11. Znajdź liczbę k o własności takiej, że iloczyn pierwszych k liczb pierwszych plus 1 nie jest liczbą pierwszą, ale ma czynnik pierwszy większy niż którakolwiek z k pierwszych liczb pierwszych. (Nie ma żadnego sprytnego triku pozwalającego na rozwiązanie tego zadania - trzeba po prostu wypróbować różne możliwości!)

1.12. Wykaż, że w dowolnym zbiorze 9 liczb całkowitych dodatnich dwie z nich mają wspólne wszystkie swoje czynniki pierwsze mniejsze lub równe 5.

1.13. Funkcja mieszająca (inaczej funkcja skrótów) prowadząca z łańcuchów tekstowych na liczby wyprowadza numeryczną wartość h(s) (skrót) z łańcuchu tekstowego s - na przykład poprzez dodanie wszystkich kodów numerycznych liter w danym łańcuchu i wzięcie reszty z dzielenia wyniku przez daną liczbę pierwszą p. Funkcja mieszająca powinna dawać powtarzalne wyniki (tzn. dwukrotne obliczenie h(s) z tego samego łańcucha s daje nam tę samą wartość) tak, by wyniki z dużym prawdopodobieństwem rozkładały się równo między możliwymi wartościami (od 0 do p - 1). Gdy funkcja mieszająca daje dwie takie same wartości dla dwóch różnych łańcuchów, mówimy wówczas, że oba te łańcuchy kolidują ze sobą na tej wartości. Liczymy liczbę kolizji na danej wartości w ten sposób, że jest ich o jeden mniej niż różnych łańcuchów z tą samą wartością funkcji mieszającej - czyli jeśli na przykład 2 łańcuchy mają tę samą wartość, to mamy 1 kolizję na tej wartości. Jeśli mamy m łańcuchów i p możliwych skrótów, to jaka jest minimalna liczba kolizji, które muszą zajść na wartości o największej liczbie kolizji? A jaka jest maksymalna liczba kolizji, które mogą zajść na niektórych wartościach?

Rozdział 2Podstawowe techniki dowodzenia

Poniżej znajduje się sformułowanie zasady szufladkowej w języku naturalnym:

Jeśli mamy więcej rzeczy niż szufladek i każda rzecz trafia do jednej szufladki, to jakaś szufladka musi zawierać więcej niż jedną rzecz.

Przypuśćmy jednak, że nasz znajomy nie wierzy w prawdziwość tego stwierdzenia. W jaki sposób można przekonująco uzasadnić, że jest ona prawdziwa?

Można spróbować przekonać znajomego, że w żaden sposób nie mogłaby być prawdziwa sytuacja odwrotna. Można spróbować wyobrazić sobie, że każda z szufladek nie zawiera więcej niż jedną rzecz. Liczymy wtedy szufladki, a ponieważ każda szufladka zawiera zero lub jedną rzecz, liczba szufladek może co najwyżej równać się liczbie rzeczy. Zaczęliśmy jednak od założenia, że jest więcej rzeczy niż szufladek, a więc jest to niemożliwe! Ponieważ nie ma możliwości, by każda szufladka zawierała co najwyżej jedną rzecz, to pewna szufladka musi zawierać więcej niż jedną rzecz, a to jest dokładnie to, co chcemy udowodnić.

W tym rozdziale dowiemy się, jak budować takie nieformalne, ale szczegółowe argumentacje i w jaki sposób zamieniać je w formalne, ogólne dowody matematyczne. Dowód jest argumentacją, która zaczyna się od jednej lub więcej przesłanek (na przykład "mamy więcej rzeczy niż szufladek") i z pomocą reguł logiki wywodzi z nich wniosek (na przykład "pewna szufladka zawiera więcej niż jedną rzecz"). Chociaż wydaje się, że łatwiej napisać (i zrozumieć!) zdania sformułowane w języku naturalnym, to jednak może on być nieprecyzyjny lub niepotrzebnie szczegółowy. Będzie zatem jaśniej i bardziej ogólnie, gdy przedstawimy matematyczną sytuację w sposób formalny.

Weźmy dla przykładu takie zdanie i zastanówmy się, co może ono znaczyć:

Każdy kogoś kocha.

(2.1)

Może to znaczyć, że dla każdej osoby na świecie istnieje ktoś, kogo ta osoba kocha - tak więc różni zakochani mogą mieć różne ukochane. Tak więc w języku pseudo matematycznym przedstawilibyśmy tę interpretację jako:

Dla każdej osoby A istnieje pewna osoba B taka, że A kocha B.

(2.2)

Istnieje jednak inna interpretacja (2.1), mianowicie to, że istnieje pewna specjalna osoba, którą każdy kocha, innymi słowy

Istnieje taka osoba B, że dla każdej osoby A, A kocha B.

(2.3)

Między tymi dwiema interpretacjami jest ogromna różnica, a jednym z celów istnienia języka matematyki jest rozwiązywanie podobnych dwuznaczności języka naturalnego.

Wyrażenia "dla każdego", "dla dowolnego", "dla wszystkich", "dla pewnego" oraz "istnieje" nazywamy kwantyfikatorami. Ich ostrożne użycie jest ważną częścią matematycznego dyskursu. Symbol ? oznacza "dla wszystkich", "dla każdego", zaś symbol $ oznacza "istnieje" czy "dla pewnego". Użycie tych symboli oszczędza czas, ale też sprawia, że proza matematyczna może nieco dezorientować czytelnika. Będziemy więc unikać ich stosowania aż do momentu, gdy omówimy formalizację rachunku kwantyfikatorów w rozdziale 12.

Kwantyfikatory modyfikują predykaty, takie jak "A kocha B". Predykat to szablon zdania, który przyjmuje jeden lub więcej argumentów, w tym przypadku A i B. Sam z siebie predykat nie ma wartości logicznej (tzn. nie jest prawdziwy ani fałszywy). Dopiero znając wartości A i B, możemy powiedzieć, czy "A kocha B" jest prawdą czy fałszem. Przyjmuje wartość logiczną prawda tylko wtedy, gdy zostanie skwantyfikowany (jak w (2.2) lub (2.3)) albo kiedy zastosuje się go do konkretnych argumentów (na przykład "Romeo kocha Julię"). W jednych przypadkach może być wtedy prawdziwy, a w innych - fałszywy.

Poniżej przyjrzymy się prostemu przykładowi twierdzenia matematycznego wraz z dowodem.

Twierdzenie 2.4. O liczbach całkowitych nieparzystych. Każda całkowita liczba nieparzysta jest równa różnicy kwadratów pewnych liczb całkowitych.

Na początek upewnijmy się, że rozumiemy to stwierdzenie. Liczba całkowita nieparzysta to każda liczba całkowita, którą możemy zapisać jako 2k + 1, gdzie k to także liczba całkowita. Kwadratem liczby całkowitej n jest n2 = n - n. Twierdzenie 2.4. mówi, że dla każdej wartości k istnieją dwie liczby całkowite - nazwijmy je m i n - takie, że jeśli weźmiemy ich kwadraty i odejmiemy jeden od drugiego, to wynik będzie równy 2k + 1 (zwróćmy uwagę na kwantyfikatory: dla każdego k istnieją takie m i n, że... ).

Liczbę całkowitą m nazywamy liczbą kwadratową, jeśli stanowi ona kwadrat jakiejś innej liczby całkowitej, tak więc zwięzłym sposobem wyrażenia tego twierdzenia byłoby powiedzenie, że każda liczba nieparzysta stanowi różnicę dwóch liczb kwadratowych. Czymś typowym dla matematyki, jak w tym przypadku, jest to, że poprzez zdefiniowanie odpowiednich pojęć sformułować można bardzo proste wyrażenia prawd ogólnych.

Następnym krokiem jest przekonanie się, dlaczego to stwierdzenie jest prawdziwe. Jeśli powód nie jest oczywisty, pomocne może okazać się przeanalizowanie kilku przypadków. Zacznijmy więc od obliczenia kilku liczb kwadratowych.

Możemy łatwo sprawdzić, że stwierdzenie jest prawdziwe dla kilku konkretnych liczb nieparzystych, powiedzmy dla 1, 3, 5 i 7:

Po przeanalizowaniu tych przykładów możemy zauważyć pewne wyłaniające się prawidłowości: każda liczba nieparzysta jest różnicą kwadratów dwóch następujących po sobie liczb całkowitych: 0 i 1, potem 1 i 2, potem 2 i 3, następnie 3 i 4. Inna obserwacja - suma tych następujących po sobie liczb całkowitych to nasza docelowa liczba nieparzysta: 0 + 1 = 1, 1 + 2 = 3, 2 + 3 = 5, zaś 3 + 4 = 7. Na razie możemy postawić hipotezę, że dla liczby nieparzystej 2k + 1 liczbami, których kwadraty powinniśmy od siebie odjąć są, k i k + 1. Spróbujmy zatem:

co upraszcza się do 2k + 1.

Tak więc nasze domysły okazały się trafne! Ponieważ nie patrzyliśmy na konkretne przypadki liczb nieparzystych, lecz zapisaliśmy to za pomocą definicji liczby nieparzystej (2k + 1), potwierdziliśmy, że działa to dla każdej liczby nieparzystej. Jest to nawet prawdziwe dla liczb nieparzystych ujemnych (ponieważ te także są równe 2k + 1 dla ujemnych wartości k), chociaż na sam pomysł wpadliśmy wyłącznie na podstawie przykładów dotyczących liczb dodatnich.

Ten tok rozumowania pokazuje, jak można wpaść na jakiś pomysł, ale jest to zbyt zagmatwane, by nadawało się na dowód formalny. Ostateczny dowód powinien zawierać tylko rzeczy istotne. Na przykład zrobione konkretne przykłady nie wnoszą niczego do dowodu - musimy wykazać, że twierdzenie jest prawdziwe zawsze, a nie tylko dla tych przypadków, które wypróbowaliśmy. Spokojnie możemy więc je pominąć. Oto formalny dowód twierdzenia 2.4:

Dowód. Każdą liczbę nieparzystą zapisać można jako 2k + 1 dla pewnej liczby całkowitej k. Możemy przepisać to wyrażenie:

2k + 1 = (k2 + 2k + 1) - k2     (dodanie i odjęcie k2)

= (k + 1)2 - k2     (zapis pierwszego wyrażenia w postaci kwadratu).

Teraz niech m = k + 1, zaś n = k. Wtedy 2k + 1 = m2 - n2, tak więc określiliśmy liczby całkowite m i n o własności, którą trzeba było udowodnić.-

Zanim zajmiemy się kwestiami merytorycznymi, kilka uwag na temat stylu dowodu. Po pierwsze, został on zapisany pełnymi zdaniami. Wyrażenia matematyczne zostały użyte dla precyzji i jasności, ale sama argumentacja zapisana jest słownie. Po drugie, jego struktura jest przejrzysta: zaczynamy od przyjętych założeń, że liczba całkowita jest nieparzysta, a na końcu jasno stwierdzamy, że osiągnęliśmy cel, zauważając, że m oraz n liczbami, których szukaliśmy. Po trzecie, dowód jest ścisły: podaje matematyczne definicje znaczących terminów ("liczba nieparzysta"), co zmusza nas do precyzyjnego i jasnego sposobu wyrażania się. Każdy następny krok dowodu jasno i logicznie wynika z poprzedniego.

I wreszcie, całość jest przekonująca. Dowód podaje odpowiednią ilość szczegółów - na tyle dużo, by czytelnik łatwo mógł zrozumieć, dlaczego każdy następny krok jest prawidłowy, ale nie aż tyle, by rozpraszało to uwagę i odciągało od toku rozumowania. Moglibyśmy, na przykład, pominąć nieco arytmetyki i stwierdzić po prostu, że

Ta równość nie jest jednak oczywista, a uważny czytelnik mógłby pokusić się o jej sprawdzenie. Kiedy zawrzemy w dowodzie krok pośredni, arytmetyka staje się zrozumiała. Z drugiej strony, pewnych założeń dowodzić nie potrzeba - na przykład tego, że prawidłowy jest zapis

Wynika to z tego, że gdy przeniesiemy składniki i pogrupujemy je w inny sposób, suma pozostaje niezmieniona. W tym kontekście reguły te są raczej podstawowe i można je przyjmować bez uzasadnienia, a ich dowodzenie tylko odciągałoby czytelnika od głównego toku rozumowania. Jednak w podręczniku arytmetyki formalnej moglibyśmy udowodnić te własności dodawania. Poziom szczegółowości, jaki należy przyjąć, zależy od kontekstu oraz docelowych czytelników dowodu - praktyczną regułą jest pisanie w taki sposób, jakby się chciało przekonać osobę o zbliżonym poziomie wiedzy.

Powróćmy teraz do treści dowodu. Jest to przede wszystkim przykład dowodu konstruktywnego. Twierdzenie, którego dowodzimy, mówi wyłącznie o istnieniu czegoś: że dla każdej liczby nieparzystej istnieją dwie liczby całkowite, których różnica kwadratów da nam naszą liczbę początkową. Dowód konstruktywny nie tylko dowodzi, że tak jest, lecz także dokładnie pokazuje, jak te liczby znaleźć. Dowód twierdzenia 2.4 dla danej liczby nieparzystej 2k + 1 pokazuje nam, jak znaleźć dwie liczby całkowite o poszukiwanych własnościach podanych w twierdzeniu - jedna z nich to k + 1, a druga to k. Jeśli liczbą nieparzystą, którą chcemy wyrazić jako różnicę dwóch kwadratów, jest na przykład 341, to dowód mówi nam, że możemy odjąć 1 od 341 i wynik podzielić przez 2 i wtedy otrzymana liczba (170) oraz liczba o jeden większa (171) będą tymi, których poszukujemy. Łatwo to sprawdzić:

Nie było żadnego powodu, by sprawdzić akurat ten przypadek, a nie inny, ale sprawdzenie któregokolwiek zwiększa nasz poziom pewności co do tego, że nie zrobiliśmy po drodze żadnego błędu algebraicznego.

Ogólnie rzecz biorąc, procedurę znalezienia odpowiedzi na pytanie lub rozwiązania problemu nazywamy algorytmem, jeśli jej opis jest na tyle szczegółowy i precyzyjny, że może być w zasadzie przeprowadzona w sposób mechaniczny - czy to przez maszynę, czy przez człowieka bezrefleksyjnie wykonującego zadane instrukcje. Dowód konstruktywny implicite opisuje algorytm na znalezienie lub obliczenie obiektu, którego istnienie jest treścią dowodu. W przypadku twierdzenia 2.4 dowód opisuje algorytm, który dla danej liczby nieparzystej 2k + 1 znajduje liczby całkowite m i n, takie że m2 - n2 = 2k + 1.

Nie każdy dowód jest konstruktywny - niekiedy można wykazać, że coś istnieje, nie wskazując, jak to znaleźć. Takie dowody nazywamy niekonstruktywnymi. Później przyjrzymy się niektórym interesującym przypadkom dowodów niekonstruktywnych. W szczególności dowód zasady szufladkowej będzie niekonstruktywny, ponieważ nie potrafi on określić konkretnej szufladki zawierającej więcej niż jedną rzecz. Informatycy uwielbiają jednak dowody konstruktywne, ponieważ konstruktywny dowód na istnienie czegoś od razu daje algorytm na obliczenie tego czegoś - i to taki, który można zamienić w użyteczny program komputerowy[2]. Jeszcze jedna uwaga na temat twierdzenia 2.4. Dowód ten nie tylko jest konstruktywny, lecz także dowodzi nawet więcej, niż chcieliśmy. Wykazuje, że nie tylko każda liczba nieparzysta jest równa różnicy dwóch kwadratów liczb całkowitych, lecz także to, że każda liczba nieparzysta jest różnicą kwadratów dwóch następujących po sobie liczb całkowitych. Po zakończeniu dowodu zawsze warto spojrzeć wstecz i zobaczyć, czy nie zawiera on jakichś interesujących informacji wykraczających poza stwierdzenie, które staraliśmy się udowodnić.

***

Bardzo często celem dowodów matematycznych jest ustalenie równoważności dwóch stwierdzeń - tzn. tego, że jedno ze stwierdzeń jest prawdziwe wtedy, gdy prawdziwe jest drugie i na odwrót. Rozważmy na przykład zdanie:

Kwadrat danej liczby całkowitej jest nieparzysty wtedy i tylko wtedy, gdy sama ta liczba jest nieparzysta.

Lub też w bardziej konwencjonalnym stylu matematycznym:

Twierdzenie 2.5. Dla każdej liczby całkowitej n, n2 jest nieparzyste wtedy i tylko wtedy, gdy n jest nieparzyste.

Jest to całkiem typowe twierdzenie matematyczne. Warto odnotować tu kilka spostrzeżeń.

- Używa się tu zmiennej n na oznaczenie tego, o czym się mówi. W ten sposób ta sama nazwa może być użyta w różnych częściach stwierdzenia i odnosić się do tego samego przedmiotu.

- Umownie, użycie nazwy "n" sugeruje, że mówimy o liczbie całkowitej. Inne nazwy sugerują inne rzeczy, np. użycie nazwy "x" sugeruje, że jest to dowolna liczba rzeczywista, zaś "p" - że jest to liczba pierwsza. Użycie nazw sugerujących w ten sposób coś czytelnikowi ułatwia zrozumienie stwierdzenia, chociaż oczywiście z matematycznego punktu widzenia dobór nazw zmiennych jest bez znaczenia.

- Chociaż użyto sugestywnej nazwy zmiennej, twierdzenie niezależnie precyzuje znaczenie nazwy. Zostało podane wprost, że n jest liczbą całkowitą, ponieważ w innych kontekstach "n" może oznaczać liczbę całkowitą dodatnią lub nieujemną, albo jeszcze coś innego.

- W twierdzeniu użyto kwantyfikatora ("dla każdej") w celu sprecyzowania, że własność, którą opisuje, jest spełniona dla wszystkich liczb całkowitych.

- Zdanie "n2 jest nieparzyste wtedy i tylko wtedy, gdy n jest nieparzyste" to tak naprawdę dwa zdania w jednym:

1) "n2 jest nieparzyste wtedy, gdy n jest nieparzyste", czyli innymi słowy: "jeśli n jest nieparzyste, to n2 jest nieparzyste" oraz

2) "n2 jest nieparzyste tylko wtedy, gdy n jest nieparzyste", czyli innymi słowy: "jeśli n2 jest nieparzyste, to n jest nieparzyste".

Oznaczmy literami obie części twierdzenia "wtedy i tylko wtedy": niech p oznacza "n2 jest nieparzyste", zaś q niech oznacza "n jest nieparzyste". Skupmy się na chwilę na znaczeniu wyrażenia "tylko wtedy gdy": "p tylko wtedy gdy q" oznacza to samo, co "jeśli p, to q". Innymi słowy, jeśli wiemy, że p jest prawdą, to jedyną pozostałą możliwością jest to, że q też musi być prawdą, a to właśnie znaczy, że "jeśli p, to q".

Zdanie "wtedy i tylko wtedy" jest prawdziwe tylko wtedy, gdy oba zdania "p jeśli q" i "p tylko jeśli q" są prawdziwe, albo inaczej mówiąc, jeśli oba zdania składowe są równoważne. Wyrażenie "wtedy i tylko wtedy" jest czasami skracane do wtw.

Dowód równoważności dwóch zdań często składa się z dwóch dowodów, w których wykazuje się, że każde z dwóch zdań pociąga za sobą drugie. W przypadku twierdzenia 2.5 udowodnimy, że jeśli liczba jest nieparzysta, to również jej kwadrat jest nieparzysty. Następnie udowodnimy, że jeśli kwadrat liczby jest nieparzysty, to sama ta liczba również jest nieparzysta. Generalnie dowody w różne strony mogą być całkiem inne. Niezależnie od tego, jak trudne było przeprowadzenie dowodu w jedną stronę, cały dowód równoważności jest niekompletny, dopóki nie udowodni się jego prawdziwości również w drugą stronę!

Dowód w pierwszą stronę twierdzenia 2.5. ("jeśli n jest nieparzyste, to n2 jest nieparzyste") można przeprowadzić bezpośrednio. Ten typ dowodu jest prosty: zakładamy, że założenia są prawdziwe i wychodząc od nich, krok po kroku dochodzimy do konkluzji. Jednak wynikanie w drugą stronę ("jeśli n2 jest nieparzysta, to n jest nieparzysta") łatwiej będzie wykazać w nieco inny sposób. W dowodzie bezpośrednim, po przyjęciu założenia, że n2 jest nieparzyste, staralibyśmy się dojść do wniosku, że w takim razie n również musi być nieparzyste - ale wydaje się, że nie istnieje prosty sposób na to. Natomiast równoważnym sposobem dowodzenia jest wykazanie, że gdy n nie jest nieparzyste - tzn. jest parzyste - to n2 również nie jest nieparzyste.

Dowód. Najpierw wykażmy, że jeśli n jest nieparzyste, to n2 również jest nieparzyste. Jeśli n jest nieparzyste, to możemy je zapisać jako n = 2k + 1, gdzie k jest liczbą całkowitą. Wtedy

n2 = (2k + 1)2    (ponieważ n = 2k + 1)

= 4k2 + 4k + 1    (wzór skróconego mnożenia)

= 2(2k2 + 2k) + 1    (wyciągnięcie 2 przed nawias dla dwóch pierwszych wyrażeń)

Niech j będzie liczbą całkowitą równą 2k2 + 2k, wtedy n2 = 2j + 1, zatem n2 jest nieparzyste.

Następnie wykażemy, że jeśli n2 jest nieparzyste, to i n musi być nieparzyste. Przypuśćmy, że tak nie jest dla wszystkich n i że n jest taką szczególną liczbą całkowitą, że n2 jest nieparzyste, ale n nie jest nieparzyste. Ponieważ każda liczba całkowita, która nie jest nieparzysta, jest parzysta, to i n musi być parzyste. Aby udowodnić, że takie n istnieć nie może, musimy wykazać, że jeśli n jest dowolną liczbą parzystą, to i n2 musi być parzyste. Jeśli n jest parzyste, to można je zapisać jako n = 2k, gdzie k jest pewną inną liczbą całkowitą. Wtedy

n2 = (2k)2    (ponieważ n = 2k)

= 4k2

= 2(2k2).

Niech j będzie liczbą całkowitą równą 2k2, wtedy n2 = 2j, więc n2 jest parzyste. Wobec tego poprzednie założenie ("n jest taką liczbą całkowitą, że n2 jest nieparzyste, ale n nie jest nieparzyste") było fałszywe. Zatem prawdziwa jest jego negacja: jeśli n2 jest nieparzyste, to n jest nieparzyste.-

Powyższy dowód składa się z większej liczby kroków niż dowód twierdzenia 2.4 i jest nieco bardziej ustrukturyzowany. Jeśli dowód jest dłuższy, jego poszczególne kroki muszą być spójne, tak by czytelnik zrozumiał nie tylko pojedyncze kroki, ale również ogólną myśl dowodu.

Jeśli dowód jakiegoś kroku pośredniego jest szczególnie długi lub skomplikowany, pomocne może być oddzielne podanie dowodu dla tego kroku, tak by główny ciąg dowodowy nie był nazbyt skomplikowany. Taki krok może stanowić pełnoprawne twierdzenie, ale jeśli nie jest ono zbyt interesujące poza kontekstem dowodzenia głównego twierdzenia, to nazywamy je lematem. Z drugiej strony, jeśli istnieje jakiś ciekawy wynik, który, gdy już udowodnimy jakieś twierdzenie, staje się bardzo łatwy do udowodnienia, to zamiast prezentować go jako oddzielne twierdzenie, mówimy o nim jako o wniosku. Dla przykładu, oto wniosek z twierdzenia 2.5:

Wniosek 2.6. Jeśli n jest nieparzyste, to n4 jest nieparzyste.

Dowód. Zauważmy, że n4 = (n2)2. Ponieważ n jest nieparzyste, to na podstawie twierdzenia 2.5, n2 jest nieparzyste. W takim razie, znów na podstawie tego samego twierdzenia, n4 jest nieparzyste.-

W drugiej części dowodu twierdzenia 2.5 wzięliśmy implikację - zdanie w postaci "jeśli p, to q" - i zamieniliśmy ją na postać równoważną "jeśli nie q, to nie p". W tej części dowodu p oznaczało "n2 jest nieparzyste", zaś q oznaczało "n jest nieparzyste". Istnieje kilka różnych rodzajów implikacji, ważne więc, by móc zidentyfikować i nazwać każdą z nich[3].

Każdą implikację "jeśli p to q" można "odwrócić" na trzy różne sposoby. Odwrotność (implikację przeciwną) otrzymamy, jeśli po prostu zanegujemy oba zdania składowe: "jeśli nie p, to nie q". Konwersję (implikację odwrotną) otrzymujemy, zamieniając zdania miejscami: "jeśli q, to p". Kontrapozycję (implikację przeciwstawną) mamy wtedy, gdy zarówno zamieniamy zdania miejscami, jak i je negujemy: "jeśli nie q, to nie p".

Kontrapozycja dowolnego zdania jest równoważna jemu samemu, więc zawsze możemy udowodnić dane zdanie poprzez udowodnienie jego kontrapozycji - lub odwrotnie. To trochę tak, jakby dowodzić przez sprowadzenie do sprzeczności, jak to widzieliśmy powyżej. To dlatego mogliśmy udowodnić zdanie "jeśli n nie jest nieparzyste, to n2 nie jest nieparzyste". zamiast udowadniać "jeśli n2 jest nieparzyste, to n jest nieparzyste". Każde z tych zdań stanowi kontrapozycję drugiego.

Zauważmy jednak, że odwrotność i konwersja danego zdania nie są mu równoważne. Na przykład w dowodzie powyżej musieliśmy oddzielnie udowodnić, że "jeśli n jest nieparzyste, to n2 jest nieparzyste", oraz że "jeśli n2 jest nieparzyste, to n jest nieparzyste". Każde z tych zdań stanowi konwersję drugiego i nie są one sobie równoważne.

Użyliśmy tu jeszcze jednego przekształcenia stwierdzenia. Negacja zdania p to zdanie głoszące, że p jest fałszywe - innymi słowy, "nie p". Tak więc negacją zdania "n jest nieparzyste" jest w efekcie "n jest parzyste". Natomiast kontrapozycją zdania "jeśli p to q" jest zdanie "jeśli negacja q, to negacja p".

***

Chociaż język matematyki pozwala nam wyrażać nasze myśli w sposób bardziej ogólny, a jednocześnie bardziej precyzyjny, większa abstrakcja potrafi niekiedy zdezorientować. Kiedy wyrażamy w ten sposób myśli, trzeba być bardzo ostrożnym i uważać, czy to, co zapisujemy, na pewno ma sens. W dowodzie każdy krok musi wynikać z poprzednich, doradzamy więc sceptycyzm. Rozważmy na przykład następujący fałszywy dowód, że 1 = 2:

Niech a = b. Możemy wówczas zapisać:

a2 = ab    (mnożymy obie strony przez a)

a2 - b2 = ab - b2    (odejmujemy b2 od obu stron)

(a + b)(a - b) = b(a - b)    (wzory skróconego mnożenia dla obu stron)

(a + b) = b    (dzielimy obie strony przez a - b)

2b = b (podstawiamy a pod b z lewej strony, ponieważ a = b)

a zatem 2 = 1    (dzielimy obie strony przez b)

Co zrobiliśmy źle? Zaczynając od niewinnej i jak najbardziej możliwego założenia, że a = b, doszliśmy do niemożliwego wniosku. Gdzieś po drodze w dowodzie musieliśmy więc wykonać krok, który nie ma logicznego sensu.

Błąd nastąpił podczas przejścia od trzeciego do czwartego wiersza. Założyliśmy, że a = b, więc gdy podzieliliśmy przez a - b, tak naprawdę podzieliliśmy przez zero, a to nie jest dozwolona arytmetyczna operacja. Logika więc zawiodła w tym miejscu, a reszta jest nonsensem. Podczas pisania dowodów warto pamiętać o znaczeniu, jakie nadajemy symbolom. Pozwoli nam to uniknąć takich pomyłek jak powyższa.

***

W fałszywym dowodzie, iż 2 = 1, zaprezentowaliśmy coś, co wyglądało jak dowód, ale tak naprawdę nim nie było. Stwierdziliśmy, że gdzieś musiał być popełniony błąd, ponieważ skończyliśmy na zdaniu wewnętrznie sprzecznym. Zmusiło nas to do cofnięcia się w krokach dowodowych, by znaleźć błąd w rozumowaniu. Ten rodzaj rozumowania - wnioskowanie na podstawie uzyskania sprzeczności, że gdzieś w rozumowaniu jest błąd - to tak naprawdę bardzo użyteczna technika dowodzenia. Widzieliśmy już ją w akcji, w przykładzie z dowodem nie wprost (inaczej dowód przez sprowadzenie do sprzeczności, łac. reductio ad absurdum), w drugiej części dowodu twierdzenia 2.5.

Dowód nie wprost zaczyna się przez dodanie do zbioru założeń negacji zdania, które mamy nadzieję udowodnić. Jeśli możemy z tego dojść do sprzeczności (oczywiście bez popełniania po drodze żadnych logicznych błędów), to znaczy, że jedynym miejscem, które mogło być źródłem tej sprzeczności, jest sam początek, tzn. założenie. Ponieważ założenie, iż zdanie jest fałszywe, prowadzi do sprzeczności, możemy wnioskować, że to zdanie musi być prawdziwe.

Jako następny przykład weźmiemy dowód nie wprost tego, że ?2 jest liczbą niewymierną. Jak zwykle, przede wszystkim upewnijmy się, że rozumiemy zdanie, o którym mowa. Liczbą wymierną jest taka liczba, którą można przedstawić jako iloraz dwóch liczb całkowitych. Na przykład liczba 1,25 jest liczbą wymierną, ponieważ można ją przedstawić jako 5/4 (albo 125/100, albo na wiele innych sposobów). Liczba jest niewymierna, jeśli nie jest wymierna: a to znaczy, że nie może być przedstawiona jako iloraz jakichkolwiek dwóch liczb całkowitych.

Można oczywiście próbować udowodnić wprost, że ?2 jest liczbą niewymierną, ale właściwie nie bardzo wiadomo, jak to zrobić (ani nawet jak zacząć!). Tak więc zamiast to robić, zastanówmy się, co by było, gdyby to zdanie nie było prawdziwe i zbadajmy, czy aby logiczne konsekwencje tego założenia nie są sprzeczne wewnętrznie.

Twierdzenie 2.7. ?2 jest liczbą niewymierną.

Dowód. W celu uzyskania sprzeczności załóżmy, że twierdzenie jest fałszywe, tzn. ?2 nie jest liczbą niewymierną. To oznacza, że ?2 jest liczbą wymierną, czyli ilorazem dwóch liczb całkowitych. Załóżmy więc, że ?2 = a/b dla pewnych liczb całkowitych a, b ?2, z których co najwyżej jedna jest parzysta. To dodatkowe założenie jest bezpieczne, bo gdyby obie były parzyste, to moglibyśmy podzielić każdą przez 2 i w ten sposób otrzymać ułamek o tej samej wartości, lecz o mniejszym liczniku i mianowniku

Jeśli powtórzymy ten krok wystarczającą liczbę razy, otrzymamy iloraz, w którym licznik lub mianownik jest nieparzysty (lub oba). Możemy więc założyć - bez utraty ogólności - że ?2 = a/b oraz co najmniej jedna z liczb a, b jest nieparzysta. Ponieważ ?2 = a/b, to mnożąc obie strony równania przez b, otrzymamy b ? ?2 = a. Podniesienie obu stron równania do drugiej potęgi da nam:

(2.8)

Okazuje się zatem, że a2 jest podzielne przez 2. Wobec tego a2 nie jest nieparzyste, tak więc według twierdzenia 2.5 również a nie jest nieparzyste - innymi słowy, a jest podzielne przez 2. Możemy więc zapisać a = 2k, gdzie k jest jakąś inną liczbą całkowitą. Wzór (2.8) przyjmuje zatem postać:

Po podzieleniu obu stron przez 2 otrzymujemy b2 = 2k2. Tak więc b2 jest parzyste, a zatem i b musi być parzyste. Wykazaliśmy jednak, że zarówno a, jak i b są parzyste. Stoi to w sprzeczności z założeniem, że co najwyżej jedna spośród liczb a, b jest parzysta! Wobec tego ?2 musi być niewymierne, co było do wykazania.-

***

Niekiedy łatwiej przeprowadzić dowód, jeśli dowodzone twierdzenie można rozbić na mniejsze części, które możemy następnie udowodnić niezależnie od siebie, po czym złożyć dowód w całość. Prostą wersją tej techniki jest przypadek dowodu twierdzenia 2.5 na stronie 17, kiedy to rozbiliśmy zdanie "wtedy i tylko wtedy" na dwie implikacje dowodzone oddzielnie. Innym przykładem wykorzystania tej techniki dowodzenia jest tak zwana analiza przypadków, w której ogólne stwierdzenie na temat jakiejś klasy rozbijamy na kilka stwierdzeń dotyczących podklas. Jeśli dane twierdzenie możemy udowodnić niezależnie w odniesieniu do wszystkich rodzajów obiektów, to musi być ono prawdziwe również ogólnie. Prosty przykład takiej analizy widzieliśmy na stronie 7, kiedy to chcieliśmy znaleźć liczbę pierwszą większą od k pierwszych liczb pierwszych p1, ..., pk i uzasadnialiśmy, że (p1 - ... - pk) + 1 jest albo liczbą pierwszą, albo ma dzielniki pierwsze większe od którejkolwiek z liczb pi i w ten sposób doszliśmy do pożądanej konkluzji. W następnym przykładzie zastosowano nieco bardziej skomplikowaną analizę przypadków.

Przykład 2.9. Wykaż, że w dowolnej grupie 6 osób jest są 3 osoby znające się nawzajem albo 3 zupełnie sobie obce osoby (relacja "znajomości" jest symetryczna - jeśli A zna B, to B zna A)[4].

Rozwiązanie do przykładu. Zacznijmy od wyboru dowolnej osoby X spośród naszej szóstki. Wśród pozostałej piątki ludzi muszą istnieć przynajmniej 3 osoby, których X nie zna lub przynajmniej 3 osoby, które X zna (patrz zadanie 2.15). W zależności od tego, który z tych przypadków jest prawdziwy, dowód rozdziela się na dwa główne przypadki, a każdy z nich zawiera następne dwa podprzypadki.

Przypadek 1. X zna przynajmniej 3 osoby. Rozważmy zatem relacje między tym trojgiem. Jeśli spośród nich żadna dwójka się nie zna, to tworzą oni zbiór trzech osób, z których żadne nie zna pozostałych. Jeśli spośród tych trojga jakaś dwójka zna się nawzajem, to ta dwójka oraz X tworzą zbiór trzech osób, z których każdy zna się z każdym.

Przypadek 2. Są przynajmniej trzy osoby, których X nie zna. Rozważmy tę trójkę. Jeśli wszyscy oni znają się nawzajem, to tworzą oni zbiór trojga osób, spośród których wszyscy znają wszystkich. W przeciwnym razie przynajmniej dwoje z nich nie zna się nawzajem i w tym przypadku tworzą oni wraz z X zbiór trzech osób, którzy nie znają się nawzajem.-

W tym dowodzie rozumowanie w przypadku 2 wygląda bardzo podobnie do tego w przypadku 1, tylko role "znania" i "nie znania" się odwracają. Poza tą zamianą rozumowanie są identyczne. Ten przykład ilustruje nam inną powszechnie używaną i użyteczną technikę dowodzenia: symetrię.

Na rysunku 2.1 zilustrowano przykład symetrii w rozumowaniu. Widzimy tam graf, rodzaj diagramu, któremu przyjrzymy się szczegółowo w rozdziałach 16-18. A, B,... , F reprezentują sześć osób. Jeśli dwie osoby się znają, to łącze je niebieska linia, a w przeciwnym razie - łączy je linia czerwona. Tak więc przypadek 1 zachodzi, jeśli X jest kimś, jak E na ilustracji, kto zna (jest połączony niebieskimi liniami z) przynajmniej trzy osoby, zaś przypadek 2 zachodzi, jeśli X jest kimś, kto - jak A na ilustracji - nie zna (jest połączony czerwonymi liniami z) przynajmniej trzech innych osób. Oba rozumowania są identyczne, poza tym, że odwraca się w nich rola niebieskich i czerwonych linii. Antycypując terminologię, którą poznamy dopiero potem, można powiedzieć, że jeśli w grafie o 6 wierzchołkach i krawędziach między każdymi dwoma wierzchołkami każda krawędź ma jeden z dwóch możliwych kolorów, to graf ten musi zawierać monochromatyczny (jednokolorowy) trójkąt. (Na rysunku 2.1 taki trójkąt tworzą wierzchołki E, B i D).

Rysunek 2.1. Graf ilustrujący relacje pomiędzy 6 osobami, gdzie niebieskie linie łączą pary osób znających się nawzajem, zaś czerwone linie łączą nieznajomych

Kiedy już zidentyfikujemy symetrię, nie ma sensu podawać dwa razy w zasadzie tego samego rozumowania. Zamiast tego w przypadku 2 moglibyśmy napisać tylko coś w rodzaju "Jeśli są przynajmniej 3 osoby, których X nie zna, to rozumowanie jest symetryczne w stosunku do poprzedniego przypadku, jedynie zamienione są w nim "znania" i "nie znania". Uzasadnienie na podstawie symetrii może być zarazem krótsze i pozostawić czytelnika z głębszym poczuciem zrozumienia niż te, w których nie stosujemy symetrii. W tym przypadku nawet sformułowanie twierdzenia staje się dzięki symetrii prostsze, ponieważ jednokolorowy trójkąt może reprezentować zarówno 3 osoby, które się znają, jak i 3 nieznajomych.

Podsumowanie rozdziału

- Dowód jest formalnym, ogólnym i precyzyjnym matematycznym rozumowaniem rozpoczynającym się od jednego lub więcej założeń i przeprowadzanym z użyciem reguł logiki w celu określenia wniosku.

- Kwantyfikatory, takie jak "dla wszystkich", "dla dowolnego", "dla każdego", "dla niektórych" i "istnieje", określają zasięg predykatu.

- Predykat jest schematem zdania przyjmującym jeden lub więcej argumentów. Predykat sam w sobie nie jest ani prawdziwy, ani fałszywy, ale przyjmuje wartości logiczne, jeśli go zastosować do konkretnych argumentów.

- Dowód konstruktywny pokazuje, jak odnaleźć coś, co rzekomo istnieje. Dowód niekonstruktywny wykazuje, że coś istnieje, bez pokazania, jak to coś odnaleźć.

- Algorytm to szczegółowa i precyzyjna procedura, która można być przeprowadzona w sposób mechaniczny - na przykład przez komputer.

- Aby udowodnić, że dwa zdania są sobie równoważne, często najłatwiej niezależnie udowodnić wynikanie w obu kierunkach: aby udowodnić, że "p wtedy i tylko wtedy, gdy q", wykazujemy oddzielnie "p wtedy gdy q" i "p tylko wtedy gdy q".

- Dowód wprost (bezpośredni) zaczynamy od przyjęcia założeń, a następnie na ich podstawie dochodzimy do udowadnianej tezy

- Dowód nie wprost (reductio ad absurdum) rozpoczynamy od zanegowania dowodzonego zdania i opierając się na tym założeniu dochodzimy do sprzeczności.

- Dla zdania "jeśli p, to q" kontrapozycją jest zdanie "jeśli nie q, to nie p". Jego inwersją jest zdanie "jeśli nie p, to nie q", zaś jego konwersją jest "jeśli q, to p". Negacją zdania p jest "nie p".

- Dane zdanie i jego kontrapozycja są sobie równoważne (inwersja i konwersja nie są równoważne zdaniu początkowemu), więc w celu udowodnienia danego zdania wystarczy udowodnić jego kontrapozycję.

- Analiza przypadków dowodzi pewnego ogólnego twierdzenia poprzez rozbicie go na wiele twierdzeń ograniczonych, które łącznie wyczerpują wszystkie możliwości. Każdego z przypadków dowodzi się oddzielnie, niezależnie od pozostałych.

- Uzasadnienie na podstawie symetrii pozwala nam uniknąć powtarzania niemal identycznych rozumowań.

Zadania

2.1. Czy według podanej przez nas definicji -1 jest liczbą nieparzystą? Dlaczego tak lub dlaczego nie?

2.2. Zapisz inwersję, konwersję i kontrapozycję następującego zdania: Jeśli pada deszcz, to mam ze sobą parasol.

2.3. Wykaż, że iloczyn dwóch liczb nieparzystych jest liczbą nieparzystą.

2.4. Wykaż, że ?3 jest liczbą niewymierną.

2.5. Wykaż, że 3?2 jest liczbą niewymierną.

2.6. Wykaż, że dla każdej liczby całkowitej dodatniej n, ?n jest albo liczbą całkowitą, albo niewymierną.

2.7. Wykaż, że istnieje uczciwa kostka siedmiościenna, tj. wielościan o siedmiu ścianach, który rzucony ma jednakowe prawdopodobieństwo upadnięcia na dowolną ze swoich ścian. Podpowiedź: Rozumowanie nie jest ścisłym dowodem matematycznym i opiera się częściowo na intuicji w odniesieniu do własności przedmiotów fizycznych o podobnych kształtach geometrycznych, rozciągniętych w jednym z wymiarów.

2.8. Wykaż, że wszystkie parzyste liczby kwadratowe są podzielne przez 4.

2.9. (a) Wykaż lub podaj kontrprzykład: jeśli c oraz d są liczbami kwadratowymi, to cd jest liczbą kwadratową.

(b) Wykaż lub podaj kontrprzykład: jeśli cd jest liczbą kwadratowa i c ? d, to c oraz d są liczbami kwadratowymi

(c) Wykaż lub podaj kontrprzykład: jeśli c oraz d są liczbami kwadratowymi takimi, że c > d oraz x2 = c i y2 = d, to x > y (zakładamy, że x oraz y są liczbami całkowitymi).

2.10. Wykaż poprzez sprowadzenie do sprzeczności, że jeśli 17n + 2 jest nieparzyste, to n jest nieparzyste.

2.11. Obal następujący fałszywy dowód:

2.12. Co stanowi konwersję kontrapozycji zdania "jeśli p, to q"? Jakiemu prostszemu zdaniu jest ona równoważna?

2.13. Zapisz następujące stwierdzenia za pomocą kwantyfikatorów i implikacji. Można założyć, że wyrażenia "dodatni", "rzeczywisty" i "pierwszy" są zrozumiałe, ale "parzyste" i "różne" trzeba wyrazić w zdaniu.

(a) Każda dodatnia liczba rzeczywista ma dwa różne pierwiastki kwadratowe.

(b) Każdą dodatnią liczbę parzystą można wyrazić jako sumę dwóch liczb pierwszych[5].

2.14. Wykaż poprzez dowód niekonstruktywny, że istnieją takie liczby niewymierne x i y, że xy jest liczbą wymierną. Podpowiedź: rozważ liczbę i przeanalizuj dwa przypadki: jest ona wymierna lub niewymierna. W drugim przypadku spróbuj ją podnieść do potęgi ?2.

2.15. Korzystając z pojęć przedstawionych w rozdziale 1, wyjaśnij krok dowodu z przykładu 2.9, w którym stwierdzono, że gdy wybierzemy pojedynczą osobę X, to "wśród pozostałych 5 osób musi być przynajmniej 3, które X zna, lub przynajmniej 3, których nie zna".

Rozdział 3Dowód przez indukcję matematyczną

Ile wynosi suma n pierwszych potęg 2?

Jak zwykle, pierwszym krokiem prowadzącym do rozwiązania podobnego problemu jest upewnienie się, że rozumie się, o czym mowa. Czym jest potęga 2? Jest to liczba taka jak 23, czyli 8, która jest równa dwójce podniesionej do jakiejś całkowitej potęgi. No dobrze, w takim razie czym jest n? O tym nie ma ani słowa! W takim razie n może być czymkolwiek, dla czego reszta pytania ma sens. W pytaniu mowa o dodawaniu do siebie rzeczy, a n jest liczbą rzeczy, które do siebie dodajemy. Tak więc "n" musi być zmienną reprezentującą liczbę całkowitą, jak np. 10. Na końcu musimy się upewnić, że rozumiemy, co to znaczy n "pierwszych" potęg 2. Czy "pierwsza" potęga 2 jest równa 20, czy 21, a może jest to jeszcze co innego? W informatyce często liczenie zaczyna się od 0.

Gdybyśmy znali wartość n, moglibyśmy po prostu obliczyć odpowiedź. Na przykład dla n = 10 pytamy o wartość

która, jak się okazuje, wynosi 1023.

Ale nie chcemy tylko i wyłącznie odpowiedzi dla przypadku n = 10. Pytanie zostało zadane z użyciem zmiennej n, więc oczekiwana jest odpowiedź odnosząca się w jakiś sposób do n. A dokładniej, poszukujemy wartości wyrażenia

Każdy element takiej sumy nazywamy składnikiem (wyrazem) - zatem w powyższej sumie składnikami są 20, 21, ..., 2n-1. Zauważmy, że ostatnim składnikiem jest 2n-1, nie 2n. Zaczęliśmy liczyć od 0, więc pierwsze n potęg 2 to 2 to potęgi 0, 1, 2, ... i n-1, a ostatnim z n składników jest 2n-1.

Wielokropek "..." nazywamy elipsą. Sugeruje on schemat, który powinien być oczywisty dla czytelnika. Ale oczywistość mieszka w umyśle patrzącego i być może nie zgadza się z intencjami autora. Gdybyśmy dysponowali jedynie wzorem

(3.1)

to czy jest oczywiste, jakie wyrażenia ominęliśmy, a nawet ile ich było? Nie bardzo. Wcześniej mówiliśmy, że rozważamy sumy potęg dwójki, ale gdybyśmy mieli jedynie wzór (3.1), to istniałby więcej niż jeden sposób ekstrapolacji brakujących składników. Być może chodzi o to, że drugi składnik jest o jeden większy od pierwszego, trzeci - o dwa większy od drugiego i tak dalej? W takim wypadku czwarty składnik byłby o trzy większy od trzeciego, czyli równałby się 7. Wtedy byłby to

(3.2)

a nie

Pewnego wysiłku wymaga ustalenie, czy 512 mogłoby być ostatnim składnikiem ciągu określonego tak jak (3.2) (patrz zadanie 3.10).

Sposobem na uniknięcie dwuznaczności w podobnych sytuacjach jest znalezienie sposobu zapisu typowego wyrazu ciągu i użycie "notacji sumy" dla pokazania, jakie wyrażenia do siebie dodajemy. Typowa potęga dwójki wygląda tak: 2i - musimy wybrać zmienną inną niż n dla wykładnika, ponieważ n używamy już do oznaczenia liczby dodawanych do siebie składników. Sumę pierwszych n wyrazów tej postaci możemy wtedy jednoznacznie zapisać w sposób następujący:

(3.3)

Symbol ? to grecka wielka litera sigma, oznaczająca "sumę".

W przeciwieństwie do notacji z elipsą, notacja sumy nie zostawia nic dla wyobraźni. Ma sens nawet w przypadku n = 1 czy n = 0. Gdy n = 1, (3.3) przyjmuje postać

czyli sumy złożonej z jednego wyrazu. Gdy n = 0, górne ograniczenie sumowania jest mniejsze od dolnego, więc (3.3) staje się sumą 0 wyrazów, czyli umownie jest równe 0:

pusta suma

Rozpatrzmy następny przykład: jak zapisalibyśmy sumę pierwszych n liczb nieparzystych? Liczby nieparzyste to liczby o postaci 2i + 1, zaś pierwszą liczbą nieparzystą jest 1, czyli 2i + 1 gdzie i = 0. Zatem sumę n pierwszych liczb nieparzystych można zapisać następująco[6]:

Powróćmy teraz do pytania zadanego na początku tego rozdziału. Czy można znaleźć prosty wzór równoważny (3.3) bez żadnych wielokropków ani znaku sumowania?

Gdy już jesteśmy pewni, że zrozumieliśmy pytanie, pierwszą rzeczą do zrobienia jest przyjrzenie się kilku przykładom. Możemy dzięki temu zyskać jakieś pojęcie na temat tego, co tu się dzieje. Tej samej strategii używaliśmy do przy dowodzie twierdzenia 2.4. Spróbujmy z n = 1, 2, 3:

(3.4)

Wartości 1, 3 i 7 są o jeden mniejsze od odpowiednio 2, 4, i 8, które z kolei stanowią kolejne potęgi dwójki. Wypróbujmy jeszcze jeden przykład, zanim sformułujemy naszą hipotezę:

(3.5)

15 także jest o 1 mniejsze niż 16, czyli następnej potęgi dwójki. Jeszcze niczego nie udowodniliśmy, ale prawidłowość ta jest zbyt regularna, by była zwykłym zbiegiem okoliczności. Sformułujmy więc hipotezę

(3.6)

Czy dobrze to zapisaliśmy? A może prawa strona powinna wyglądać tak: 2n-1 - 1, a może tak: 2n+1 - 1? Podstawmy we wzorze 4, tak dla pewności. Dla n = 4 lewa strona jest taka sama jak (3.5), a mianowicie 15. Tymczasem prawa strona równania (3.6) jest równa 24 - 1 = 15. Tak więc (3.6) wygląda na dobrą hipotezę. Działa nawet w przypadku n = 0:

(3.7)

ponieważ lewa strona, gdzie końcowa wartość i jest mniejsza niż początkowa, opisuje sumę zerowej liczby składników, która jest równa 0.

Nadal nie jest to jednak dowód. Teraz potrzebujemy jakiegoś błyskotliwego spostrzeżenia. Musi być jakiś powód, dla którego (3.5) wynika z (3.4). Mianowicie to, że jeśli 23 dodamy do 23 - 1, to wynikiem będzie 23 + 23 - 1 = 2 - 23 - 1 = 24 - 1.

Prawidłowość, że dodanie do potęgi dwójki do siebie samej daje nam następną potęgę dwójki, jest spełniona w przypadku ogólnym. Przypuśćmy więc, że wiemy, iż wzór (3.6) jest spełniony dla danej wartości n. W dowodzie indukcyjnym taką przesłankę nazywamy hipotezą indukcyjną. Sedno dowodu, krok indukcyjny, polega na tym, by udowodnić, że jeśli hipoteza indukcyjna jest prawdziwa, to ten sam predykat jest spełniony również dla następnej wartości, tzn. wtedy, gdy n zostanie zastąpione przez n + 1. Oto dowód kroku indukcyjnego:

co jest dokładnie tym, co obiecuje (3.6), gdy podstawimy n + 1 w miejsce n.

Jest to klasyczny przykład dowodu przez indukcję matematyczną. Termin "indukcja" odnosi się do idei, że prawdziwość danego zdania w odniesieniu do jednej wartości n pociąga prawdziwość tego zdania dla następnej wartości, n + 1. Jeśli zatem możemy potwierdzić prawdziwość tego zdania dla dowolnej wartości, wiemy, że jest również ono prawdziwe dla każdej większej wartości. Podobnie, jeśli mamy niezawodny sposób przechodzenia z jednego szczebla drabiny na następny, to wynika z tego, że możemy dotrzeć na każdy szczebel powyżej pierwszego takiego szczebla, o którym wiemy, że możemy na niego wejść (patrz rys. 3.1).

Rysunek 3.1. Metafora drabiny dla indukcji matematycznej. Jeśli można wejść na dolny szczebel drabiny (przypadek bazowy) i jeśli pod warunkiem, że doszło się do dowolnego wybranego szczebla (hipoteza indukcyjna), można wejść na następny szczebel (krok indukcyjny), to wtedy można wejść na każdy szczebel drabiny (wniosek)

Obok widzimy ogólny schemat dowodu przez indukcję (patrz rysunek 3.2).

Rysunek 3.2. Zasada indukcji matematycznej. Rozpoczynamy od wykazania przypadku bazowego (P(n0), na czerwono). Następnie wykazujemy, że jeśli P(n) jest prawdziwe (ostatnia zielona wartość), to wtedy również P(n + 1) musi być prawdą (wartość niebieska)

Aby udowodnić, że predykat P(n) jest spełniony dla każdej liczby n większej lub równej pewnej liczbie n0:

Przypadek bazowy. Udowodnij P(n0).

Hipoteza indukcyjna. Niech n będzie dowolną, ale ustaloną liczbą większą lub równią n0 i załóżmy P(n).

Krok indukcyjny. Po przyjęciu hipotezy indukcyjnej udowodnij P(n + 1).

Zastosujmy ten schemat tak, by dać poprawny dowód hipotezy (3.6), ukrywając wszystkie szczególne przypadki i przypuszczenia, które czyniliśmy, aby określić, co może stanowić ogólny predykat.

Przykład 3.8. Dla każdego n ? 0,

Rozwiązanie do przykładu. W odniesieniu do schematu indukcji P(n) jest predykatem

zaś n0 = 0.

Przypadek bazowy. P(0) jest stwierdzeniem, że

które jest prawdziwe, ponieważ zarówno lewa, jak i prawa strona równania są równe 0 (patrz wzór (3.7)).

Hipoteza indukcyjna. Założeniem indukcyjnym jest P(n), to znaczy

gdzie n ? 0 jest jakąś ustaloną dowolną wartością.

Krok indukcyjny. Musimy wykazać, że jest spełniony P(n + 1), to znaczy

(3.9)

Jeśli wyciągniemy poza nawias ostatni dodawany wyraz, lewa strona (3.9) wygląda następująco:

Ale według hipotezy indukcyjnej jest dokładnie równa 2n - 1, więc w celu dokończenia dowodu musimy wykazać, że

co jest prawdą, ponieważ 2n + 2n = 2n+1.-

***

Jak pokazuje nam to następny przykład, technika dowodu przez matematyczną indukcję jest bardzo silna i elastyczna.

Przykład 3.10. Dla każdego n ? 0,

(3.11)

Rozwiązanie do przykładu. Niech P(n) oznacza predykat

(3.12)

Przypadek bazowy. n0 = 0. Dla P(0) suma po lewej stronie jest pusta, więc ma wartość 0, zaś wyrażenie po prawej stronie przyjmuje postać (0 - (0 + 1))/2, co również daje 0.

Hipoteza indukcyjna. Przyjmijmy, że jest spełniony P(n), czyli

gdzie n ? 0 jest ustalone, lecz dowolne.

Krok indukcyjny. Musimy udowodnić P(n + 1), to znaczy

Raz jeszcze, wyciągając ostatnie wyrażenie poza nawias, możemy skorzystać z hipotezy indukcyjnej:

Niekiedy dowód formalny nie wystarcza, by wywołać odpowiednie skojarzenia: po serii działań na symbolach w celu osiągnięcia pożądanego wyniku nadal może nie być jasne, dlaczego dane wyrażenie jest prawdziwe. Interpretacja na konkretnych przykładach może być bardziej satysfakcjonująca. Dobrą interpretację geometryczną wzoru (3.12) (i wielu innych problemów z sumami) stanowią prostokąty złożone z kafelków.

Rysunek 3.3 stanowi geometryczną interpretację (3.12) dla n = 5. Pierwszy rząd ma n czarnych kafelków, następny n - 1, ..., i tak dalej, aż do ostatniego, który zawiera jeden. Wobec tego liczba czarnych kafelków wynosi . Jednak liczbę czarnych kafelków możemy obliczyć również innym sposobem: cały prostokąt ma długość n + 1 i wysokość n, zaś połowa kafelków jest czarna (porównajmy kształt czerwony do czarnego), więc liczba czarnych kafelków będzie równa połowie wszystkich kafelków w prostokącie, czyli (n(n + 1))/2.

Rysunek 3.3. Ile czarnych kafelków tu widzimy? Możemy je policzyć na dwa sposoby: jest to suma liczb 1, ..., n - ale również połowa powierzchni całości. Tak więc obie te wartości muszą być sobie równe

Możemy również podać geometryczną interpretację kroku indukcyjnego. Hipoteza indukcyjna mówi, że . W kroku indukcyjnym chcemy dodać jeszcze n + 1 kafelków, aby otrzymać w sumie ((n+1)(n+2))/2. Na rysunku 3.4 widzimy prostokąt (n + 1) × (n + 2) z lewą górną połową w kolorze czarnym i szarym, a dolną prawą połową w kolorze czerwonym. Czarne kafelki na rysunku 3.4. odpowiadają dokładnie tym z rysunku 3.3, a wraz z dodatkowymi n + 1 szarymi kafelkami ułożonymi po przekątnej pokrywają one dokładnie połowę powierzchni nowego prostokąta (n + 1) × (n + 2).

Rysunek 3.4. Wychodząc od pokrytego w połowie na czarno prostokąta o szerokości n + 1 i wysokości n, możemy dodać n + 1 szarych kafelków, by pokryć połowę powierzchni nowego prostokąta o szerokości n + 2 i wysokości n + 1

***

Czasami zamiast sumy następujących po sobie wartości chcemy wyrazić ich iloczyn. Istnieje do tego odpowiednia notacja z użyciem dużej greckiej liczby pi, ?, analogicznie do ? dla sumy. Na przykład wyrażenie (1.6) na stronie 6 możemy zapisać w postaci:

Elementy, które mnożymy przez siebie, nazywamy czynnikami, tak jak elementy sumy nazywamy składnikami. W powyższym iloczynie czynnikami są .

Wypróbujmy schemat indukcji na twierdzeniu dotyczącym iloczynu.

Przykład 3.13. Dla każdego n ? 1,

(3.14)

Aby przyjrzeć się przykładowi: zgodnie ze wzorem (3.14), dla n = 3 zachodzi:

Zapisanie tego samego w innej postaci sugeruje powód, dla którego zachodzi to w przypadku ogólnym:

Iloczyn każdego z ułamków jest równy mianownikowi następnego, więc wszystkie mianowniki poza ostatnim ulegają skróceniu. Aby podać poprawny dowód, użyjemy indukcji matematycznej.

Rozwiązanie do przykładu. Niech P(n) oznacza następujący predykat:

(3.15)

Przypadek bazowy. n0 = 1 (wzór 3.15) mówi, że:

co jest prawdą, ponieważ obie strony równania mają wartość 2.

Hipoteza indukcyjna. Przypuśćmy, że dla dowolnej ustalonej liczby n ? 1 jest spełniony P(n), tzn.:

Krok indukcyjny. Rozważmy teraz P(n + 1). Lewa strona równania (3.15.) przyjmuje wtedy następującą postać:

co było do udowodnienia.-

Równanie (3.14.) ma sens również w przypadku n = 0, o ile przyjmiemy umownie, że iloczyn zera czynników wynosi 1:

= pusty iloczyn = 1 = 0 + 1

Dlaczego ta konwencja ma sens? Przyjęliśmy podobną konwencję dla sum o zerowej liczbie składników - mianowicie sumy takie równe są 0. Intuicyjnie, jeśli dodamy do siebie kilka składników, a potem dodamy do tego jeszcze zero składników, wtedy "dodanie zera składników więcej" jest równoważne dodaniu 0. Podobnie, jeśli pomnożymy przez siebie kilka czynników, a potem pomnożymy to jeszcze przez zero czynników, wtedy "mnożenie przez jeszcze zero czynników" jest równoważne pomnożeniu przez 1.

***

Indukcję możemy również stosować do dowodzenia faktów na temat obiektów innych niż liczby. W informatyce często spotykamy ciągi zer i jedynek. 1 i 0 będziemy nazywali bitami[7],

zaś ciągi bitów, takie jak np. 10001001 - łańcuchami. W tym przypadku mamy do czynienia z łańcuchem o długości 8. Dopełnieniem łańcucha bitów (dopełnieniem bitowym) nazywamy rezultat operacji polegającej na zastąpieniu wszystkich zer jedynkami i na odwrót. Na przykład dopełnieniem 10001001 jest 01110110. Konkatenacja dwóch łańcuchów bitów polega na zapisaniu jednego łańcucha bezpośrednio po drugim. Konkatenacją 10001001 i 111 jest 10001001111. Długością konkatenacji dwóch łańcuchów jest suma ich długości - 8 + 3=11 w tym przypadku. Istnieje interesujący ciąg łańcuchów bitowych zwany słowem Thue'ego[8], zdefiniowany w następujący sposób:

T0 = 0 i dla każdego n ? 0,

Tn+1 = konkatenacja Tn i dopełnienia Tn.

Powyżej widzimy przykład definicji, którą nazywamy indukcyjną lub rekurencyjną. Definicja T0 jest przypadkiem bazowym, zaś definicja Tn+1 w kategoriach Tn jest przypadkiem konstrukcyjnym. Zobaczmy, jak wygląda kilka pierwszych łańcuchów tego ciągu.

0. T0 = 0; to jest przypadek bazowy.

1. T1 jest wynikiem konkatenacji T0 (tj. 0) z jego dopełnieniem (tj. 1). Stąd T1 = 01.

2. T2 jest wynikiem konkatenacji T1 (tj. 01) z jego dopełnieniem (tj. 10). Stąd T2 = 0110.

3. T3 jest wynikiem konkatenacji T2 (tj. 0110) z jego dopełnieniem (tj. 1001). Stąd T3 = 01101001.

4. T4 jest wynikiem konkatenacji T3 (tj. 01101001) z jego dopełnieniem (tj. 10010110). Stąd T4 = 0110100110010110.

Ponieważ Tn stanowi pierwszą połowę Tn+1 dla każdego n ? 0, możemy zdefiniować nieskończony łańcuch bitów t0t1t2..., po prostu przyjmując, że ti jest i-tym bitem Tn dla każdego n dostatecznie dużego, by Tn miał przynajmniej i bitów. Jeśli na przykład i = 4, to T0, T1 i T2 mają mniej niż 5 bitów, ale dla wszystkich n ? 3 Tn ma długość równą przynajmniej 5 i wszystkie mają ten sam piąty bit. Tym bitem jest t4, który jest równy 1.

Słowo Thue'ego ma kilka bardzo interesujących własności. Wygląda na pełne powtórzeń, ale tak naprawdę wcale tak nie jest. Wygląda na dość przypadkowe, ale tak naprawdę w ogóle nie jest przypadkowe. Poniżej dowodzimy kilku prostych własności z pomocą indukcji matematycznej.

Przykład 3.16. Dla każdego n ? 0 długość Tn wynosi 2n.

Rozwiązanie do przykładu. Dowodzimy tego przez indukcję.

Przypadek bazowy. n0 = 0. Słowo Tn0 = T0 = 0, co ma długość 1 = 20 = 2n0 .

Hipoteza indukcyjna. Przyjmijmy, że Tn ma długość 2n.

Krok indukcyjny. Tn+1 to wynik konkatenacji Tn z jego dopełnieniem. Ponieważ oba te łańcuchy mają długość 2n, to długość Tn+1 wynosi 2n + 2n = 2n+1.-

Przykład 3.17. Dla każdego n ? 1, Tn zaczyna się od 01, a kończy na 01, jeśli n jest nieparzyste, zaś kończy się na 10, jeśli n jest parzyste.

Rozwiązanie do przykładu. T1 = 01, więc są to dwa pierwsze bity każdego Tn dla n ? 1. Aby dowieść tego, jaką postać ma koniec Tn, posłużymy się indukcją.

Przypadek bazowy: n0 = 1. Liczba 1 jest nieparzysta, a Tn0 = T0 = 01, czyli kończy się na 01.

Hipoteza indukcyjna: Niech n ? 1 i załóżmy, że Tn kończy się na 01, jeśli n jest nieparzyste, i na 10, jeśli n jest parzyste.

Krok indukcyjny: Tn+1 kończy się dopełnieniem ostatnich dwóch bitów Tn, zaś n + 1 jest parzyste, jeśli n jest nieparzyste, natomiast jest nieparzyste, jeśli n jest parzyste. Zatem Tn+1 kończy się na 01, jeśli n + 1 jest nieparzyste, i na 10, jeśli n + 1 jest parzyste.-

Przykład 3.18. Dla każdego n ? 0, Tn nigdy nie zawiera więcej niż dwa zera lub dwie jedynki z rzędu.

Rozwiązanie do przykładu. T0 ma tylko jeden bit, więc powyższe stwierdzenie jest spełnione dla T0. Twierdzenia dowodzimy przez indukcję, zaczynając od n0 = 1.

Przypadek bazowy. n0 = 1. Wówczas łańcuch Tn0 = T0 = 01 nie zawiera żadnych kolejnych identycznych bitów, wobec tego nie ma więcej niż dwóch kolejnych identycznych bitów.

Hipoteza indukcyjna. Niech n ? 1 i załóżmy, że Tn nie zawiera więcej niż dwa zera lub jedynki z rzędu.

Krok indukcyjny. Tn+1 zawiera bity odziedziczone z Tn w pierwszej swojej połowie oraz bity odziedziczone po dopełnieniu Tn w drugiej swojej połowie. Żadna z wymienionych części nie zawiera fragmentu 000 lub 111, na podstawie hipotezy indukcyjnej. Jeśli więc jeden z tych fragmentów ma zawierać się w Tn+1, musi się znajdować na styku obu części, tak by dwa bity z jednej części i jeden bit z drugiej układały się razem w trzy identyczne, następujące po sobie bity. Jednak na podstawie przykładu 3.17, czterema bitami na styku obu połów mogą być jedynie 0110 lub 1010 - a żadna z tych możliwości nie dopuszcza trzech identycznych bitów z rzędu (patrz rys. 3.5).-

Rysunek 3.5. Tworzenie T2 z T1 i jego dopełnienia, T3 z T2 i jego dopełnienia oraz T4 z T3 i jego dopełnienia. Czerwone bity stanowią dopełnienie czarnych bitów. Ani czarne, ani czerwone bity nie zawierają podsłowa 000 ani 111, jeśli więc ma się ono zawierać w łańcuchu będącym wynikiem konkatenacji, musi się to zdarzyć na styku, w czterobitowym wyróżnionym okienku. Okienka te zawierają jednak zawsze 0110 albo 1010

Niektóre inne własności słowa Thue'ego są tematem zadań 3.11 i 11.11.

***

Możemy użyć indukcji matematycznej, by dowieść zasady szufladkowej, na co czekamy przecież od strony 3! Wymaga to nieco zastanowienia, ponieważ sama zasada nie wspomina nigdzie o liczbie n, "według której" można "przeprowadzić indukcję". W przypadku ogólnym zmienna taka zwana jest zmienną indukcji - w poprzednich przykładach zawsze była oznaczana jako "n".

Przykład 3.19. Jeśli f : X ? Y i |X| > |Y|, to istnieją elementy x1, x2 ? X, takie że x1 ? x2 i f(x1) = f(x2).

Rozwiązanie do przykładu. Aby przeprowadzić dowód przez indukcję, musimy określić zmienną. Istnieją dwie dość oczywiste możliwości: moc zbioru X i moc zbioru Y. Możemy użyć dowolnej z tych możliwości, jednak dowody są wtedy nieco różne. Tutaj zrobimy to poprzez indukcję po |X|. W tym celu przeformułujmy zasadę jako stwierdzenie, że P(n) jest prawdziwe dla każdego n ? 2, gdzie P(n) mówi, że

Dla dowolnych skończonych zbiorów X i Y, takich że |X| > |Y| oraz |X| = n, jeśli f : X ? Y, to istnieją dwa różne elementy x1, x2 ? X, takie że f(x1) = f(x2).

W zadaniu 3.2. przeprowadzamy indukcję po mocy zbioru Y zamiast po mocy zbioru X.

Przypadek bazowy. n0 = 2. Jeśli |X| > |Y| i |X| = 2 oraz istnieje funkcja z X do Y, to |Y| musi wynosi 1: Y musi zawierać co najmniej jeden element, ponieważ f(x) ? Y dla każdego x ? X. Y nie może też zawierać więcej niż jednego elementu, skoro jest mniej liczny niż X. Wtedy jednak oba elementy X muszą zostać odwzorowane na jedyny element Y, co było do udowodnienia.

Hipoteza indukcyjna. Załóżmy, że dla pewnego dowolnego ustalonego n ? 2 oraz dla dowolnych skończonych zbiorów X i Y, takich że |X| > |Y| oraz |X| = n, jeśli f: X ? Y, to istnieją różne elementy x1, x2 ? X, takie że f(x1) = f(x2).

Krok indukcyjny. Chcemy udowodnić, że jeśli |X| > |Y|, |X| = n + 1 oraz f : X ? Y, to istnieją różne elementy x1, x2 ? X, takie że f(x1) = f(x2).

Wybierzmy dowolny element x ? X. Istnieją dwie możliwości (to, co teraz nastąpi, to analiza przypadków). Albo istnieje taki element x? ? X, że x? ? x oraz f(x?) = f(x), albo nie. W pierwszym przypadku (patrz rys. 3.6) krok indukcyjny jest udowodniony, bo znaleźliśmy dwa różne elementy X, które są odwzorowane na ten sam element w Y. W drugim przypadku x jest jedynym elementem X, którego wartość w f jest równa f(x) (patrz rys. 3.7). Niech X? będzie zbiorem otrzymanym poprzez usunięcie x z X, zaś Y? - zbiorem otrzymanym poprzez usunięcie f(x) z Y. Teraz |X?| = n, zaś |Y?| = |Y| - 1 < n, zatem można zastosować hipotezę indukcyjną. Funkcja f ? : X? ? Y? identyczna z f na elementach X? jest wtedy funkcją ze zbioru o mocy n w zbiór mniej liczny. Na podstawie hipotezy indukcyjnej istnieją wtedy różne od siebie x1, x2 ? X?, takie że f ?(x1) = f ?(x2) ? Y?. Ale wówczas x1, x2 są również elementami X, dla których f ma identyczne wartości.-

Rysunek 3.6. Dowód przez indukcję zasady szufladkowej, przypadek 1: x i x? są różnymi elementami X odwzorowanymi przez f na f(x)

Rysunek 3.7. Przypadek 2: x jest jedynym elementem X, który f odwzorowuje na f(x). Poprzez usunięcie x z X oraz f(x) z Y otrzymujemy funkcję f ? : X? ? Y?, do której można zastosować hipotezę indukcyjną, ponieważ że |X?| = |X| - 1

Podsumowanie rozdziału

- Notacji sumy używamy dla oznaczenia sumy ciągu wyrazów. Na przykład wyrażenie

oznacza sumę wyrazów 2i dla wartości i znajdujących się w przedziale od 0 do n - 1.

- Umownie suma zera wyrazów jest równa 0.

- Dowód przez indukcję składa się z trzech następujących części:

Przypadek bazowy. Dowód na to, że predykat jest spełniony dla danej wartości n0.

Hipoteza indukcyjna. Założenie, że predykat jest spełniony dla pewnej ustalonej wartości n ? n0.

Krok indukcyjny. Dowód na to, że jeśli hipoteza indukcyjna jest prawdziwa, to predykat jest spełniony również dla n + 1.

Dzięki temu można ustalić, że predykat jest spełniony dla wszystkich wartości większych lub równych n0.

- Notacji iloczynu używamy dla oznaczenia iloczynu ciągu czynników. Na przykład wyrażenie

oznacza iloczyn czynników dla wartości i zawartych w przedziale od 1 do k.

- Umownie iloczyn zera czynników równy jest 1.

- Definicja indukcyjna bądź rekurencyjna definiuje pewien ciąg przy użyciu przypadków: bazowego i konstrukcyjnego. Przykładem tak zdefiniowanego obiektu jest słowo Thue'ego.

Zadania

3.1. Znajdź postać zamkniętą (bez wielokropków i symboli sumowania) dla wyrażenia ze strony 30,

3.2. Udowodnij zasadę szufladkową poprzez indukcję (przykład 3.19) po |Y| zamiast po |X|.

3.3. Udowodnij przez indukcję rozszerzoną zasadę szufladkową (s. 5).

3.4. (a) Korzystając z notacji ?, zapisz wyrażenie na sumę pierwszych n nieparzystych potęg 2 (tj. sumę 21, 23 itd.). Dowiedź przez indukcję, że wartość tej sumy równa się 2(4n - 1)/3.

(b) Korzystając z notacji ?, zapisz wyrażenie na iloczyn pierwszych n ujemnych potęg 2 (tj. iloczyn 2-1, 2-2 itd.). Jaka jest jego wartość?

3.5. Udowodnij przez indukcję, że dla dowolnego n ? 0,

3.6. Niech dla dowolnego n ? 0:

Chcemy wykazać, że S(n) jest zawsze mniejsze od 2, ale dla dostatecznie dużego n staje się dowolnie bliskie 2.

(a) Ile wynoszą S(0), S(1), S(2) i S(3)?

(b) Sformułuj hipotezę na temat ogólnego wzoru na S(n) w postaci:

S(n) = 2 - ....

(c) Wykaż przez indukcję, że wzór ten jest prawdziwy dla każdego n ? 0.

(d) Niech ? będzie małą dodatnią liczbą rzeczywistą. Jak duże musi być n, aby S(n) różniło się od 2 o najwyżej ??

3.7. Wykaż przez indukcję, że dla każdego n ? 0,

3.8. Wykaż przez indukcję, że dla każdego n ? 1,

(a)

(b)

3.9. Co jest nie tak z następującym "dowodem"?

Wszystkie konie są tego samego koloru.

Przypadek bazowy. Rozważmy zbiór koni o liczebności 1. Jest w nim tylko jeden koń, a jest on tego samego koloru, co on sam, więc twierdzenie jest spełnione.

Hipoteza indukcyjna. Załóżmy, że dla wszystkich zbiorów koni o liczebności n ? 1 wszystkie konie w danym zbiorze są tego samego koloru.