19.g
Tekst zadatka namerno ne prikazujemo jer želimo da podržimo izdavača Krugove zbirke. Možeš pronaći tekst zadatka u zbirci.
Dokazati da je sledeća formula tautologija:
Zadatak ćemo rešiti svođenjem na protivrečnost (reductio ad absurdum). Pretpostavimo suprotno, odnosno da data formula nije tautologija.
To znači da postoji neka valuacija (dodela istinitosnih vrednosti iskaznim slovima) za koju je vrednost cele formule netačna, odnosno (neistina).
Formula je oblika implikacije gde je i
Implikacija je netačna ako i samo ako je uslov tačan, a posledica netačna. Dakle, mora istovremeno važiti:
Iz uslova da je posledica netačna, imamo Implikacija je netačna samo kada je prvi iskaz tačan, a drugi netačan, pa iz toga nedvosmisleno sledi:
Sada posmatramo uslov da je premisa tačna. Konjunkcija je tačna samo ako su svi njeni članovi tačni, što znači da svaka od tri implikacije mora biti tačna:
Znamo da je Da bi prva implikacija bila tačna, posledica ne sme biti netačna. Zato mora važiti:
Sada znamo da je Da bi druga implikacija bila tačna, iz istog razloga mora važiti:
Konačno, znamo da je Da bi treća implikacija bila tačna, mora važiti:
Međutim, u jednom od prethodnih koraka smo iz netačnosti posledice cele formule zaključili da je Dobili smo da je iskaz istovremeno i tačan i netačan, što je nemoguće.
Pošto nas je pretpostavka da formula nije tautologija dovela do logičke protivrečnosti, zaključujemo da je naša polazna pretpostavka pogrešna.
Dakle, data formula je uvek tačna za svaku moguću valuaciju iskaznih slova, čime je dokazano da ona jeste tautologija.