| dbpprop:abstract
|
- In Boolean logic, the algebraic normal form (ANF) is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving (ATP), but is more commonly used in the design of cryptographic random number generators, specifically linear feedback shift registers (LFSRs). A logical formula is considered to be in ANF if and only if it is a single algebraic sum of a constant <math>a_0</math> and one or more conjunctions of the function arguments. ANF is also known as "Zhegalkin polynomials" and as "Positive Polarity (or Parity) Reed-Muller" expression. Putting a formula into ANF makes it easy to identify linear functions, as is needed for linear feedback in LFSRs: a linear function is one that is a sum of literals. Properties of nonlinear feedback shift registers can also be deduced from certain properties of the feedback function in ANF. The general ANF can be written as: where <math>a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^*</math> fully describes <math>f</math>. For each function <math>f</math> there is a unique ANF. There are only four functions with one argument: <math>f(x)=0</math>, <math>f(x)=1</math>, <math>f(x)=x</math>, <math>f(x)=1+x</math> (all of them are given in the ANF). To represent a function with multiple arguments one can use the following equality: <math>f(x_1,x_2,\ldots,x_n) = g(x_2,\ldots,x_n) + x_1 h(x_2,\ldots,x_n)</math>, where <math>g(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n)</math> and <math>h(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) + f(1,x_2,\ldots,x_n)</math>. Indeed, if <math>x_1=0</math> then <math>x_1 h = 0</math> and so <math>f(0,\ldots) = f(0,\ldots)</math>; if <math>x_1=1</math> then <math>x_1 h = h</math> and so <math>f(1,\ldots) = f(0,\ldots) + f(0,\ldots) + f(1,\ldots)</math>. Since both <math>g</math> and <math>h</math> have less arguments than <math>f</math> it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of <math>f(x,y)= x \lor y</math> (logical or): <math>f(x,y) = f(0,y) + x(f+f)</math>; since <math>f(0,y)=0 \lor y = y</math> and <math>f(1,y)=1 \lor y = 1</math>, it follows that <math>f(x,y) = y + x (y + 1)</math>; by opening the parentheses we get the final ANF: <math>f(x,y) = y + x y + x = x + y + x y</math>.
- Na lógica booleana, a forma normal algébrica (FNA), também conhecida como "Polinômio de Zhegalkin" ou "Expressão de Polaridade 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 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: onde <math>a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^*</math>. Álgebra booleana Forma normal conjuntiva Forma normal disjuntiva Grafo lógico Registrador de deslocamento Fórmula lógica
|
![[RDF Data]](/statics/sw-cube.png)
