1/9
Looks like no tags are added yet.
Šta je negaciona normalna forma (NNF)?
Formula sastavljena od literala samo pomoću ∧ i ∨, ili konstanta ⊤/⊥.
Gde se negacija sme pojaviti u NNF?
Samo neposredno ispred atoma, u negativnim literalima.
Koja su dva glavna koraka svođenja na NNF?
Eliminisati implikacije i ekvivalencije; zatim spustiti negacije do atoma.
Kako se eliminiše P ⇒ Q tokom NNF transformacije?
P ⇒ Q ≡ ¬P ∨ Q.
Kako se eliminiše P ⇔ Q tokom NNF transformacije?
P ⇔ Q ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q).
Kako se negacija spušta kroz ∧ i ∨?
¬(P ∧ Q) ≡ ¬P ∨ ¬Q; ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
Kako se u NNF uklanja dvostruka negacija?
¬¬P ≡ P.
Kako je organizovana funkcija nnf u prezentaciji?
nnf(f) poziva nnf′(simplify(f)); nnf′ rekurzivno obrađuje strukturu formule.
Zašto NNF transformacija može eksponencijalno povećati formulu?
Eliminacija ekvivalencije može umnožiti pojavljivanja potformula.
Mini-zadatak: Svedi ¬(p ⇒ q) ∨ r na NNF.
(p ∧ ¬q) ∨ r.