Editing Algebraic normal form

{{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"/>

== Common uses ==
ANF is a [[canonical form (Boolean algebra)|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 normal form|conjunctive]] and [[disjunctive normal form|disjunctive]] normal forms also require recording whether each variable is negated or not. [[Negation normal form]] is unsuitable for determining equivalence, since on negation normal forms, equivalence does not imply equality: a &or; ¬a is not reduced to the same thing as 1, even though they are logically equivalent.

Putting a formula into ANF also makes it easy to identify [[linearity|linear]] functions (used, for example, in [[linear-feedback shift register]]s): a linear function is one that is a sum of single literals.  Properties of nonlinear-feedback [[shift register]]s can also be deduced from certain properties of the feedback function in ANF.

== Performing operations within algebraic normal form ==
There are straightforward ways to perform the standard Boolean operations on ANF inputs in order to get ANF results.

XOR (logical exclusive disjunction) is performed directly:
: ({{fontcolor|red|1 ⊕ x}}) ⊕ ({{fontcolor|green|1 ⊕ x ⊕ y}})
: {{fontcolor|red|1 ⊕ x}} ⊕ {{fontcolor|green|1 ⊕ x ⊕ y}}
: 1 ⊕ 1 ⊕ x ⊕ x ⊕ y
: y

NOT (logical negation) is XORing 1:<ref name="not-equiv">[http://www.wolframalpha.com/input/?i=simplify+1+xor+a WolframAlpha NOT-equivalence demonstration: ¬a = 1 ⊕ a]</ref>
: {{fontcolor|red|¬}}{{fontcolor|green|(1 ⊕ x ⊕ y)}}
: {{fontcolor|red|1 ⊕ }}{{fontcolor|green|(1 ⊕ x ⊕ y)}}
: 1 ⊕ 1 ⊕ x ⊕ y
: x ⊕ y

AND (logical conjunction) is [[distributive property|distributed algebraically]]<ref name="and-equiv">[http://www.wolframalpha.com/input/?i=%28a+xor+b%29+and+%28c+xor+d%29+in+anf WolframAlpha AND-equivalence demonstration: (a ⊕ b)(c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd]</ref>
: ({{fontcolor|red|1}} ⊕ {{fontcolor|red|x}}){{fontcolor|green|(1 ⊕ x ⊕ y)}}
: {{fontcolor|red|1}}{{fontcolor|green|(1 ⊕ x ⊕ y)}} ⊕ {{fontcolor|red|x}}{{fontcolor|green|(1 ⊕ x ⊕ y)}}
: (1 ⊕ x ⊕ y) ⊕ (x ⊕ x ⊕ xy)
: 1 ⊕ x ⊕ x ⊕ x ⊕ y ⊕ xy
: 1 ⊕ x ⊕ y ⊕ xy

OR (logical disjunction) uses either 1 ⊕ (1 ⊕ a)(1 ⊕ b)<ref name="or-demorgans">From [[De Morgan's laws]]</ref> (easier when both operands have purely true terms) or a ⊕ b ⊕ ab<ref name="or-equiv">[http://www.wolframalpha.com/input/?i=simplify+a+xor+b+xor+%28a+and+b%29 WolframAlpha OR-equivalence demonstration: a + b = a ⊕ b ⊕ ab]</ref> (easier otherwise):
: ({{fontcolor|red|1 ⊕ x}}) + ({{fontcolor|green|1 ⊕ x ⊕ y}})
: 1 ⊕ (1 ⊕ {{fontcolor|red|1 ⊕ x}})(1 ⊕ {{fontcolor|green|1 ⊕ x ⊕ y}})
: 1 ⊕ x(x ⊕ y)
: 1 ⊕ x ⊕ xy

== Converting to algebraic normal form ==
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. For example:
: x + (y &sdot; ¬z)
: x + (y(1 ⊕ z))
: x + (y ⊕ yz)
: x ⊕ (y ⊕ yz) ⊕ x(y ⊕ yz)
: x ⊕ y ⊕ xy ⊕ yz ⊕ xyz

== Formal representation ==
ANF is sometimes described in an equivalent way:
:{| cellpadding="4"
|-
|<math>f(x_1, x_2, \ldots, x_n) = \!</math>
|<math>a_0 \oplus \!</math>
|-
|
|<math>a_1x_1 \oplus a_2x_2 \oplus \cdots \oplus a_nx_n \oplus \!</math>
|-
|
|<math>a_{1,2}x_1x_2 \oplus \cdots \oplus a_{n-1,n}x_{n-1}x_n \oplus \!</math>
|-
|
|<math>\cdots \oplus \!</math>
|-
|
|<math>a_{1,2,\ldots,n}x_1x_2\ldots x_n \!</math>
|}
:where <math>a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^*</math> fully describes <math>f</math>.

=== Recursively deriving multiargument Boolean functions ===
There are only four functions with one argument:
* <math>f(x)=0</math>
* <math>f(x)=1</math>
* <math>f(x)=x</math>
* <math>f(x)=1 \oplus x</math>

To represent a function with multiple arguments one can use the following equality:
: <math>f(x_1,x_2,\ldots,x_n) = g(x_2,\ldots,x_n) \oplus x_1 h(x_2,\ldots,x_n)</math>, where
:* <math>g(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n)</math>
:* <math>h(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) \oplus f(1,x_2,\ldots,x_n)</math>

Indeed,
* if <math>x_1=0</math> then <math>x_1 h = 0</math> and so <math>f(0,\ldots) = f(0,\ldots)</math>
* if <math>x_1=1</math> then <math>x_1 h = h</math> and so <math>f(1,\ldots) = f(0,\ldots) \oplus f(0,\ldots) \oplus f(1,\ldots)</math>

Since both <math>g</math> and <math>h</math> have fewer arguments than <math>f</math> it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of <math>f(x,y)= x \lor y</math> (logical or):
* <math>f(x,y) = f(0,y) \oplus x(f(0,y) \oplus f(1,y))</math>
* since <math>f(0,y)=0 \lor y = y</math> and <math>f(1,y)=1 \lor y = 1</math>
* it follows that <math>f(x,y) = y \oplus x (y \oplus 1)</math>
* by distribution, we get the final ANF: <math>f(x,y) = y \oplus x y \oplus x = x \oplus y \oplus x y</math>

==See also==
{{Commonscat|Algebraic normal form}}
* [[Reed–Muller expansion]]
* [[Zhegalkin normal form]]
* [[Boolean function]]
* [[Logical graph]]
* [[Zhegalkin polynomial]]
* [[Negation normal form]]
* [[Conjunctive normal form]]
* [[Disjunctive normal form]]
* [[Karnaugh map]]
* [[Boolean ring]]

== References ==
{{reflist|refs=
<ref name="Steinbach_2009">{{cite book |author-first1=Bernd |author-last1=Steinbach |author-link1=:de:Bernd Steinbach |author-first2=Christian |author-last2=Posthoff |title=Logic Functions and Equations - Examples and Exercises |chapter=Preface |publisher=[[Springer Science + Business Media B. V.]] |date=2009 |edition=1st |isbn=978-1-4020-9594-8 |lccn=2008941076 |page=xv}}</ref>
}}

== Further reading==
* {{cite book |author-first=Ingo |author-last=Wegener |authorlink = Ingo Wegener|title=The complexity of Boolean functions |publisher=[[Wiley-Teubner]] |date=1987 |isbn=3-519-02107-2 |page=6 |url=http://ls2-www.cs.uni-dortmund.de/monographs/bluebook}}
* {{cite web |title=Presentation |publisher=[[University of Duisburg-Essen]] |language=German |url=http://www.is.informatik.uni-duisburg.de/courses/infoa_ss03/slides/02-slides.pdf#page=34 |access-date=2017-04-19 |url-status=live |archive-url=https://web.archive.org/web/20170420000915/http://www.is.informatik.uni-duisburg.de/courses/infoa_ss03/slides/02-slides.pdf#page=34 |archive-date=2017-04-20}}
* {{cite web |title=Reed-Muller Logic |work=Logic 101 |at=Part 3 |author-first=Clive "Max" |author-last=Maxfield |date=2006-11-29 |publisher=[[EETimes]] |url=http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545 |access-date=2017-04-19 |url-status=live |archive-url=https://web.archive.org/web/20170419235904/http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545 |archive-date=2017-04-19}}

[[Category:Boolean algebra]]
[[Category:Normal forms (logic)]]

[[ru:Полином Жегалкина]]
{{Normal forms in logic}}