3044.

18.b

TEKST ZADATKA

Ispitati da li je formula tautologija: ((p∧q)∨(q∧r))⇒(p∧r) ((p \land q) \lor (q \land r)) \Rightarrow (p \land r) ;

REŠENJE ZADATKA

Da bi iskazna formula bila tautologija, ona mora biti tačna (⊤ \top ) za sve moguće kombinacije istinitosnih vrednosti iskaznih slova koja se u njoj pojavljuju.

Formula je oblika implikacije A⇒B, A \Rightarrow B , gde je A=(p∧q)∨(q∧r) A = (p \land q) \lor (q \land r) i B=p∧r. B = p \land r . Implikacija je netačna (⊥ \bot ) samo u slučaju kada je uslov A A tačan, a posledica B B netačna.

(A⇒B)=⊥  ⟺  A=⊤ i B=⊥(A \Rightarrow B) = \bot \iff A = \top \text{ i } B = \bot

Pokušaćemo da pronađemo kombinaciju vrednosti za koju je formula netačna. Pretpostavimo da je posledica netačna:

p∧r=⊥p \land r = \bot

Ovo znači da barem jedno od iskaznih slova p p ili r r mora biti netačno. Neka je na primer p=⊥. p = \bot .

Sada zahtevamo da uslov A A bude tačan:

(p∧q)∨(q∧r)=⊤(p \land q) \lor (q \land r) = \top

Pošto smo pretpostavili da je p=⊥, p = \bot , izraz p∧q p \land q je sigurno netačan (⊥ \bot ). Zamenjujemo to u uslov:

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

Da bi ceo uslov bio tačan, mora važiti da je preostali deo tačan:

q∧r=⊤q \land r = \top

Konjunkcija je tačna samo kada su oba iskaza tačna, što znači da mora biti q=⊤ q = \top i r=⊤. r = \top .

Proveravamo celu formulu za dobijenu kombinaciju vrednosti: p=⊥, p = \bot , q=⊤, q = \top , r=⊤. r = \top .

((⊥∧⊤)∨(⊤∧⊤))⇒(⊥∧⊤)((\bot \land \top) \lor (\top \land \top)) \Rightarrow (\bot \land \top)

Računamo vrednost izraza u zagradama:

(⊥∨⊤)⇒⊥(\bot \lor \top) \Rightarrow \bot

Sređujemo levu stranu implikacije:

⊤⇒⊥\top \Rightarrow \bot

Konačna vrednost formule za ovu kombinaciju je netačna:

⊥\bot

Pošto smo pronašli barem jednu kombinaciju istinitosnih vrednosti (na primer p=⊥, p = \bot , q=⊤, q = \top , r=⊤ r = \top ) za koju je vrednost formule netačna, zaključujemo da formula nije tautologija.