Tautologija sa ekvivalencijama i negacijama iskaza

Da bi iskazna formula bila tautologija, ona mora biti tačna (istinita) za sve moguće kombinacije istinitosnih vrednosti iskaznih slova koja se u njoj pojavljuju. Obeležimo levu i desnu stranu glavne ekvivalencije sa $A$ i $B .$

\begin{aligned} A &= (p \lor q) \Leftrightarrow r \\ B &= (\neg r \Leftrightarrow \neg p) \land (\neg r \Leftrightarrow \neg q) \end{aligned}

Pojednostavimo izraz $B .$ Znamo da su iskazi $\neg x \Leftrightarrow \neg y$ i $x \Leftrightarrow y$ logički ekvivalentni.

B \equiv (r \Leftrightarrow p) \land (r \Leftrightarrow q)

Sada analiziramo kada bi formula $A \Leftrightarrow B$ mogla biti netačna. To se dešava kada $A$ i $B$ imaju različite istinitosne vrednosti. Pokušaćemo da pronađemo takav slučaj (kontraprimer).

Izraz $B$ zahteva da $r$ ima istu istinitosnu vrednost kao $p$ i istu kao $q .$ To znači da $B$ može biti tačno samo ako su $p$ i $q$ isti. Šta ako su $p$ i $q$ različiti? Neka je $p = \top$ i $q = \bot .$

\begin{aligned} p &= \top \\ q &= \bot \end{aligned}

Neka je $r = \top .$ Računamo vrednost izraza $A$ za ove vrednosti.

\begin{aligned} A &= (\top \lor \bot) \Leftrightarrow \top \\ A &= \top \Leftrightarrow \top \\ A &= \top \end{aligned}

Sada računamo vrednost izraza $B$ za iste vrednosti ( $p = \top ,$ $q = \bot ,$ $r = \top$ ).

\begin{aligned} B &= (\top \Leftrightarrow \top) \land (\top \Leftrightarrow \bot) \\ B &= \top \land \bot \\ B &= \bot \end{aligned}

Zamenjujemo dobijene vrednosti za $A$ i $B$ u početnu formulu.

A \Leftrightarrow B \equiv \top \Leftrightarrow \bot \equiv \bot

Pošto smo pronašli kombinaciju istinitosnih vrednosti ( $p=\top, q=\bot, r=\top$ ) za koju je vrednost formule netačna ( $\bot$ ), zaključujemo da data formula nije tautologija.

Započni učenje

Online časovi

18.d

Beleške