3037. Osnovne operacije sa iskazima

TEKST ZADATKA

Dokazati da je formula tautologija: $(p \Rightarrow (q \Rightarrow r)) \Leftrightarrow ((p \land q) \Rightarrow r)$

REŠENJE ZADATKA

Da bismo dokazali da je formula tautologija, možemo uprostiti levu i desnu stranu ekvivalencije koristeći poznate logičke zakone. Prvo se podsetimo zakona uklanjanja implikacije:

x \Rightarrow y \equiv \neg x \lor y

Takođe će nam biti potreban De Morganov zakon za negaciju konjunkcije:

\neg (x \land y) \equiv \neg x \lor \neg y

Transformišimo levu stranu glavne ekvivalencije, odnosno formulu $p \Rightarrow (q \Rightarrow r) :$

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

Sada transformišimo desnu stranu glavne ekvivalencije, odnosno formulu $(p \land q) \Rightarrow r :$

\begin{aligned} (p \land q) \Rightarrow r &\equiv \neg (p \land q) \lor r \\ &\equiv (\neg p \lor \neg q) \lor r \\ &\equiv \neg p \lor \neg q \lor r \end{aligned}

Upoređivanjem dobijenih rezultata vidimo da su leva i desna strana logički ekvivalentne, jer se obe svode na isti izraz $\neg p \lor \neg q \lor r .$

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

Pošto su leva i desna strana ekvivalencije uvek iste istinitosne vrednosti, njihova ekvivalencija je uvek tačna, čime smo dokazali da je početna formula tautologija.

((p \Rightarrow (q \Rightarrow r)) \Leftrightarrow ((p \land q) \Rightarrow r)) \equiv \top

17.g