Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1.Metodydowoduimplikacji
Dowódniewprost
11
Metodadowoduniewprostopierasięnanastępującejtautologiirachunku
zdań,zwanejprawemkontrapozycji:
(p⇒q)⇔(¬q⇒¬p).
Zatemstosująctęmetodę,zakładamy,żeqjestzdaniemfałszywymipoka~
zujemy,żepjestrównieżzdaniemfałszywym.
Przykład1.3.Udowodnićniewprost?żejeżeliiloczyndwóchliczbcałko-
witychaibjestliczbąparzystą?toajestliczbąparzystąlubbjestliczbą
parzystą.
Rozwiązanie.Niechpoznaczazdanieπiloczyna·bjestparzystyfl,aqzda~
nieπajestparzystelubbjestparzystefl.Żebywykazaćimplikacjęp⇒q,
udowodnimyimplikację¬q⇒¬p.PonieważzprawDeMorganamamy,że
¬(q1∨q2)⇔¬q1∧¬q2,
więczaprzeczeniezdaniaqrównoważnejesttemu,żeajestnieparzysteibjest
nieparzyste.Zatemistniejąliczbycałkowitelimtakie,że
a=2l+1orazb=2m+1.
Stądotrzymujemy,że
a·b=(2l+1)(2m+1)=4ml+2m+2l+1
=2(2ml+m+l)+1,
czyliiloczyna·bjestnieparzysty,tj.zdanie¬pjestprawdziwe.
Przykład1.4.Udowodnićniewprost?żejeżelinjestiloczynemdwóchdo-
datnichliczbcałkowitychaib?toa<√nlubb<√n.
Rozwiązanie.Załóżmy,żenaszatezajestfałszywa,toznaczy,że
¬(a<√n∨b<√n).
wyrażenietorównoważnejestkoniunkcji
a>√n∧b>√n.
Stądnatychmiastwynika,żea·b>n,copociągazasobą,że
¬(a·b=n).
Pokazaliśmyzatem,żezałożeniestwierdzeniajestfałszywe.
