3048.

17.d

TEKST ZADATKA

Dokazati da je formula tautologija:

((p∨q∨r)⇒s)⇔((p⇒s)∧(q⇒s)∧(r⇒s))((p \lor q \lor r) \Rightarrow s) \Leftrightarrow ((p \Rightarrow s) \land (q \Rightarrow s) \land (r \Rightarrow s))
REŠENJE ZADATKA

Da bismo dokazali da je data formula tautologija, možemo koristiti poznate logičke ekvivalencije. Transformisaćemo levu stranu ekvivalencije.

(p∨q∨r)⇒s(p \lor q \lor r) \Rightarrow s

Primenjujemo pravilo za zamenu implikacije disjunkcijom: A⇒B≡¬A∨B. A \Rightarrow B \equiv \neg A \lor B .

¬(p∨q∨r)∨s\neg(p \lor q \lor r) \lor s

Zatim primenjujemo De Morganove zakone na izraz ¬(p∨q∨r). \neg(p \lor q \lor r) . Negacija disjunkcije je konjunkcija negacija.

(¬p∧¬q∧¬r)∨s(\neg p \land \neg q \land \neg r) \lor s

Sada primenjujemo zakon distributivnosti disjunkcije prema konjunkciji: (A∧B∧C)∨D≡(A∨D)∧(B∨D)∧(C∨D). (A \land B \land C) \lor D \equiv (A \lor D) \land (B \lor D) \land (C \lor D) .

(¬p∨s)∧(¬q∨s)∧(¬r∨s)(\neg p \lor s) \land (\neg q \lor s) \land (\neg r \lor s)

Ponovo primenjujemo pravilo za implikaciju, ali u obrnutom smeru: ¬A∨B≡A⇒B. \neg A \lor B \equiv A \Rightarrow B .

(p⇒s)∧(q⇒s)∧(r⇒s)(p \Rightarrow s) \land (q \Rightarrow s) \land (r \Rightarrow s)

Dobili smo tačno desnu stranu početne ekvivalencije. Pošto su leva i desna strana logički ekvivalentne, njihova ekvivalencija je uvek tačna, odnosno predstavlja tautologiju.

((p∨q∨r)⇒s)⇔((p⇒s)∧(q⇒s)∧(r⇒s))≡⊤((p \lor q \lor r) \Rightarrow s) \Leftrightarrow ((p \Rightarrow s) \land (q \Rightarrow s) \land (r \Rightarrow s)) \equiv \top