Zajęcia prowadził: dr hab. Jerzy Jaworski
______________________________________________________________________
jaworski@amu.edu.pl
Dyżury: pokój B3-22
Podręcznik obowiązujący: “Matematyka dyskretna dla informatyków-cz. I elementy kombinatoryki”
______________________________________________________________________
Metody dowodzenia twierdzeń:
Twierdzenie - implikacja złożona z założenia (poprzednika implikacji) i tezy (następnika implikacji)
gdzie:
p-założenie
q-teza
1. Dowód wprost
Dowodzimy, że nigdy nie zachodzi q=0, jeżeli p=1
Przykład 1.
Udowodnij, ze dla każdej liczby całkowitej a, 5 jest dzielnikiem
Założenie:
Teza:
Dowód:
Skoro a-4 jest podzielne przez 5, można a-4 zapisać jako liczbę 5k.
2. Dowód nie wprost
Dowodzimy, że jeżeli q=0, to p=0, czyli nigdy dla q=0 nie zachodzi p=1 (implikacja byłaby fałszywa)
Przykład 2.
Udowodnij, że jeśli a i b są parzyste, ich iloczyn także jest liczbą parzystą.
Dowodzimy nie wprost, zatem zakładamy, że a i b są nieparzyste, to ich iloczyn musi być liczbą nieparzystą:
a=2k+1 , b=2m+1,
a*b=(2k+1)*(2m+1)=2km+2k+2m+1=2(km+k+m)+1 - liczba ta jest nieparzysta.
Co kończy dowód.
3. Dowód przez zaprzeczenie
Dowodzimy zakładając, ze założenie jest prawdziwe, natomiast teza fałszywa i robimy tak, żeby nam wyszła sprzeczność.
Pokazując fałszywość implikacji w nawiasie, pokazujemy prawdziwość tezy.
Przykład 3.
Udowodnij, ze wśród 13 osób co najmniej dwie mają urodziny w tym samym miesiącu.
Dowód:
Zakładamy, że każda z 13 osób ma urodziny w innym miesiącu. Wynika stąd, ze musi być co najmniej 13 miesięcy, co jest oczywiście fałszywe. Zatem implikacja w nawiasie jest fałszywa, co oznacza ze teza jest prawdziwa (dwie osoby muszą mieć urodziny w tym samym miesiącu)
4. Dowód indukcyjny.
1) Oznacza to, że dla najmniejszej liczby teza jest spełniona.
2)
Oznacza to, że dla każdego k (jeśli jest spełniony pierwszy warunek!) wynika prawdziwość tezy dla k+1. Nazywa się to krokiem indukcyjnym.
Przykład 4.
Udowodnij wzór na sumę wszystkich liczb całkowitych począwszy od 1 aż do n.
1+2+3+…+n=S(n)
Wzór, jak pamiętamy:
Zatem:
1)
1=1
L=P
2) Założenie indukcyjne:
3) Teza indukcyjna:
Zatem dowodzimy tezy przy pomocy założeniai:
Za podkreślony fragment można podstawić prawą stronę pierwszego równania, którą udowodniliśmy w 1 kroku. Nazywa sie to podstawieniem indukcyjnym.
Zatem:
wyłączamy k+1 i otrzymujemy równość:
L=P
cnd.
5. Zasada szufladkowa
Jeśli mamy n obiektów i m miejsc, przy czym n>m to istnieje miejsc, gdzie znajdują się co najmniej dwa obiekty.
Inaczej:
n > k*m to istnieje szufladka, gdzie znajduje się co najmniej k+1 obiektów.
