Негацијска нормална форма

Из Википедије, слободне енциклопедије

Логичка формула је у негацијској нормалној форми ако се негације јављају само уз атомичке исказне формуле, а у формули се јављају само везници {\lnot, \lor,\land}. У класичној логици свака формула може да се преведе у ову форму тако што се импликације и еквиваленције замене својим дефиницијама, искористе се де Морганови закони да се негације спусте што је могуће дубље, и елиминишу се двоструке негације. Овај процес се може представити следећим логичким еквиваленцијама:

\lnot (\forall x \; G) \equiv \exists x \; \lnot G
\lnot (\exists x \; G) \equiv \forall x \; \lnot G
\lnot \lnot G \equiv G
\lnot (G_1 \land G_2) \equiv (\lnot G_1) \lor (\lnot G_2)
\lnot (G_1 \lor G_2) \equiv (\lnot G_1) \land (\lnot G_2)

Формула у негацијској нормалној форми се може превести у јачу конјуктивну нормалну форму или дисјунктивну нормалну форму применом дистрибутивних закона.

Спољашње везе[уреди]