Tautologija: tranzitivnost implikacije p ⇒ q ⇒ r

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.

Započni učenje

Online časovi

19.a

Beleške