Algebraic normal form

It has been suggested that Zhegalkin polynomial and Reed–Muller expansion be merged into this article. (Discuss) Proposed since July 2024.

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]