3046. Osnovne operacije sa iskazima

TEKST ZADATKA

Dokazati da su sledeće formule tautologije: $a) (p \Rightarrow q) \Rightarrow ((q \Rightarrow r) \Rightarrow (p \Rightarrow r))$ ;

REŠENJE ZADATKA

Zadatak ćemo rešiti svođenjem na kontradikciju. Pretpostavimo suprotno, odnosno da data formula nije tautologija. To znači da postoji neka kombinacija istinitosnih vrednosti za koju je formula netačna (označimo netačno sa $\bot ,$ a tačno sa $\top$ ).

(p \Rightarrow q) \Rightarrow ((q \Rightarrow r) \Rightarrow (p \Rightarrow r)) = \bot

Implikacija $A \Rightarrow B$ je netačna samo u slučaju kada je $A = \top$ i $B = \bot .$ Primenjujući ovo pravilo na glavnu implikaciju u našoj formuli, dobijamo dva uslova:

p \Rightarrow q = \top \quad \text{i} \quad (q \Rightarrow r) \Rightarrow (p \Rightarrow r) = \bot

Sada posmatramo drugu dobijenu jednakost. Ponovo imamo implikaciju koja je netačna, pa na isti način mora važiti:

q \Rightarrow r = \top \quad \text{i} \quad p \Rightarrow r = \bot

Iz uslova $p \Rightarrow r = \bot$ direktno dobijamo istinitosne vrednosti za iskaze $p$ i $r :$

p = \top \quad \text{i} \quad r = \bot

Sada poznate vrednosti za $p$ i $r$ menjamo u preostale uslove. Iz prvog uslova $p \Rightarrow q = \top$ imamo:

\top \Rightarrow q = \top \implies q = \top

Zamenimo sada vrednosti $q = \top$ i $r = \bot$ u preostali uslov $q \Rightarrow r = \top :$

\top \Rightarrow \bot = \top \implies \bot = \top

Dobili smo očiglednu kontradikciju ( $\bot = \top$ ). To znači da je naša polazna pretpostavka bila pogrešna, pa zaključujemo da je data formula uvek tačna, odnosno da jeste tautologija.

19.a