Algebraic normal form

Algebraic normal form (ANF) is a representation of functions in boolean algebra. Formulas written in ANF are also known as ring sum normal form (RSNF or RNF), Zhegalkin polynomials (Russian: полиномы Жегалкина), or Positive Polarity (or parity) Reed–Muller expansions (PPRM). These terms describe a way of writing propositional logic formulas in one of three sub-forms:

• The entire formula is purely true or false:
  • ${\displaystyle 1}$
  • ${\displaystyle 0}$
• One or more variables are combined into a term by AND (${\displaystyle \land }$), then one or more terms are combined by XOR (${\displaystyle \oplus }$) together into ANF. Negations are not permitted: $${\displaystyle a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)}$$
• The previous subform with a purely true term: $${\displaystyle 1\oplus a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)}$$

Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927, they are the polynomial ring over the integers modulo 2. The resulting degeneracies of modular arithmetic result in Zhegalkin polynomials being simpler than ordinary polynomials, requiring neither coefficients nor exponents. Coefficients are redundant because 1 is the only nonzero coefficient. Exponents are redundant because in arithmetic mod 2, x² = x. Hence a polynomial such as 3x²y⁵z is congruent to, and can therefore be rewritten as, xyz.