Forma normal da negação

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde outubro de 2011).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

Uma fórmula lógica está na forma normal da negação se a negação ocorre logo após fórmulas atômicas, e {\lnot, \lor,\land} são os únicos conectivos booleanos permitidos. Na lógica clássica, cada fórmula pode ser convertida para essa forma substituindo implicações e equivalências pelas suas definições, usando as leis de De Morgan para internalizar a negação na fórmula e eliminando duplas negações. Esse processo pode ser representado através das seguintes regras de conversão:

\lnot (\forall x. G) \twoheadrightarrow \exists x. \lnot G
\lnot (\exists x. G) \twoheadrightarrow \forall x. \lnot G
\lnot \lnot G \twoheadrightarrow G
\lnot (G_1 \land G_2) \twoheadrightarrow (\lnot G_1) \lor (\lnot G_2)
\lnot (G_1 \lor G_2) \twoheadrightarrow (\lnot G_1) \land (\lnot G_2)

Uma fórmula na forma normal da negação pode ser colocada numa forma mais forte, como a forma normal conjuntiva ou a forma normal disjuntiva aplicando as leis da distributividade.

Ver também[editar | editar código-fonte]