142255620076615650228811902819 n

V: e E\{y} (r.y) € R.

Viey\(y> (r,y)eR.

V: e />,()'. R)\{y\ (y,:) e R V : e ł\{y) (y, -) ^{€ R}-Vre UY,R)\{y) (r.y) e R

Elementy € ł'jest elementem największym zbioru ł'jeśli: }'£, zbiór elementów największych zbioru Y w [B. R)

Elementy e B jest ograniczeniem górny m zbioru Yjeśli: //,(}’. R) - zbiór ograniczeń górnych zbioru )' w (B. R) Elementy e /*()', R) jest kresem góm> m zbioru Yjeśli: supR Y - zbiór kresów górnych zbioru Y w (B. R) Elementy e B jest ograniczeniem dolnym zbioru )'jeśli: lj(Y. R) - zbiór ograniczeń dolnych zbioru )’w (B. R) Elementy e lj(Y, /?) jest kresem dolnym zbioru ł'jeśli: inf_R Y - zbiór kresów dolnych zbioru Y w (B. R)

Indukcja matematyczna

Metoda indukcii matematycznej ma zastosowanie w suuactach. w których:

1.    Znamy na początku odpowiedź.

2.    Wiemy, jak wyprowadzić odpowiedź w danym kroku z odpowiedzi w poprzednim kroku.

3.    Odgadujemy ogólne rozwiązanie.

Każdy niepusty podzbiór zbioru N ma element najmniejszy.

Zasada dobrego uporządkowania

Twierdzenie o niezmiennikach pętli

Przypuśćmy, że p jest niezmiennikiem pętli „dopóki g, wykonuj S'' oraz. że z.danie p jest prawdziwe, kiedy wchodzimy w pętlę. Wtedy 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 jest fałszywe.

Twierdzenie 1

Dla danych liczb całkowitych min. gdzie m > 0 i n. > 0. algorytm dzielenia konstruuje liczby całkowite q i r takie, że m = q - n — r oraz 0 < r < n.

srr. 12/15