mad1_2010cw.pdf

Matematykadyskretna

dlainformatyk ó w

Czƒ–¢I:Elementykombinatoryki

JerzyJaworski

ZbigniewPalka

JerzySzyma«ski

Uniwersytetim.AdamaMickiewicza

Pozna«2007

Metodydowodzenia

twierdzeń

Przezzdanierozumiemydowolnestwierdzenie,kt ó rejestalboprawdziwe,albofa“szywe(nie

mo»eby¢onojednocze–nieprawdziweifa“szywe).Tradycyjniebƒdziemyu»ywalima“ychliter

p;q;r;::: jakozmiennychzdaniowych,toznaczy,zmiennychreprezentuj¡cychdowolnezdania,

oraznastƒpuj¡cychsp ó jnik ó wmiƒdzyzdaniowych: ∧ (koniunkcja), ∨ (alternatywa), ⇒ (imp-

likacja), ⇔ (r ó wnowa»no–¢), ¬ (negacja).

Wpierwszymparagra etegorozdzia“uinteresowa¢nasbƒdzieprawdziwo–¢zdania p

⇒

1.1.Metodydowoduimplikacji

q jestfa“szywawtedyitylkowtedy,gdyjejpoprzednik p

jestprawdziwy,anastƒpnik q jestfa“szywy;wpozosta“ychtrzechprzypadkachimplikacjajest

zdaniemprawdziwym.

⇒

Dow ó dwprost

Metodadowoduwprostpoleganaza“o»eniu,»e p jestprawd¡ipokazaniu,»ew ó wczas q jest

prawd¡.

Przyk“ad1.1.Udowodni¢wprost,»eje»eli a jesttak¡liczb¡ca“kowit¡,»e a

−

4 jestpodzielne

przez5,to a 3 +1 jestpodzielneprzez5.

Przyk“ad1.2.Udowodni¢wprost,»eje»eli x jesttak¡liczb¡rzeczywist¡,»e x 2

−

3 x

−

10=0 ,

to x =

−

2 lub x =5 .

Dow ó dniewprost

Metodadowoduniewprostopierasiƒnanastƒpuj¡cejtautologiirachunkuzda«,zwanejprawem

kontrapozycji:

p ) :

Zatemstosuj¡ctƒmetodƒzak“adamy,»e q jestzdaniemfa“szywymipokazujemy,»e p jestr ó wnie»

zdaniemfa“szywym.

Przyk“ad1.3.Udowodni¢niewprost,»eje»eliiloczyndw ó chliczbca“kowitych a i b jestliczb¡

parzyst¡,to a jestliczb¡parzyst¡lub b jestliczb¡parzyst¡.

( p

⇒

q )

⇔

(

⇒¬

(je»eli p ,to q ).Wtymprzypadkum ó wimy,»e p jestwarunkiemdostatecznymdla q lub,»e q jest

warunkiemkoniecznymdla p .Stwierdzenie,»e p jestwarunkiemkoniecznymidostatecznymdla

q jesttymsamym,costwierdzenieprawdziwo–cir ó wnowa»no–ci p⇔q ( p wtedyitylkowtedy,

gdy q ).

Przypomnijmy,i»implikacja p

2 1.Metodydowodzeniatwierdze«

Przyk“ad1.4.Udo w odni¢nie wp rost,»eje»eli n jestiloczynemdw ó chdodatnichliczbca“kow-

itych a i b ,to a

6 √ n .

Dow ó dprzezzaprzeczenie

Przypomnijmyinneznanepraworachunkuzda«

( p⇒q ) ⇔ ( ¬p∨q ) :

Stosuj¡cdojegoprawejstronyprawoDeMorgana,otrzymujemyr ó wnowa»no–¢

( p

⇒

q )

⇔¬

( p

∧¬

q ) ;

q ) jestfa“szem.

Przyk“ad1.5.Udowodni¢przezzaprzeczenie,»espo–r ó dtrzynastuludzidw ó chlubwiƒcejma

swojeurodzinywtymsamymmiesi¡cu.

∧¬

Przyk“ad1.6.Udowodni¢przezzaprzeczenie,»eje»eliwybrano41kulzszu adkizawieraj¡cej

kuleczerwone,bia“e,niebieskie,zielonei» ó “te(zak“adamy,»ewka»dymkolorzejestwiƒcejkul

ni»wybieramy),toconajmniej12kuljestczerwonychlubconajmniej15kuljestbia“ych,lub

conajmniej4kules¡niebieskie,lubconajmniej10kuljestzielonych,lubconajmniej4kules¡

» ó “te.Poda¢dow ó dtegofaktuprzezzaprzeczenie.

1.2.Zasadaindukcjimatematycznej

Niech p ( n ) bƒdziezdaniem,kt ó redlaka»degonaturalnego n mo»eby¢zdaniemprawdzi-

wymlubfa“szywym.Abyudowodni¢,»ezdanie p ( n ) jestprawdziwedlawszystkichliczb

naturalnych n ,gdzie n

n 0 ,wystarczypokaza¢,»e

(a)zdanie p ( n 0 ) jestprawdziwe,

(b)dlaka»dego k

n 0 ,

p ( k +1) ; (1.1)

tzn.zdanie p ( k +1) jestprawdziweje»elitylkozdanie p ( k ) jestprawdziwe.

p ( k )

⇒

Warunek(a)nazywasiƒwarunkiempocz¡tkowym.Za“o»enie,»e p ( k ) jestprawdziwenazywa

siƒza“o»eniemindukcyjnym,a p ( k +1) tez¡indukcyjn¡,za–samaimplikacja(1.1)krokiemin-

dukcyjnym.

Przyk“ad1.7.Znale„¢iudowodni¢wz ó rnasumƒpierwszych n liczbnaturalnych.

Przyk“ad1.8.Znale„¢iudowodni¢wz ó rnasumƒsze–cian ó w n pierwszychliczbnaturalnych,

tzn.nasumƒ

1 3 +2 3 + ::: + n 3 :

Przyk“ad1.9.Pokaza¢,»edlaka»degonaturalnego n ,wyra»enie

6 n +2 +7 2 n +1

jestpodzielneprzez 43 .

6 √ n lub b

nakt ó rejopierasiƒmetodadowoduprzezzaprzeczenie(zwanegotak»edowodemprzezsprowadze-

niedosprzeczno–ci).Stosuj¡ctopodej–ciezak“adamy,»e p jestprawd¡a q fa“szemipokazujemy,

»eprowadzitodosprzeczno–ci,toznaczy,pokazujemy»e ( p

1.3.Zasadaszu adkowa 3

Przyk“ad1.10.Pokaza¢,»edlaka»degonaturalnego n

4 ,

3 n >n 3 :

Przyk“ad1.11.Pokaza¢,»esuma n pierwszychwyraz ó wci¡guarytmetycznegoopierwszym

wyrazie a ior ó »nicy d ,r ó wnajest

2 n (2 a +( n

−

1) d ) :

Zasadƒindukcjimatematycznejmo»nasformu“owa¢nawieler ó wnowa»nychsposob ó w.Poni»ej

podamyinn¡,czƒstowykorzystywan¡wersjƒtejzasady,kt ó r¡nastƒpnieu»yjemywPrzyk“adzie1.12.

Niech p ( n ) bƒdziezdaniem,kt ó redlaka»degonaturalnego n mo»eby¢zdaniemprawdzi-

wymlubfa“szywym.Abyudowodni¢,»ezdanie p ( n ) jestprawdziwedlawszystkichliczb

naturalnych n ,gdzie n > n 0 ,wystarczypokaza¢,»e

(a)zdanie p ( n 0 ) jestprawdziwe,

(b)dlaka»dego k

n 0 ,

( p ( n 0 ) ∧p ( n 0 +1) ∧···∧p ( k )) ⇒p ( k +1)

tzn.zdanie p ( k +1) jestprawdziweje»elitylkowszystkiezdania p ( i ) s¡prawdziwe

dla n 0

k .

Przyk“ad1.12.Pokaza¢,»eje»elis¡spe“nionewarunki a 0 =12 ;a 1 =29 (nazywanepocz¡tkowymi)

orazdla n

2 zachodziwz ó r

a n =5 a n 1 − 6 a n 2

(nazywanywzoremrekurencyjnym),todlaka»degonaturalnego n

a n =5

3 n +7

2 n :

1.3.Zasadaszu adkowa

Zasadaszu adkowa(znanate»jakozasadaszu adkowaDirichleta)poleganaprostejobserwacji,

»eje»elirozmie–cimy n przedmiot ó ww m szu adkach,gdzie n>m ,toistniejeszu adka,kt ó ra

zawieraconajmniejdwaprzedmioty.Og ó lniej:

Je»elirozmie–cimy n przedmiot ó ww m szu adkach,przyczym n>k·m ( k∈ N ),to

wkt ó rej–szu adceznajdziesiƒconajmniej k +1 przedmiot ó w.

Przyk“ad1.13.Uzasadni¢,»ewka»dymmie–cielicz¡cymconajmniej1,7milionamieszka«c ó w

znajdziemyconajmniejpiƒ¢os ó botejsamejliczbiew“os ó wnag“owie,je»eliprzyjmiemy,»e

ro–nieichnaludzkiejg“owieconajwy»ej400000.

Przyk“ad1.14.Wturniejupi“karskim,wkt ó rymdocelowoka»dadru»ynamazagra¢zka»d¡

inn¡bierzeudzia“ n zespo“ ó w.Uzasadni¢,»ewdowolnymmomencietrwaniaturniejuznajd¡siƒ

dwiedru»yny,kt ó rerozegra“ydotegomomentutƒsam¡liczbƒmecz ó w.

Przyk“ad1.15.Pokaza¢,»eje»eliwtr ó jk¡cier ó wnobocznymobokud“ugo–ci 4 umie–cimy17

punkt ó w,toznajdziemydwapunkty,miƒdzykt ó rymiodleg“o–¢nieprzekracza1.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: