Dokaz tautologije: izvoz implikacije na konjunkciju

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

Započni učenje

Online časovi

17.g

Beleške