17.b
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 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 kombinacija istinitosnih vrednosti iskaznih slova za koju je formula netačna (ima vrednost ).
Glavna operacija u formuli je implikacija. Implikacija je netačna ako i samo ako je uslov tačan, a posledica netačna.
Iz pretpostavke da je leva strana (uslov) tačna, zaključujemo da iskazi i moraju imati istu istinitosnu vrednost.
Razmotrimo prvi slučaj, kada su i i tačni. Zamenimo ove vrednosti u desnu stranu formule (posledicu).
Primenom osnovnih pravila iskazne algebre ( i ), izraz se pojednostavljuje:
Kako je svaki iskaz ekvivalentan samom sebi, obe ekvivalencije su tačne, pa je i njihova konjunkcija tačna.
Dobili smo da je desna strana formule tačna (), što je u suprotnosti sa našom pretpostavkom da je desna strana netačna ().
Razmotrimo sada drugi slučaj, kada su i i netačni. Zamenimo ove vrednosti u desnu stranu formule.
Primenom pravila iskazne algebre ( i ), izraz se pojednostavljuje:
Ponovo dobijamo konjunkciju dve tačne ekvivalencije, što znači da je cela desna strana tačna.
Kao i u prvom slučaju, dobijamo da je desna strana tačna, što protivreči pretpostavci da je netačna.
Pošto smo u oba moguća slučaja došli do protivrečnosti, naša početna pretpostavka da formula može biti netačna je pogrešna. Dakle, data formula je uvek tačna, odnosno ona je tautologija.