3034.

20.v

TEKST ZADATKA

Ispitati da li su formule tautologije: (p⇒q)⇒(((p∧r)⇒(q∧r))∧((p∨r)⇒(q∨r))). (p \Rightarrow q) \Rightarrow (((p \land r) \Rightarrow (q \land r)) \land ((p \lor r) \Rightarrow (q \lor r))) .

REŠENJE ZADATKA

Zadatak ćemo rešiti svođenjem na protivrečnost (kontradikciju). Pretpostavimo suprotno, da data formula nije tautologija. To znači da postoji neka valuacija za koju je vrednost cele formule netačna (označićemo sa ⊥ \bot ).

(p⇒q)⇒(((p∧r)⇒(q∧r))∧((p∨r)⇒(q∨r)))=⊥(p \Rightarrow q) \Rightarrow (((p \land r) \Rightarrow (q \land r)) \land ((p \lor r) \Rightarrow (q \lor r))) = \bot

Implikacija A⇒B A \Rightarrow B je netačna samo u slučaju kada je prvi iskaz tačan (A=⊤ A = \top ), a drugi iskaz netačan (B=⊥ B = \bot ). Primenom ovog pravila na našu formulu dobijamo dva uslova:

p⇒q=⊤((p∧r)⇒(q∧r))∧((p∨r)⇒(q∨r))=⊥\begin{aligned} p \Rightarrow q &= \top \\ ((p \land r) \Rightarrow (q \land r)) \land ((p \lor r) \Rightarrow (q \lor r)) &= \bot \end{aligned}

Konjunkcija dva iskaza je netačna ako je barem jedan od njih netačan. Zbog toga se drugi uslov grana na dva moguća slučaja koja moramo posebno analizirati:

Slucˇaj 1: (p∧r)⇒(q∧r)=⊥Slucˇaj 2: (p∨r)⇒(q∨r)=⊥\begin{aligned} \text{Slučaj 1: } & (p \land r) \Rightarrow (q \land r) = \bot \\ \text{Slučaj 2: } & (p \lor r) \Rightarrow (q \lor r) = \bot \end{aligned}

Analiziramo **Slučaj 1**. Ponovo imamo implikaciju koja je netačna, što znači da je njen levi deo tačan, a desni netačan:

p∧r=⊤q∧r=⊥\begin{aligned} p \land r &= \top \\ q \land r &= \bot \end{aligned}

Iz uslova da je konjunkcija p∧r p \land r tačna, direktno sledi da oba iskaza moraju biti tačna:

p=⊤ir=⊤p = \top \quad \text{i} \quad r = \top

Sada koristimo početni uslov p⇒q=⊤. p \Rightarrow q = \top . Pošto smo utvrdili da je p=⊤, p = \top , da bi implikacija ostala tačna, mora važiti i da je q=⊤. q = \top .

q=⊤q = \top

Proveravamo dobijene vrednosti u uslovu q∧r=⊥. q \land r = \bot . Kako su i q=⊤ q = \top i r=⊤, r = \top , njihova konjunkcija mora biti tačna (⊤ \top ). Međutim, mi smo dobili da ona mora biti netačna (⊥ \bot ). Ovo predstavlja **kontradikciju**!

q∧r=⊤∧⊤=⊤≠⊥q \land r = \top \land \top = \top \neq \bot

Prelazimo na **Slučaj 2**. Implikacija je netačna, pa je levi deo tačan, a desni netačan:

p∨r=⊤q∨r=⊥\begin{aligned} p \lor r &= \top \\ q \lor r &= \bot \end{aligned}

Iz uslova da je disjunkcija q∨r q \lor r netačna, direktno sledi da oba iskaza moraju biti netačna:

q=⊥ir=⊥q = \bot \quad \text{i} \quad r = \bot

Ponovo koristimo početni uslov p⇒q=⊤. p \Rightarrow q = \top . Pošto smo utvrdili da je q=⊥, q = \bot , da bi implikacija bila tačna, mora važiti da je i p=⊥. p = \bot .

p=⊥p = \bot

Proveravamo dobijene vrednosti u uslovu p∨r=⊤. p \lor r = \top . Kako su i p=⊥ p = \bot i r=⊥, r = \bot , njihova disjunkcija mora biti netačna (⊥ \bot ). Međutim, mi smo dobili da ona mora biti tačna (⊤ \top ). Ovo takođe predstavlja **kontradikciju**!

p∨r=⊥∨⊥=⊥≠⊤p \lor r = \bot \lor \bot = \bot \neq \top

Pošto su oba moguća slučaja dovela do logičke kontradikcije, zaključujemo da je naša polazna pretpostavka bila pogrešna. Ne postoji valuacija za koju je formula netačna, što znači da je ona uvek tačna.

Data formula jeste tautologija.\text{Data formula jeste tautologija.}