Dla

Iny, Rachel i Aarona

Dane oryginału

Original edition copyright © 2013 by Cengage Learning. All rights reserved. Title of English-language original: Introdution to the theory of computation. Third edition by Michael Sipser. Polish edition copyright 2020 by Polish Scientific Publishers PWN Wydawnictwo Naukowe PWN Spółka Akcyjna. All rights reserved.

Przekład Marek Włodarz na zlecenie WITKOM Witold Sikorski

Projekt okładki polskiego wydania Joanna Andryjowicz

Wydawca Wioleta Szczygielska-Dybciak

Redaktor prowadzący Jolanta Kowalczuk

Redaktor Piotr Faliszewski

Korekta Jolanta Kucharska

Koordynator produkcji Anna Bączkowska

Konsultacja merytoryczna

dr hab. inż. Piotr Faliszewski, profesor nadzwyczajny

Akademii Górniczo-Hutniczej im. Stanisława Staszica w Krakowie

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

Skład wersji elektronicznej na zlecenie Wydawnictwa Naukowego PWN

Monika Lipiec / Woblink

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 SA

Warszawa 2020

ISBN 978-83-01-21099-1

eBook został przygotowany na podstawie wydania papierowego z 2020 r., (wyd. III - I w WN PWN)

Warszawa 2020

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.pl

www.pwn.pl

Spis treści

Przedmowa do pierwszego wydania

Do studentów

Do nauczycieli

Pierwsze wydanie

Uwagi do autora

Podziękowania

Przedmowa do drugiego wydania

Przedmowa do trzeciego wydania

0. Wstęp

0.1 Automaty, obliczalność i złożoność

Teoria złożoności

Teoria obliczalności

Teoria automatów

0.2 Pojęcia matematyczne i terminologia

Zbiory

Ciągi i krotki

Funkcje i relacje

Grafy

Słowa i języki

Logika Boole’a

Podsumowanie terminów matematycznych

0.3 Definicje, twierdzenia i dowody

Znajdowanie dowodów

0.4 Typy dowodów

Dowód przez konstrukcję

Dowód nie wprost (przez sprowadzenie do sprzeczności)

Dowód indukcyjny

Dowód

CZĘŚĆ I. AUTOMATY I JĘZYKI

1. Języki regularne

1.1 Automaty skończone

Formalna definicja automatu skończonego

Przykłady automatów skończonych

Formalna definicja obliczeń

Projektowanie automatów skończonych

Operacje regularne

1.2 Niedeterminizm

Formalna definicja niedeterministycznego automatu skończonego

Równoważność NFA i DFA

Zamknięcie ze względu na operacje regularne

1.3 Wyrażenia regularne

Formalna definicja wyrażenia regularnego

Równoważność z automatami skończonymi

1.4 Języki nieregularne

Lemat o pompowaniu dla języków regularnych

2. Języki bezkontekstowe

2.1 Gramatyki bezkontekstowe

Formalna definicja gramatyki bezkontekstowej

Przykłady gramatyk bezkontekstowych

Projektowanie gramatyk bezkontekstowych

Niejednoznaczność

Postać normalna Chomsky’ego

2.2 Automaty ze stosem

Formalna definicja automatu ze stosem

Przykłady automatów ze stosem

Równoważność z gramatykami bezkontekstowymi

2.3 Języki niebędące bezkontekstowymi

Lemat o pompowaniu dla języków bezkontekstowych

2.4 Deterministyczne języki bezkontekstowe

Właściwości języków DCFL

Deterministyczne gramatyki bezkontekstowe

Zależności między DPDA a gramatykami DCFG

Parsing i gramatyki LR(k)

CZĘŚĆ II .TEORIA OBLIZALNOŚCI

3. Hipoteza Churcha-Turinga

3.1 Maszyny Turinga

Formalna definicja maszyny Turinga

Przykłady maszyn Turinga

3.2 Odmiany maszyn Turinga

Wielotaśmowe maszyny Turinga

Niedeterministyczne maszyny Turinga

Enumeratory

Równoważność z innymi modelami

3.3 Definicja algorytmu

Problemy Hilberta

Konwencja opisywania maszyn Turinga

4. Rozstrzygalność

4.1 Języki rozstrzygalne

Problemy rozstrzygalne dotyczące języków regularnych

Problemy rozstrzygalne dotyczące języków bezkontekstowych

4.2 Nierozstrzygalność

Metoda diagonalizacji

Język nierozstrzygalny

Język nierozpoznawalny w sensie Turinga

5. Redukowalność

5.1 Nierozstrzygalne problemy teorii języków

Redukcje przez historie obliczeń

5.2 Prosty problem nierozstrzygalny

5.3 Redukcja przez odwzorowanie

Funkcje obliczalne

Formalna definicja redukcji przez odwzorowanie

6. Zaawansowane zagadnienia teorii obliczalności

6.1 Twierdzenie o rekurencji

Samoodniesienie

Posługiwanie się twierdzeniem o rekurencji

Zastosowania

6.2 Rozstrzygalność teorii logicznych

Teoria rozstrzygalna

Teoria nierozstrzygalna

6.3 Redukowalność w sensie Turinga

6.4 Pojęcie informacji

Opisy minimalnej długości

Optymalność definicji

Słowa niekompresowalne i losowość

CZĘŚĆ III.TEORIA ZŁOŻONOŚCI

7. Złożoność czasowa

7.1 Mierzenie złożoności

Notacja wielkiego O i małego o

Analiza algorytmów

Zależności między złożonościami modeli

7.2 Klasa P

Czas wielomianowy

Przykłady problemów z klasy P

7.3 Klasa NP

Przykłady problemów z klasy NP

Zagadnienie P versus NP

7.4 NP-zupełność

Redukowalność w czasie wielomianowym

Definicja NP-zupełności

Twierdzenie Cooka-Levina

7.5 Dalsze problemy NP-zupełne

Problem pokrycia wierzchołkowego

Problem ścieżki Hamiltona

Problem sumy podzbioru

8. Złożoność pamięciowa

8.1 Twierdzenie Savitcha

8.2 Klasa PSPACE

8.3 PSPACE-zupełność

Problem TQBF

Strategie wygrywające w grach

Uogólniona gra w łańcuszek

8.4 Klasy L i NL

8.5 NL-zupełność

Przeszukiwanie grafów

8.6 Klasa NL równa się klasie coNL

9. Problemy trudne

9.1 Twierdzenia o hierarchii

Zupełność pamięci wykładniczej

9.2 Relatywizacja

Ograniczenia stosowalności metody diagonalizacji

9.3 Złożoność obwodów

10. Zaawansowane zagadnienia teorii złożoności

10.1 Algorytmy aproksymacyjne

10.2 Algorytmy probabilistyczne

Klasa BPP

Pierwszość

Programy z rozgałęzieniami z jednokrotnym odczytem

10.3 Alternacje

Czas i pamięć w obliczeniach alternujących

Wielomianowa hierarchia czasowa

10.4 Systemy dowodów interaktywnych

Nieizomorfizm grafów

Definicja modelu

IP = PSPACE

10.5 Obliczenia równoległe

Jednolite obwody logiczne

Klasa NC

P-zupełność

10.6 Kryptografia

Klucze tajne

Systemy szyfrowania z kluczem publicznym

Funkcje jednokierunkowe

Funkcje z bocznym wejściem

Wybrana bibliografia

Przypisy

Przedmowa do pierwszego wydania

Do studentów

Witajcie!

Za moment rozpoczniecie poznawanie fascynującej i ważnej dziedziny: teorii obliczeń. Obejmuje ona fundamentalne własności matematyczne sprzętu komputerowego, oprogramowania i ich pewnych zastosowań. Studiując tę dziedzinę, staramy się określić, co można, a czego nie można obliczyć, jak szybko można to zrobić, jak dużo potrzeba do tego pamięci i w jakiego rodzaju modelu obliczeniowym. Zagadnienia te są w oczywisty sposób związane z praktyką inżynierską, a jednocześnie, podobnie jak w wielu dziedzinach nauki, mają również aspekty czysto filozoficzne.

Wiem, że wielu z was z niecierpliwością oczekuje na poznanie tego materiału, choć być może nie wszyscy są tu z własnej woli. Być może chcecie zdobyć dyplom informatyka lub inżyniera, a wykład z teorii jest na liście wymaganych – Bóg jeden wie, dlaczego. Czyż teoria nie jest mętna, nudna, a co gorsza, nieistotna?

Czytajcie dalej, a przekonacie się, że ta teoria nie jest ani mętna czy tajemna, ani nużąca, ale całkiem zrozumiała i wręcz interesująca. Informatyka teoretyczna zawiera wiele wspaniałych, wielkich idei, choć nie brak w niej drobnych i niekiedy nudnych szczegółów, które mogą być męczące. Uczenie się nowych rzeczy zawsze jest trudne, ale może stać się łatwiejsze i bardziej przyjemne, jeśli materiał jest odpowiednio podany. Główny cel, jak postawiłem sobie przed napisaniem tej książki, to przedstawienie Czytelnikom fascynujących aspektów teorii obliczeń bez ugrzęźnięcia w zbędnych zawiłościach. Oczywiście jedynym sposobem ustalenia, czy ta teoria okaże się interesująca, jest próba nauczenia się jej.

Teoria jest blisko powiązana z praktyką. Dostarcza narzędzi myślowych, które praktycy wykorzystują w inżynierii komputerów. Projektujesz nowy język programowania do specjalnych zastosowań? Przyda się to, czego nauczysz się o gramatykach. Zajmujesz się wyszukiwaniem słów i dopasowywaniem wzorców? Pamiętaj o automatach skończonych i wyrażeniach regularnych. Stanąłeś przed problemem, którego rozwiązanie wydaje się wymagać więcej czasu, niż możesz na to przeznaczyć? Pomyśl o tym, czego nauczyłeś się o NP-zupełności. Różne obszary zastosowań, takie jak nowoczesne protokoły kryptograficzne, opierają się na zasadach teoretycznych, których nauczysz się z tej książki.

Teoria jest ważna również dlatego, że pokazuje nową, prostszą i bardziej elegancką stronę komputerów, które zwykle uważane są za bardzo złożone maszyny. Najlepsze projekty komputerów i aplikacji wyłaniają się z eleganckich koncepcji. Teoretyczny wykład może wzmocnić zmysł estetyczny i pomóc w budowaniu piękniejszych systemów.

Wreszcie teoria jest dobra, gdyż studiowanie jej rozwija umysł. Technologie komputerowe szybko się zmieniają. Szczegółowa wiedza techniczna, choć użyteczna w tej chwili, za kilka lat stanie się przestarzała. Warto więc rozwijać umiejętność myślenia, wyrażania się jasno i precyzyjnie, aby móc rozwiązywać problemy i wiedzieć, kiedy problemu nie zdołaliśmy rozwiązać. Takie umiejętności mają trwałą wartość. Studiując teorię, ćwiczymy się w tych dziedzinach.

Pomijając kwestię praktycznej przydatności, niemal każdego wykorzystującego komputery w pracy ciekawią te niezwykłe twory, ich możliwości i ograniczenia. W ciągu ostatnich trzydziestu lat rozwinęła się nowa gałąź matematyki, której badacze szukają odpowiedzi na pewne fundamentalne pytania. Oto jedno z nich, które pozostaje nierozwiązane: Jeśli weźmiemy wielką liczbę – powiedzmy o 500 cyfrach – czy możemy znaleźć jej dzielniki (liczby, przez które dzieli się ona bez reszty) w rozsądnym czasie? Nawet korzystając z superkomputera, nikt obecnie nie wie, jak tego dokonać dla każdego przypadku w czasie krótszym niż równy wiekowi wszechświata! Problem faktoryzacji (czyli problem rozkładu na czynniki) jest ściśle związany z nowoczesnymi systemami szyfrowania. Znajdź szybką metodę rozkładu liczby na czynniki, a zdobędziesz sławę!

Do nauczycieli

Książka ta jest przeznaczona jako podręcznik z zakresu informatyki teoretycznej dla studentów studiów magisterskich oraz wyższych lat studiów licencjackich i inżynierskich. Zagadnienia przedstawione są matematycznie, oparte na twierdzeniach i dowodach. Dołożyłem starań, aby wprowadzić studentów mających niewielkie doświadczenie w dowodzeniu twierdzeń, ale bardziej zaawansowanym studentom będzie to przychodziło łatwiej.

Moim głównym celem było przedstawienie materiału w sposób przejrzysty i interesujący. Z tego względu przedkładałem intuicję i obraz ogólny nad drobiazgowe analizy szczegółów niższego poziomu.

Na przykład, choć przedstawiłem metodę dowodu przez indukcję w rozdziale Ø wraz z innymi podstawami matematycznymi, nie odgrywa ona istotnej roli w dalszej części książki. W ogólności nie pokazuję typowych indukcyjnych dowodów poprawności różnych konstrukcji dotyczących automatów. Jeżeli zostaną jasno przedstawione, to konstrukcje takie bronią się same i nie wymagają dalszego uzasadniania. Indukcja mogłaby raczej zaciemniać, niż wyjaśniać problem, gdyż sama w sobie jest dość wyrafinowaną techniką, niezrozumiałą dla wielu osób. Objaśnianie oczywistych faktów przez indukcję stwarza ryzyko, że studenci utrwalą przekonanie, że dowód matematyczny jest rodzajem formalnej manipulacji, zamiast nauczyć ich odróżniania przekonywającej argumentacji od nieprzekonywającej.

Drugi przykład występuje w częściach drugiej i trzeciej, gdzie opisuję algorytmy językiem potocznym zamiast posługiwania się pseudokodem. Nie poświęciłem zbyt wiele czasu na programowanie maszyn Turinga (ani żadnego innego formalnego modelu). Dzisiejsi studenci mają przygotowanie programistyczne i hipoteza Churcha-Turinga jest dla nich oczywista. Dlatego nie przedstawiam długich symulacji jednego modelu przez drugi, aby wykazać ich równoważność.

Mimo że większą rolę przyznaję intuicji i pominijam pewne szczegóły, przedstawiam materiał w sposób, który można nazwać klasycznym. Większość teoretyków uzna, że dobór materiału, terminologia i kolejność prezentacji są zgodne z tym, co jest zawarte w innych szeroko wykorzystywanych podręcznikach. Własną oryginalną terminologię wprowadziłem jedynie w kilku miejscach, gdy uznałem, że standardowo wykorzystywane pojęcia są szczególnie niejasne lub mylące. Wprowadziłem na przykład pojęcie redukcji przez odwzorowanie w miejsce redukcji wiele do jednego.

Ćwiczenie przez rozwiązywanie zadań jest podstawą nauki dowolnej dziedziny matematycznej. Przedstawione w książce zadania zostały podzielone na dwie kategorie: Ćwiczenia i Zadania. Ćwiczenia mają na celu przypomnienie i utrwalenie definicji i pojęć. Zadania wymagają pewnej kreatywności. Zadania oznaczone gwiazdką są trudniejsze. Starałem się, aby rozwiązywanie zarówno ćwiczeń, jak i zadań było ciekawym wyzwaniem dla studentów.

Pierwsze wydanie

Wprowadzenie do teorii obliczeń ukazało się po raz pierwszy jako wydanie wstępne w miękkiej oprawie. Pierwsze wydanie pod kilkoma istotnymi względami różni się od wydania wstępnego. Zostały dodane trzy końcowe rozdziały: rozdział 8 o złożoności pamięciowej, rozdział 9 o problemach nieobliczalnych oraz rozdział 10 poświęcony zaawansowanym zagadnieniom z teorii złożoności. Rozdział 6 został rozszerzony o kilka rozbudowanych tematów z teorii obliczalności. Inne rozdziały zostały również uzupełnione o dodatkowe przykłady i ćwiczenia.

Uwagi, jakie otrzymałem od wykładowców i studentów korzystających z wydania wstępnego, pomogły w dopracowaniu rozdziałów 0–7. Naturalnie poprawiłem też błędy, na które zwrócono mi uwagę.

Rozdziały 6 i 10 zawierają przegląd kilku bardziej zaawansowanych zagadnień należących do teorii obliczalności i złożoności. Nie mają one na celu przedstawienia tematyki w tak wyczerpujący i spójny sposób, jak pozostałe rozdziały. Rozdziały te dołączyłem, aby umożliwić nauczycielowi wybór opcjonalnych tematów, które mogą być interesujące dla studentów. Zagadnienia te same należą do różnorodnych dziedzin. Niektóre, takie jak redukowalność w sensie Turinga lub alternacje, są bezpośrednim rozwinięciem innych koncepcji omawianych w książce. Inne, takie jak rozstrzygalne teorie logiczne czy kryptografia, są tylko krótkimi wprowadzeniami do obszernych dziedzin badań.

Uwagi do autora

Internet stwarza nowe możliwości interakcji między autorami a czytelnikami. Otrzymałem wiele e-maili zawierających sugestie, pochwały i uwagi krytyczne, w tym także zgłoszenia błędów występujących w wydaniu wstępnym. Proszę, piszcie nadal! Staram się odpowiadać na każdą wiadomość, gdy tylko pozwala mi czas. Adres, pod który należy kierować korespondencję dotyczącą tej książki, to

sipserbook@math.mit.edu.

Na bieżąco prowadzona jest również strona internetowa zawierająca erratę książki. Na stronie tej mogą pojawiać się też inne materiały przydatne dla nauczycieli i studentów. Będę wdzięczny za informacje, co mogłoby się tam znaleźć. Strona ta jest dostępna pod adresem:

http://math.mit.edu/~sipser/book.html.

Podziękowania

Nie mógłbym napisać tej książki bez pomocy wielu przyjaciół, kolegów i mojej rodziny.

Chciałbym podziękować moim nauczycielom, którzy pomogli ukształtować moje poglądy naukowe i metody nauczania. Pięciu z nich wyróżnia się szczególnie. Mój promotor, Manuel Blum, zasługuje na szczególną uwagę za wyjątkową zdolność do inspirowania studentów dzięki przejrzystości przedstawianych myśli, entuzjazm i opiekę. Jest wzorem dla mnie i wielu innych. Jestem także wdzięczny Richardowi Karpowi za wprowadzenie mnie w tajniki teorii złożoności, Johnowi Addisonowi za nauczenie mnie logiki i przygotowywanie wspaniałych zadań domowych, Jurisowi Hartmanisowi za wprowadzenie w teorię obliczeń oraz mojemu ojcu za nauczenie mnie podstaw matematyki, posługiwania się komputerami i sztuki przekazywania wiedzy.

Książka to powstała na podstawie notatek do wykładu, który prowadziłem w MIT przez ostatnie 15 lat. Spisali je studenci uczestniczący w moich wykładach. Mam nadzieję, że wybaczą mi, że nie wymienię ich wszystkich. Asystenci, którzy pracowali ze mną przez te lata – Avrim Blum, Thang Bui, Benny Chor, Andrew Chou, Stavros Cosmadakis, Aditi Dhagat, Wayne Goddard, Parry Husbands, Dina Kravets, Jakov Kučan, Brian O’Neill, Ioana Popescu i Alex Russell – pomogli w redagowaniu i rozwinięci tych notatek. Są także autorami niektórych ćwiczeń i zadań.

Prawie trzy lata temu Tom Leighton przekonał mnie do napisania podręcznika z teorii obliczeń. Rozmyślałem nad tym od pewnego czasu, ale to argumentacja Toma pozwoliła przekształcić teorię w praktykę. Jestem mu wdzięczny za liczne rady dotyczące pisania książek i wiele innych rzeczy.

Chciałbym podziękować za uwagi, komentarze i pomoc w trakcie pisania książki, jakiej udzielili mi Eric Bach, Peter Beebee, Cris Calude, Marek Chrobak, Anna Chefter, Guang-Ien Cheng, Elias Dahlhaus, Michael Fischer, Steve Fisk, Lance Fortnow, Henry J. Friedman, Jack Fu, Seymour Ginsburg, Oded Goldreich, Brian Grossman, David Harel, Micha Hofri, Dung T. Huynh, Neil Jones, H. Chad Lane, Kevin Lin, Michael Loui, Silvio Micali, Tadao Murata, Christos Papadimitriou, Vaughan Pratt, Daniel Rosenband, Brian Scassellati, Ashish Sharma, Nir Shavit, Alexander Shen, Ilya Shlyakhter, Matt Stallmann, Perry Susskind, Y. C. Tay, Joseph Traub, Osamu Watanabe, Peter Widmayer, David Williamson, Derick Wood i Charles Yang.

Następujące osoby przekazały dodatkowe komentarze i uwagi, które pozwoliły ulepszyć tę książkę: Isam M. Abdelhameed, Eric Allender, Shay Artzi, Michelle Atherton, Rolfe Blodgett, Al Briggs, Brian E. Brooks, Jonathan Buss, Jin Yi Cai, Steve Chapel, David Chow, Michael Ehrlich, Yaakov Eisenberg, Farzan Fallah, Shaun Flisakowski, Hjalmtyr Hafsteinsson, C. R. Hale, Maurice Herlihy, Vegard Holmedahl, Sandy Irani, Kevin Jiang, Rhys Price Jones, James M. Jowdy, David M. Martin Jr., Manrique Mata-Montero, Ryota Matsuura, Thomas Minka, Farooq Mohammed, Tadao Murata, Jason Murray, Hideo Nagahashi, Kazuo Ohta, Constantine Papageorgiou, Joseph Raj, Rick Regan, Rhonda A. Reumann, Michael Rintzler, Arnold L. Rosenberg, Larry Roske, Max Rozenoer,Walter L. Ruzzo, Sanatan Sahgal, Leonard Schulman, Steve Seiden, Joel Seiferas, Ambuj Singh, David J. Stucki, Jayram S. Thathachar, H. Venkateswaran, Tom Whaley, Christopher Van Wyk, Kyle Young oraz Kyoung Hwan Yun.

Robert Sloan wykorzystał roboczą wersję książki w swoim wykładzie i przekazał mi nieocenione uwagi i pomysły wynikające z tego doświadczenia. Mark Herschberg, Kazuo Ohta i Latanya Sweeney przeczytali części rękopisu i zasugerowali liczne poprawki. Shafi Goldwasser pomogła mi przy pracy nad materiałem do rozdziału 10.

Otrzymałem pomoc techniczną od Williama Baxtera z firmy Superscript, który napisał pakiet makr w LATEX-u, implementujący układ wewnętrzny książki, oraz od Larry’ego Nolana z wydziału matematycznego MIT, który zadbał o to, by wszystko działało.

Przyjemnością była współpraca z ekipą z PWS Publishing przy tworzeniu wersji finalnej. Wspomnę tu tylko Michaela Sugarmana, Davida Dietza, Elise Kaiser, Monique Calello, Susan Garland oraz Tanję Brull, gdyż to z nimi miałem większość kontaktów, ale zdaję sobie sprawę, że w pracę zaangażowanych było wiele innych osób. Dziękuję Jerry’emu Moore’owi za redakcję tekstu, Diane Levy za projekt okładki oraz Catherine Hawkes za projekt układu wewnętrznego.

Dziękuję National Science Foundation za wsparcie w ramach grantu CCR-9503322.

Mój ojciec, Kenneth Sipser, oraz siostra, Laura Sipser, przekształcili rysunki zamieszczone w książce na postać elektroniczną. Moja druga siostra, Karen Fisch, ratowała nas z różnych komputerowych opresji, a moja mama, Justine Sipser, służyła matczynymi radami. Dziękuję im wszystkich za wsparcie w trudnych warunkach, w tym przy zwariowanych terminach i opornym oprogramowaniu.

Na koniec kieruję wyrazy miłości do mojej żony Iny i córki Rachel. Dziękuję, że zniosłyście to wszystko.

Michael Sipser

Cambridge, Massachusetts, październik 1996

Przedmowa do drugiego wydania

Sądząc z e-maili, które otrzymałem od tak wielu czytelników, największą wadą pierwszego wydania był brak przykładowych rozwiązań choćby niektórych zadań. Zatem już są. Każdy rozdział zawiera teraz nowy punkt zatytułowany Wybrane rozwiązania, w którym są odpowiedzi na reprezentatywny wybór ćwiczeń i zadań z tego rozdziału. Aby uzupełnić zmniejszony w ten sposób wybór zadań do samodzielnego rozwiązania, dodałem także sporo nowych ćwiczeń i zadań. Wykładowcy mogą też zamówić Podręcznik nauczyciela zawierający dodatkowe rozwiązania. W tym celu należy się skontaktować z regionalnym przedstawicielem handlowym wskazanym na stronie www.course.com.

Wielu czytelników domagało się szerszego omówienia niektórych „standardowych” zagadnień, a w szczególności twierdzenia Myhilla-Neroda oraz twierdzenia Rice’a. Częściowo zastosowałem się do tych próśb, rozwijając te zagadnienia jako zadania z rozwiązaniami. Nie zamieściłem twierdzenia Myhilla-Neroda w zasadniczym tekście, gdyż uważam, że ten wykład powinien zapewniać jedynie wprowadzenie do teorii automatów skończonych, a nie jej pogłębioną analizę. W moim ujęciu rola automatów skończonych w tej książce polega na tym, aby studenci mogli poznać prosty formalny model obliczeń jako preludium do silniejszych modeli, a także aby stanowiły podstawę wygodnych przykładów przy omawianiu dalszych zagadnień. Oczywiście niektórzy będą woleli bardziej szczegółowe potraktowanie tego tematu, podczas gdy inni chcieliby, abym w ogóle pominął wszelkie wzmianki o automatach skończonych (a przynajmniej nie uzależniał od nich późniejszych zagadnień). Nie włączyłem twierdzenia Rice’a do zasadniczego tekstu książki, gdyż, mimo że jest to użyteczne narzędzie dowodzenia nierozstrzygalności, niektórzy studenci mogliby posługiwać się nim mechanicznie, bez prawdziwego zrozumienia istoty problemu. Dowodzenie nierozstrzygalności za pomocą redukcji zamiast twierdzenia Rice’a daje lepsze przygotowanie do redukcji, które pojawiają się później w teorii złożoności.

Jestem wdzięcznym dłużnikiem moich asystentów, którzy pomogli mi w opracowaniu niektórych nowych zadań i rozwiązań. Są to Ilya Baran, Sergi Elizalde, Rui Fan, Jonathan Feldman, Venkatesan Guruswami, Prahladh Harsha, Christos Kapoutsis, Julia Khodor, Adam Klivans, Kevin Matulef, Ioana Popescu, April Rasala, Sofya Raskhodnikova oraz Iuliu Vasilescu. W opracowywaniu rozwiązań brali również udział Ching W. Law, Edmond Kayi Lee i Zulfikar Ramzan. Dziękuję Victorowi Shoupowi za znalezienie prostego sposobu załatania luki w analizie probabilistycznego algorytmu sprawdzania pierwszości liczb, która występowała w pierwszym wydaniu.

Dziękuję osobom z Course Technology za motywowanie mnie i innych uczestników tego projektu, a zwłaszcza Alyssi Pratt Aimee Poirier. Wielkie podziękowania należą się też Geraldowi Eismanowi, Weizhenowi Mao, Rupakowi Majumdarowi, Chrisowi Umansowi i Christopherowi Wilsonowi za recenzje. Jestem też zobowiązany Jerry’emu Moore’owi za świetną robotę przy redakcji tekstu i Laurze Segel z firmy ByteGraphics (lauras@bytegraphics.com) za przepiękne opracowanie rysunków.

Liczba e-maili, które dostałem, przekroczyła moje oczekiwania. Otrzymywanie wiadomości z tak wielu miejsc było wspaniałym doświadczeniem i starałem się odpowiadać wszystkim – proszę o wybaczenie tych, których pominąłem. Wymieniam tu te osoby, których sugestie miały szczególny wpływ na to wydanie, ale wszystkim dziękuję za korespondencję:

Luca Aceto, Arash Afkanpour, Rostom Aghanian, Eric Allender, Karun Bakshi, Brad Ballinger, Ray Bartkus, Louis Barton, Arnold Beckmann, Mihir Bellare, Kevin Trent Bergeson, Matthew Berman, Rajesh Bhatt, Somenath Biswas, Lenore Blum, Mauro A. Bonatti, Paul Bondin, Nicholas Bone, Ian Bratt, Gene Browder, Doug Burke, Sam Buss, Vladimir Bychkovsky, Bruce Carneal, Soma Chaudhuri, Rong-Jaye Chen, Samir Chopra, Benny Chor, John Clausen, Allison Coates, Anne Condon, Jeffrey Considine, John J. Crashell, Claude Crepeau, Shaun Cutts, Susheel M. Daswani, Geoff Davis, Scott Dexter, Peter Drake, Jeff Edmonds, Yaakov Eisenberg, Kurtcebe Eroglu, Georg Essl, Alexander T. Fader, Farzan Fallah, Faith Fich, Joseph E. Fitzgerald, Perry Fizzano, David Ford, Jeannie Fromer, Kevin Fu, Atsushi Fujioka, Michel Galley, K. Ganesan, Simson Garfinkel, Travis Gebhardt, Peymann Gohari, Ganesh Gopalakrishnan, Steven Greenberg, Larry Griffith, Jerry Grossman, Rudolf de Haan, Michael Halper, Nick Harvey, Mack Hendricks, Laurie Hiyakumoto, Steve Hockema, Michael Hoehle, Shahadat Hossain, Dave Isecke, Ghaith Issa, Raj D. Iyer, Christian Jacobi, Thomas Janzen, Mike D. Jones, Max Kanovitch, Aaron Kaufman, Roger Khazan, Sarfraz Khurshid, Kevin Killourhy, Seungjoo Kim, Victor Kuncak, Kanata Kuroda, Thomas Lasko, Suk Y. Lee, Edward D. Legenski, Li-Wei Lehman, Kong Lei, Zsolt Lengvarszky, Jeffrey Levetin, Baekjun Lim, Karen Livescu, Stephen Louie, Tzer Hung Low, Wolfgang Maass, Arash Madani, Michael Manapat, Wojciech Marchewka, David M. Martin Jr., Anders Martinson, Lyle McGeoch, Alberto Medina, Kurt Mehlhorn, Nihar Mehta, Albert R. Meyer, Thomas Minka, Mariya Minkova, Daichi Mizuguchi, G. Allen Morris III, Damon Mosk-Aoyama, Xiaolong Mou, Paul Muir, German Muller, Donald Nelson, Gabriel Nivasch, Mary Obelnicki, Kazuo Ohta, Thomas M. Oleson, Jr., Curtis Oliver, Owen Ozier, Rene Peralta, Alexander Perlis, Holger Petersen, Detlef Plump, Robert Prince, David Pritchard, Bina Reed, Nicholas Riley, Ronald Rivest, Robert Robinson, Christi Rockwell, Phil Rogaway, Max Rozenoer, John Rupf, Teodor Rus, Larry Ruzzo, Brian Sanders, Cem Say, Kim Schioett, Joel Seiferas, Joao Carlos Setubal, Geoff Lee Seyon, Mark Skandera, Bob Sloan, Geoff Smith, Marc L. Smith, Stephen Smith, Alex C. Snoeren, Guy St-Denis, Larry Stockmeyer, Radu Stoleru, David Stucki, Hisham M. Sueyllam, Kenneth Tam, Elizabeth Thompson, Michel Toulouse, Eric Tria, Chittaranjan Tripathy, Dan Trubow, Hiroki Ueda, Giora Unger, Kurt L. Van Etten, Jesir Vargas, Bienvenido Velez-Rivera, Kobus Vos, Alex Vrenios, Sven Waibel, Marc Waldman, Tom Whaley, Anthony Widjaja, Sean Williams, Joseph N. Wilson, Chris Van Wyk, Guangming Xing, Vee Voon Yee, Cheng Yongxi, Neal Young, Timothy Yuen, Kyle Yung, Jinghua Zhang, Lilla Zollei.

Podziękowania należą się też osobom, które wskazały błędy w pierwszym wydaniu: Suzanne Balik, Matthew Kane, Kurt L. Van Etten, Nancy Lynch, Gregory Roberts oraz Cem Say.

Przede wszystkim zaś dziękuję mojej rodzinie – Inie, Rachel i Aaronowi – za ich cierpliwość, wyrozumiałość i uczucie, gdy przez niekończące się godziny tkwiłem przed ekranem mojego komputera.

Michael Sipser

Cambridge, Massachusetts, grudzień 2004

Przedmowa do trzeciego wydania

Trzecie wydanie zawiera zupełnie nowy podrozdział poświęcony deterministycznym językom bezkontekstowym. Wybrałem ten temat z kilku powodów. Po pierwsze, wypełnia oczywistą lukę w poprzednim ujęciu teorii automatów i języków formalnych. Starsze wydania wprowadzały pojęcia automatów skończonych i maszyn Turinga w wariantach deterministycznych i niedeterministycznych, ale omawiałem w nich tylko niedeterministyczne wersje automatów ze stosem. Dodanie omówienia deterministycznych automatów ze stosem jest brakującym fragmentem układanki.

Po drugie, teoria deterministycznych języków bezkontekstowych jest podstawą gramatyk LR(k), ważnego i nietrywialnego zastosowania teorii automatów w projektowaniu języków programowania i kompilatorów. To zastosowanie łączy wiele kluczowych koncepcji, w tym równoważność deterministycznych i niedeterministycznych automatów skończonych oraz przekształcanie gramatyk bezkontekstowych na automaty ze stosem i odwrotnie, doprowadzając do wydajnej i pięknej metody parsingu. Mamy tu więc rzeczywiste współdziałanie teorii i praktyki.

Na koniec zagadnienie to wydaje się nie dość wyczerpująco omówione w istniejących podręcznikach teorii obliczeń, jeśli weźmiemy pod uwagę jego ważność jako naturalnego zastosowania teorii automatów. Gramatyki LR(k) studiowałem lata temu, ale nie osiągnąłem wówczas pełnego zrozumienia ich działania i nie dostrzegłem, jak pięknie pasują one do teorii deterministycznych języków bezkontekstowych. Pisząc ten podrozdział, miałem na celu przedstawienie intuicyjnego, ale ścisłego wprowadzenia do tej dziedziny, zarówno dla teoretyków, jak i praktyków, a tym samym chciałem przyczynić się do szerszego docenienia tych zagadnień. Muszę jednak dodać pewne ostrzeżenie: część materiału zawartego w tym podrozdziale jest dość wymagająca, zatem nauczyciel prowadzący pierwszy, podstawowy wykład teorii może wybrać go na lekturę dodatkową. Późniejsze rozdziały nie zależą i nie odwołują się do treści tego podrozdziału.

Wiele osób miało bezpośredni lub pośredni udział w powstawaniu tego wydania. Jestem wdzięczny recenzentom Christosowi Kapoutsisowi i Cem Say, którzy przeczytali szkic nowej części i podzielili się wartościowymi uwagami. W produkcji brało udział wiele osób z Cengage Learning, a szczególnie Alyssa Pratt i Jennifer Feltri-George. Suzanne Huizenga zredagowała tekst, a Laura Segel z firmy ByteGraphics przygotowała nowe ilustracje i zmodyfikowała niektóre spośród starszych rysunków.

Chciałbym podziękować moim asystentom z MIT, Victorowi Chenowi, Andy’emu Druckerowi, Michaelowi Forbesowi, Elenie Grigorescu, Brendanowi Juba, Christosowi Kapoutsisowi, Jonowi Kelnerowi, Swastikowi Kopparty, Kevinowi Matulef, Amandzie Redlich, Zackowi Remscrimowi, Benowi Rossmanowi, Shubhangi Saraf oraz Orenowi Weimannowi. Każde z nich pomogło mi, omawiając nowe zadania i ich rozwiązania, i dając wgląd w to, jak dobrze nasi studenci rozumieją zawartość wykładu. Praca z tak utalentowanymi i entuzjastycznymi młodymi ludźmi jest prawdziwą przyjemnością.

Wielką nagrodą jest otrzymywanie e-maili z uwagami i komentarzami z całego świata. Dziękuję za wszystkie sugestie, pytania i pomysły. Oto lista tych korespondentów, których uwagi wpłynęły na kształt tego wydania:

Djihed Afifi, Steve Aldrich, Eirik Bakke, Suzanne Balik, Victor Bandur, Paul Beame, Elazar Birnbaum, Goutam Biswas, Rob Bittner, Marina Blanton, Rodney Bliss, Promita Chakraborty, Lewis Collier, Jonathan Deber, Simon Dexter, Matt Diephouse, Peter Dillinger, Peter Drake, Zhidian Du, Peter Fejer,Margaret Fleck, Atsushi Fujioka, Valerio Genovese, Evangelos Georgiadis, Joshua Grochow, Jerry Grossman, Andreas Guelzow, Hjalmtyr Hafsteinsson, Arthur Hall III, Cihat Imamoglu, Chinawat Isradisaikul, Kayla Jacobs, Flemming Jensen, Barbara Kaiser, Matthew Kane, Christos Kapoutsis, Ali Durlov Khan, Edwin Sze Lun Khoo, Yongwook Kim, Akash Kumar, Eleazar Leal, Zsolt Lengvarszky, Cheng-Chung Li, Xiangdong Liang, Vladimir Lifschitz, Ryan Lortie, Jonathan Low, Nancy Lynch, Alexis Maciel, Kevin Matulef, Nelson Max, Hans-Rudolf Metz, Mladen MikŜa, Sara Miner More, Rajagopal Nagarajan, Marvin Nakayama, Jonas Nyrup, Gregory Roberts, Ryan Romero, Santhosh Samarthyam, Cem Say, Joel Seiferas, John Sieg, Marc Smith, John Steinberger, Nuri Tas¸demir, Tamir Tassa, Mark Testa, Jesse Tjang, John Trammell, Hiroki Ueda, Jeroen Vaelen, Kurt L. Van Etten, Guillermo Vazquez, Phanisekhar Botlaguduru Venkata, Benjamin Bing-Yi Wang, Lutz Warnke, David Warren, ThomasWatson, Joseph Wilson, David Wittenberg, Brian Wongchaowart, Kishan Yerubandi, Dai Yi.

Ponad wszystko zaś dziękuję mojej rodzinie – mojej żonie Inie i naszym dzieciom Racheli i Aaronowi. Czas jest skończony i umyka szybko. Wasza miłość jest wszystkim.

Michael Sipser

Cambridge, Massachusetts, kwiecień 2012

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 = m^2 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.1
Diagram 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.2
Diagram 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.3
Nakł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.4
Diagramy 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 A_1, A_2, … , Ak, zapisywany jako A_1 × A_2 × … × Ak. Jest to zbiór złożony ze wszystkich k-krotek (a_1, a_2, … , 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 N^2 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 : Z_5 → Z_5.

■

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 : Z_4 × Z_4 → Z_4. 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 A_1×·…·×Ak dla pewnych zbiorów A_1, … , Ak, wejściem f jest k-krotka (a_1, a_2, … , 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(a_1, …, ak) oznacza, że R(a_1, …, 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:

1. R jest zwrotna, czyli dla każdego x zachodzi xRx;

2. R jest symetryczna, czyli dla każdych x i y z xRy wynika yRx; oraz

3. 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.12
Przykł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.13
Najtań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ów[1]. Na poniższym rysunku pokazano graf H i podgraf G.

Rysunek 0.14
Graf 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.16
Graf 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.18
Graf 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 = w_1w_2 … ·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 …·w_1). 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 x_1 … xmy_1 … 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

2n^2 = m^2.

Ponieważ m^2 jest podwojeniem liczby całkowitej n^2, wiemy, że m^2 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

2n^2 = (2k)2

= 4k^2.

Dzieląc obie strony przez 2, otrzymujemy

n^2 = 2k^2.

Jednak wynik ten pokazuje, że n^2 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 P_0 = P jest oryginalnym kredytem, P_1 = MP_0 − Y jest wielkością kredytu po jednym miesiącu, P_2 = MP_1 − 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 M^0 = 1. Otrzymujemy zatem

P_0 = P,

co jest prawdą, gdyż zdefiniowaliśmy P_0 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 a^2 = ab. Od obu stron równania odejmujemy b^2, otrzymując a^2 − b^2 = ab − b^2. 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) = 1^3 + 2^3 + … + n^3 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) = S^2(n) dla każdego n.

a. S(n) = 1/3 n(n + 1).

b. C(n) = 1/3 (n^4 + 2n^3 + n^2) = 1/3 n^2(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 H_1 zawierający tyko k koni. Na mocy założenia indukcyjnego wszystkie konie ze zbioru H_1 są tego samego koloru. Teraz zwracamy usuniętego konia i usuwamy innego, aby uzyskać zbiór H_2. Na mocy tego samego rozumowania wszystkie konie w H_2 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 log_2n 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 log_2n kroków. W każdym kroku wierzchołek dodawany jest na jedną z kupek, zatem jedna z nich ma wielkość co najmniej 1/3 log_2n 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.

Przypisy

Rozdział 0

[1] W polskiej nomenklaturze tak zdefiniowany podgraf nosi nazwę grafu indukowanego (przyp. red. wyd. polskiego).