3035.

17.b

TEKST ZADATKA

Dokazati da je formula tautologija: (p⇔q)⇒((p∧r)⇔(q∧r))∧((p∨r)⇔(q∨r)). (p \Leftrightarrow q) \Rightarrow ((p \land r) \Leftrightarrow (q \land r)) \land ((p \lor r) \Leftrightarrow (q \lor r)) .

REŠENJE ZADATKA

Zadatak ćemo rešiti svođenjem na protivrečnost (reductio ad absurdum). Pretpostavimo suprotno, odnosno da data formula nije tautologija. To znači da postoji neka kombinacija istinitosnih vrednosti iskaznih slova za koju je formula netačna (ima vrednost ⊥ \bot ).

Glavna operacija u formuli je implikacija. Implikacija A⇒B A \Rightarrow B je netačna ako i samo ako je uslov A A tačan, a posledica B B netačna.

(p⇔q)=⊤i(((p∧r)⇔(q∧r))∧((p∨r)⇔(q∨r)))=⊥(p \Leftrightarrow q) = \top \quad \text{i} \quad (((p \land r) \Leftrightarrow (q \land r)) \land ((p \lor r) \Leftrightarrow (q \lor r))) = \bot

Iz pretpostavke da je leva strana (uslov) tačna, zaključujemo da iskazi p p i q q moraju imati istu istinitosnu vrednost.

(p=⊤∧q=⊤)∨(p=⊥∧q=⊥)(p = \top \land q = \top) \quad \lor \quad (p = \bot \land q = \bot)

Razmotrimo prvi slučaj, kada su i p p i q q tačni. Zamenimo ove vrednosti u desnu stranu formule (posledicu).

((⊤∧r)⇔(⊤∧r))∧((⊤∨r)⇔(⊤∨r))((\top \land r) \Leftrightarrow (\top \land r)) \land ((\top \lor r) \Leftrightarrow (\top \lor r))

Primenom osnovnih pravila iskazne algebre (⊤∧r=r \top \land r = r i ⊤∨r=⊤ \top \lor r = \top ), izraz se pojednostavljuje:

(r⇔r)∧(⊤⇔⊤)(r \Leftrightarrow r) \land (\top \Leftrightarrow \top)

Kako je svaki iskaz ekvivalentan samom sebi, obe ekvivalencije su tačne, pa je i njihova konjunkcija tačna.

⊤∧⊤=⊤\top \land \top = \top

Dobili smo da je desna strana formule tačna (⊤ \top ), što je u suprotnosti sa našom pretpostavkom da je desna strana netačna (⊥ \bot ).

Razmotrimo sada drugi slučaj, kada su i p p i q q netačni. Zamenimo ove vrednosti u desnu stranu formule.

((⊥∧r)⇔(⊥∧r))∧((⊥∨r)⇔(⊥∨r))((\bot \land r) \Leftrightarrow (\bot \land r)) \land ((\bot \lor r) \Leftrightarrow (\bot \lor r))

Primenom pravila iskazne algebre (⊥∧r=⊥ \bot \land r = \bot i ⊥∨r=r \bot \lor r = r ), izraz se pojednostavljuje:

(⊥⇔⊥)∧(r⇔r)(\bot \Leftrightarrow \bot) \land (r \Leftrightarrow r)

Ponovo dobijamo konjunkciju dve tačne ekvivalencije, što znači da je cela desna strana tačna.

⊤∧⊤=⊤\top \land \top = \top

Kao i u prvom slučaju, dobijamo da je desna strana tačna, što protivreči pretpostavci da je netačna.

Pošto smo u oba moguća slučaja došli do protivrečnosti, naša početna pretpostavka da formula može biti netačna je pogrešna. Dakle, data formula je uvek tačna, odnosno ona je tautologija.