3051. Osnovne operacije sa iskazima

TEKST ZADATKA

Dokazati da je formula tautologija: $(\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 \Rightarrow B \equiv \neg A \lor B .$

Primenjujemo ovo pravilo na izraz sa leve strane ekvivalencije:

\neg r \Rightarrow (p \lor q) \equiv \neg(\neg r) \lor (p \lor q)

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

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 \lor q \lor r

Zamenjujemo dobijeni izraz nazad u početnu formulu:

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

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

\top

17.đ