Koniunkcyjna postać normalna

Koniunkcyjna postać normalna (ang. conjunctive normal form, CNF) danej formuły logicznej to równoważna jej formuła zapisana w postaci koniunkcji klauzul.

Na przykład koniunkcyjną postacią normalną wyrażenia $(a\land b)\lor c$ jest $(a\lor c)\land (b\lor c).$

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

Przykłady przekształceń:

$a\Rightarrow b\equiv (\neg a\lor b),$

$a\Leftrightarrow b\equiv (a\Rightarrow b)\land (b\Rightarrow a)\equiv (\neg a\lor b)\land (\neg b\lor a),$

$\neg (a\land b)\equiv (\neg a\lor \neg b),$

$\neg (a\lor b)\equiv (\neg a)\land (\neg b),$

$a\lor (b\land c)\equiv (a\lor b)\land (a\lor c).$

Definicja formalna

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

$(p_{11}\vee p_{12}\vee \ldots \vee p_{1k_{1}})\wedge (p_{21}\vee p_{22}\vee \ldots \vee p_{2k_{2}})\wedge \ldots \wedge (p_{n1}\vee p_{n2}\vee \ldots \vee p_{nk_{n}}),$

gdzie każde $p_{ij}$ jest literałem.

Problem znajdowania wartościowania

Problem znajdowania wartościowania formuły w postaci CNF jest problemem trudnym, dokładniej NP-zupełnym. Podobny problem, znajdowania wartościowania formuły w dysjunkcyjnej postaci normalnej jest łatwy, tzn. istnieje algorytm wielomianowy, który go rozwiązuje. Jeśli nałoży się na klauzule występujące w formule ograniczenie by żadna z nich nie zawierała więcej niż jeden literał pozytywny (tzn. niebędący negacją zmiennej), tj. by klauzule w danej formule były klauzulami hornowskimi to problem spełnialności staje się problemem łatwym (precyzyjnie: istnieje dla niego algorytm wielomianowy).

Problem sprawdzania czy formuła jest tautologią

Jeśli wyrażenie rachunku zdań jest zapisane w koniunkcyjnej postaci normalnej, to łatwo (tj. istnieje wielomianowy algorytm realizujący to zadanie) sprawdzić czy jest tautologią. Jeśli bowiem istnieje klauzula, która nie zawiera ani stałej prawda ani przynajmniej jednej zmiennej zarówno pozytywnie, jak i negatywnie, to można tak dobrać zmienne, żeby była ona fałszywa – każdej zmiennej występującej pozytywnie przyporządkujemy fałsz, każdej zaś występującej negatywnie prawdę. Wtedy cała CNF nie będzie spełniona, tak więc nie jest on tautologią.

Jeśli zaś każda klauzula zawiera albo stałą prawda albo przynajmniej jedną zmienną zarówno pozytywnie, jak i negatywnie (w każdym wartościowaniu albo jedna albo druga będzie prawdziwa), to CNF jest tautologią.

Zobacz też

• dysjunkcyjna postać normalna
• logika
• postać normalna
• prawa De Morgana
• problem NP-zupełny