Forma normal algébrica

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

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]