Dysjunkcyjna postać normalna


Dysjunkcyjna postać normalna w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Dysjunkcyjna postać normalna (ang. disjunctive normal form, DNF) formuły logicznej – formuła zapisana w postaci dysjunkcji (alternatywy) klauzul dualnych.

Na przykład dysjunkcyjną postacią normalną wyrażenia ( a b ) c {\displaystyle (a\lor b)\land c} jest ( a c ) ( b c ) . {\displaystyle (a\land c)\lor (b\land c).}

Każde wyrażenie logiczne ma dysjunkcyjną postać normalną.

Spis treści

Definicja formalna | edytuj kod

Formuła φ jest w dysjunktywnej postaci normalnej jeśli jest ona alternatywą klauzul, z których każda jest koniunkcją literałów, tzn. ma następującą postać

( p 11 p 12 . . . p 1 k 1 ) ( p 21 p 22 . . . p 2 k 2 ) . . . ( p n 1 p n 2 . . . p n k n ) , {\displaystyle (p_{11}\wedge p_{12}\wedge ...\wedge p_{1k_{1}})\vee (p_{21}\wedge p_{22}\wedge ...\wedge p_{2k_{2}})\vee ...\vee (p_{n1}\wedge p_{n2}\wedge ...\wedge p_{nk_{n}}),}

gdzie każde p i j {\displaystyle p_{ij}} jest literałem.

Problem znajdowania wartościowania | edytuj kod

Problem znajdowania wartościowania spełniającego formuły w postaci DNF jest problemem łatwym, tzn. istnieje algorytm wielomianowy rozwiązujący ów problem. Jeśli bowiem jest choć jedna klauzula dualna, która nie zawiera ani fałszu ani jednocześnie pewnej zmiennej i jej negacji, możemy wszystkim wystąpieniom pozytywnym przyporządkować prawdę, negatywnym zaś fałsz, przez co ta klauzula dualna będzie spełniona, a zatem i cały DNF.

Jeśli natomiast każda klauzula dualna zawiera albo fałsz (a więc jest fałszywa), albo jednocześnie zmienną i jej zaprzeczenie (z których przynajmniej jedno musi być fałszywe), to oznacza to, że nie jest ona spełnialna.

Przykład algorytmu wielomianowego znajdującego wartościowanie formuły podanej w postaci DNF podany jest poniżej.

Podobny problem, znajdowania wartościowania formuły w koniunkcyjnej postaci normalnej jest NP-zupełny.

Wielomianowy algorytm znajdujący wartościowanie spełniające | edytuj kod

Przyjmijmy następujące założenia co do wejścia i wyjścia algorytmu:

  • formuła φ podana na wejściu jest zbiorem klauzul,
  • każda klauzula jest zbiorem literałów,
  • algorytm zwraca zbiór zmiennych, którym należy nadać wartość true (pozostałym zmiennym należy nadać wartość false) aby formuła φ była spełniona jeśli formuła jest spełnialna, w przeciwnym przypadku zwraca specjalną wartość nil.
foreach      C  i    ϕ   {\displaystyle C_{i}\in \phi }   begin ok := true; foreach      a  j     C  i     {\displaystyle a_{j}\in C_{i}}   foreach      b  k     C  i     {\displaystyle b_{k}\in C_{i}}   if      a  j   = ¬  b  k     {\displaystyle a_{j}=\neg b_{k}}   then ok := false; if ok then begin T :=        {\displaystyle \emptyset }  ; foreach      a  j     C  i     {\displaystyle a_{j}\in C_{i}}   if aj jest niezanegowaną zmienną xl then T :=     T  {  x  l   }   {\displaystyle T\cup \{x_{l}\}}  ; return T; end end return nil; 

Algorytm dla każdej klauzuli sprawdza czy jest ona niesprzeczna. Gdy znajdzie niesprzeczną klauzulę zwraca zbiór zmiennych, które w niej występują jako literały bez negacji. Można łatwo sprawdzić, że algorytm ten ma złożoność czasową nie gorszą niż O(n²), gdzie n to liczba literałów w formule φ.

Algorytm ten nie może posłużyć do rozwiązania NP-zupełnego problemu spełnialnosci formuł w postaci CNF ponieważ w ogólnym przypadku rozmiar formuły przy przekształcaniu jej z postaci CNF do DNF może wzrosnąć wykładniczo.

Zobacz też | edytuj kod

Na podstawie artykułu: "Dysjunkcyjna postać normalna" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy