Koniunkcyjna postać normalna
Z Wikipedii
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ą potacią normalną wyrażenia 
jest 
.
Każde wyrażenie logiczne ma koniunkcyjną postać normalną.
Spis treści |
[edytuj] 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ć
gdzie każde pij jest literałem.
[edytuj] 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. 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).
[edytuj] 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ą.
