20.v

Zadatak ćemo rešiti svođenjem na protivrečnost (kontradikciju). Pretpostavimo suprotno, da data formula nije tautologija. To znači da postoji neka valuacija za koju je vrednost cele formule netačna (označićemo sa $\bot$).

Implikacija $A \Rightarrow B$ je netačna samo u slučaju kada je prvi iskaz tačan ($A = \top$), a drugi iskaz netačan ($B = \bot$). Primenom ovog pravila na našu formulu dobijamo dva uslova:

Konjunkcija dva iskaza je netačna ako je barem jedan od njih netačan. Zbog toga se drugi uslov grana na dva moguća slučaja koja moramo posebno analizirati:

Analiziramo **Slučaj 1**. Ponovo imamo implikaciju koja je netačna, što znači da je njen levi deo tačan, a desni netačan:

Iz uslova da je konjunkcija $p \land r$ tačna, direktno sledi da oba iskaza moraju biti tačna:

Sada koristimo početni uslov $p \Rightarrow q = \top .$ Pošto smo utvrdili da je $p = \top ,$ da bi implikacija ostala tačna, mora važiti i da je $q = \top .$

Proveravamo dobijene vrednosti u uslovu $q \land r = \bot .$ Kako su i $q = \top$ i $r = \top ,$ njihova konjunkcija mora biti tačna ($\top$). Međutim, mi smo dobili da ona mora biti netačna ($\bot$). Ovo predstavlja **kontradikciju**!

Prelazimo na **Slučaj 2**. Implikacija je netačna, pa je levi deo tačan, a desni netačan:

Iz uslova da je disjunkcija $q \lor r$ netačna, direktno sledi da oba iskaza moraju biti netačna:

Ponovo koristimo početni uslov $p \Rightarrow q = \top .$ Pošto smo utvrdili da je $q = \bot ,$ da bi implikacija bila tačna, mora važiti da je i $p = \bot .$

Proveravamo dobijene vrednosti u uslovu $p \lor r = \top .$ Kako su i $p = \bot$ i $r = \bot ,$ njihova disjunkcija mora biti netačna ($\bot$). Međutim, mi smo dobili da ona mora biti tačna ($\top$). Ovo takođe predstavlja **kontradikciju**!

Pošto su oba moguća slučaja dovela do logičke kontradikcije, zaključujemo da je naša polazna pretpostavka bila pogrešna. Ne postoji valuacija za koju je formula netačna, što znači da je ona uvek tačna.