Dysjunkcyjna postać normalna

Z Wikipedii

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

Na przykład dysjunkcyjną potacią normalną wyrażenia $(a \or b) \and c$ jest $(a \and c) \or (b \and c)$ .

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

Spis treści

1 Definicja formalna
2 Problem znajdowania wartościowania
- 2.1 Wielomianowy algorytm znajdujący wartościowanie spełniające
3 Zobacz również

[edytuj] Definicja formalna

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} \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_ij jest literałem.

[edytuj] Problem znajdowania wartościowania

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.

[edytuj] Wielomianowy algorytm znajdujący wartościowanie spełniające

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 
begin
    ok := true;
    foreach 
        foreach 
            if  then ok := false;
    if ok then
    begin
        T := ;
        foreach 
            if a_j jest niezanegowaną zmienną x_l then T := ;
        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 poslużyc 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.