0.Wstęp
Rozpoczniemy od przyjrzenia się tym obszarom teorii obliczeń, które zostaną przedstawione w tej książce. Następnie Czytelnik będzie miał okazję poznania i/lub przypomnienia sobie pewnych koncepcji matematycznych, których będzie później potrzebować.
0.1 Automaty, obliczalność i złożoność
Książka ta skupia się na trzech obszarach tradycyjnie związanych z teorią obliczeń: automatach, obliczalności i złożoności. Obszary te łączy pytanie:
Jakie są fundamentalne możliwości i ograniczenia komputerów?
Pytanie to sięga do lat 30. XX wieku, gdy logicy matematyczni po raz pierwszy zaczęli rozważać naturę obliczeń. Postępy techniczne od tego czasu znacznie powiększyły nasze zdolności obliczania i spowodowały, że pytanie to przestało być domeną teorii, a stało się częścią świata zastosowań praktycznych.
W każdym z tych trzech obszarów - automatów, obliczalności i złożoności - pytanie to jest odmiennie interpretowane i odpowiedzi zmieniają się zgodnie z tą interpretacją. Po tym wprowadzającym rozdziale będziemy badać każdy z tych obszarów w oddzielnych częściach książki. W tym miejscu przedstawimy te części w odwrotnej kolejności, gdyż dzięki rozpoczęciu od końca Czytelnik będzie mógł lepiej zrozumieć uwarunkowania stojące na początku.
Teoria złożoności
Problemy obliczeniowe występują w rozmaitych odmianach; niektóre są łatwe, inne naprawdę trudne. Na przykład problem sortowania należy do tych łatwych. Załóżmy, że potrzebujemy uporządkować listę liczb w kolejności rosnącej. Nawet niewielki komputer potrafi dość szybko posortować milion liczb. Porównajmy to z problemem planu zajęć. Załóżmy, że musimy znaleźć plan wykładów dla całego uniwersytetu, spełniając pewne rozsądne ograniczenia, takie jak to, że żadne dwa wykłady nie mogą odbywać się w tej samej sali w tym samym czasie. Problem planowania wydaje się znacznie trudniejszy niż problem sortowania. Jeśli mamy choćby tysiąc grup, znalezienie najlepszego planu zajęć może trwać wieki, nawet przy użyciu superkomputera.
Co sprawia, że pewne problemy są obliczeniowo trudne, a inne łatwe?
Jest to centralne zagadnienie teorii złożoności. Co istotne, nie znamy na nie odpowiedzi, mimo że intensywne poszukiwania trwają od ponad 40 lat. Później zbadamy bliżej to fascynujące pytanie i niektóre z jego wariantów.
W jednym z ważnych osiągnięć teorii złożoności, jakie udało się uzyskać do tej pory, badacze odkryli elegancki schemat klasyfikowania problemów w zależności od ich trudności obliczeniowej. Jest on analogiczny do tablicy okresowej pierwiastków, stosowanej do klasyfikowania ich według własności chemicznych. Używając tego schematu, możemy wskazać metodę znajdowania przesłanek, że określone problemy są trudne obliczeniowo, nawet jeśli nie będziemy w stanie udowodnić, że takie są.
Stając w obliczu problemu, który wydaje się trudny obliczeniowo, mamy do dyspozycji kilka opcji. Po pierwsze, przez zrozumienie, jaki aspekt problemu jest źródłem tej trudności, możemy być w stanie zmienić go tak, aby problem stał się łatwiejszy do rozwiązania. Po drugie, może się okazać, że niedoskonałe rozwiązanie jest wystarczające. W określonych sytuacjach znalezienie takiego, które jest jedynie przybliżeniem najlepszego, jest łatwe. Po trzecie, niektóre problemy są trudne tylko w najgorszym przypadku, ale w większości pozostałych sytuacji są łatwe. Zależnie od zastosowania możemy być usatysfakcjonowani procedurą, która okazjonalnie jest bardzo powolna, ale zazwyczaj działa szybko. Na koniec wreszcie można rozważyć alternatywne rodzaje przetwarzania, takie jak obliczenia randomizowane, co pozwala przyśpieszyć określone zadania.
Jednym z obszarów zastosowań, na który teoria złożoności ma bezpośredni wpływ, jest starożytna dziedzina kryptografii. W większości zagadnień problemy łatwe obliczeniowo są preferowane względem tych trudnych, gdyż rozwiązywanie łatwych jest tańsze. Kryptografia jest nietypowa, gdyż stawiane jest wymaganie, aby problemy obliczeniowe były trudne, a nie łatwe. Tajne szyfry powinny być trudne do złamania bez znajomości tajnego klucza czy hasła. Teoria złożoności nakierowała kryptografów w stronę problemów trudnych obliczeniowo, na podstawie których zostały zaprojektowane nowe szyfry.
Teoria obliczalności
W pierwszej połowie dwudziestego wieku tacy matematycy, jak Kurt Gödel, Alan Turing i Alonzo Church odkryli, że pewnych problemów podstawowych nie można rozwiązać przy użyciu komputerów. Przykładem takiego zjawiska jest kwestia ustalenia, czy pewne twierdzenie matematyczne jest prawdziwe, czy fałszywe. Zadanie to jest chlebem powszednim matematyków. Wydawałoby się, że rozwiązywanie go przy użyciu komputerów byłoby czymś naturalnym, gdyż leży ono w obrębie królestwa matematyki. Jednak żaden algorytm komputerowy nie może zrealizować tego zadania.
Jedną z konsekwencji tego głębokiego wyniku było opracowanie koncepcji dotyczących teoretycznych modeli komputerów, które ostatecznie powinny pomóc w konstruowaniu rzeczywistych komputerów.
Teorie obliczalności i złożoności są ściśle powiązane. W teorii złożoności celem jest sklasyfikowanie problemów jako łatwych lub trudnych; tymczasem w teorii obliczalności problemy są klasyfikowalne jako te, które są możliwe do rozwiązania, lub takie, które nie są. Teoria obliczalności wprowadza wiele koncepcji wykorzystywanych w teorii złożoności.
Teoria automatów
Teoria automatów zajmuje się definicjami i własnościami matematycznych modeli obliczeń. Modele te odgrywają rolę w wielu stosowanych obszarach informatyki. Jeden z tych modeli, nazywany automatem skończonym, jest wykorzystywany w projektowaniu przetwarzania tekstów, kompilatorów i sprzętu. Inny model, nazywany gramatyką bezkontekstową, jest używany w językach programowania i projektowaniu sztucznej inteligencji.
Teoria automatów jest doskonałym miejscem do rozpoczęcia studiów nad teorią obliczeń. Teorie obliczalności i złożoności wymagają precyzyjnego zdefiniowania, czym jest komputer. Teoria automatów pozwala na przećwiczenie formalnych definicji obliczeń, jako że wprowadza idee istotne dla innych, nieteoretycznych obszarów informatyki.
0.2 Pojęcia matematyczne i terminologia
Podobnie jak w każdym podręczniku matematycznym, rozpoczniemy od omówienia podstawowych obiektów matematycznych, narzędzi i notacji, których zamierzamy używać.
Zbiory
Zbiór jest grupą obiektów traktowaną jako jednostka. Zbiory mogą zawierać dowolne typy obiektów, w tym liczby, symbole, a nawet inne zbiory. Obiekty w zbiorze nazywane są elementami. Zbiory mogą być formalnie opisywane różnymi sposobami.
Pierwszym z nich jest wyliczenie elementów zbioru w nawiasach klamrowych. Tym samym zbiór
S = {7, 21, 57}
zawiera elementy 7, 21 oraz 57. Symbole ? oraz ? oznaczają odpowiednio należenie i nienależenie do zbioru. Możemy napisać 7 ? {7, 21, 57} oraz 8 ? {7, 21, 57}. Dla dwóch zbiorów A i B mówimy, że A jest podzbiorem zbioru B, co zapisujemy jako A ? B, jeśli każdy element zbioru A jest również elementem zbioru B. Mówimy, że A jest podzbiorem właściwym B, co zapisujemy A ? B, jeśli A jest podzbiorem B i nie jest równe B.
Kolejność elementów w zbiorze nie jest istotna, podobnie jak powtórzenia elementów. Pisząc {57, 7, 7, 7, 21}, uzyskamy ten sam zbiór S. Gdybyśmy chcieli uwzględniać liczbę wystąpień elementów, grupę taką nazywamy wielozbiorem, a nie zbiorem. Tym samym {7} i {7, 7} są różnymi wielozbiorami, ale są identyczne jako zbiory. Zbiór nieskończony zawiera nieskończenie wiele elementów. Nie można wypisać listy wszystkich elementów zbioru nieskończonego, zatem niekiedy będziemy używać zapisu "..." w znaczeniu "kontynuować sekwencję w nieskończoność". Tym samym możemy zapisać zbiór liczb naturalnych N jako
{1, 2, 3, ...}.
Zbiór liczb całkowitych Z można zapisać jako
{... ,-2,-1, 0, 1, 2, ...}.
Zbiór, który ma zero elementów, nazywamy zbiorem pustym i zapisujemy jako ?. Zbiór zawierający dokładnie jeden element niekiedy nazywany jest singletonem, a zbiór o dwóch elementach - parą nieuporządkowaną.
Kiedy chcemy opisać zbiór zawierający elementy spełniające pewną regułę, zapisujemy to jako {n : reguła dotycząca n}. Tym samym {n : n = m2 dla pewnego m ? N} oznacza zbiór liczb stanowiących kwadraty liczb naturalnych.
Mając dwa zbiory A i B, ich sumą, zapisywaną jako A ? B, jest zbiór, który uzyskamy, łącząc wszystkie elementy zbiorów A i B w jeden. Przecięciem (częścią wspólną) zbiorów A i B, zapisywanym jako A ? B, jest zbiór tych elementów, które należą zarówno do A, jak i do B. Dopełnieniem zbioru A, zapisywanym jako A, jest zbiór wszystkich elementów rozważanej dziedziny, które nie należą do A.
Jak często bywa w matematyce, rysunek może pomóc w wyjaśnieniu niektórych pojęć. W przypadku zbiorów używamy tak zwanych diagramów Venna. Reprezentują one zbiory jako regiony zawarte w owalnych liniach. Niech zbiór START-t będzie zbiorem wszystkich słów rozpoczynających się literą t. W tym przykładzie na rysunku koło oznacza zbiór START-t. Kilka elementów tego zbioru jest reprezentowanych jako punkty wewnątrz tego koła.
Rysunek 0.1Diagram Venna dla zbioru słów zaczynających się na literę "t"
Analogicznie na kolejnym rysunku możemy przedstawić zbiór END-z złożony ze słów kończących się na literę "z".
Rysunek 0.2Diagram Venna dla zbioru angielskich słów kończących się na literę "z"
Aby przedstawić obydwa zbiory w tym samym diagramie Venna, musimy narysować je tak, aby koła się nakładały, sygnalizując, że mają pewne elementy wspólne, jak na kolejnym rysunku. Na przykład słowo topaz należy do obu zbiorów. Rysunek ten zawiera też koło dla zbioru START-j. Nie nakłada się ono na koło dla zbioru START-t, gdyż żadne słowo nie może należeć do obu tych zbiorów.
Rysunek 0.3Nakładające się koła wskazują na wspólne elementy
Kolejne dwa diagramy Venna ilustrują sumę i przecięcie zbiorów A i B.
Rysunek 0.4Diagramy dla (a) A ? B oraz (b) A ? B
Ciągi i krotki
Ciągiem nazywamy listę pewnych obiektów w określonym porządku. Zwyczajowo ciąg zapisujemy, umieszczając jego elementy w nawiasach okrągłych. Na przykład ciąg 7, 21, 57 można zapisać jako
(7, 21, 57).
W zbiorze porządek elementów nie ma znaczenia, ale w ciągu jest istotny. W związku z tym (7, 21, 57) nie jest tym samym ciągiem, co (57, 7, 21). Podobnie powtarzanie elementów w ciągu jest istotne, choć nie ma znaczenia w zbiorze. Oznacza to, że ciąg (7, 7, 21, 57) różni się od obu wcześniejszych ciągów, choć zbiór {7, 21, 57} jest identyczny ze zbiorem {7, 7, 21, 57}.
Podobnie jak w przypadku zbiorów, ciągi mogą być skończone lub nieskończone. Ciągi skończone są często nazywane krotkami. Ciąg o k elementach nazywamy k-krotką. Tak więc (7, 21, 57) jest 3-krotką. 2-krotka często bywa nazywana parą uporządkowaną - analogicznie używamy pojęć trójki, czwórki czy piątki uporządkowanej.
Zbiory i ciągi mogą występować jako elementy innych zbiorów i ciągów. Na przykład zbiorem potęgowym zbioru A jest zbiór wszystkich podzbiorów A. Jeśli A będzie zbiorem {0, 1}, wówczas zbiór potęgowy A to zbiór { ?, {0}, {1}, {0, 1} }. Zbiór wszystkich uporządkowanych par, których elementy to zera i jedynki, to { (0, 0), (0, 1), (1, 0), (1, 1) }.
Jeśli A i B to zbiory, to ich iloczynem kartezjańskim, zapisywanym jako A × B, jest zbiór wszystkich par uporządkowanych, w których pierwszy element należy do zbioru A, zaś drugi należy do zbioru B.
Przykład 0.5
Jeżeli A = {1, 2} i B = {x, y, z}, to
A × B = { (1, x), (1, y), (1, z), (2, x), (2, y), (2, z) }.
-
Możemy również wykonać iloczyn kartezjański k zbiorów A1, A2, ... , Ak, zapisywany jako A1 × A2 × ... × Ak. Jest to zbiór złożony ze wszystkich k-krotek (a1, a2, ... , ak), w których ai ? Ai.
Przykład 0.6
Jeżeli A i B są takimi zbiorami, jak w przykładzie 0.5, to
A × B × A = { (1, x, 1), (1, x, 2), (1, y, 1), (1, y, 2), (1, z, 1), (1, z, 2),
(2, x, 1), (2, x, 2), (2, y, 1), (2, y, 2), (2, z, 1), (2, z, 2)}.
-
Jeśli tworzymy iloczyn kartezjański zbioru z nim samym, możemy użyć skrótowego zapisu
k
A × A × ... × A = Ak.
Przykład 0.7
Zbiór N2 jest równy N × N. Składa się ze wszystkich uporządkowanych par liczb naturalnych. Możemy go również zapisać jako {(i, j) : i, j ? 1}.
Funkcje i relacje
Funkcje są podstawą matematyki. Funkcja jest obiektem definiującym relację wejście-wyjście. Przyjmuje dane wejściowe (argument) i zwraca wynik (wartość, inaczej wyjście funkcji). W każdej funkcji ten sam argument musi zawsze zwrócić tę samą wartość. Jeśli f jest funkcją, której wartość wyjściowa wynosi b dla argumentu a, zapisujemy to jako
f(a) = b.
Funkcja bywa również nazywana odwzorowaniem: jeśli f(a) = b, mówimy, że f odwzorowuje a na b.
Na przykład funkcja wartości bezwzględnej abs przyjmuje liczbę x jako wejście i zwraca x, jeśli x jest liczbą dodatnią, oraz -x, jeśli x jest ujemne. Tym samym abs(2) = abs(-2) = 2. Innym przykładem funkcji może być dodawanie, które zapiszemy jako add. Wejściem dla funkcji dodawania jest uporządkowana para liczb, a wyjściem (wartością) jest suma tych liczb.
Zbiór możliwych wartości wejściowych funkcji nazywamy jej dziedziną. Wyniki (wartości wyjściowe) należą do zbioru określonego jako przeciwdziedzina (zbiór wartości) funkcji. Stwierdzenie, że f jest funkcją o dziedzinie D i wartościach ze zbioru W, zapisujemy jako
f : D ? W.
W przypadku funkcji abs, gdybyśmy ograniczyli się do liczb całkowitych, zarówno dziedziną, jak i przeciwdziedziną jest Z, zatem możemy napisać abs : Z ? Z. W przypadku funkcji dodawania liczb całkowitych dziedziną jest zbiór par liczb całkowitych Z × Z, zaś przeciwdziedziną jest Z, zatem napiszemy add : Z × Z ? Z. Zauważmy, że funkcja nie musi wykorzystywać wszystkich elementów wskazanego zbioru wartości. Na przykład funkcja abs nigdy nie przyjmuje wartości -1, mimo że -1 ? Z. Funkcję, która wykorzystuje wszystkie elementy zbioru wartości, nazywamy funkcją "na" (surjekcją).
Funkcje można przedstawiać na wiele sposobów. Jednym z nich jest procedura obliczania wartości wyjściowej dla podanej wartości wejściowej. Inną metodą jest tablica wyliczająca wszystkie możliwe argumenty i podająca wartości dla każdego z nich.
Przykład 0.8
Rozważmy funkcję f : {0, 1, 2, 3, 4}?{0, 1, 2, 3, 4}.
n
f(n)
0
1
1
2
2
3
3
4
4
0
Funkcja ta dodaje 1 do argumentu i zwraca wynik modulo 5. Przypomnijmy, że liczba modulo m to reszta z dzielenia tej liczby przez m. Na przykład wskazówka minutowa na tarczy zegarowej podaje wartości modulo 60. Przy posługiwaniu się arytmetyką reszty definiujemy Zm = {0, 1, 2, ..., m - 1}. W przypadku tej notacji wspomniana wcześniej funkcja f ma formę f : Z5 ? Z5.
-
Przykład 0.9
Niekiedy, gdy dziedzina funkcji jest iloczynem kartezjańskim dwóch zbiorów, do przedstawienia jej wartości używa się tablicy dwuwymiarowej. Oto kolejna funkcja, g : Z4 × Z4 ? Z4. Komórka tablicy z wiersza oznaczonego i oraz kolumny z etykietą j zawiera wartość g(i, j).
g
0
1
2
3
0
0
1
2
3
1
1
2
3
0
2
2
3
0
1
3
3
0
1
2
Funkcja g to funkcja dodawania modulo 4.
-
Jeśli dziedziną funkcji jest A1×-...-×Ak dla pewnych zbiorów A1, ... , Ak, wejściem f jest k-krotka (a1, a2, ... , ak) i poszczególne ai nazywamy argumentami funkcji f. Funkcja z k argumentami nazywana jest funkcją k-argumentową, zaś k nazywamy argumentowością (niekiedy arnością) tej funkcji. Jeśli k jest równe 1, f ma pojedynczy argument i nazywamy ją funkcją jednoargumentową (unarną). Jeśli k to 2, f jest funkcją dwuargumentową (binarną). Pewne dobrze znane funkcje dwuargumentowe są zapisywane przy użyciu szczególnej notacji infiksowej, w której symbol funkcji umieszczany jest między dwoma argumentami, a nie ogólnie stosowanej notacji prefiksowej, gdzie symbol funkcji poprzedza argumenty. Na przykład funkcja dodawania add jest zwyczajowo zapisywana w notacji infiksowej z symbolem + między argumentami, czyli a + b, zamiast notacji prefiksowej add(a, b).
Predykat lub własność to funkcja, której przeciwdziedziną jest zbiór {TRUE (prawda), FALSE (fałsz)}. Na przykład niech even będzie własnością przyjmującą wartość TRUE, jeśli argument jest liczbą parzystą, oraz FALSE, gdy jest to liczba nieparzysta. Tak więc even(4) = TRUE i even(5) = FALSE.
Własność, której dziedziną jest zbiór k-krotek A × ... × A nazywamy relacją, relacją k-argumentową albo k-argumentową relacją na A. Często spotykanym przypadkiem jest relacja dwuargumentowa, inaczej nazywana relacją binarną. Przy zapisywaniu wyrażeń wykorzystujących relacje dwuargumentowe zwyczajowo używamy notacji infiksowej. Na przykład "mniejsze niż" jest relacją, którą zwyczajowo zapisujemy przy użyciu symbolu infiksowego <. "Równość", zapisywana przy użyciu symbolu =, to inna dobrze znana relacja. Jeśli R jest relacją binarną, wyrażenie aRb oznacza, że aRb = TRUE. Analogicznie, jeśli R jest relacją k-argumentową, wyrażenie R(a1, ..., ak) oznacza, że R(a1, ..., ak) = TRUE.
Przykład 0.10
W grze w kamień, papier, nożyce dwóch graczy jednocześnie wybiera element ze zbioru {NOŻYCE, PAPIER, KAMIEŃ} i prezentuje wybór odpowiednim ułożeniem dłoni. Jeśli wybory są identyczne, gra jest powtarzana. Jeśli wybory się różnią, jeden z graczy wygrywa zgodnie z relacją bije.
bije
NOŻYCE
PAPIER
KAMIEŃ
NOŻYCE
FALSE
TRUE
FALSE
PAPIER
FALSE
FALSE
TRUE
KAMIEŃ
TRUE
FALSE
FALSE
Z tablicy tej możemy wyczytać, że NOŻYCE bije PAPIER jest równe TRUE, zaś PAPIER bije NOŻYCE to FALSE.
-
Czasami wygodniejsze jest przedstawienie predykatów jako zbiorów, a nie jako funkcji. Predykat P : D?{TRUE, FALSE} można zapisać jako (D, S), gdzie S = {a ? D : P(a) = TRUE} lub po prostu S, jeśli dziedzina D w sposób oczywisty wynika z kontekstu. Tym samym relację bije można zapisać jako
{(NOŻYCE, PAPIER), (PAPIER, KAMIEŃ), (KAMIEŃ, NOŻYCE)}.
Szczególny typ relacji dwuargumentowej, nazywany relacją równoważności, prezentuje pojęcie równości dwóch obiektów pod pewnym względem. Relacja dwuargumentowa R jest relacją równoważności, jeżeli spełnia trzy warunki:
R jest
zwrotna, czyli dla każdego
x zachodzi
xRx;
R jest
symetryczna, czyli dla każdych
x i
y z
xRy wynika
yRx; oraz
R jest
przechodnia, czyli dla każdych
x,
y i
z, jeżeli
xRy i
yRz, to
xRz.
Przykład 0.11
Zdefiniujmy relację równoważności dla liczb naturalnych, zapisywaną jako ?7. Dla i, j Î N niech i ?7 j, jeśli i - j jest wielokrotnością 7. Jest to relacja równoważności, gdyż spełnia trzy wymienione warunki. Po pierwsze jest zwrotna, gdyż i - i = 0, co jest wielokrotnością liczby 7. Po drugie jest symetryczna, gdyż jeśli i - j jest wielokrotnością 7, to można sprawdzić, że j - i również jest wielokrotnością 7. Po trzecie jest przechodnia, gdyż jeśli i - j jest wielokrotnością 7 i j - k jest wielokrotnością 7, wówczas i - k = (i - j) + (j - k) jest sumą dwóch wielokrotności 7, a tym samym również jest wielokrotnością 7.
-
Grafy
Graf nieskierowany lub po prostu graf to zbiór punktów z liniami łączącymi pewne z nich ze sobą. Punkty te nazywamy wierzchołkami lub węzłami, zaś linie nazywamy krawędziami, jak na poniższym rysunku.
Rysunek 0.12Przykłady grafów
Liczbę krawędzi spotykających się w określonym wierzchołku nazywamy stopniem tego wierzchołka. Na rysunku 0.12(a) wszystkie wierzchołki mają stopień 2. Na rysunku 0.12(b) wszystkie wierzchołki mają stopień 3. Między dwoma dowolnymi wierzchołkami dozwolona jest co najwyżej jedna krawędź. W pewnych sytuacjach możemy zezwolić na krawędzie prowadzące od wierzchołka do niego samego, czyli pętle zwrotne.
W grafie G zawierającym wierzchołki i oraz j para (i, j) reprezentuje krawędź łączącą te wierzchołki. Kolejność i oraz j nie ma znaczenia w grafie nieskierowanym, zatem pary (i, j) oraz (j, i) reprezentują tę samą krawędź. Nieskierowane krawędzie są niekiedy przedstawiane jako nieuporządkowane pary przy użyciu notacji zbiorów, czyli {i, j}. Jeśli V to zbiór wierzchołków G, a E jest zbiorem krawędzi, możemy to zapisać jako G = (V, E). Graf możemy przedstawić za pomocą diagramu lub bardziej formalnie specyfikując zbiory V i E. Na przykład formalny opis grafu z rysunku 0.12(a) to
({1, 2, 3, 4, 5}, {(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)}),
a formalny opis grafu z rysunku 0.12(b) to
({1, 2, 3, 4}, {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}).
Grafy są często wykorzystywane do przedstawiania danych. Wierzchołki mogą być miastami, a krawędzie łączącymi je szosami albo wierzchołki mogą przedstawiać ludzi, natomiast krawędzie - przyjaźń między nimi. Niekiedy dla wygody możemy opatrywać etykietami wierzchołki i/lub krawędzie grafu, który wówczas nazywany jest grafem etykietowanym (labeled graph). Na rysunku 0.13 przedstawiono graf, którego wierzchołki są miastami, zaś krawędzie zostały opisane kosztem najtańszego bezpośredniego przelotu między tymi miastami, o ile taki bezpośredni lot (non stop) jest możliwy.
Rysunek 0.13Najtańsze taryfy lotnicze non stop między różnymi miastami
Mówimy, że graf G jest podgrafem grafu H, jeśli wierzchołki G są podzbiorem wierzchołków H i krawędzie G są krawędziami H dla odpowiednich wierzchołków1. Na poniższym rysunku pokazano graf H i podgraf G.
Rysunek 0.14Graf G (pokazany jako ciemniejszy) jest podgrafem grafu H
Ścieżka w grafie jest ciągiem wierzchołków połączonych krawędziami. Ścieżką prostą (drogą) nazywamy ścieżkę, w której żaden wierzchołek się nie powtarza. Graf jest spójny, jeśli dla dowolnych dwóch wierzchołków istnieje łącząca je ścieżka. Ścieżkę nazywamy cyklem, jeśli jest zamknięta, czyli zaczyna się i kończy w tym samym wierzchołku. Cykl prosty to cykl złożony z co najmniej trzech różnych wierzchołków, w którym powtarza się tylko pierwszy wierzchołek (jako ostatni). Graf jest drzewem, jeśli jest spójny i nie zawiera prostych cykli, jak na rysunku 0.15 (c). Drzewo może zawierać specjalnie wyróżniony wierzchołek nazywany korzeniem. W drzewie, z wyjątkiem korzenia, wierzchołki o stopniu 1 nazywane są liśćmi drzewa.
Rysunek 0.15(a) Ścieżka w grafie, (b) cykl w grafie oraz (c) drzewo
Graf skierowany jest przedstawiany przy użyciu strzałek zamiast linii, co pokazano na kolejnym rysunku. Liczbę strzałek wychodzących z określonego wierzchołka nazywamy stopniem wyjściowym tego wierzchołka, zaś liczbę strzałek wskazujących na dany wierzchołek nazywamy jego stopniem wejściowym.
Rysunek 0.16Graf skierowany
W grafie skierowanym krawędź z wierzchołka i do wierzchołka j przedstawiamy jako parę uporządkowaną (i, j). Formalny zapis grafu skierowanego G to (V, E), gdzie V jest zbiorem wierzchołków, E - zbiorem krawędzi. Formalny zapis grafu pokazanego na rysunku 0.16 to
({1,2,3,4,5,6}, {(1,2), (1,5), (2,1), (2,4), (5,4), (5,6), (6,1), (6,3)}).
Ścieżkę, w której wszystkie strzałki wskazują w tym samym kierunku, od początku do końca, nazywamy ścieżką skierowaną. Graf skierowany jest silnie spójny, jeśli dla każdych dwóch węzłów istnieje łącząca je ścieżka skierowana. Grafy skierowane są wygodną metodą opisywania relacji dwuargumentowych. Jeśli R jest relacją dwuargumentową o dziedzinie D × D, to można ją reprezentować jako graf etykietowany G = (D, E), gdzie E = {(x, y) : xRy}.
Przykład 0.17
Graf skierowany pokazany poniżej reprezentuje relację z przykładu 0.10.
Rysunek 0.18Graf dla relacji bije
Słowa i języki
Słowa, czyli ciągi znaków, stanowią fundamentalne cegiełki informatyki. Alfabet, nad którym definiowane są słowa, może się zmieniać w zależności od zastosowań. Dla naszych celów alfabet definiujemy jako niepusty skończony zbiór. Elementy tego zbioru są symbolami alfabetu. Zazwyczaj będziemy używać wielkich liter greckich S i G do oznaczania alfabetów oraz małych liter czcionki o stałej szerokości dla symboli alfabetu. Poniżej pokazano kilka przykładów alfabetów.
?1 = {0, 1}
?2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
? = {0, 1, x, y, z}
Słowem nad alfabetem (także ciągiem nad alfabetem) jest skończony ciąg symboli z tego alfabetu, zazwyczaj wypisanych jeden po drugim bez odstępów i przecinków. Jeśli ?1 = {0,1}, wówczas 01001 jest słowem nad ?1. Jeśli ?2 = {a, b, c, ... , z}, wtedy abracadabra jest słowem nad ?2. Jeżeli w jest słowem nad ?, długość w, zapisywana jako |w|, jest liczbą zawartych w nim symboli. Słowo o długości zero nazywane jest pustym słowem i zapisywane jako ?. Słowo puste odgrywa rolę analogiczną do 0 w systemie liczbowym. Jeśli słowo w ma długość n, to możemy zapisać ją jako w = w1w2 ... -wn, gdzie każdy wi ? ?. Odwrócenie słowa w, zapisywane jako wR, jest słowem uzyskiwanym z w przez zapisanie go w odwrotnej kolejności (czyli wnwn-1 ...-w1). Słowo z jest podsłowem w, jeśli jest spójnym podciągiem słowa w. Na przykład cad jest podsłowem słowa abracadabra.
Jeśli mamy słowo x o długości m oraz słowo y o długości n, to konkatenacją x i y, zapisywaną xy, jest słowo uzyskiwane przez dołączenie słowa y na końcu słowa x, czyli słowo x1 ... xmy1 ... yn. W przypadku wielokrotnej konkatenacji słowa ze sobą samym używamy zapisu wykładniczego xk, oznaczającego
k
xx ... x.
Porządek leksykograficzny słów jest tożsamy z dobrze znanym porządkiem słownikowym. Będziemy od czasu do czasu używać zmodyfikowanego porządku leksykograficznego, nazywanego shortlex, który jest identyczny z porządkiem leksykograficznym, z wyjątkiem tego, że krótsze słowa poprzedzają dłuższe. Tym samym porządek shortlex wszystkich słów nad alfabetem {0,1} to
(?, 0, 1, 00, 01, 10, 11, 000, ...).
Mówimy, że słowo x jest prefiksem (przedrostkiem) słowa y, jeśli istnieje takie słowo z, że xz = y, przy czym x nazywamy prefiksem właściwym słowa y, jeśli dodatkowo x ? y.
Język jest zbiorem słów. Język nazywamy przedrostkowym, jeśli żaden element (słowo) języka nie jest prefiksem właściwym innego elementu.
Logika Boole'a
Logika Boole'a jest systemem matematycznym zbudowanym wokół dwóch wartości TRUE i FALSE. Choć oryginalnie wynaleziony jako koncepcja czysto matematyczna, system ten jest obecnie postrzegany jako fundament projektowania elektroniki cyfrowej i komputerów. Wartości TRUE i FALSE nazywane są wartościami boolowskimi (logicznymi) i często są reprezentowane jako numeryczne wartości 1 i 0. Wartości boolowskich używamy w sytuacjach, gdy dostępne są tylko dwie możliwości, takich jak wysoki lub niski poziom napięcia, stwierdzenie, które może być prawdziwe lub fałszywe lub pytanie, na które odpowiedź musi brzmieć tak lub nie.
Przekształcanie wartości boolowskich odbywa się przez operacje boolowskie (logiczne). Najprostszą operacją boolowską jest negacja, czyli operacja NOT (nie), oznaczana symbolem ?. Negacją wartości boolowskiej jest przeciwna wartość. Tym samym ?0 = 1 oraz ?1 = 0. Koniunkcję, czyli operację AND oznaczamy symbolem ?. Koniunkcja dwóch wartości boolowskich jest równa 1 (prawda), jeśli obie te wartości mają wartość 1. Alternatywę lub operację OR oznaczamy symbolem ?. Alternatywa dwóch wartości boolowskich ma wartość 1, jeśli którakolwiek z tych wartości jest równa 1. Informacje te można podsumować w następujący sposób:
0 ? 0 = 0
0 ? 0 = 0
?0 = 1
0 ? 1 = 0
0 ? 1 = 1
?1 = 0
1 ? 0 = 0
1 ? 0 = 1
1 ? 1 = 1
1 ? 1 = 1
Operacje boolowskie wykorzystywane są do łączenia prostych stwierdzeń w bardziej złożone wyrażenia boolowskie, podobnie jak używamy operacji arytmetycznych + i × do konstruowania złożonych wyrażeń arytmetycznych. Przykładowo, jeśli P jest wartością boolowską reprezentującą prawdziwość stwierdzenia "Słońce świeci", a Q reprezentuje prawdziwość stwierdzenia "dziś jest poniedziałek", to możemy napisać P ? Q, aby przedstawić prawdziwość stwierdzenia "Słońce świeci i dziś jest poniedziałek"; analogiczna zależność zachodzi dla P ? Q, przy czym "i" zastępujemy przez "lub". Wartości P i Q nazywamy operandami operacji.
Od czasu do czasu będzie pojawiać się kilka innych operacji boolowskich. Alternatywa wykluczająca (rozłączna, exclusive or), inaczej XOR, oznaczana jest symbolem ? i ma wartość 1, jeśli albo jeden, albo drugi operand ma wartość 1, ale nie obydwa jednocześnie. Operacja równoważności, zapisywana za pomocą symbolu ?, ma wartość 1, gdy obydwa operandy mają tę samą wartość. Na koniec operacja implikacji, opisywana symbolem ?, ma wartość 0, jeśli jej pierwszy (lewy) operand ma wartość 1, a drugi 0; w pozostałych przypadkach ? ma wartość 1. Podsumowujemy te informacje w następujący sposób.
0 ? 0 = 0
0 ? 0 = 1
0 ? 0 = 1
0 ? 1 = 1
0 ? 1 = 0
0 ? 1 = 1
1 ? 0 = 1
1 ? 0 = 0
1 ? 0 = 0
1 ? 1 = 0
1 ? 1 = 1
1 ? 1 = 1
Między tymi operacjami zachodzą różne zależności. W istocie możemy wyrazić wszystkie operacje boolowskie jedynie przez operacje AND oraz NOT, co pokazują poniższe tożsamości. Dwa wyrażenia w każdym wierszu są równoważne. Każdy wiersz prezentuje w lewej kolumnie zapis operacji przy użyciu pojęć omówionych wyżej, zaś w prawej równoważne operacje wykorzystujące AND oraz NOT.
P ? Q
?(?P ? ?Q)
P ? Q
?P ? Q
P ? Q
(P ? Q) ? (Q ? P)
P ? Q
?(P ? Q)
Prawo rozdzielności koniunkcji i alternatywy przydaje się przy przekształcaniu wyrażeń boolowskich. Jest ono podobne do prawa rozdzielności mnożenia względem dodawania, które głosi, że a × (b+c) = (a × b)+(a × c). Wersja boolowska występuje w dwóch postaciach:
P ? (
Q ?
R) jest równe (
P ?
Q) ? (
P ?
R), oraz
P ? (
Q ?
R) jest równe (
P ?
Q) ? (
P ?
R).
Podsumowanie terminów matematycznych
Alfabet - skończony, niepusty zbiór obiektów nazywanych symbolami
Alternatywa - operacja boolowska OR
Argument - wartość wejściowa (dana) funkcji
Ciąg - uporządkowana lista obiektów
Cykl - ścieżka zaczynająca się i kończąca w tym samym wierzchołku
Dopełnienie - operacja zwracająca zbiór wszystkich elementów nienależących do danego zbioru
Drzewo - spójny graf niezawierający prostych cykli
Dwuargumentowa relacja - relacja, której dziedziną jest zbiór par uporządkowanych
Dziedzina - zbiór wszystkich możliwych wartości wejściowych (argumentów) funkcji
Element - obiekt należący do zbioru
Funkcja - operacja przekształcająca wartości wejściowe na wartości wyjściowe
Graf - zbiór punktów i linii łączących niektóre pary tych punktów
Iloczyn kartezjański - operacja na zbiorach tworząca zbiór wszystkich krotek złożonych z elementów odpowiednich zbiorów
Język - zbiór słów nad pewnym alfabetem
k-krotka - ciąg k obiektów
Koniunkcja - operacja boolowska AND
Konkatenacja - operacja łączenia ze sobą słów
Krawędź - linia łącząca wierzchołki grafu
Nieuporządkowana para - zbiór o dwóch elementach
Operacja boolowska - operacja na wartościach boolowskich
Predykat - funkcja, której przeciwdziedziną jest zbiór {TRUE, FALSE}
Prosta ścieżka - ścieżka bez powtarzających się wierzchołków
Przeciwdziedzina - zbiór, z którego pochodzą wartości wyjściowe funkcji
Przecięcie (iloczyn zbiorów) - operacja na zbiorach tworząca zbiór elementów wspólnych dla tych zbiorów
Relacja równoważności - relacja dwuargumentowa, która jest zwrotna, symetryczna i przechodnia
Relacja - predykat, którego dziedziną jest zbiór k-krotek
Singletonowy zbiór - zbiór jednoelementowy
Skierowany graf - zbiór punktów i strzałek (par uporządkowanych) łączących wybrane pary tych punktów
Spójny graf - graf zawierający ścieżki łączący dowolne dwa wierzchołki
Suma zbiorów - operacja na zbiorach łącząca wszystkie elementy uczestniczących zbiorów w jeden zbiór
Symbol - element alfabetu
Słowo puste - słowo o długości zero
Słowo - skończona lista symboli z pewnego alfabetu
Ścieżka - sekwencja wierzchołków grafu połączonych krawędziami
Uporządkowana para - lista o dwóch elementach, ciąg dwuelementowy
Wartość boolowska - wartości TRUE (prawda) lub FALSE (fałsz), często reprezentowane przez 1 lub 0
Wierzchołek - punkt w grafie
Węzeł (inaczej wierzchołek) - punkt w grafie
Własność - inaczej predykat
Zbiór pusty - zbiór, który nie ma żadnych elementów
Zbiór - grupa obiektów
0.3 Definicje, twierdzenia i dowody
Twierdzenia i dowody to ciało i krew matematyki, a definicje są jej duszą. Te trzy byty stanowią podstawę każdego działu matematyki, w tym naszego.
Definicje opisują obiekty i pojęcia, którymi się posługujemy. Definicja może być prosta, jak w przypadku definicji zbioru przedstawionej wcześniej w tym rozdziale, albo złożona, jak definicja bezpieczeństwa w systemie kryptograficznym. Zasadniczą cechą każdej definicji matematycznej jest precyzja. Gdy definiujemy jakiś obiekt, musimy zapewnić jednoznaczność tego, co określa dany obiekt, a co nie.
Po zdefiniowaniu różnych obiektów i pojęć zazwyczaj formułujemy zdania matematyczne (stwierdzenia) na ich temat. Typowe stwierdzenie głosi, że pewien obiekt ma określoną własność. Zdanie może być prawdziwe lub nie; jednak ponownie jak definicja, musi być precyzyjne. Żadna niepewność co do jego znaczenia nie jest dopuszczalna.
Dowód jest przekonywającą logiczną argumentacją, że określone zdanie jest prawdziwe. W matematyce argumentacja ta musi być ścisła; inaczej mówiąc, musi być przekonywająca w znaczeniu absolutnym. W codziennym życiu czy w prawie standardy stawiane dowodom są niższe. W procesie o morderstwo wymagany jest dowód "wykraczający poza uzasadnione wątpliwości". Waga świadectwa (zeznania czy materialnego faktu) może przekonać przysięgłych, by uznali niewinność lub winę oskarżonego. Jednak takie świadectwa nie odgrywają żadnej roli w dowodzie matematycznym. Matematyk domaga się dowodu poza wszelkimi wątpliwościami.
Twierdzeniem nazywamy zdanie matematyczne, którego prawdziwość została dowiedziona. W ogólności rezerwujemy użycie tego słowa dla zdań o szczególnym znaczeniu. Od czasu do czasu dowodzimy stwierdzeń, które są interesujące tylko dlatego, że są pomocne w dowodzeniu innych, bardziej znaczących zdań. Tego typu zdania nazywane są lematami. Niekiedy zdarza się, że twierdzenie lub jego dowód pozwala łatwo wywnioskować, że inne powiązane stwierdzenia są prawdziwe. Takie zdania nazywamy wnioskami z twierdzenia.
Znajdowanie dowodów
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ą.
0.4 Typy dowodów
W dowodach matematycznych często pojawia się kilka typów argumentacji. W tym miejscu opiszemy kilka takich, które często występują w teorii obliczeń. Zwróćmy uwagę, że dowód może zawierać więcej niż jeden typ argumentacji, gdyż dowód może mieć kilka różnych dowodów podrzędnych.
Dowód przez konstrukcję
Wiele twierdzeń głosi, że istnieje pewien określony typ obiektu. Jedna z metod dowiedzenia takiego twierdzenia polega na zademonstrowaniu, jak skonstruować taki obiekt. Technika ta jest nazywana dowodem przez konstrukcję (dowodem konstrukcyjnym).
Spróbujmy użyć dowodu przez konstrukcję dla wykazania następującego twierdzenia. Graf definiujemy jako k-regularny, jeśli każdy wierzchołek grafu ma stopień k.
Twierdzenie 0.22
Dla każdej liczby parzystej n większej od 2 istnieje 3-regularny graf o n wierzchołkach.
Dowód Niech n będzie liczbą parzystą większą od 2. Konstruujemy graf G = (V, E) o n wierzchołkach zgodnie z następującą procedurą: zbiór wierzchołków G to V = {0, 1, ..., n - 1}, zaś zbiór krawędzi G to zbiór
E = { {i, i + 1} : dla 0 ? i ? n - 2} ? { {n - 1, 0} }? { {i, i + n/2} : dla 0 ? i ? n/2 - 1}.
Wierzchołki tego grafu można przedstawić, rozmieszczając je równomiernie na okręgu. W tym przypadku krawędzie opisane przez górny wiersz definicji zbioru E łączą sąsiadujące pary wierzchołków wokół okręgu. Krawędzi opisane w dolnym wierszu definicji zbioru E biegną między wierzchołkami po przeciwnej stronie okręgu. Taki myślowy obraz jasno pokazuje, że każdy wierzchołek grafu G ma stopień 3.
Dowód nie wprost (przez sprowadzenie do sprzeczności)
Inna typowa forma argumentacji w dowodzeniu twierdzenia polega na założeniu, że twierdzenie jest fałszywe, a następnie wykazanie, że założenie to prowadzi w oczywisty sposób do fałszywych wniosków, nazywanych sprzecznością. Tego typu rozumowania używamy często w codziennym życiu, jak w poniższym przykładzie.
Przykład 0.23
Jack widzi Jill, która przed chwilą była na świeżym powietrzu. Zauważa, że nie zmokła, toteż wie, że nie pada deszcz. Jego "dowód", że nie pada, polega na tym, że gdyby padało (założenie, że twierdzenie jest fałszywe), Jill by zmokła (oczywiście fałszywy skutek). Tym samym nie może padać.
-
Teraz spróbujmy dowieść nie wprost, że pierwiastek kwadratowy z 2 jest liczbą niewymierną. Liczba jest wymierna, jeśli jest ułamkiem m/n, gdzie m i n są liczbami całkowitymi; mówiąc inaczej, liczba wymierna jest ilorazem liczb całkowitych m i n. Na przykład 2/3 w oczywisty sposób jest liczbą wymierną. Liczbę nazywamy niewymierną, jeśli nie jest wymierna.
Twierdzenie 0.24
? 2 jest liczbą niewymierną.
Dowód Na potrzeby dowodu nie wprost zakładamy, że ? 2 jest liczbą wymierną. Tym samym
gdzie m i n są liczbami całkowitymi. Jeśli obie liczby m i n są podzielne przez tę samą liczbę całkowitą większą od 1, dzielimy obie przez największą taką liczbę (skracamy ułamek). Działanie takie nie zmienia wartości ułamka. W rezultacie przynajmniej jedna z liczb m i n musi być liczbą nieparzystą.
Mnożymy obie strony równania przez n i uzyskujemy
n? 2 = m.
Podnosimy obie strony do kwadratu i uzyskujemy
2n2 = m2.
Ponieważ m2 jest podwojeniem liczby całkowitej n2, wiemy, że m2 jest liczbą parzystą. Zatem samo m również jest parzyste, gdyż kwadrat liczby nieparzystej zawsze jest nieparzysty. Możemy zatem zapisać m = 2k, gdzie k jest pewną liczbą całkowitą. Podstawiając 2k za m, otrzymujemy
2n2 = (2k)2
= 4k2.
Dzieląc obie strony przez 2, otrzymujemy
n2 = 2k2.
Jednak wynik ten pokazuje, że n2 jest parzyste, a tym samym n jest parzyste. Wykazaliśmy zatem, że zarówno m, jak i n są parzyste. Jednak wcześniej wykonaliśmy redukcję m i n (skróciliśmy ułamek), a więc obie jednocześnie nie mogą być parzyste - sprzeczność.
Dowód indukcyjny
Dowód indukcyjny jest zaawansowaną metodą wykazywania, że wszystkie elementy pewnego nieskończonego zbioru mają określoną własność. Na przykład możemy użyć dowodu indukcyjnego dla wykazania, że pewne wyrażenie arytmetyczne oblicza pożądaną wartość dla każdego przypisania zmiennych albo że program działa poprawnie we wszystkich krokach lub dla wszystkich wartości wejściowych.
Aby zilustrować, jak przebiega dowód indukcyjny, przyjmijmy zbiór nieskończony jako zbiór liczb naturalnych N = {1, 2, 3, ...}, zaś badaną własność nazwiemy P. Naszym celem jest wykazanie, że P(k) jest prawdą dla każdej liczby naturalnej k. Mówiąc inaczej, chcemy udowodnić, że P(1) jest prawdą, podobnie jak P(2), P(3), P(4) i tak dalej.
Każdy dowód indukcyjny składa się z dwóch części, kroku podstawowego (bazy indukcji) oraz kroku indukcyjnego. Każda z tych części jest indywidualnym dowodem. W kroku podstawowym udowadniamy, że P(1) jest prawdziwe. Krok indukcyjny dowodzi, że dla każdego i ? 1, jeśli P(i) jest prawdziwe, to prawdziwe jest także P(i + 1).
Po udowodnieniu obu części uzyskujemy pożądany wynik - konkretnie to, że P(i) jest prawdziwe dla każdego i. Dlaczego? Po pierwsze wiemy, że P(1) jest prawdziwe, gdyż udowodniliśmy to w kroku podstawowym. Po drugie wiemy, że P(2) jest prawdziwe, gdyż krok indukcyjny dowodzi, że jeśli P(1) jest prawdziwe, to P(2) jest prawdziwe, a wiemy już, że P(1) jest prawdziwe. Po trzecie wiemy, że P(3) jest prawdziwe, gdyż krok indukcyjny dowodzi, że jeśli P(2) jest prawdziwe, to P(3) jest prawdziwe, a wiemy już, że P(2) jest prawdziwe. Proces ten kontynuujemy dla wszystkich liczb naturalnych, wykazując, że P(4) jest prawdziwe, P(5) jest prawdziwe i tak dalej.
Po zrozumieniu poprzedniego akapitu można łatwo stosować warianty i uogólnienia tej metody. Na przykład krok podstawowy nie musi się koniecznie zaczynać od 1; możemy rozpoczynać od dowolnej wartości b. W takim przypadku dowód indukcyjny wykaże, że P(k) jest prawdziwe dla każdego k nie mniejszego od b.
W kroku indukcyjnym założenie, że P(i) jest prawdziwe, nazywamy hipotezą indukcyjną (założeniem indukcyjnym). Niekiedy użyteczne jest użycie silniejszej hipotezy indukcyjnej stwierdzającej, że P(j) jest prawdziwe dla każdego j ? i. Dowód indukcyjny nadal będzie działać, gdyż kiedy chcemy wykazać, że P(i + 1) jest prawdziwe, udowodniliśmy już, że prawdziwe jest P(j) dla każdego j ? i.
Format zapisywania dowodów indukcyjnych jest następujący:
Krok podstawowy: Udowadniamy, że P(1) jest prawdą.
?
Krok indukcyjny: Dla każdego i ? 1 zakładamy, że P(i) jest prawdą, po czym wykorzystujemy to założenie, aby wykazać, że P(i + 1) jest prawdą.
?
Udowodnimy teraz przez indukcję poprawność formuły używanej do obliczania wielkości miesięcznych rat kredytów hipotecznych. Przy kupowaniu domu wiele osób pożycza część pieniędzy potrzebnych na zakup, po czym spłaca ten dług przez określoną liczbę lat. Warunki spłaty przewidują, że ustalona kwota jest płacona każdego miesiąca na pokrycie odsetek, jak również jako część oryginalnej sumy, tak że całość zostaje spłacona np. w ciągu 30 lat. Wzór na obliczenie wielkości miesięcznych rat jest okryty tajemnicą, ale w istocie jest całkiem prosty. Dotyczy codziennych spraw wielu ludzi, zatem powinien być interesujący. Użyjemy indukcji, aby udowodnić jego poprawność, co zapewni dobrą ilustrację tej techniki.
Na początek określimy nazwy i znaczenie kilku zmiennych. Niech P będzie kapitałem, czyli sumą oryginalnej pożyczki. Niech I > 0 będzie roczną stopą oprocentowania kredytu, gdzie I = 0.06 oznacza oprocentowanie 6%. Niech Y będzie ratą miesięczną. Dla wygody użyjemy I do zdefiniowania zmiennej M, czyli mnożnika miesięcznego. Jest to stopa zmian kredytu każdego miesiąca z powodu naliczania odsetek. Zgodnie ze standardową praktyką bankowości miesięczna stopa oprocentowania jest jedną dwunastą stopy rocznej, czyli M = 1 + I/12, zaś odsetki naliczane są co miesiąc (miesięczna kapitalizacja).
Każdego miesiąca występują dwie rzeczy. Po pierwsze wielkość kredytu ma skłonność do wzrostu z powodu miesięcznego mnożnika. Po drugie wielkość ta zmniejsza się z powodu miesięcznej spłaty. Niech Pt będzie wielkością kredytu pozostałą do spłacenia po t-tym miesiącu. Przy tej konwencji P0 = P jest oryginalnym kredytem, P1 = MP0 - Y jest wielkością kredytu po jednym miesiącu, P2 = MP1 - Y wielkością po dwóch miesiącach. Teraz jesteśmy gotowi sformułować i udowodnić przez indukcję po t twierdzenie podające wzór na wartości Pt.
Twierdzenie 0.25
Dla każdego t ? 0 zachodzi
Dowód
Krok podstawowy: Udowadniamy, że wzór jest poprawny dla t = 0. Jeśli t = 0, wówczas wzór przybiera kształt
Prawą stronę można uprościć, zauważając, że M0 = 1. Otrzymujemy zatem
P0 = P,
co jest prawdą, gdyż zdefiniowaliśmy P0 jako P. W ten sposób udowodniliśmy, że krok podstawowy indukcji jest spełniony.
Krok indukcyjny: Dla każdego k ? 0 zakładamy, że jeśli wzór jest spełniony dla t = k, to wynika stąd, że jest spełniony dla t = k + 1. Hipoteza indukcyjna stwierdza, że
Naszym celem jest udowodnienie, że
Zrealizujemy to w następujących krokach. Ponieważ Pk+1 definiowane jest na podstawie Pk, wiemy, że
Pk+1 = PkM - Y.
Tym samym, używając hipotezy indukcyjnej do obliczenia Pk, otrzymujemy
Po pomnożeniu przez M i przekształceniu Y uzyskujemy
Tym samym wzór jest poprawny dla t = k + 1, co kończy dowód twierdzenia.
W zadaniu 0.15 należy użyć powyższego wzoru do obliczenia bieżących rat kredytu.
Ćwiczenia
0.1 Zbadaj poniższe formalne przedstawienia zbiorów, aby zrozumieć, jakie elementy zawierają. Dla każdego zbioru napisz krótki nieformalny opis w języku potocznym.
a. {1, 3, 5, 7, ...}
b. {...,-4,-2, 0, 2, 4, ...}
c. {n : n = 2m dla pewnego m należącego do N}
d. {n : n = 2m dla pewnego m należącego do N, oraz n = 3k dla pewnego k z N}
e. {w : w jest słowem złożonym z zer i jedynek i w jest równe odwróconemu w}
f. {n : n jest liczbą całkowitą i n = n + 1}
0.2 Napisz formalne definicje następujących zbiorów.
a. Zbiór zawierający liczby 1, 10 i 100
b. Zbiór zawierający wszystkie liczby całkowite większe od 5
c. Zbiór zawierający wszystkie liczby naturalne mniejsze od 5
d. Zbiór zawierający słowo aba
e. Zbiór zawierający puste słowo
f. Zbiór, który niczego nie zawiera
0.3 Niech A będzie zbiorem {x, y, z}, a B zbiorem {x, y}.
a. Czy A jest podzbiorem B?
b. Czy B jest podzbiorem A?
c. Czym jest A ? B?
d. Czym jest A ? B?
e. Czym jest A × B?
f. Czym jest zbiór potęgowy zbioru B?
0.4 Jeśli A zawiera a elementów, zaś B ma b elementów, ile elementów będzie zawierać A × B? Odpowiedź uzasadnij.
0.5 Jeśli C jest zbiorem o c elementach, ile elementów zawiera zbiór potęgowy zbioru C? Odpowiedź uzasadnij.
0.6 Niech X będzie zbiorem {1, 2, 3, 4, 5}, a Y zbiorem {6, 7, 8, 9, 10}. Jednoargumentowa funkcja f : X ? Y i dwuargumentowa funkcja g : X × Y ? Y opisane są następującymi tablicami.
n
f(n)
g
6
7
8
9
10
1
6
1
10
10
10
10
10
2
7
2
7
8
9
10
6
3
6
3
7
7
8
8
9
4
7
4
9
8
7
6
10
5
6
5
6
6
6
6
6
a. Jaka jest wartość f(2)?
b. Jaka jest dziedzina i przeciwdziedzina f?
c. Jaka jest wartość g(2, 10)?
d. Jaka jest dziedzina i przeciwdziedzina g?
e. Jaka jest wartość g(4, f(4))?
0.7 Dla każdego punktu podaj przykład relacji, która spełnia podany warunek.
a. Zwrotna i symetryczna, ale nie przechodnia
b. Zwrotna i przechodnia, ale nie symetryczna
c. Symetryczna i przechodnia, ale nie zwrotna
0.8 Rozważ nieskierowany graf G = (V, E), gdzie V, czyli zbiór wierzchołków, to {1, 2, 3, 4}, a E, czyli zbiór krawędzi, to {{1, 2}, {2, 3}, {1, 3}, {2, 4}, {1, 4}}. Narysuj graf G. Jaki jest stopień każdego wierzchołka? Na rysunku grafu G zaznacz ścieżkę od wierzchołka 3 do wierzchołka 4.
0.9 Napisz formalny opis poniższego grafu.
Zadania
0.10 Znajdź błąd w poniższym dowodzie, że 2 = 1.
Rozważmy równanie a = b. Mnożymy obie strony równania przez a, uzyskując a2 = ab. Od obu stron równania odejmujemy b2, otrzymując a2 - b2 = ab - b2. Przekształcamy obie strony do postaci (a+b)(a-b) = b(a-b), po czym dzielimy obie strony przez (a-b), otrzymując a+b = b. Na koniec podstawiamy 1 za a i b, co daje 2 = 1.
0.11 Niech S(n) = 1 + 2 + ... + n będzie sumą pierwszych n liczb naturalnych, zaś C(n) = 13 + 23 + ... + n3 niech będzie sumą pierwszych n sześcianów liczb naturalnych. Udowodnij następujące równości, używając indukcji po n, aby dojść do zadziwiającego wniosku, że C(n) = S2(n) dla każdego n.
a. S(n) = 1/3 n(n + 1).
b. C(n) = 1/3 (n4 + 2n3 + n2) = 1/3 n2(n + 1)2.
0.12 Znajdź błąd w poniższym dowodzie, że wszystkie konie są tego samego koloru.
Twierdzenie: W dowolnym zbiorze h koni wszystkie konie są tego samego koloru.
Dowód: Przez indukcję po h.
Krok podstawowy: Dla h = 1. W dowolnym zbiorze zawierającym tylko jednego konia wszystkie konie oczywiście mają ten sam kolor.
Krok indukcyjny: Dla k ? 1, zakładamy, że teza jest prawdziwa dla h = k i wykażemy, że jest też prawdziwa dla h = k+1. Weźmy dowolny zbiór H zawierający k+1 koni. Wykażemy, że wszystkie konie w tym zbiorze są tego samego koloru. Usuwamy jednego konia z tego zbioru, aby uzyskać zbiór H1 zawierający tyko k koni. Na mocy założenia indukcyjnego wszystkie konie ze zbioru H1 są tego samego koloru. Teraz zwracamy usuniętego konia i usuwamy innego, aby uzyskać zbiór H2. Na mocy tego samego rozumowania wszystkie konie w H2 są tego samego koloru. Tym samym wszystkie konie w zbiorze muszą mieć ten sam kolor, co kończy dowód.
0.13 Wykaż, że każdy graf bez pętli zwrotnych z dwoma lub więcej wierzchołkami zawiera dwa wierzchołki o równych stopniach.
A*0.14 Twierdzenie Ramseya. Niech G będzie grafem. Kliką w G nazywamy podgraf, w którym każde dwa wierzchołki są ze sobą połączone krawędzią. Antyklika, nazywana też zbiorem niezależnym, to podgraf, w którym dowolne dwa wierzchołki nie są ze sobą połączone krawędzią. Udowodnij, że każdy graf o n wierzchołkach zawiera albo kilkę, albo antyklikę z co najmniej 1/3 log2n wierzchołkami.
A0.15 Użyj twierdzenia 0.25, aby wyprowadzić wzór na obliczanie wielkości miesięcznej raty spłaty kredytu na podstawie wartości kredytu P, stopy oprocentowania I oraz liczby spłat t. Przyjmij założenie, że po wykonaniu t spłat wielkość długu jest zredukowana do 0. Użyj tego wzoru do obliczenia wartości miesięcznej raty dla 30-letniego kredytu z 360 miesięcznymi ratami dla początkowej wartości kredytu wynoszącej 100 000 dolarów przy rocznej stopie oprocentowania 5%.
Wybrane rozwiązania
0.14 Przygotuj miejsce na dwie kupki wierzchołków: A i B. Następnie rozważaj po kolei wszystkie wierzchołki i jeśli dany wierzchołek x ma stopień większy niż połowa nierozważonych jeszcze wierzchołków, to umieść go na kupce A a w przeciwnym razie na kupce B; jeśli x został umieszczony na kupce A (na kupce B), usuń z grafu wszystkie wierzchołki z którymi x nie jest (jest) połączony. Wykonuj te operacje, aż wszystkie wierzchołki zostaną rozważone lub usunięte. W każdym kroku usuwamy nie więcej niż połowę wierzchołków, więc wykonamy co najmniej log2n kroków. W każdym kroku wierzchołek dodawany jest na jedną z kupek, zatem jedna z nich ma wielkość co najmniej 1/3 log2n wierzchołków. Kupka A zawiera wierzchołki tworzące klikę, zaś kupka B wierzchołki tworzące antyklikę.
0.15 Przyjmujemy Pt = 0 i rozwiązujemy wzór ze względu na Y, aby uzyskać wzór: Y = PMt(M - 1)//(Mt - 1). Dla P = $100,000, I = 0.05 i t = 360 otrzymujemy M = 1 + (0.05)/12. Następnie można użyć kalkulatora, aby ustalić, że rata miesięczna Y " $536.82.
