Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
matematykadyskretna.niezbędnikdlainformatyków
Rozdział2
Podstawowetechnikidowodzenia
Poniżejznajdujesięsformułowaniezasadyszufladkowejwjęzyku
naturalnym:
Jeślimamywięcejrzeczyniższufadekikażdarzecztrafa
dojednejszufadki,tojakaśszufadkamusizawieraćwięcej
niżjednąrzecz.
Przypuśćmyjednak,żenaszznajomyniewierzywprawdziwość
tegostwierdzenia.Wjakisposóbmożnaprzekonującouzasadnić,że
jestonaprawdziwa?
Możnaspróbowaćprzekonaćznajomego,żewżadensposóbnie
mogłabybyćprawdziwasytuacjaodwrotna.Możnaspróbowaćwyobrazić
sobie,żekażdazszufladekniezawierawięcejniżjednąrzecz.Liczymy
wtedyszufladki,aponieważkażdaszufladkazawierazerolubjedną
rzecz,liczbaszufladekmożeconajwyżejrównaćsięliczbierzeczy.Za-
częliśmyjednakodzałożenia,żejestwięcejrzeczyniższufladek,awięc
jesttoniemożliwe!Ponieważniemamożliwości,bykażdaszufladka
zawierałaconajwyżejjednąrzecz,topewnaszufladkamusizawierać
więcejniżjednąrzecz,atojestdokładnieto,cochcemyudowodnić.
Wtymrozdzialedowiemysię,jakbudowaćtakienieformalne,ale
szczegółoweargumentacjeiwjakisposóbzamieniaćjewformalne,
ogólnedowodymatematyczne.Dowódjestargumentacją,którazaczyna
sięodjednejlubwięcejprzesłanek(naprzykładnmamywięcejrzeczy
niższufladek”)izpomocąregułlogikiwywodziznichwniosek(na
przykładnpewnaszufladkazawierawięcejniżjednąrzecz”).Chociaż
wydajesię,żełatwiejnapisać(izrozumieć!)zdaniasformułowane
wjęzykunaturalnym,tojednakmożeonbyćnieprecyzyjnylubnie-
potrzebnieszczegółowy.Będziezatemjaśniejibardziejogólnie,gdy
przedstawimymatematycznąsytuacjęwsposóbformalny.
Weźmydlaprzykładutakiezdanieizastanówmysię,comożeono
znaczyć:
Każdykogośkocha.
12
(2.1)
