Liczby naturalne

Zasada indukcji matematycznej (zupełnej) jest jedną z metod
dowodzenia twierdzeń dotyczących liczb naturalnych.
Są to twierdzenia postaci:

nN p(n)

gdzie {p(n)}

nN

jest ciągiem zdań

Aksjomaty arytmetyki:
1. Jeden jest liczbą naturalną
2. Jeden nie jest następnikiem żadnej liczby naturalnej
3. Dla każdej liczby naturalnej n istnieje dokładnie jedna liczba

s(n), która jest
następnikiem n

4. Jeżeli k jest następnikiem n i k jest następnikiem m, to m=n
5. Zasada indukcji zupełnej

Jeżeli A jest podzbiorem zbioru liczb naturalnych N takim, że

1. 1  A

2. Dla każdej liczby naturalnej n, jeżeli n  A i m jest

następnikiem n,

to m A

to A = N.

Liczby naturalne cd.

Zdefiniujmy (indukcyjnie) operacje dodawania i mnożenia:

n+1=s(n)

n*1=n

n+s(m)=s(n+m)

n*s(m)=n*m+n

UWAGA: W przypadku zliczania od zera

n+0=n

n*0=0

UWAGA: Można wprowadzić liczby naturalne począwszy od zera

wtedy zmieni się pierwszy i drugi aksjomat

Zasada indukcji dla liczb

naturalnych

Jeśli W jest własnością określoną w zbiorze liczb naturalnych N,
spełniającą założenia:

1. 1 ma własność W (ozn. W(1))
2. dla dowolnej liczby naturalnej n, jeśli W(n), to W(n+1),

to każda liczba naturalna ma własność W.

Twierdzenie (zasada minimum)
W każdym niepustym zbiorze liczb naturalnych istnieje liczba najmniejsza

Dowód: (hip.) Niech A, A N i w A nie ma liczby najmniejszej.

1. Weźmy B = {n : 

m n

(m A)} – wszystkie liczby nie należące do A mniejsze

od każdej liczby należącej do A

1 1 B

2 Załóżmy, że n B

gdyby n+1A, to byłaby to najmniejsza liczba w A, czyli n+1A,

a zatem n+1B.

Na mocy zasady indukcji B=N. Oznacza to, że zbiór A jest pusty.

Sprzeczność z zał.

Przypomnienie - uzupełnienie

UWAGA: Zasadę minimum można wywieść z faktu, że zbiór liczb naturalnych

jest dobrze uporządkowany przez relację  (niewiększości).

Definicja

Relację binarną R określoną w zbiorze X nazywamy dobrym
porządkiem wttw R jest liniowym porządkiem oraz w dowolnym
niepustym podzbiorze zbioru X (AX) istnieje element

minimalny.

Czyli najmniejszy, bo porządek jest liniowy.

Druga zasada indukcji

matematycznej

Niech { p(n) }

nN

( p(1), p(2),.... ) będzie ciągiem zdań.

Jeżeli:
1. Zdanie p(1) jest prawdziwe
2. Jeżeli wszystkie zdania p(1),...,p(m-1) są zdaniami
prawdziwymi, to
p(m) też jest zdaniem prawdziwym
to nN p(n) jest zdaniem prawdziwym

Dowód: (hip.) nN p(n) jest fałszywe

Zasada minimum mówi, że każdy niepusty podzbiór zbioru N ma element najm.
Niech k będzie najmniejszą liczbą, dla której p(k) jest fałszywe
1. k=1, p(1) fałszywe – sprzeczność z założeniem
2. k>1, stąd k-11 i k jest najmniejszą liczbą naturalną, dla której p(k) jest fałszywe,

czyli p(1),...,p(k-1) są prawdziwe, a zatem p(k) jest prawdziwe, co jest sprzeczne
z założeniem.
UWAGA: Pierwsza zasada indukcji matematycznej zakłada, że w każdym kroku
indukcyjnym zdanie p(k) jest prawdziwe, jeśli zdanie bezpośrednio
je poprzedzające p(k-1) jest prawdziwe. Okazuje się, że możemy założyć, że
prawdziwe są wszystkie poprzedniki p(k), stąd druga zasada indukcji.

Jak stosować indukcję

matematyczną

w dowodzeniu twierdzeń

1. Sprawdzamy, czy twierdzenie jest prawdziwe dla

bazy indukcji

(n=1 lub pewnej

małej liczby naturalnej)
2. Zakładamy, że twierdzenie jest prawdziwe dla pewnej liczby

naturalnej k

(

założenie indukcyjne

). Formułujemy

tezę indukcyjną

i

dowodzimy jej

prawdziwości, tzn. dowodzimy, że z założenia indukcyjnego

wynika, że

twierdzenie jest prawdziwe dla liczby k+1 (

krok indukcyjny

).

Stąd wnioskujemy, że twierdzenie jest prawdziwe dla dowolnej

liczby naturalnej.

Przykład

Twierdzenie (pierwszy wykład)
Jeżeli X jest zbiorem n-elementowym, a Y zbiorem m-elementowym, to produkt
XY ma n*m elementów

.

Dowód:
1. Jeśli X={x}, Y={y

1

,...,y

m

}, to wszystkie elementy produktu są postaci

<x,y

1

>, <x,y

2

>,...,<x,y

m

>.

2. Załóżmy, że dla X={x

1

,...,x

n

} i Y = {y

1

,...,y

m

} produkt X



Y ma

n*m elementów.
3. Dla zbiorów X’=X {x}, Y produkt ma (n+1)*m elementów.

Produkt X`Y składa się z par, w których występuje x i z par, w których x nie

występuje. Par pierwszego rodzaju jest dokładnie m, a par drugiego rodzaju jest tyle,
ile w produkcie X  Y, czyli n*m. Zatem łącznie mamy (n+1)*m par.

Rekurencja – kilka słów

Definicja
Rekurencja jest to metoda definiowania za pomocą indukcji.

Mówimy, że ciąg jest zdefiniowany rekurencyjnie, jeśli:
1. Określony jest pewien skończony zbiór wyrazów ciągu

(zazwyczaj pierwszy wyraz lub kilka pierwszych wyrazów).

2. Pozostałe wyrazy ciągu zdefiniowane są za pomocą

poprzednich wyrazów ciągu (wzór, który je definiuje,
nazywamy wzorem rekurencyjnym).

Przykłady:
1. Silnia(0)=1 Silnia(n)=Silnia(n-1)*n
( inaczej a1=1 an=n*a(n-1) dla n>1 )

2. Ciąg Fibonacciego F(0)=1 F(1)=1 F(n)=F(n-1)+F(n-2) dla n>1
( inaczej a1=a2=1 an=a(n-1)+a(n-2) dla n>2 )

Niezmiennik pętli

Rozpatrujemy pętlę (**)
dopóki g wykonuj

g – warunek dozoru pętli

s

s – treść (instrukcja) pętli
(treść wykonywana iteracyjnie)

koniec

Jeśli w pewnej iteracji warunek dozoru nie jest spełniony, to
opuszczamy pętlę.

Definicja
Zdanie p jest niezmiennikiem pętli (**) wtedy, gdy spełnia ono
następujący warunek:

- jeśli zdania p i g (warunek dozoru) są prawdziwe zanim
wykonamy krok s, to

zdanie p będzie prawdziwe po wykonaniu s

Niezmiennik pętli - cd

Przykłady: Rozpatrzmy algorytm dzielenia dwóch liczb całkowitych m>0, n0

(dane wejściowe), w wyniku którego otrzymujemy liczby całkowite

q i r takie, że q*n+r=m oraz 0r<n (dane wyjściowe)

początek
q:=0
r:=m
dopóki rn wykonuj

q:=q+1
r:=r-n

koniec

Niezmiennikiem pętli jest tutaj: „q*n+r=m i r0”

Niezmiennik gwarantuje, że dla powyższego algorytmu (pętla się
kończy (r:=r-n)) otrzymamy poprawne wyniki dla każdych liczb
całkowitych.

Zasada niezmiennika

pętli

Twierdzenie (Zasada niezmiennika)
Jeśli p jest niezmiennikiem pętli (**) oraz zdanie p jest prawdziwe,
kiedy wchodzimy w pętlę, to zdanie p jest prawdziwe po każdej iteracji pętli.
Jeśli pętla kończy się, to po jej zakończeniu zdanie p jest prawdziwe, a zdanie
g (warunek dozoru) jest fałszywe.

Przykłady:Algorytm Euklidesa NWD(m,n) (mn – dane wejściowe, x – NWD(m,n))

początek
x:=m; y := n;
dopóki y  0 wykonuj

d:=x
x:=y; y:=d mod y
koniec

Niezmiennikiem pętli jest tutaj: NWD(m,n)=NWD(n, m mod n)

Korzystamy właśnie z takiego stwierdzenia NWD(m,n)=NWD(n, m
mod n)

x=45 y=12
x=12 y=9

d=45

x=9

y=3
d=12

x=3

y=0
d=9

Algorytm Euklidesa

inaczej ?

Przykłady: Algorytm Euklidesa NWD(m,n) (m,n – dane wejściowe,

x=y=NWD(m,n))

początek
x:=m; y := n;
dopóki x  y wykonuj

jeśli x>y to x:=x-y
wpp. y:=y-x
koniec

x=45 y=12
x=33 y=12
x=21 y=12
x=9

y=12

x=9

y=3

x=6

y=3

x=3

y=3

Niezmiennikiem pętli jest tutaj: NWD(m,n)=NWD(x, y)