3042. Osnovne operacije sa iskazima

TEKST ZADATKA

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

REŠENJE ZADATKA

Zadatak ćemo rešiti svođenjem na protivrečnost (kontradikciju). Pretpostavimo suprotno, tj. da data formula nije tautologija. To znači da postoji neka kombinacija istinitosnih vrednosti iskaznih slova za koju je vrednost cele formule netačna ( $\bot$ ).

Glavna logička operacija u formuli je implikacija. Implikacija $A \Rightarrow B$ je netačna ako i samo ako je prvi deo (pretpostavka) tačan ( $\top$ ), a drugi deo (zaključak) netačan ( $\bot$ ).

Primenom ovog pravila na našu formulu dobijamo dva uslova koja moraju biti ispunjena istovremeno:

\begin{aligned} 1^\circ \quad & ((p \Rightarrow q) \Rightarrow r) = \top \\ 2^\circ \quad & ((r \Rightarrow p) \Rightarrow (q \Rightarrow p)) = \bot \end{aligned}

Posmatrajmo drugi uslov. Da bi ova implikacija bila netačna, ponovo primenjujemo isto pravilo, pa mora važiti:

\begin{aligned} r \Rightarrow p &= \top \\ q \Rightarrow p &= \bot \end{aligned}

Iz uslova $q \Rightarrow p = \bot$ jednoznačno određujemo istinitosne vrednosti za iskazna slova $q$ i $p :$

\begin{aligned} q &= \top \\ p &= \bot \end{aligned}

Zamenom vrednosti $p = \bot$ u uslov $r \Rightarrow p = \top$ dobijamo:

r \Rightarrow \bot = \top

Da bi implikacija čiji je zaključak netačan bila tačna, njena pretpostavka mora biti netačna. Odatle sledi:

r = \bot

Sada imamo vrednosti svih iskaznih slova: $p = \bot ,$ $q = \top ,$ $r = \bot .$ Proverimo da li ove vrednosti zadovoljavaju prvi uslov $((p \Rightarrow q) \Rightarrow r) = \top .$

Zamenom vrednosti u prvi uslov računamo:

\begin{aligned} ((\bot \Rightarrow \top) \Rightarrow \bot) &= \top \\ (\top \Rightarrow \bot) &= \top \\ \bot &= \top \end{aligned}

Dobili smo kontradikciju ( $\bot = \top$ ). Pošto pretpostavka da je formula netačna dovodi do kontradikcije, zaključujemo da je polazna pretpostavka pogrešna.

Dakle, formula je uvek tačna za sve kombinacije istinitosnih vrednosti iskaznih slova, odnosno ona je tautologija.

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

19.b