Algebraic normal form

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 (XOR) of a constant $a\_0$ and one or more conjunctions of the function arguments. ANF is also known as "Zhegalkin polynomials" ( _ru. полиномы Жегалкина) 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 $a\_0,\; a\_1,\; ldots,\; a\_\{1,2,ldots,n\}\; in\; \{0,1\}^*$ fully describes $f$.

For each function $f$ there is a unique ANF. There are only four functions with one argument: $f(x)=0$, $f(x)=1$, $f(x)=x$, $f(x)=1+x$ (all of them are given in the ANF). To represent a function with multiple arguments one can use the following equality: $f(x\_1,x\_2,ldots,x\_n)\; =\; g(x\_2,ldots,x\_n)\; +\; x\_1\; h(x\_2,ldots,x\_n)$, where $g(x\_2,ldots,x\_n)\; =\; f(0,x\_2,ldots,x\_n)$ and $h(x\_2,ldots,x\_n)\; =\; f(0,x\_2,ldots,x\_n)\; +\; f(1,x\_2,ldots,x\_n)$. Indeed, if $x\_1=0$ then $x\_1\; h\; =\; 0$ and so $f(0,ldots)\; =\; f(0,ldots)$; if $x\_1=1$ then $x\_1\; h\; =\; h$ and so $f(1,ldots)\; =\; f(0,ldots)\; +\; f(0,ldots)\; +\; f(1,ldots)$. Since both $g$ and $h$ have less arguments than $f$ it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of $f(x,y)=\; x\; lor\; y$ (logical or): $f(x,y)\; =\; f(0,y)\; +\; x(f(0,y)+f(1,y))$; since $f(0,y)=0\; lor\; y\; =\; y$ and $f(1,y)=1\; lor\; y\; =\; 1$, it follows that $f(x,y)\; =\; y\; +\; x\; (y\; +\; 1)$; by opening the parentheses we get the final ANF: $f(x,y)\; =\; y\; +\; x\; y\; +\; x\; =\; x\; +\; y\; +\; x\; y$.

ee also

* Boolean function
* Conjunctive normal form
* Disjunctive normal form
* Logical graph