Tautologija: (p ∨ q ∨ r) ⇒ s kao tri implikacije

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

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

Primenjujemo pravilo za zamenu implikacije disjunkcijom: $A \Rightarrow B \equiv \neg A \lor B .$

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

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

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

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

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

Ponovo primenjujemo pravilo za implikaciju, ali u obrnutom smeru: $\neg A \lor B \equiv A \Rightarrow B .$

(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 \lor q \lor r) \Rightarrow s) \Leftrightarrow ((p \Rightarrow s) \land (q \Rightarrow s) \land (r \Rightarrow s)) \equiv \top

Započni učenje

Online časovi

17.d

Beleške