Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
12
1.Metodydowodzeniatwierdzeń
Dowódprzezzaprzeczenie
Przypomnijmyinneznanepraworachunkuzdań
(p⇒q)⇔(¬p∨q).
StosującdojegoprawejstronyprawoDeMorgana,otrzymujemyrównoważ~
ność
(p⇒q)⇔¬(p∧¬q),
naktórejopierasięmetodadowoduprzezzaprzeczenie(zwanegotakżedowo~
demprzezsprowadzeniedosprzeczności).Stosująctopodejście,zakładamy,
żepjestprawdąaqfałszemipokazujemy,żeprowadzitodosprzeczności,
toznaczy,pokazujemy,że(p∧¬q)jestfałszem.
Przykład1.5.Udowodnićprzezzaprzeczenie?żespośródtrzynastuludzi
dwóchlubwięcejmaswojeurodzinywtymsamymmiesiącu.
Rozwiązanie.Stwierdzenie,któremamyudowodnić,mapostaćp⇒q,
gdziepjestzdaniemπmamytrzynastuludziwgrupiefl,aqjestzdaniem
πdwóchlubwięcejczłonkówgrupymaswojeurodzinywtymsamymmie~
siącufl.Załóżmywięc,żemamygrupętrzynastuludziiżadnychdwóchznich
niemaurodzinwtymsamymmiesiącu,czylip∧¬q.Tooczywiścieprowa~
dzidostwierdzenia,żejestconajmniejtrzynaścieróżnychmiesięcy,cojest
sprzecznezeznanymskądinąd(!)faktem,żemamytylkodwanaściemiesięcy.
Zatemimplikacjap⇒qjestprawdziwa.
Przykład1.6.Udowodnićprzezzaprzeczenie?żejeżeliwybrano41kulzszu-
fladkizawierającejkuleczerwone?białe?niebieskie?zieloneiżółte(zakła-
damy?żewkażdymkolorzejestwięcejkulniżwybieramy)?toconajmniej
12kuljestczerwonychlubconajmniej15kuljestbiałych?lubconajmniej
4kulesąniebieskie?lubconajmniej10kuljestzielonych?lubconajmniej4
kulesążółte.
Rozwiązanie.Niechx1,x2,x3,x4,x5oznaczająodpowiednioliczbęwybra~
nychkulczerwonych,białych,niebieskich,zielonychiżółtych.Mamyudo~
wodnićnastępującąimplikację:
x1+x2+x3+x4+x5=41⇒x1>12∨x2>15∨x3>4∨x4>10∨x5>4.
Załóżmywięc,żex1+x2+x3+x4+x5=41izaprzeczmytezie,toznaczy
przyjmijmy,że
x1<11∧x2<14∧x3<3∧x4<9∧x5<3.
