3047. Osnovne operacije sa iskazima

TEKST ZADATKA

Ispitati da li je formula tautologija:

((p \lor q) \Rightarrow r) \Leftrightarrow ((\neg r \Rightarrow \neg p) \land (\neg r \Rightarrow \neg q))

REŠENJE ZADATKA

Da bismo ispitali da li je formula tautologija, možemo koristiti pravila logičke ekvivalencije da uprostimo desnu stranu ekvivalencije.

Posmatrajmo desnu stranu formule:

(\neg r \Rightarrow \neg p) \land (\neg r \Rightarrow \neg q)

Primenjujemo pravilo kontrapozicije koje glasi $A \Rightarrow B \equiv \neg B \Rightarrow \neg A .$ Za naše izraze to znači:

\begin{aligned} \neg r \Rightarrow \neg p &\equiv p \Rightarrow r \\ \neg r \Rightarrow \neg q &\equiv q \Rightarrow r \end{aligned}

Zamenom ovih ekvivalencija u desnu stranu dobijamo:

(p \Rightarrow r) \land (q \Rightarrow r)

Sada primenjujemo pravilo za implikaciju koje kaže da je $A \Rightarrow B \equiv \neg A \lor B :$

(\neg p \lor r) \land (\neg q \lor r)

Primenjujemo zakon distributivnosti disjunkcije prema konjunkciji u obrnutom smeru:

(\neg p \land \neg q) \lor r

Primenjujemo De Morganov zakon na izraz u prvoj zagradi:

\neg (p \lor q) \lor r

Ponovo primenjujemo pravilo za implikaciju ( $\neg A \lor B \equiv A \Rightarrow B$ ):

(p \lor q) \Rightarrow r

Dobili smo izraz koji je identičan levoj strani početne formule. Zamenom u početnu ekvivalenciju imamo:

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

Pošto je svaka formula ekvivalentna samoj sebi ( $A \Leftrightarrow A \equiv \top$ ), zaključujemo da je data formula tautologija.

\top

18.g