Forma normal da negação

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes. (desde outubro de 2011). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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]