Forma normal algébrica

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 julho de 2009). 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)

Na lógica booleana, a forma normal algébrica (FNA) , também conhecida como "Polinômio de Zhegalkin" ou "Expressão de Polaridade (Paridade) Positiva Reed-Muller", é vista como um método de padronização e normalização de fórmulas lógicas.

Assim como a forma normal, ela pode ser usada em demonstradores automáticos de teoremas, no entanto, sua utilidade mais comum está no projeto de geradores de números aleatórios criptográficos, especificamente em registradores de deslocamento com realimentação linear (RDRL).

Considera-se que uma fórmula lógica está na forma normal algébrica se somente se ela é uma soma algébrica exclusiva (XOR) de uma ou mais conjunções de uma ou mais literais. Ao se colocar uma fórmula na FNA torna-se fácil a identificação de funções lineares (uma função linear é uma soma de literais) como as necessárias para a realimentação linear em RDRLs.

As propriedades que dizem respeito aos registradores de deslocamento com realimentação não-linear também podem ser deduzidas a partir de certas propriedades da avaliação de funções na FNA. Uma FNA pode ser escrita genericamente da seguinte forma:

f(x_1, x_2, \ldots , x_n) = \! a_0 + \!
a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!
a_{1,2}x_1x_2 + a_{n-1,n}x_{n-1}x_n + \!
\ldots + \!
a_{1,2,\ldots,n}x_1x_2\ldots x_n \!

onde a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^*.

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