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
Kategoria:Logika matematyczna Kategoria:Teoria obliczeń