In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), Zhegalkin normal form, or Reed–Muller expansion is a way of writing propositional logic formulas in one of three subforms: Formulas written in ANF are also known as Zhegalkin polynomials and Positive Polarity (or Parity) Reed–Muller expressions (PPRM).
[1] ANF is a canonical form, which means that two logically 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.
Putting a formula into ANF also makes it easy to identify linear functions (used, for example, in linear-feedback shift registers): a linear function is one that is a sum of single literals.
XOR (logical exclusive disjunction) is performed directly: NOT (logical negation) is XORing 1:[2] AND (logical conjunction) is distributed algebraically[3] OR (logical disjunction) uses either 1 ⊕ (1 ⊕ a)(1 ⊕ b)[4] (easier when both operands have purely true terms) or a ⊕ b ⊕ ab[5] (easier otherwise): Each variable in a formula is already in pure ANF, so one only needs to perform the formula's Boolean operations as shown above to get the entire formula into ANF.