Algebraic normal form


In Boolean algebra, the algebraic normal form, ring sum normal form, Zhegalkin normal form, or Reed–Muller expansion is a way of writing logical formulas in one of three subforms:
Formulas written in ANF are also known as Zhegalkin polynomials and Positive Polarity Reed–Muller expressions.

Common uses

ANF is a normal form, which means that two equivalent formulas will convert to the same ANF, easily showing whether two formulas are equivalent for automated theorem proving. Unlike other normal forms, it can be represented as a simple list of lists of variable names. Conjunctive and disjunctive normal forms also require recording whether each variable is negated or not. Negation normal form is unsuitable for that purpose, since it doesn't use equality as its equivalence relation: a ∨ ¬a isn't reduced to the same thing as 1, even though they're equal.
Putting a formula into ANF also makes it easy to identify linear functions : a linear function is one that is a sum of single literals. Properties of nonlinear feedback shift registers can also be deduced from certain properties of the feedback function in ANF.

Performing operations within algebraic normal form

There are straightforward ways to perform the standard boolean operations on ANF inputs in order to get ANF results.
XOR is performed directly:
NOT is XORing 1:
AND is distributed algebraically
OR uses either 1 ⊕ or a ⊕ b ⊕ ab :

Converting to algebraic normal form

Each variable in a formula is already in pure ANF, so you only need to perform the formula's boolean operations as shown above to get the entire formula into ANF. For example:

Formal representation

ANF is sometimes described in an equivalent way:

Recursively deriving multiargument Boolean functions

There are only four functions with one argument:
To represent a function with multiple arguments one can use the following equality:
Indeed,
Since both and have fewer arguments than it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of :