3051.

17.đ

TEKST ZADATKA

Dokazati da je formula tautologija: (¬r⇒(p∨q))⇔(p∨q∨r). (\neg r \Rightarrow (p \lor q)) \Leftrightarrow (p \lor q \lor r) .

REŠENJE ZADATKA

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

Koristimo pravilo za oslobađanje od implikacije: A⇒B≡¬A∨B. A \Rightarrow B \equiv \neg A \lor B .

Primenjujemo ovo pravilo na izraz sa leve strane ekvivalencije:

¬r⇒(p∨q)≡¬(¬r)∨(p∨q)\neg r \Rightarrow (p \lor q) \equiv \neg(\neg r) \lor (p \lor q)

Zatim primenjujemo pravilo dvojne negacije ¬(¬r)≡r: \neg(\neg r) \equiv r :

r∨(p∨q)r \lor (p \lor q)

Zbog svojstava asocijativnosti i komutativnosti logičke disjunkcije, zagrade i redosled operanada nisu bitni, pa izraz možemo zapisati kao:

p∨q∨rp \lor q \lor r

Zamenjujemo dobijeni izraz nazad u početnu formulu:

(p∨q∨r)⇔(p∨q∨r)(p \lor q \lor r) \Leftrightarrow (p \lor q \lor r)

Kako je svaka iskazna formula ekvivalentna samoj sebi (A⇔A≡⊤ A \Leftrightarrow A \equiv \top ), zaključujemo da je data formula uvek tačna, odnosno da je tautologija.

⊤\top