19.v
Tekst zadatka namerno ne prikazujemo jer želimo da podržimo izdavača Krugove zbirke. Možeš pronaći tekst zadatka u zbirci.
Dokazati da su sledeće formule tautologije: ;
Pretpostavimo suprotno, odnosno da data iskazna formula nije tautologija. To znači da postoji neka kombinacija istinitosnih vrednosti iskaznih slova za koju je vrednost cele formule netačna, odnosno jednaka
Glavna logička operacija u formuli je implikacija. Implikacija je netačna samo u slučaju kada je pretpostavka tačna (), a zaključak netačan (). Iz toga dobijamo dva uslova:
Posmatrajmo drugi uslov. Ponovo imamo implikaciju koja je netačna, što znači da njen prvi deo mora biti tačan, a drugi netačan:
Iz uslova direktno sledi jedinstvena kombinacija istinitosnih vrednosti za i
Sada poznatu vrednost za možemo zameniti u uslov
Da bi ova implikacija bila tačna, s obzirom na to da je prvi iskaz tačan, i drugi iskaz mora biti tačan. Dakle, dobijamo vrednost za
Sada imamo vrednosti svih iskaznih slova: i Zamenićemo ove vrednosti u prvi uslov koji smo dobili na početku, kako bismo proverili da li je on zadovoljen.
Rešavamo prvo implikaciju u zagradi. Znamo da je
Konačno, vrednost implikacije na levoj strani je pa dobijamo:
Dobili smo kontradikciju (). Ovo znači da je naša polazna pretpostavka bila pogrešna i da ne postoji kombinacija istinitosnih vrednosti za koju je formula netačna. Time smo dokazali da data formula jeste tautologija.