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" (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.

Performing standard boolean operations

There are straightforward ways to perform the standard boolean operations on ANF inputs in order to get ANF results.

XOR is performed directly:

• (1 ⊕ x) ⊕ (1 ⊕ x ⊕ y)
• 1 ⊕ 1 ⊕ x ⊕ x ⊕ y
• y

NOT (logical complement) is XORing 1:

• ¬(1 ⊕ x ⊕ y)
• = (1 ⊕ x ⊕ y) ⊕ 1
• = 1 ⊕ 1 ⊕ x ⊕ y
• = x ⊕ y

AND (logical conjunction) is distributed algebraically:

• (1 ⊕ x)(1 ⊕ x ⊕ y)
• = 1(1 ⊕ x ⊕ y) ⊕ x(1 ⊕ x ⊕ y)
• = (1 ⊕ x ⊕ y) ⊕ (x ⊕ xx ⊕ xy)
• = 1 ⊕ x ⊕ x ⊕ x ⊕ y ⊕ xy
• = 1 ⊕ x ⊕ y ⊕ xy

OR (logical disjunction) uses De Morgan's laws (that is, x + y = (x ⊕ 1)(y ⊕ 1) ⊕ 1)):

• (1 ⊕ x) + (1 ⊕ x ⊕ y)
• (1 ⊕ x ⊕ 1)(1 ⊕ x ⊕ y ⊕ 1) ⊕ 1
• x(x ⊕ y) ⊕ 1
• 1 ⊕ x ⊕ xy

Obtaining algebraic normal form

The above ways of performing operations can be used to obtain ANF form from an arbitrary boolean expression. For example:

• x + (y · ¬z)
• = x + (y(1 ⊕ z))
• = x + (y ⊕ yz)
• = x ⊕ (y ⊕ yz) ⊕ (xy ⊕ xyz)
• = x ⊕ y ⊕ xy ⊕ yz ⊕ xyz

ANF can represent all boolean functions

The general ANF can be written as:

$f(x_{1},x_{2},\ldots ,x_{n})=\!$	$a_{0}\oplus \!$
	$a_{1}x_{1}\oplus a_{2}x_{2}\oplus \cdots \oplus a_{n}x_{n}\oplus \!$
	$a_{1,2}x_{1}x_{2}\oplus \cdots \oplus a_{n-1,n}x_{n-1}x_{n}\oplus \!$
	$\cdots \oplus \!$
	$a_{1,2,\ldots ,n}x_{1}x_{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\oplus x$.

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})\oplus x_{1}h(x_{2},\ldots ,x_{n})$, where

• $g(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})$
• $h(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})\oplus 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 )\oplus f(0,\ldots )\oplus f(1,\ldots )$

Since both $g$ and $h$ have fewer 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)\oplus x(f(0,y)\oplus 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\oplus x(y\oplus 1)$
• by opening the parentheses we get the final ANF: $f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy$

See also

• Zhegalkin polynomial
• Boolean function
• Conjunctive normal form
• Disjunctive normal form
• Logical graph