3043. Osnovne operacije sa iskazima

TEKST ZADATKA

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

REŠENJE ZADATKA

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 $\bot .$

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

Glavna logička operacija u formuli je implikacija. Implikacija je netačna samo u slučaju kada je pretpostavka tačna ( $\top$ ), a zaključak netačan ( $\bot$ ). Iz toga dobijamo dva uslova:

\begin{cases} p \Rightarrow (q \Rightarrow r) \equiv \top \\ (p \Rightarrow q) \Rightarrow (p \Rightarrow r) \equiv \bot \end{cases}

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:

\begin{cases} p \Rightarrow q \equiv \top \\ p \Rightarrow r \equiv \bot \end{cases}

Iz uslova $p \Rightarrow r \equiv \bot$ direktno sledi jedinstvena kombinacija istinitosnih vrednosti za $p$ i $r :$

p \equiv \top, \quad r \equiv \bot

Sada poznatu vrednost za $p$ možemo zameniti u uslov $p \Rightarrow q \equiv \top :$

\top \Rightarrow q \equiv \top

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 $q :$

q \equiv \top

Sada imamo vrednosti svih iskaznih slova: $p \equiv \top ,$ $q \equiv \top$ i $r \equiv \bot .$ Zamenićemo ove vrednosti u prvi uslov $p \Rightarrow (q \Rightarrow r) \equiv \top$ koji smo dobili na početku, kako bismo proverili da li je on zadovoljen.

\top \Rightarrow (\top \Rightarrow \bot) \equiv \top

Rešavamo prvo implikaciju u zagradi. Znamo da je $\top \Rightarrow \bot \equiv \bot .$

\top \Rightarrow \bot \equiv \top

Konačno, vrednost implikacije na levoj strani je $\bot ,$ pa dobijamo:

\bot \equiv \top

Dobili smo kontradikciju ( $\bot \equiv \top$ ). 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.

19.v