Indukcja Matematyczna (1) Matematyka Dyskretna
INDUKCJA
INDUKCJA
MATEMATYCZNA
MATEMATYCZNA
Kilka przykładów:
(1) Kiedyś wiedziałem co to indukcja. Każdego dnia jeśli dzień
wcześniej wiem czym jest indukcja, to i tego dnia też wiem (bo nie
zapominam niczego z dnia na dzień).
(2) Zapisałem dzisiejszy wykład w 1250 linijkach. Jeśli potrafię coś
zapisać w n linikach to potrafię to też zapisać w n  1 linijkach (o ile
n > 1).
(3)
p "! q p "! q
gdzie " " {(", '", , "!, �"}
(r " p)"!(r " q) (p " r)"!(q " r)
p"!q
(~p)"!(~q)
|= p (q ((~p (" ~q) r))
|= (~p (" ~q) "! (~q (" ~p)
? p (q ((~q (" ~p) r))
Indukcja Matematyczna (2) Matematyka Dyskretna
(4) Regulamin.
ż1
Na wykładzie obecność jest obowiązkowa jedynie dla tych studentów,
którzy nie opuścili do tej pory żadnego wykładu oraz dla tych, którzy
dopuścili się wykroczenia przeciw temu regulaminowi.
(5) Ile by osób nie było już w tym audytorium, to i tak zawsze się
jeszcze jedna zmieści.
Indukcja Matematyczna (3) Matematyka Dyskretna
Aksjomat indukcji wyjęty wprost z teorii arytmetyki:
(tak naprawdę jest to schemat generujący nieskończenie wiele aksjo-
matów)
Dla każdego predykatu P:
|- [P(1) '" "k(P(k) P(k + 1))] "k(P(k))
Twierdzenie:
"k (1 + 2 + ... + k = k(k + 1) / 2)
Krok 1: Definiujemy P(k) �! 1 + 2 + ... + k = k(k + 1) / 2
Krok 2: Dowodzimy P(1): 1=1 �! P(1)
Krok 3: Dowodzimy P(k) �! P(k + 1) (dla k " N):
P(k) �!
1 + 2 + ... + k = k(k + 1) / 2 �!
1 + 2 + ... + k + (k + 1) = k(k + 1) / 2 + (k + 1) �!
1 + 2 + ... + k + (k + 1) = (k + 1) (k + 2) / 2 �!
P(k + 1)
*
Zasada indukcji nr 1
Dla dowolnej funkcji zdaniowej P(k), aby udowodnić "k(P(k))
wystarczy pokazać, że P(1) oraz że P(k) �! P(k + 1) przyjmując, że
uniwersum jest N.
Jak udowodnic twierdzenie:
Jeżeli k " N, k e" 4 to 2k e" k2
Chciałoby się przyjąć P(k) �! 2k e" k2 ale... wówczas mamy ~P(3).
Indukcja Matematyczna (4) Matematyka Dyskretna
Zasada indukcji nr 2 (w troszkę ogólniejszej wersji):
Dla dowolnej funkcji zdaniowej P(k), aby udowodnić "k e" s (P(k))
wystarczy pokazać, że P(s) oraz że
k e" s '" P(k) �! P(k + 1)
przyjmując, że uniwersum jest N.
Dowód: (korzystamy z zasdy indukcji nr 1)
Przypuśćmy, że:
(1) P(s) oraz
(2) k e" s '" P(k) �! P(k + 1).
śamy pokazać: "k e" s (P(k))
Krok 1: Niech Q(k) �! P(k) (" k < s.
Krok 2: Dowodzimy Q(1):
Gdy s = 1 to mamy Q(1) z (1) i z def. Q
Gdy s > 1 to mamy Q(1) bezp. z def. Q
Krok 3: Dowodzimy Q(k) �! Q(k + 1)
Rozpatrzmy następujące możliwe wartości k:
(1) k + 1 < s: Wówczas poprzednik i następnik Q(k) Q(k + 1) są
prawdziwe bezp. z def. Q.
(2) k + 1 = s: Wówczas z (1) następnik implikacji Q(k) Q(k + 1)
jest prawdziwy.
(3) k +1 > s: Wówczas z def. Q mamy Q(k) "! P(k) oraz Q(k + 1) "!
P(k + 1), a z (2) mamy P(k) P(k + 1) co w efekcie daje Q(k) Q(k
+ 1)
Z (1), (2), (3) otrzymujemy Q(k) �! Q(k + 1)
Stąd, na podstawie poprzedniej zasady indukcji mamy:
"k (Q(k)) �!
"k (P(k) (" k < s) �!
"k (k e" s P(k)) �!
"k e" s (P(k))
*
Indukcja Matematyczna (5) Matematyka Dyskretna
Wróćmy do naszego twierdzenia:
dowód: (z zasady indukcji nr 2)
Krok 1: Definiujemy P(k) �! 2k e" k2
Krok 2: Dowodzimy P(4): 24 = 42 �! P(4)
Krok 3: Dowodzimy P(k) �! P(k + 1) (dla k " N, k e" 4):
P(k) '" k e" 4 �!
2k e" k2 '" k e" 4 �!
(2k+1 e" k2 + k2 > k2 + 2k + 1 = (k + 1)2) '" k e" 4 �! // k > 1 + 2 �!
P(k + 1) // k2 > 2k + 1
Archipelag n wysp jest obsługiwany przez towarzystwo lotnicze w
taki sposób, że dla dowolnych dwóch wysp istnieje bezpośrednie
połączenie lotnicze ale tylko w jedną stronę. (Samolot lata z wyspy A
na wyspę B ale nie lata z B na A). Jak udowodnić, że można zwiedzić
ten archipelag odwiedzając wszystkie wyspy w taki sposób, żeby na
każdej być tylko raz?
Dowód indukcyjny ze względu na liczbę wysp.
Krok początkowy: Dla n = 1, 2 prawdziwość tezy jest oczywista.
Krok indukcyjny: Przypuśćmy, że twierdzenie jest prawdziwe dla
wszystkich k < n.
Wybierzmy dowolną wyspę A.
Niech I oznacza zbiór tych wysp, z których lata samolot do A.
Niech O oznacza zbiór tych wysp, do których lata samolot z A.
Oczywiście |I| < n oraz |O| < n.
Z zał. indukcyjnego zarówno I jak i O można zwiedzić odwiedzając
każdą wyspę tego zbioru dokładnie raz.
Ostatecznie cały archipelag można zwiedzić zwiedzając zgodnie z
powyższą metodą podarchipelag I następnie wyspę A i wreszcie
podarchipelag O.
*
Indukcja Matematyczna (6) Matematyka Dyskretna
Zasada indukcji nr 3 (w jeszcze ogólniejszej wersji):
Dla dowolnej funkcji zdaniowej P(k), aby udowodnić "k e" s (P(k))
wystarczy pokazać, że P(s) oraz że
k e" s '" "k e" r e" s (P(r)) �! P(k + 1)
przyjmując, że uniwersum jest N.
Dowód: (korzystamy z zasdy indukcji nr 2)
Przypuśćmy, że:
(1) P(s) oraz
(2) k e" s '" "k e" r e" s (P(r)) �! P(k + 1)
śamy pokazać: "k e" s (P(k))
Krok 1: Niech Q(k) �! "k e" r e" s (P(r)).
Krok 2: Dowodzimy Q(s): Q(s) jest spełnine bezpośrednio z def. Q
oraz z (1).
Krok 3: Dowodzimy k e" s '" Q(k) �! Q(k + 1):
k e" s '" Q(k) �! // z def. w kroku 1
k e" s '" "k e" r e" s (P(r)) �! // z (2)
"k e" r e" s (P(r)) '" P(k + 1) �! "k+1 e" r e" s (P(r)) �! Q(k + 1)
Zgodnie z zasadą indukcji nr 2 udowodniliśmy: "k e" s (Q(k)).
"k e" s (Q(k)) �! "k e" s ("k e" r e" s (P(r))) �! "k e" s (P(k))
*
Czy można używać indukcji do dowodzenia własności innych
obiektów niż zbiór liczb naturalnych (z ewentualnym pominięciem
pewnego przedziału {1, 2,..., k})?
Dla pewnego zbioru A chcemy udowodnić, że "x"A(P(x)). śożemy
wykorzystać mechanizm indukcji, jeżeli potrafimy znalez
ć surjekcję
f : N A oraz pokazać przez indukcję, że "n"N(Q(n)) przyjmując
Q(n) �! P(f(n)).
Indukcja Matematyczna (7) Matematyka Dyskretna
Przykład: (NP - zbiór liczb nieparzystych)
Twierdzenie "k"�P(1 + 3 + 5 + ... + k = (k + 1)2 / 4).
Dowód:
Niech P(x) �! 1 + 3 + 5 + ... + x = (x + 1)2 / 4 (dla x " NP).
Niech f(n) = 2n  1.
f jest nie tylko surjekcją ale także funkcją wzajemnie jednoznaczną
gdyż istnieje funkcja odwrotna f -1(x) = (x + 1) / 2.
Krok 1: Q(n) �! P(f(n))
Krok 2: 1 = (1 + 1)2 / 4
Krok 3: Q(n) �! 1 + 3 + 5 + ... + 2n  1 = (2n  1 + 1)2 / 4 �!
1 + 3 + 5 + ... + 2(n + 1)  1 = (2n  1 + 1)2 / 4 + 2n + 1 =
(4n2 + 8n + 4) / 4 = (2n + 2)2 / 4 = (2(n + 1)  1 + 1)2 / 4 �!
Q(n + 1)
Czy można stosować indukcję dla predykatów więcej niż jedno-
argumentowych?
Przyjmujemy X = N.
Chcemy udowodnić "k("r(P(k, r))).
Krok 1: Q(k) �! "r(P(k, r))
Krok 2: Q(1)
Krok 3: Q(k) �! Q(k + 1)
Krok 2 oznacza konieczność dowodu "r"N(P(1, r)) w tym celu też
możemy zastosować indukcję (ale nie musimy):
Krok 2.1: S(r) �! P(1, r)
Krok 2.2: S(1) // musimy wykazać prawdziwość P(1, 1)
Krok 2.3: S(r) �! S(r + 1) // P(1, r) �! P(1, r + 1)
Indukcja Matematyczna (8) Matematyka Dyskretna
Zasada indukcji nr 4 (w wersji dla dwóch zmiennych):
Dla dowolnej funkcji zdaniowej P(k, r), aby udowodnić:
"k("r(P(k, r)))
wystarczy pokazać, że P(1, 1) oraz że
P(k, r) �! [P(k + 1, r) '" P(k, r + 1)]
przyjmując, że uniwersum jest N.
Dowód:
Załóżmy:
(1) P(1, 1)
(2) P(k, r) �! [P(k + 1, r) '" P(k, r + 1)]
śamy udowodnić:"k("r(P(k, r)))
Dowód indukcyjny ze względu na k:
Krok 1: Q(k) �! "r(P(k, r))
Krok 2: Q(1):
Dowód indukcyjny ze względu na r:
Krok 2.1: T(r) �! P(1, r)
Krok 2.2: T(1): wynika bezp. z (1)
Krok 2.3: T(r) �! T(r + 1): wynika prawie bezp. z (2)
Krok 3: Q(k) �! Q(k + 1):
Z (2) mamy: P(k, r) �! P(k + 1, r) czyli
|= P(k, r) P(k + 1, r) // stosujemy prawo uogólniania
|= "r[P(k, r) P(k + 1, r)] // stosyjemy odpowiednie prawo rach. kw.
|= "r[P(k, r)] "r[P(k + 1, r)] czyli
"r[P(k, r)] �! "r[P(k + 1, r)] co kończy dodód Kroku 3.
Udowodniliśmy zatem "k(Q(k))
*
Przykład:
Udowodnić, że 3 | k3 + n3 + 2k  n dla k, n " N.
Krok 1: P(k, n) �! 3 | k3 + n3 + 2k  n
Krok 2: P(1, 1): 3 | 13 + 13 + 2�1  1 �! P(1, 1)
Indukcja Matematyczna (9) Matematyka Dyskretna
Krok 3a: P(k, n) �! P(k + 1, n):
P(k, n) �!
3 | k3 + n3 + 2k  n �!
3 | k3 + n3 + 2k  n + 3k2 + 3k + 3 �!
3 | k3 + 3k2 + 3k + 1 + n3 + 2k + 2  n �!
3 | (k + 1)3 + n3 + 2(k + 1)  n �!
P(k + 1, n)
Krok 3b: P(k, n) �! P(k, n + 1):
P(k, n) �!
3 | k3 + n3 + 2k  n �!
3 | k3 + n3 + 2k  n + 3n2 + 3n �!
3 | k3 + n3 + 3n2 + 3n + 1 + 2k + 2  n  1 �!
3 | k3 + (n + 1)3 + 2(k + 1)  (n + 1) �!
P(k, n + 1)
Indukcja Matematyczna (10) Matematyka Dyskretna
Rozważmy jeszcze raz zasadę nr 3:
Dla dowolnej funkcji zdaniowej P(k), aby udowodnić "k e" s (P(k))
wystarczy pokazać, że P(s) oraz że
k e" s '" "k e" r e" s (P(r)) �! P(k + 1)
przyjmując, że uniwersum jest N.
Z prawa konrapozycji implikację indukcyjną możemy zastąpić
formułą: ~P(k + 1) �! k < s (" "k e" r e" s (~P(r)), a dalej w oparciu o
odpowiednią tautologię rach. zd. (jaką?):
~P(k + 1) '" k e" s �! "k e" r e" s (~P(r))
dla s = 1 mamy prostszą postać: ~P(k + 1) �! "r d" k (~P(r))
Powyższa formuła pozwala na przeprowadzanie dowodów indukcyj-
nych w następującej formie:
Krok 1: Dowodzimy P(1)
Krok 2: Przypuśćmy, że k jest najmniejszą liczbą naturalną dla której
~P(k). Pokazujemy, że istnieje r < k dla którego ~P(r).
Zasada indukcji nr 5:
Dla dowolnej funkcji zdaniowej P(k), aby udowodnić "k e" s (P(k))
wystarczy pokazać, że P(s) oraz że
~P(k + 1) '" k e" s �! "k e" r e" s (~P(r))
przyjmując, że uniwersum jest N.
Indukcja Matematyczna (11) Matematyka Dyskretna
Przypuśćmy, że dla pewnej funkcji zdaniowej P(n) potrafimy pokazać
dla pewnej liczby c " N:
(1) P(1)
(2) P(n) �! P(cn)
(3) P(n) '" n > 1 �! P(n  1)
Czy na tej podstawie możemy udowodnić "n(P(n)) ?
Z zasdy indukcji (1) i (2) dają natychmiast "k(P(ck))
Dowolną liczbę n " N można przedstawić w postaci ck  r dobierając
pewne liczby naturalne k i r.
Przyjmując
ńł
P(ck - r) dla r < ck
Qk (r) �! gdzie r " N *" {0}
�ł
dla r e" ck
ół1
mamy P(ck) �! Qk(0)
A z (3) otrzymujemy Qk(r) �! Qk(r + 1)
A zatem na zasadzie indukcji mamy "re"0(Qk(r))
co z def. Qk daje "r d" c (P(ck  r))
k
Wybierając dowolne n udowodniliśmy P(n), a zatem "n(P(n)).
Indukcja Matematyczna (12) Matematyka Dyskretna
Przykład dowodu z indukcją wsteczną:
Udowodnimy, że:
x1+ ... + xn
n
x1�"�"�" xn d" dla dowolnych x1,..., xn " R+ i n " N.
n
x1+ ... + xn
�ł
Niech P(n) �! "x1,...,xn�łn x1�"�"�" xn d"
�ł �ł
�ł łł
n
Krok 1a: P(1) - oczywiste
Krok 1b: P(2) - proste przekształcenie algebraiczne
Krok 2: P(n) �! P(2n):
Niech x1,..., xn, y1,...,yn będą dowolnymi liczbami z R+
Przyjmijmy ci = (xiyi)1/2
c1+ ... + cn
P(n) �! n c1�"�"�" cn d"
n
xi + yi
P(2) �! ci d"
2
Stąd mamy:
"(x + yi )/ 2
i
x1+ ... + yn)
n
c1�"�"�" cn d"1d"id"n �! 2nx1�"�"�" yn d"
n 2n
Ponieważ x1,..., xn, y1,...,yn były wybrane dowolnie więc udowodniliś-
my P(n) �! P(2n).
Krok 3: P(n) '" n > 1 �! P(n  1):
x1+ ... + xn-1
Wybieramy x1,..., xn 1 dowolnie i przyjmujemy xn = . Po
n -1
zastosowaniu nierówności P(n) i prostych przekształceniach
algebraicznych otrzymujemy P(n  1) dla x1,..., xn 1.
Ponieważ x1,..., xn 1 były wybrane dowolnie, więc udowodnilismy, że
P(n) '" n > 1 �! P(n  1).
Indukcja Matematyczna (13) Matematyka Dyskretna
Niech f1, f2,... będzie ciągiem dowolnych funkcji takich, że fi : Ai 1
A.
Istnieje dokładnie jeden ciąg x1, x2,... taki, że xi+1 = fi+1(x1, x2,..., xi)
Dowód - natychmiast z zasady indukcji.
Taki sposób definiowania ciągu nazywać będziemy definicją reku-
definicją reku-
rencyjną.
rencyjną.
Przykłady:
x1 = a, xi+1 = bxi, dla a, b " R.
x1 = a, xi+1 = b + xi, dla a, b " R.
x1 = x2 = 1, xi+2 = xi+1 + xi
Z indukcją trzeba postępować ostrożnie:
Wszystkie konie są tego samego koloru bo:
Dla jednego konia twierdzenie zachodzi. Załóżmy, że twierdzenie
zachodzi dla każdych n koni i rozpatrzmy dowolny zbiór n + 1 koni A.
Niech Misio i Ptysio będą dowolnymi końmi z A. Powiedzmy, że
Rysio jest n + 1 koniem. Wyrzućmy na chwilę Ptysia uzyskując zbiór
n koni. A zatem Misio i Rysio są tego samego koloru. Teraz zastąpmy
Misia Ptysiem. Znów mamy n koni więc Rysio i Ptysio są tego samego
koloru. Rysio jest więc tego samego koloru co Ptysio i Misio, ale
Ptysio i Misio byli wybrani dowolnie, więc Rysio jest tego samego
koloru co wszystkie inne konie w A.
Indukcja Matematyczna (14) Matematyka Dyskretna
Indukcja a programowanie
Indukcja a programowanie
Jak dowodzić poprawności programów?
Przeważnie chcemy mieć pewność, że bezpośrednio po lub przed
wykonaniem zadanej instrukcji wartości zamiennych programu będą
przyjmowały wartości spełniające zadane warunki.
Gdyby nie pętle i rekurencja program posiadałby skończoną liczbę
scieżek obliczeń, które można by było przeanalizować jedna po
drugiej. Jak zatem dowodzić poprawności instrukcji pętli?
Ograniczmy się do pętli P(w, I): while w do I,
gdzie w jest pewnym zdaniem, a I ciągiem instrukcji programu.
Zdanie z nazwiemy niezmiennikiem pętli P wtedy i tylko wtedy gdy
prawdziwość zdania z '" w przed wykonaniem ciągu instrukcji I pętli
implikuje prawdziwość z bezpośrednio po wykonaniu I.
Przykład
x = 1;
i = 1;
while (i d" n) {
x = yx;
i += 1;
}
Niezmiennik: z �! x = yi 1
Wiemy więc, że jeżeli x = yi 1 w momencie rozpoczęcia pętli while to
także x = yi 1 po jej zakończeniu. Wystarczy zatem ustalić jaką
wartość będzie przyjmować zmienna i.
O ile tylko n e" 0, to powyższy program realizuje instrukcje:
{ i = n + 1; x = yn}