3043.

19.v

TEKST ZADATKA

Dokazati da su sledeće formule tautologije: (p⇒(q⇒r))⇒((p⇒q)⇒(p⇒r)) (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⇒(q⇒r))⇒((p⇒q)⇒(p⇒r))≡⊥(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:

{p⇒(q⇒r)≡⊤(p⇒q)⇒(p⇒r)≡⊥\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:

{p⇒q≡⊤p⇒r≡⊥\begin{cases} p \Rightarrow q \equiv \top \\ p \Rightarrow r \equiv \bot \end{cases}

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

p≡⊤,r≡⊥p \equiv \top, \quad r \equiv \bot

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

⊤⇒q≡⊤\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 :

q≡⊤q \equiv \top

Sada imamo vrednosti svih iskaznih slova: p≡⊤, p \equiv \top , q≡⊤ q \equiv \top i r≡⊥. r \equiv \bot . Zamenićemo ove vrednosti u prvi uslov p⇒(q⇒r)≡⊤ 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.