3038.

18.d

TEKST ZADATKA

Ispitati da li je formula tautologija: ((p∨q)⇔r)⇔((¬r⇔¬p)∧(¬r⇔¬q)). ((p \lor q) \Leftrightarrow r) \Leftrightarrow ((\neg r \Leftrightarrow \neg p) \land (\neg r \Leftrightarrow \neg q)) .

REŠENJE ZADATKA

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 A i B. B .

A=(p∨q)⇔rB=(¬r⇔¬p)∧(¬r⇔¬q)\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. B . Znamo da su iskazi ¬x⇔¬y \neg x \Leftrightarrow \neg y i x⇔y x \Leftrightarrow y logički ekvivalentni.

B≡(r⇔p)∧(r⇔q)B \equiv (r \Leftrightarrow p) \land (r \Leftrightarrow q)

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

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

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

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

A=(⊤∨⊥)⇔⊤A=⊤⇔⊤A=⊤\begin{aligned} A &= (\top \lor \bot) \Leftrightarrow \top \\ A &= \top \Leftrightarrow \top \\ A &= \top \end{aligned}

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

B=(⊤⇔⊤)∧(⊤⇔⊥)B=⊤∧⊥B=⊥\begin{aligned} B &= (\top \Leftrightarrow \top) \land (\top \Leftrightarrow \bot) \\ B &= \top \land \bot \\ B &= \bot \end{aligned}

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

A⇔B≡⊤⇔⊥≡⊥A \Leftrightarrow B \equiv \top \Leftrightarrow \bot \equiv \bot

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