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)