Indukcja matematyczna i 

niezmienniki pętli 

wykładowca: dr Magdalena Kacprzak 
 

Materiały pomocnicze do wykładu 

 

Charakteryzacja zbioru 

liczb naturalnych 

Arytmetyka liczb naturalnych 

Jedną z najważniejszych teorii matematycznych  
jest arytmetyka liczb naturalnych. Elementarna  
arytmetyka liczb naturalnych używa języka,  
w którym oprócz stałej 0 występuje  
jednoargumentowa funkcja  

suc  

nazywana następnikiem, i relacja równości.  

Aksjomaty Peano 

 
Aksjomaty tej teorii, a więc podstawowe prawa  
rządzące liczbami naturalnymi, sformułował  
Peano.  
 

Aksjomaty Peano 

Aksjomaty Peano liczb naturalnych 
Ax1. 

Zero

 jest liczbą naturalną. 

Ax2. Dla każdej liczby naturalnej n istnieje 

dokładnie jedna liczba naturalna 

suc(n)

, która 

jest następnikiem n. 

Ax3. Zero 

nie

 jest następnikiem żadnej liczby 

naturalnej. 

Ax4. Jeżeli k jest następnikiem liczby n,  
 

k=suc(n), i k jest następnikiem liczby m,  

 

k=suc(m), to n = m. 

Aksjomaty Peano c.d. 

Ax5. Zasada indukcji matematycznej:  
 
Jeżeli A jest podzbiorem zbioru liczb naturalnych  
N takim, że spełnione są warunki (1), (2):  
 

(1)

0



A,  

 

(2)

dla każdej liczby naturalnej n,  

 

jeżeli n



A i m jest następnikiem n, to m



A,  

 

to A=N. 

Intuicje 

Aksjomat piąty mówi jak można zbudować zbiór  
liczb naturalnych z zera przez sukcesywne  
zastosowanie funkcji następnika: każda liczba  
naturalna n jest otrzymana z zera przez n-krotne  
wykonanie operacji następnika,  
 

1=

df

 suc(0)  

2 =

 df

 suc(suc(0))  

3 =

 df

 suc(suc(suc(0)))  

...........  

Intuicje 

Fakt ten wielokrotnie, i często nieświadomie,  
wykorzystuje się w programowaniu z użyciem  
pętli "while" stwierdzając, że program  
 

{x:= 0; while x < y do x := x+1 od }  

 
nie zapętla się dla wszystkich wartości  
naturalnych zmiennej y. 

Przykład 

Twierdzenie:  

Każda liczba postaci n

5

-n dla n



 N jest podzielna  

przez 5. 
 

Dowód.

 Niech  

A={n



N: (n

5

 - n) mod 5 = 0}.  

Udowodnimy, że N=A. 
 

1.

0



A, ponieważ 0

5

 - 0 = 0.  

Przykład 

2.

Weźmy jakąś ustaloną liczbę n należącą do A. Wynika 

stąd oczywiście, że dla pewnego naturalnego k, mamy  

n

5

 - n = 5k.  

 

Wtedy jednak (n+1)

5

 - (n+1) jest też podzielne przez 5, bo 

(n+1)

5

-(n+1) =  

n

5

+5n

4

+10n

3 

+10n

2

+5n +1- n -1 =  

n

5 

- n + 5(n

4

 +2n

3 

+2n

2 

+n) =  

5(k+n

4

 +2n

3 

+2n

2 

+n) . 

 
Stąd n+1 



 A. 

Przykład 

 
Ponieważ oba założenia zasady indukcji  
matematycznej zostały spełnione, zatem możemy  
wywnioskować, że A=N. Oznacza to, że dla  
dowolnej liczby naturalnej n, liczba n

5

-n jest  

podzielna przez 5.  

 

Zasada minimum 

Zasada minimum 

Z zasady indukcji matematycznej wynika  
natychmiast następujące twierdzenie zwane  
"zasadą minimum". 
 

Twierdzenie

 

W każdym niepustym zbiorze liczb naturalnych  
istnieje liczba najmniejsza. 
 

Dowód zasady minimum 

Niech A 



 



, A 



 N i przypuśćmy, że w A nie ma  

liczby najmniejszej (tzn. A nie ma elementu  
pierwszego). Oznacza to w szczególności, że 0



A.  

Rozważmy zbiór B takich liczb naturalnych n, że  
ani n ani żadna liczba mniejsza od n nie należy do  
A,  

B = {n : (

"

 m



 n) m



A}.  

Udowodnimy, że wobec przyjętych założeń, musi  
być B=N. Dowód tego faktu przeprowadzimy  
wykorzystując zasadę indukcji matematycznej.  

Dowód zasady minimum 

 

(1)

Ponieważ 0 nie należy do A, to z definicji 

zbioru B wynika, że 0



B. 

 

(2)

Załóżmy, że dla pewnego n, n



B. 

Udowodnimy, że liczba n+1 należy do B. 

Dowód  zasady minimum 

Z założenia indukcyjnego wynika, że wszystkie liczby  
mniejsze od n oraz samo n nie należą do zbioru A. Gdyby  
więc (n+1)



 A, to byłby to element najmniejszy w A, co nie  

jest możliwe wobec przyjętego w A założenia. Zatem  
(n+1)



A, a stąd (n+1)



B. 

  

 

Ponieważ wykazaliśmy, że oba założenia zasady indukcji są  
spełnione, to na mocy tejże zasady indukcji wszystkie liczby  
naturalne należą do B.  

Dowód zasady minimum 

 
Skoro jednak udowodniliśmy, że N=B, to zbiór A  
musi być pusty, wbrew założeniu. Sprzeczność ta  
dowodzi, że nie można znaleźć takiego niepustego  
podzbioru A zbioru liczb naturalnych, który nie  
miałby elementu pierwszego, a to oznacza, że  
każdy niepusty podzbiór N ma element pierwszy.  

Przykład 

Udowodnimy, że  

{n



N : 3|(n

3

-n)} = N.  

 
W przedstawionym dowodzie "nie wprost" wykorzystamy  
zasadę minimum. Niech  

A= {n



N : 3|(n

3

-n)}.  

Przypuśćmy, że A 



 N. Wtedy na mocy zasady minimum,  

w zbiorze N\A istnieje element najmniejszy. Ponieważ 3|0,  
więc 0



A, a tym samym 0 nie jest elementem najmniejszym  

w N\A. Niech więc elementem najmniejszym w N\A będzie  
jakaś liczba k>0. Jako element zbioru N\A, k nie jest  
dzielnikiem (k

3

-k).  

Przykład 

Rozważmy liczbę k-1. Mamy (k-1)



N oraz 

(k-1)

 3

 -(k-1) =  

k

3

-3k

2

 + 3k -1 -k +1 =  

(k

3

-k) -3k(k-1). 

Ponieważ (k

3

-k) nie dzieli się całkowicie przez 3,  

a 3k(k-1) jest wielokrotnością 3, zatem liczba  
(k-1)

 3

 -(k-1) nie dzieli się przez 3.  

Wynika stąd, że (k-1)



N\A, co przeczy  

założeniu, że k było liczbą najmniejszą w zbiorze  
N\A. W konsekwencji musi być A=N.  

 

 

Zasada indukcji –  

różne sformułowania 

Zasada indukcji matematycznej 1 

Jeżeli 
(1) W(0), tzn. 0 ma własność W, oraz 
 
(2) dla dowolnej liczby naturalnej k,  
 

jeśli W(k), to W(k+1),  

 

 

to dla każdej liczby naturalnej n, W(n)  
(tzn. każda liczba naturalna ma własność W). 

Przykład 

Lemat:  
 

Liczba wszystkich podzbiorów zbioru n  
elementowego wynosi 2

n

, czyli dla  

dowolnego zbioru X, jeśli |X| = n,  
to |P(X)| = 2

n

. 

 

Dowód lematu 

Oznaczmy przez W zdanie wyrażające  
własność liczb naturalnych taką, że  
 

W(n) wttw liczba podzbiorów zbioru n 

elementowego wynosi 2

n

. 

Dowód lematu 

Baza indukcji.  
 
Ponieważ zbiór pusty ma dokładnie jeden  
podzbiór, zatem jeśli |X| = 0,  
to |P(X)|= 1=2

0

.  

 
Wynika stąd, że liczba 0 ma własność W. 

Dowód lematu 

Założenie indukcyjne.  
 
Załóżmy, że wszystkie zbiory  
k elementowe mają własność W(k), tzn.  
liczba wszystkich podzbiorów zbioru  
k-elementowego wynosi 2

k

.  

Dowód lematu 

Teza indukcyjna.  
 
Będziemy dowodzili, że zbiór  
(k+1)-elementowy ma też własność W.  

Dowód lematu 

Dowód tezy indukcyjnej.  
 
Rozważmy zbiór (k+1)-elementowy X,  

X={x

1

,x

2

,..., x

k

,x

k+1

}.  

Podzielmy wszystkie podzbiory zbioru X na dwie  
kategorie: 
-  Podzbiory  zbioru  X,  w  których  nie  występuje 

element x

k+1

, 

-  Podzbiory  zbioru  X,  w  których  występuje 

element x

k+1. 

 

Dowód lematu 

 
Podzbiory pierwszej kategorii są to  
wszystkie podzbiory zbioru  
k-elementowego, więc na mocy  
założenia indukcyjnego jest ich 2

k

.  

Dowód lematu 

Podzbiory drugiej kategorii otrzymujemy  
biorąc jakikolwiek podzbiór A zbioru  
k-elementowego X\{x

 k+1

}, a następnie  

dołączając element x

k+1

.  

Takich podzbiorów, znów na mocy  
założenia indukcyjnego jest 2

k

.  

 
Razem 2

k

 + 2

k

 = 2

k+1

 podzbiorów. Czyli  

własność W jest prawdziwa dla k+1. 

Dowód lematu 

 
Na mocy zasady indukcji możemy teraz  
wyciągnąć wniosek, że zdanie W(n) jest  
prawdziwe dla wszystkich liczb  
naturalnych. 

Zasada indukcji matematycznej 2 

  

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

1.

0



A, oraz 

 

2.

dla każdej liczby n, jeśli k



A dla wszystkich 

k<n+1, to n+1



A,  

 

to A=N. 

Przykład 

Lemat: 

 

Udowodnić, wykorzystując jedną z postaci zasady  
indukcji matematycznej, że dla dowolnego  
a>-1 i dla dowolnej liczby naturalnej n,  

(1+a)

n

 



 1 + na.  

Dowód lematu 

Niech W(n) oznacza zdanie  

(1+a)

n

 



 1+ na. 

 
Baza indukcji:  
 
Ponieważ (1+a)

0

 



 1, zatem zachodzi  

W(0). 

Dowód lematu 

Założenie indukcyjne:  
Załóżmy, W(k) dla pewnego k,  
tzn. mamy (1+a)

k

 



 1+ka. 

 
Teza: W(k+1) jest zdaniem  
prawdziwym, tzn.  

(1+a)

k+1

 



 1+(k+1)a. 

Dowód lematu 

Dowód tezy:  
(1+a)

k+1

=(1+a)

k

(1+a).  

 
Wykorzystamy teraz założenie indukcyjne i  
otrzymamy  

(1+a)

k+1

 



(1+ ka)(1+a) 



1+ka+a+kaa 



 1+ (k+1)a + ka

2

.  

Dowód lematu 

Ponieważ ka

2



0, zatem ostatecznie  

(1+a)

k+1

 



 1+(k+1)a.  

Czyli prawdziwe jest zdanie W(k+1).  
 
Ponieważ oba założenia zasady indukcji  
matematycznej są spełnione, zatem  
wnioskujemy, że W(n) jest prawdziwe dla  
wszystkich liczb naturalnych n. 

Zasada indukcji dla liczb 

całkowitych 

 

Niech m będzie liczbą całkowitą oraz niech 

a

(n)  

będzie zdaniem określonym na zbiorze  

{n



Z : n



 m}.  

Jeśli  

1.

zdanie 

a

 (m) jest prawdziwe, oraz  

2.

jeśli wszystkie zdania 

a

(m), 

a

(m+1),..., 

a

(k-1) 

dla  pewnego  k>m  są  prawdziwe,  to 

a

(k)  też 

jest zdaniem prawdziwym,  

to 

a

(n) jest zdaniem prawdziwym dla dowolnych  

liczb całkowitych n 



 m. 

Zasada skończonej indukcji 

Niech m i k będą liczbami naturalnymi oraz niech  

a

(n) będzie zdaniem wyrażającym pewne  

własności liczb naturalnych m



 n



 k. Jeśli  

1.

zdanie 

a

(m) jest prawdziwe, oraz  

2.

jeśli z prawdziwości zdania 

a

(i) dla pewnego 

m



 i< k wynika, że zdanie 

a

(i+1) też jest 

prawdzie,  

to 

a

(n) jest zdaniem prawdziwym dla dowolnych  

n 



 m i n



 k. 

 

 

Definicje indukcyjne 

Ciąg nieskończony 

Ciąg nieskończony jest to, jak wiadomo  
funkcja całkowita określona na zbiorze liczb  
naturalnych N.  
Jednym z wygodnych sposobów określania  
wyrazów ciągu jest 

definicja indukcyjna.  

Ten sposób definiowania polega na 

określeniu  

pierwszego wyrazu

 ciągu (lub kilku pierwszych  

wyrazów) np. a

0

, i 

podaniu metody konstrukcji  

wyrazu (n+1)-go

 w zależności od wyrazu n-tego  

lub innych wyrazów już zdefiniowanych. 

Ciąg nieskończony 

Przyjmijmy następującą definicję ciągu (a

i

)

i



N

: 

a

0 

= 1, a

n+1

 = a

n

 + 2  

dla wszystkich n 



 0. 

Łatwo wyliczyć, że  

a

1 

= a

0

 + 2 = 1+2 = 3, a

2 

= a

1

 +2 = 5 itd.  

Przyglądając się bliżej tym definicjom zauważymy,  
że  
a

1 

= a

0

 + 2 = 1+ 1



2 ,  

a

2 

= 1 +2



2 = 5,  

a

3 

= 1 +2



2 +2 = 1 +3



2. 

Ciąg nieskończony 

Domyślamy się, że  

a

k 

= 1+ k



2  

dla wszystkich k>0.  
Stosując zasadę indukcji matematycznej  
możemy pokazać, że a

k 

= 1+ 2k dla wszystkich k. 

Rzeczywiście, dla k=0 otrzymujemy a

0 

= 1.  

Natomiast krok indukcyjny wynika z indukcyjnej  
definicji ciągu, założenia indukcyjnego dla k i  
prostego przekształcenia wzoru:  

a

k+1 

= a

k

 + 2 = (1+ 2k) + 2 = 1+ 2(k+1). 

 

 

 

Niezmienniki 

Definicja 

Powiemy, że zdanie 

a

 jest niezmiennikiem  

pętli postaci while 

g

 do I od, gdzie 

g

 jest  

warunkiem, a I treścią pętli, jeśli dla  
każdej iteracji tej pętli z tego, że warunki 

g

  

i 

a

 są spełnione przed wykonaniem treści  

pętli I, wynika że 

a

 jest prawdziwe po jej  

wykonaniu. 

Przykład – algorytm Euklidesa 

NWD(n,m)  (n,m 



) 

  

{x:=n; y := m; 

while x 



 y  

 

do  

  if x>y then  

   

x := x-y  

  else  

   

y:=y-x  

  fi  

od;  

return y;} 

 

Przykład – algorytm Euklidesa 

Niezmiennikiem pętli w tym algorytmie jest  
formuła  

nwd(x,y)=nwd(n,m).  

 
Rzeczywiście, załóżmy że x 



 y i formuła  

nwd(x,y)= nwd(n,m) jest prawdziwa  
w chwili wejścia do pętli while.  

Przykład – algorytm Euklidesa 

Lemat: Jeśli x>y, to nwd(x-y,y)=nwd(x,y).  
 
Wykonując jedyną przewidzianą w tym przypadku  
instrukcję  

x := x-y,  

spowodujemy (nową wartością x jest stara  
wartość x-y), że na nowo spełniona jest równość  
nwd(x,y)=nwd(n,m).  

Przykład – algorytm Euklidesa 

Analogicznie w drugim przypadku. Zatem,  
po wykonaniu instrukcji "if" nadal jest  
spełniona formuła  
 

nwd(x,y)=nwd(n,m). 

Przykład – algorytm Euklidesa 

Zakończenie całego procesu nastąpi wówczas, gdy  
x=y. Stosując skończoną zasadę indukcji  
matematycznej, skoro  

nwd(x,y)=nwd(n,m)  

jest prawdziwa tuż przed wykonaniem pętli  
"while" i dla każdej iteracji z prawdziwości tej  
formuły przed wykonaniem instrukcji "if" wynika  
jej prawdziwość po wykonaniu instrukcji "if", to  

nwd(x,y)=nwd(n,m)  

jest też prawdziwa po wyjściu z pętli "while".  
Ale wtedy nwd(n,m)=nwd(x,y)= nwd(y,y)=y.  

Przykład – algorytm Euklidesa 

 
Wynika stąd, że wyliczona przez procedurę  
wartość jest rzeczywiście największym  
wspólnym dzielnikiem liczb n i m.  
 

Przykład – algorytm Euklidesa 

Pozostał jeszcze jeden problem, czy  
ten algorytm kiedykolwiek doprowadzi do  
sytuacji, w której  

x=y.  

 
Czy pętla "while" zatrzyma się  
kiedykolwiek?  

Przykład – algorytm Euklidesa 

Tutaj znów przychodzi nam z pomocą indukcja  
matematyczna. Zauważmy, że jeśli wartości x i y  
kolejno uzyskiwane w czasie działania algorytmu  
zapiszemy jako kolejne pozycje ciągu  
(x

1

,y

1

), (x

2

,y

2

),..., to iloczyn  

(x

i

y

i

)  

tworzy ciąg malejący.  

Przykład – algorytm Euklidesa 

Ponieważ jest to ciąg liczb naturalnych,  
zatem na mocy zasady minimum nie może  
być ciągiem nieskończonym.  
Istnieje więc taka iteracja, w której  

x

i

=y

i

,  

czyli algorytm zatrzyma się. 

Lemat 

 
Jeśli zdanie 

a

 jest prawdziwe przed  

wykonaniem instrukcji "while" i jest  
niezmiennikiem tej pętli, to po wykonaniu  
instrukcji "while" jest prawdziwe zdanie  

(

ag

.