Koniunkcyjna postać normalna

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 \and b) \or c jest (a \or c) \and (b \or c).

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

Definicja formalna[edytuj | edytuj kod]

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 ... \vee p_{1k_1}) \wedge (p_{21} \vee p_{22} \vee ... \vee p_{2k_2}) \wedge ... \wedge (p_{n1} \vee p_{n2} \vee ... \vee p_{nk_n})

gdzie każde pij jest literałem.

Problem znajdowania wartościowania[edytuj | edytuj kod]

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. nie będący negacja 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ą[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]