3039. Osnovne operacije sa iskazima

TEKST ZADATKA

Dokazati da je sledeća formula tautologija:

((p \Rightarrow q) \land (q \Rightarrow r) \land (r \Rightarrow s)) \Rightarrow (p \Rightarrow s)

REŠENJE ZADATKA

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 valuacija (dodela istinitosnih vrednosti iskaznim slovima) za koju je vrednost cele formule netačna, odnosno $\bot$ (neistina).

Formula je oblika implikacije $A \Rightarrow B ,$ gde je $A = (p \Rightarrow q) \land (q \Rightarrow r) \land (r \Rightarrow s)$ i $B = (p \Rightarrow s) .$

Implikacija je netačna ako i samo ako je uslov tačan, a posledica netačna. Dakle, mora istovremeno važiti:

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

Iz uslova da je posledica netačna, imamo $(p \Rightarrow s) = \bot .$ Implikacija je netačna samo kada je prvi iskaz tačan, a drugi netačan, pa iz toga nedvosmisleno sledi:

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

Sada posmatramo uslov da je premisa tačna. Konjunkcija je tačna samo ako su svi njeni članovi tačni, što znači da svaka od tri implikacije mora biti tačna:

(p \Rightarrow q) = \top, \quad (q \Rightarrow r) = \top, \quad (r \Rightarrow s) = \top

Znamo da je $p = \top .$ Da bi prva implikacija $(p \Rightarrow q)$ bila tačna, posledica $q$ ne sme biti netačna. Zato mora važiti:

q = \top

Sada znamo da je $q = \top .$ Da bi druga implikacija $(q \Rightarrow r)$ bila tačna, iz istog razloga mora važiti:

r = \top

Konačno, znamo da je $r = \top .$ Da bi treća implikacija $(r \Rightarrow s)$ bila tačna, mora važiti:

s = \top

Međutim, u jednom od prethodnih koraka smo iz netačnosti posledice cele formule zaključili da je $s = \bot .$ Dobili smo da je iskaz $s$ istovremeno i tačan i netačan, što je nemoguće.

s = \top \quad \text{i} \quad s = \bot \quad \Rightarrow \quad \text{Protivrečnost!}

Pošto nas je pretpostavka da formula nije tautologija dovela do logičke protivrečnosti, zaključujemo da je naša polazna pretpostavka pogrešna.

Dakle, data formula je uvek tačna za svaku moguću valuaciju iskaznih slova, čime je dokazano da ona jeste tautologija.

19.g