Editing Algebraic normal form (section)

{{merging from|Zhegalkin polynomial|Reed–Muller expansion|discuss=Talk:Algebraic normal form#Merge proposal|date=April 2025}}
{{Short description|Boolean polynomials as sums of monomials}}
{{refimprove|date=July 2013}}
{{about|Boolean algebra|other uses|Normal form (disambiguation)}}
In [[Boolean algebra]], the '''algebraic normal form''' ('''ANF'''), '''ring sum normal form''' ('''RSNF''' or '''RNF'''), ''[[Zhegalkin polynomial|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:
** <math>1</math>
** <math>0</math>
* One or more variables are combined into a term by [[logical conjunction|AND]] (<math>\and</math>), then one or more terms are combined by [[exclusive or|XOR]] (<math>\oplus</math>) together into ANF. [[Negation]]s are not permitted: <math display="block"> a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) </math>
* The previous subform with a purely true term: <math display="block"> 1 \oplus a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) </math>

{{anchor|PPRM}}Formulas written in ANF are also known as [[Zhegalkin polynomial]]s and Positive Polarity (or Parity) [[Reed–Muller code|Reed–Muller expressions]] (PPRM).<ref name="Steinbach_2009"/>