Algebraic normal form

Zhegalkin polynomial and Reed–Muller expansion are in the process of being merged into this article. If possible, please edit only this article, as the article mentioned above may be turned into a redirect. Relevant discussion may be found here. (April 2025)

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Algebraic normal form" – news · newspapers · books · scholar · JSTOR (July 2013) (Learn how and when to remove this message)

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:

• 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)}$$

Formulas written in ANF are also known as Zhegalkin polynomials and Positive Polarity (or Parity) Reed–Muller expressions (PPRM).^[1]