7. Konjuktivna i disjunktivna normalna forma u iskaznoj logici. Programska realizacija.

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/10

encourage image

There's no tags or description

Looks like no tags are added yet.

11 Terms

1
New cards

Šta je disjunktivna normalna forma (DNF)?

Disjunkcija konjunkcija literala: D₁ ∨ ... ∨ Dₙ.

2
New cards

Šta je konjunktivna normalna forma (KNF)?

Konjunkcija klauza (disjunkcija literala): K₁ ∧ ... ∧ Kₙ.

3
New cards

Kako su DNF i KNF povezane sa NNF?

Svaka DNF i KNF su ujedno NNF, ali imaju dodatno ograničenu strukturu.

4
New cards

Da li svaka iskazna formula ima ekvivalentnu DNF i KNF?

Da. DNF i KNF nisu jedinstveno određene.

5
New cards

Kako se NNF prevodi u DNF distributivnošću?

Distributivnošću ∧ preko ∨: P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R).

6
New cards

Kako se NNF prevodi u KNF distributivnošću?

Distributivnošću ∨ preko ∧: P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R).

7
New cards

Kako program konstruiše DNF?

Prvo računa NNF, zatim rekurzivno distribuira ∧ preko ∨ (dnf′ i distribdnf).

8
New cards

Kako se dobija kanonska DNF iz istinitosne tablice?

Za svaki red gde je F tačna napravi konjunkciju literala, pa disjunkciju tih redova.

9
New cards

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.

10
New cards

Mini-zadatak: Svedi p ∨ (q ∧ r) na KNF.

(p ∨ q) ∧ (p ∨ r).

11
New cards

Zašto direktno svođenje na KNF/DNF može biti skupo?

Distributivnost može eksponencijalno povećati veličinu formule.