Algebraic normal form

From Wikipedia, the free encyclopedia

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" (Russian: полиномы Жегалкина) 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:

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

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$ .

[edit] See also

$\lnot(p\land\lnot p)$

This logic-related article is a stub. You can help by expanding it.

This article does not cite any references or sources. (December 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.