sciaga dyskretnaaa, STUDIA, Matematyka dyskretna

Twoim problemem jest to, że powszechną NICOŚĆ mylisz z osobistą PUSTKĄ

Indukcja matematyczna :metoda dowodzenia twierdzeń; zazwyczaj twierdzenia te dotyczą liczb naturalnych, ale nie tylko; poprawność jej wynika z dobrego uporządkowania liczb naturalnych (czyli z zasady minimum)

Zasada Minimum (ZMin): Dowolny niepusty podzbiór S zbioru liczb naturalnych N ma w sobie liczbę najmniejszą

Przykład 1 (Francesco Maurolio - 1575) Suma początkowych n liczb nieparzystych wynosi n do kwadratu. 1 + 3 + 5 + … + (2n-1)=n^2 Przeprowadzone rozumowanie wykazuje, że Jeśli Z jest jakimś zbiorem liczb naturalnych, w którym jest zero oraz Z wraz z każdą liczbą naturalną k zawiera również kolejną liczbę k+1

(tzn. dla każdego k należącego do Z zachodzi, że k+1 należy do Z to wówczas Z musi zawierać wszystkie liczby naturalne, tzn Z=N.

Przykład 2 0 + 1 + 2 + … + n = n(n+1)/2 dla n >= 0

Przykład 3 0^2 + 1^2 + 2^2 +3^2 + … +(n-1)^2 +n^2 = n(n+1)(2n+1)/6, Czasami jest tak, że pewna własność nie dotyczy wszystkich liczb naturalnych, ale prawie wszystkich (tzn. wszystkich poza być może pewną skończoną liczbą wartości początkowych.

Zasada Indukcji Matematycznej (ZIM) Jeżeli Z zawiera się w zbiorze liczb naturalnych N :w którymko należy do Z oraz Z wraz z każdą liczbą naturalną k >= ko zawiera również kolejną liczbę k+1 (tzn. dla każdego k >= ko zachodzi, że jeśli k należy do Z , to k+1 należy do Z), to zbiór Z zawiera wszystkie liczby naturalne n >= ko (tzn. N – {0,1,...,ko-1} zawiera się w Z).

Pierwszy warunek nazywamy bazą indukcji (krok podstawowy).

W drugim warunku najpierw dokonujemy założenia indukcyjnego (o tym, że k należy do Z),a następnie wykonujemy krok indukcyjny dowodząc, że k+1 należy do Z.

Przykład 4.n^2 < 2^n dla n >= 5

Przykład 5.Dla dowolnej liczby rzeczywistej a >= -1 oraz dowolnego n należącego do N zachodzi(1+a)^n >= 1+ n*a

Przykład 6.O ile tylko n >= 2, to liczba postaci 2^(2^n) ma na końcu w zapisie dziesiętnym cyfrę 6, tzn. 2^(2^n) = 10x +6 dla pewnej liczby naturalnej x.

Zasada Indukcji Zupełnej (ZIZ) Jeżeli Z jest jakimś zbiorem liczb naturalnych , który wraz z każdym początkowym fragmentem zbioru N postaci {0,1,...,k-1} zawiera

również kolejną liczbę k (tzn. dla każdego k należącego do N zachodzi:jeśli (dla każdego l<k jest tak, że l należy do Z), to k+1 należy do Z to Z zawiera wszystkie liczby naturalne (Z=N). Zauważmy, że nie ma tu wyróżnionego kroku bazowego (ukryty jest on w warunku dla k=0, bo poprzednik implikacji jest trywialnie spełniony).

Przykład 7. Mamy prostokątną czekoladę złożoną z K=a*b (a,b > 0) kwadratowych kawałków. Wykonujemy cięcia wzdłuż którejś z linii pomiędzy kawałkami.

Ile razy trzeba ułamać czekoladę, by rozdzielić wszystkie kwadraciki.

Zasada Maksimum (ZMax) Dowolny niepusty i ograniczony od góry podzbiór S zbioru liczb naturalnych ma w sobie liczbę największą Twierdzenie 1

Następujące zasady są równowazne:Zmin, ZIZ, ZIM, ZMax. a) ZMin implikuje ZIZ b) ZIZ implikuje ZIM c) ZIM implikuje Zmax d) ZMax implikuje ZMin

Metoda indukcji matematycznej ma zastosowanie w sytuacjach następujących: znamy na początku odpowiedź; wiemy jak wyprowadzić odpowiedź w danym kroku z odpowiedzi w poprzednim kroku; odgadujemy ogólne rozwiązanie.

Niezmiennik pętli (używany do projektowania algorytmów i dowodzenia ich poprawności)

Zdanie p jest niezmiennikiem pętli dopóki q, wykonuj S wtedy, gdy spełnia ono następujący warunek: jeśli zdania p i q są prawdziwe, zanim wykonamy krok S, to zdanie p będzie prawdziwe po wykonaniu S.

Twierdzenie o niezmiennikach pętli Załóżmy, że p jest niezmiennikiem pętli „dopuki q, wykonuj S” oraz zdanie p jest prawdziwe kiedy wchodzimy do pętli. Wówczas zdanie p jest prawdziwe po każdej iteracji pętli. Jeśli pętla kończy się, to po jej zakończeniu zadanie p jest prawdziwe, a zdanie q jest fałszywe.

Przykład (algorytm dzielenia)

{Dane: liczby całkowite m>=0 i n>0} {Wyniki: liczby całkowite q i r takie, że q*n + r = m oraz 0 <= r < n} początek q:=0 r:=m {niezmiennik pętli: q*n + r = m oraz r >= 0} dopóki r>=n, wykonuj q:=q+1 r:=r-n koniec

Dowód.

1. Zdanie „ q*n + r = m oraz r >= 0” jest prawdziwe przed wejściem w pętlę

2. Zakładamy, że zdanie „ q*n + r = m oraz r >= 0” prawdziwe w pewnym kroku iteracji

3. Dowieść można, że po kolejnej iteracji zdanie „ q'*n + r' = m oraz r'>= 0” też jest prawdziwe

q'*n + r' = (q+1)*n + (r - n) = q*n + n + r – n = q*n +r =m

r' = r – n >= n-n = 0

Powołujemy się na twierdzenie o niezmiennikach pętli i otrzymujemy:

po zakończeniu pętli zdanie q*n + r = m oraz zdanie r >= 0 są prawdziwe, a zdanie r >=n jest fałszywe czyli r<n.

Funkcja o dziedzinie X i przeciwdziedzinie Y to dowolna relacja f zawarta w X x Y (f: X → Y) taka, że:każdy element dziedziny ma jakąś wartość przypisaną funkcją f

∏ (x ε X) ∑ (y ε Y) ( f(x)=y) Taka wartość jest co najwyżej jedna ∏ (x ε X) ∏ (y1, y2 ε Y) ( jeżeli f(x)=y1 oraz f(x)=y2, to y1=y2)

Surjekcja (funkacja „na”) to funkcja f: X → Y spełniająca warunek: cała przeciwdziedzina jest wykorzystana tzn. każdy jej element jest wartością funkcji dla jakiegoś elementu dziedziny ∏ (y ε Y) ∑ (x ε X) ( f(x)=y)

Injekcja (funkcja rożnowartościowa, 1-1) jeżeli różnym elementom dziedziny przyporządkowuje różne elementy przeciwdziedziny ∏ (x1, x2 ε X) ( jeżeli x1 ≠ x2, to f(x1) ≠ f(x2))

Bijekcja, to funkcja, która jest jednocześnie surjekcją i injekcją.

Funkcja odwrotna do funkcji f: X → Y, jest to funkcja f-1 taka, że ; każdy element dziedziny f-1 ma przypisaną jakąś wartość, co oznacza, że sama funkcja f wyczerpuje wszystkie elementy przeciwdziedziny, a zatem jest surjekcją ;f-1 ma przypisywać dokładnie jeden taki element, czyli każdy element z Y jest przypisany (przez f) jednemu elementowi z X, a zatem f musi być injekcją A zatem: funkcja posiada funkcję odwrotną wtw gdy jest bijekcją.

Złożenie funkcji f: X → Y i funkcji g: Y → Z to funkcja gf:X → Z określona dla wszystkich argumentów x ε X jako (gf(x)=g(f(x)).

Złożenie gf i fg to na ogół różne funkcje.

Gdy f:X → Y jest bijekcją to istnieje funkcja odwrotna f-1: Y → X i (f-1f):X → X (identyczność na zbiorze X i (f-1f)(x) = (f-1(f(x)) = x. Dla h:X → Y, g:Y → Z i f:Z → W zachodzi f(gh)=(fg)h.

ZLICZANIE ZBIORÓW Niech: Z0=zbiór pusty Z1={0} Z2={0,1} Z3={0,1,2} . . . Zk={0,1,2, . . . , k-1} Gdy m<n, to nie istnieje injekcja z Zn w Zm.

Zbiór X skończony to zbiór bijektywny z pewnym zbiorem Zn (f:Zn → X).

Liczba elementów skończonego zbioru X, to jedyna liczba naturalna n taka, że istnieje bijekcja z Zn w X i oznaczamy ją przez |X|.

Np. |Zn|=n; |Z0|=0

Zbiór X jest nieskończony wtw istnieje injekcja z N w X.

Zbiór przeliczalny to zbiór skończony lub bijektywny z N (f: N → X).

Zasada Szufladkowa DirichletaJeśli n obiektów jest rozmieszczonych w m szufladach i n>m, to istnieje szuflada z przynajmniej dwoma obiektami.

Dowód. Zbiór obiektów jest bijektywny ze zbiorem Zn, a zbiór szuflad ze zbiorem Zm. Rozmieszczenie obiektów w szufladach to określenie funkcji z Zn w Zm.

Ponieważ n>m to ta funkcja nie jest injekcją (1-1), a zatem lokuje co najmniej dwa obiekty w tej samej szufladzie.

Przykład. *W grupie 13 osób muszą być co najmniej dwie, które urodziły się w tym samym miesiącu. *Pewna grupa osób wita się podając sobie ręce. Nikt nie wita się z samym sobą i żadna para osób nie wita się podwójnie. Czy muszą być dwie osoby, które witały taką samą liczbę osób? *Wybierzmy dowolnie 10 różnych liczb naturalnych a1,a2,...,a10 spośród 1,2,..,100. W zbiorze { a1,a2,...,a10} można wybrać dwa rozłączne podzbiory, dające tę samą sumę. (max suma 91 + … + 100 =955; 1024 podzbiorów 10-elementowego zbioru; zatem dawa o tej samej sumie)

Uogólniona Zasada Szufladkowa Jeśli m obiektów rozmieszczonych jest w n szufladach i m>n*r, dla pewnego naturalnego r, to istnieje szufladka z co najmniej r+1 obiektami.(jeżeli każda szuflada ma co najwyżej r obiektów i n szuflad jest, to w sumie jest co najwyżej n*r obiektów)

Zasada mnożenia Dla skończonych zbiorów X,Y zachodzi |X x Y| = |X| * |Y|.

Dowód. Pokazujemy, że |Zm x Zn| = m*n. Pokazujemy, ze funkcja f: Zm x Zn → Zmn, gdzie f(i,j)=i*n+j ε Zmn (gdy odpowiednie i,j) jest bijekcją.

Założenie: f(i,j) = f(i',j') czyli i*n+j = i'*n +j'. Założenie i<=i'. Wówczas (i' – i)n =j-j'.

Lewa strona: wielokrotność n, prawa leży w zbiorze {-n+1, …, n-1}, gdyż j,j' ε Zn.

0 jedyna wielokrotność w zbiorze tym, to i'-i=0 i j-j'=0, co dowodzi injektywności f.

Surjektywność. Niech y ε Zmn, i największa liczba taka, że in<y.

Wówczas y<(i+1)n, a zatem istnieje j ε {0, …, n-1} takie, że y=in+j=f(i,j).

Zalożenie, |X|=m i |Y|=n. Wówczas |X x Y| = |Zm x Zn|= m*n = |X|*|Y|.

Przykład. Turniej rycerzy z bractwa czerwonych (12 rycerzy) i niebieskich (15). Ile różnych indywidualnych pojedynków może być stoczonych, jeśli nie walczą z rycerzami z tego samego bractwa.C, N, pojedynek, to uporządkowana para (c,n), gdzie c ε C, n ε N.,|C x N| = |C| * |N| = 12 * 15 = 300

Zasada dodawania(a) Dla skończonych i rozłącznych zbiorów A i B mamy: |A υ B| = |A| + |B|.(b) Dla skończonych zbiorów mamy: |A υ B| = |A| + |B| - |A ∩ B|.

Dowód.(a) Niech liczności zbiorów |A|=m , |B|=n będą poświadczone bijekcjami f:Zm → A i g:Zn → B. Wtedy funkcja Zm+n → A υ B zadana przez : h(x) = f(x) dla x ε {0,1, … , m-1} h(x) = g(x-m) dla x ε {m, … , m+n+1} jest bijekcją.

h jest injekcją: niech x1 ε {0,1, … , m-1} oraz x2 ε {m, … , m+n+1} (x1 ≠ x2);

mamy, że h(x1) ≠ h(x2). h jest surjekcją: niech y ε A υ B. Niech y ε A. Wówczas z surjektywności f wiemy, że istnieje x ε Zm taki, że f(x)=y. Ale h(x)=f(x)=y.

(b) |S υ T| = |S| + |T\S|

|T| = |T\S| + |S ∩ T|

|S υ T| + |S ∩ T| = |S| + |T\S| + |S ∩ T| = |S| + |T|

Zasada włączania i wyłączania Dla zbiorów skończonych {A1, …, An} zachodzi|A1 υ … υ An| = ∑I ε {1, … , n} (-1)|I|+1 |∩i ε I Ai|= |A1| + … + |An| - |A1 ∩ A2| - |A1 ∩ A3| - … - |An-2 ∩ An| - |An-1 ∩ An|+ |A1 ∩ A2 ∩ A3| + …+ |An-2 ∩ An-1 ∩ An| - |A1 ∩ A2 ∩ A3 ∩ A4| - … - |An-3 ∩ An-2 ∩ An-1 ∩ An|+ …(-1) n+1 |A1 ∩ … ∩ An|

Zbiór potęgowy (czyli zbiór podzbiorów) zbioru X oznaczamy przez P(X).

Przykład. P(pusty_zbiór) = {pusty zbiór} i |P(pusty_zbiór)|= 1

P({pusty_zbiór})={ pusty_zbiór, { pusty_zbiór} i |P({pusty_zbiór})|=2

P({a,b}) = {pusty_zbiór, {a}, {b}, {a,b}}

P({a,b,c}) = {pusty_zbiór, {a}, {b}, {c}, {a,b}, {a,c},{b,c},{a,b,c}}

Ogólna sytuacja Niech pn oznacza liczbę podzbiorów zbioru n-elementowego.

Wówczas pn =2n. Uzasadnienie. Znamy liczbę pn i chcemy policzyć pn +1.

Niech zbiór Z ma n+1 elementów. Jeżeli a ε Z, to Z'=Z\{a}.

Podzbiory zbioru Z można podzielic na dwa elementy: (a) mające w sobie element a (b) nie mające w sobie element a W drugim przypadku są to podzbiory zbioru Z'. Jest więc ich dokładnie pn

Każdy zaś podzbiór pierwszego typu (czyli A zawarte w Z, takie, że a ε A) jest jednoznacznie wyznaczony przez swoje pozostałe elementy (tzn. elementy różne od a). A zatem każdy taki zbiór A (że a ε A zawartego w Z) jest postaci A' υ {a} dla pewnego A' zawartego w Z'. A zatem podzbiorów zbioru Z, w których jest element a, jest też tyle ile podzbiorów zbioru Z', tzn. pn.

Łacznie więc zbiór Z ma pn + pn podzbiorów czyli pn+1= 2* pn. Teraz już można stwierdzić, że to wraz z warunkiem pn=1 jest spełnione przez pn =2n.

Dla dowolnego skończonego zbioru X mamy |P(X)|= 2|X|.

Zliczanie funkcji Zbiór funkcji X → Y oznaczamy YX.

Uwaga Dla skończonych zbiorów X,Y mamy |YX| = |Y||X|.

Dowód. Niech X={x0, …, xm-1} oraz Y={y0, …, yn-1). Każda funkcja f:X → Y to krotka wartości dla kolejnych Xi:

(f(x0), …, f(xm-1)) ε Y x … x Y (m razy)

A więc zbiór funkcji z X w Y jest równoliczny z Ym.

Z zasady mnożenia otrzymujemy więc:

|Y x … x Y |(m razy) = |Y| x … x |Y| (m razy) = nm =|Y||X|.

Przykłady 1,2

Uwaga Liczba injekcji ze zbioru skończonego X w zbiór skończony Y wynosi

|Y| * (|Y|-1) * … * (|Y|-|X|+1) = |Y|! / (|Y|-|X|)!