1/10
Looks like no tags are added yet.
Šta je disjunktivna normalna forma (DNF)?
Disjunkcija konjunkcija literala: D₁ ∨ ... ∨ Dₙ.
Šta je konjunktivna normalna forma (KNF)?
Konjunkcija klauza (disjunkcija literala): K₁ ∧ ... ∧ Kₙ.
Kako su DNF i KNF povezane sa NNF?
Svaka DNF i KNF su ujedno NNF, ali imaju dodatno ograničenu strukturu.
Da li svaka iskazna formula ima ekvivalentnu DNF i KNF?
Da. DNF i KNF nisu jedinstveno određene.
Kako se NNF prevodi u DNF distributivnošću?
Distributivnošću ∧ preko ∨: P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R).
Kako se NNF prevodi u KNF distributivnošću?
Distributivnošću ∨ preko ∧: P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R).
Kako program konstruiše DNF?
Prvo računa NNF, zatim rekurzivno distribuira ∧ preko ∨ (dnf′ i distribdnf).
Kako se dobija kanonska DNF iz istinitosne tablice?
Za svaki red gde je F tačna napravi konjunkciju literala, pa disjunkciju tih redova.
Kako se dobija kanonska KNF iz istinitosne tablice?
Za svaki red gde je F netačna napravi klauzu koja je u tom redu netačna, pa konjunkciju.
Mini-zadatak: Svedi p ∨ (q ∧ r) na KNF.
(p ∨ q) ∧ (p ∨ r).
Zašto direktno svođenje na KNF/DNF može biti skupo?
Distributivnost može eksponencijalno povećati veličinu formule.