b'\n_START_ARTICLE_\nKoniunkcyjna posta\xc4\x87 normalna\n_START_PARAGRAPH_\nKoniunkcyjna posta\xc4\x87 normalna (ang. conjunctive normal form, CNF) danej formu\xc5\x82y logicznej to r\xc3\xb3wnowa\xc5\xbcna jej formu\xc5\x82a zapisana w postaci koniunkcji klauzul._NEWLINE_Na przyk\xc5\x82ad koniunkcyjn\xc4\x85 postaci\xc4\x85 normaln\xc4\x85 wyra\xc5\xbcenia  jest ._NEWLINE_Ka\xc5\xbcde wyra\xc5\xbcenie logiczne ma koniunkcyjn\xc4\x85 posta\xc4\x87 normaln\xc4\x85._NEWLINE_Przyk\xc5\x82ady przekszta\xc5\x82ce\xc5\x84:\n_START_SECTION_\nProblem znajdowania warto\xc5\x9bciowania\n_START_PARAGRAPH_\nProblem znajdowania warto\xc5\x9bciowania formu\xc5\x82y w postaci CNF jest problemem trudnym, dok\xc5\x82adniej NP-zupe\xc5\x82nym._NEWLINE_Podobny problem, znajdowania warto\xc5\x9bciowania formu\xc5\x82y w dysjunkcyjnej postaci normalnej jest \xc5\x82atwy, tzn istnieje algorytm wielomianowy, kt\xc3\xb3ry go rozwi\xc4\x85zuje. Je\xc5\x9bli na\xc5\x82o\xc5\xbcy si\xc4\x99 na klauzule wyst\xc4\x99puj\xc4\x85ce w formule ograniczenie by \xc5\xbcadna z nich nie zawiera\xc5\x82a wi\xc4\x99cej ni\xc5\xbc jeden litera\xc5\x82 pozytywny (tzn. nie b\xc4\x99d\xc4\x85cy negacja zmiennej), tj. by klauzule w danej formule by\xc5\x82y klauzulami hornowskimi to problem spe\xc5\x82nialno\xc5\x9bci staje si\xc4\x99 problemem \xc5\x82atwym (precyzyjnie: istnieje dla niego algorytm wielomianowy).\n_START_SECTION_\nProblem sprawdzania czy formu\xc5\x82a jest tautologi\xc4\x85\n_START_PARAGRAPH_\nJe\xc5\x9bli wyra\xc5\xbcenie rachunku zda\xc5\x84 jest zapisane w koniunkcyjnej postaci normalnej, to \xc5\x82atwo (tj. istnieje wielomianowy algorytm realizuj\xc4\x85cy to zadanie) sprawdzi\xc4\x87 czy jest tautologi\xc4\x85. Je\xc5\x9bli bowiem istnieje klauzula, kt\xc3\xb3ra nie zawiera ani sta\xc5\x82ej prawda ani przynajmniej jednej zmiennej zar\xc3\xb3wno pozytywnie, jak i negatywnie, to mo\xc5\xbcna tak dobra\xc4\x87 zmienne, \xc5\xbceby by\xc5\x82a ona fa\xc5\x82szywa - ka\xc5\xbcdej zmiennej wyst\xc4\x99puj\xc4\x85cej pozytywnie przyporz\xc4\x85dkujemy fa\xc5\x82sz, ka\xc5\xbcdej za\xc5\x9b wyst\xc4\x99puj\xc4\x85cej negatywnie prawd\xc4\x99. Wtedy ca\xc5\x82a CNF nie b\xc4\x99dzie spe\xc5\x82niona, tak wi\xc4\x99c nie jest on tautologi\xc4\x85._NEWLINE_Je\xc5\x9bli za\xc5\x9b ka\xc5\xbcda klauzula zawiera albo sta\xc5\x82\xc4\x85 prawda albo przynajmniej jedn\xc4\x85 zmienn\xc4\x85 zar\xc3\xb3wno pozytywnie, jak i negatywnie (w ka\xc5\xbcdym warto\xc5\x9bciowaniu albo jedna albo druga b\xc4\x99dzie prawdziwa), to CNF jest tautologi\xc4\x85.'