3017.

9.b

TEKST ZADATKA

Sastaviti tablicu istinitosti za De Morganov zakon i odrediti da li je formula tautologija:

¬(p∧q)⇔(¬p∨¬q)\neg(p \land q) \Leftrightarrow (\neg p \lor \neg q)
REŠENJE ZADATKA

Prvo ćemo odrediti sve moguće kombinacije istinitosnih vrednosti za iskaze p p i q, q , a zatim izračunati vrednosti za negacije ¬p \neg p i ¬q. \neg q .

pp
qq
¬p\neg p
¬q\neg q
⊤\top
⊤\top
⊥\bot
⊥\bot
⊤\top
⊥\bot
⊥\bot
⊤\top
⊥\bot
⊤\top
⊤\top
⊥\bot
⊥\bot
⊥\bot
⊤\top
⊤\top

Sledeći korak je određivanje istinitosne vrednosti konjunkcije p∧q p \land q i njene negacije ¬(p∧q), \neg(p \land q) , što predstavlja levu stranu ekvivalencije.

pp
qq
p∧qp \land q
¬(p∧q)\neg(p \land q)
⊤\top
⊤\top
⊤\top
⊥\bot
⊤\top
⊥\bot
⊥\bot
⊤\top
⊥\bot
⊤\top
⊥\bot
⊤\top
⊥\bot
⊥\bot
⊥\bot
⊤\top

Sada računamo desnu stranu ekvivalencije, odnosno disjunkciju negacija ¬p∨¬q. \neg p \lor \neg q .

¬p\neg p
¬q\neg q
¬p∨¬q\neg p \lor \neg q
⊥\bot
⊥\bot
⊥\bot
⊥\bot
⊤\top
⊤\top
⊤\top
⊥\bot
⊤\top
⊤\top
⊤\top
⊤\top

Na kraju, upoređujemo levu i desnu stranu formule pomoću operacije ekvivalencije ⇔. \Leftrightarrow . Ako su vrednosti u poslednjoj koloni uvek tačne (⊤ \top ), formula je tautologija.

pp
qq
¬(p∧q)\neg(p \land q)
¬p∨¬q\neg p \lor \neg q
¬(p∧q)⇔(¬p∨¬q)\neg(p \land q) \Leftrightarrow (\neg p \lor \neg q)
⊤\top
⊤\top
⊥\bot
⊥\bot
⊤\top
⊤\top
⊥\bot
⊤\top
⊤\top
⊤\top
⊥\bot
⊤\top
⊤\top
⊤\top
⊤\top
⊥\bot
⊥\bot
⊤\top
⊤\top
⊤\top

Pošto su sve vrednosti u poslednjoj koloni tablice istinitosti tačne (⊤ \top ), zaključujemo da je data formula tautologija.

Formula je tautologija (T)\text{Formula je tautologija (T)}