Algebraic normal form

<h2 id="common-uses">Common uses</h2>
<p>ANF is a <a href="/facts/Canonical_form_(Boolean_algebra)/SSb88ExW">canonical form</a>, which means that two <a href="/facts/Logically_equivalent/ysCWmsxA">logically equivalent</a> formulas will convert to the same ANF, easily showing whether two formulas are equivalent for <a href="/facts/Automated_theorem_proving/vKGvuKFI">automated theorem proving</a>. Unlike other normal forms, it can be represented as a simple list of lists of variable names—<a href="/facts/Conjunctive_normal_form/B3sY1lTW">conjunctive</a> and <a href="/facts/Disjunctive_normal_form/hsw2pRPu">disjunctive</a> normal forms also require recording whether each variable is negated or not. <a href="/facts/Negation_normal_form/A0tjapJz">Negation normal form</a> is unsuitable for determining equivalence, since on negation normal forms, equivalence does not imply equality: a ∨ ¬a is not reduced to the same thing as 1, even though they are logically equivalent.
</p><p>Putting a formula into ANF also makes it easy to identify <a href="/facts/Linearity/fChtg3KC">linear</a> functions (used, for example, in <a href="/facts/Linear-feedback_shift_register/22pktBbX">linear-feedback shift registers</a>): a linear function is one that is a sum of single literals.  Properties of nonlinear-feedback <a href="/facts/Shift_register/foHzdJft">shift registers</a> can also be deduced from certain properties of the feedback function in ANF.
</p>
<h2 id="performing-operations-within-algebraic-normal-form">Performing operations within algebraic normal form</h2>
<p>There are straightforward ways to perform the standard Boolean operations on ANF inputs in order to get ANF results.
</p><p>XOR (logical exclusive disjunction) is performed directly:
</p>
(1 ⊕ x) ⊕ (1 ⊕ x ⊕ y)
1 ⊕ x ⊕ 1 ⊕ x ⊕ y
1 ⊕ 1 ⊕ x ⊕ x ⊕ y
y
<p>NOT (logical negation) is XORing 1:<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
¬(1 ⊕ x ⊕ y)
1 ⊕(1 ⊕ x ⊕ y)
1 ⊕ 1 ⊕ x ⊕ y
x ⊕ y
<p>AND (logical conjunction) is <a href="/facts/Distributive_property/0LNBrVJl">distributed algebraically</a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
(1 ⊕ x)(1 ⊕ x ⊕ y)
1(1 ⊕ x ⊕ y) ⊕ x(1 ⊕ x ⊕ y)
(1 ⊕ x ⊕ y) ⊕ (x ⊕ x ⊕ xy)
1 ⊕ x ⊕ x ⊕ x ⊕ y ⊕ xy
1 ⊕ x ⊕ y ⊕ xy
<p>OR (logical disjunction) uses either 1 ⊕ (1 ⊕ a)(1 ⊕ b)<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> (easier when both operands have purely true terms) or a ⊕ b ⊕ ab<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> (easier otherwise):
</p>
(1 ⊕ x) + (1 ⊕ x ⊕ y)
1 ⊕ (1 ⊕ 1 ⊕ x)(1 ⊕ 1 ⊕ x ⊕ y)
1 ⊕ x(x ⊕ y)
1 ⊕ x ⊕ xy
<h2 id="converting-to-algebraic-normal-form">Converting to algebraic normal form</h2>
<p>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:
</p>
x + (y ⋅ ¬z)
x + (y(1 ⊕ z))
x + (y ⊕ yz)
x ⊕ (y ⊕ yz) ⊕ x(y ⊕ yz)
x ⊕ y ⊕ xy ⊕ yz ⊕ xyz
<h2 id="formal-representation">Formal representation</h2>
<p>ANF is sometimes described in an equivalent way:
</p>
<table><tbody><tr><td>                    f        (                  x                      1                          ,                  x                      2                          ,        …        ,                  x                      n                          )        =                      {\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=\!}  </td><td>                              a                      0                          ⊕                      {\displaystyle a_{0}\oplus \!}  </td></tr><tr><td></td><td>                              a                      1                                    x                      1                          ⊕                  a                      2                                    x                      2                          ⊕        ⋯        ⊕                  a                      n                                    x                      n                          ⊕                      {\displaystyle a_{1}x_{1}\oplus a_{2}x_{2}\oplus \cdots \oplus a_{n}x_{n}\oplus \!}  </td></tr><tr><td></td><td>                              a                      1            ,            2                                    x                      1                                    x                      2                          ⊕        ⋯        ⊕                  a                      n            −            1            ,            n                                    x                      n            −            1                                    x                      n                          ⊕                      {\displaystyle a_{1,2}x_{1}x_{2}\oplus \cdots \oplus a_{n-1,n}x_{n-1}x_{n}\oplus \!}  </td></tr><tr><td></td><td>                    ⋯        ⊕                      {\displaystyle \cdots \oplus \!}  </td></tr><tr><td></td><td>                              a                      1            ,            2            ,            …            ,            n                                    x                      1                                    x                      2                          …                  x                      n                                        {\displaystyle a_{1,2,\ldots ,n}x_{1}x_{2}\ldots x_{n}\!}  </td></tr></tbody></table>
where 
  
    
      
        
          a
          
            0
          
        
        ,
        
          a
          
            1
          
        
        ,
        …
        ,
        
          a
          
            1
            ,
            2
            ,
            …
            ,
            n
          
        
        ∈
        {
        0
        ,
        1
        
          }
          
            ∗
          
        
      
    
    {\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}}
  
 fully describes 
  
    
      
        f
      
    
    {\displaystyle f}
  
.
<h3>Recursively deriving multiargument Boolean functions</h3>
<p>There are only four functions with one argument:
</p>
<ul><li>
  
    
      
        f
        (
        x
        )
        =
        0
      
    
    {\displaystyle f(x)=0}
  
</li>
<li>
  
    
      
        f
        (
        x
        )
        =
        1
      
    
    {\displaystyle f(x)=1}
  
</li>
<li>
  
    
      
        f
        (
        x
        )
        =
        x
      
    
    {\displaystyle f(x)=x}
  
</li>
<li>
  
    
      
        f
        (
        x
        )
        =
        1
        ⊕
        x
      
    
    {\displaystyle f(x)=1\oplus x}
  
</li></ul>
<p>To represent a function with multiple arguments one can use the following equality:
</p>

f
        (
        
          x
          
            1
          
        
        ,
        
          x
          
            2
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
        =
        g
        (
        
          x
          
            2
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
        ⊕
        
          x
          
            1
          
        
        h
        (
        
          x
          
            2
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
      
    
    {\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=g(x_{2},\ldots ,x_{n})\oplus x_{1}h(x_{2},\ldots ,x_{n})}
  
, where
<ul><li>
  
    
      
        g
        (
        
          x
          
            2
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
        =
        f
        (
        0
        ,
        
          x
          
            2
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
      
    
    {\displaystyle g(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})}
  
</li>
<li>
  
    
      
        h
        (
        
          x
          
            2
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
        =
        f
        (
        0
        ,
        
          x
          
            2
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
        ⊕
        f
        (
        1
        ,
        
          x
          
            2
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
      
    
    {\displaystyle h(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})\oplus f(1,x_{2},\ldots ,x_{n})}
  
</li></ul>
<p>Indeed,
</p>
<ul><li>if 
  
    
      
        
          x
          
            1
          
        
        =
        0
      
    
    {\displaystyle x_{1}=0}
  
 then 
  
    
      
        
          x
          
            1
          
        
        h
        =
        0
      
    
    {\displaystyle x_{1}h=0}
  
 and so 
  
    
      
        f
        (
        0
        ,
        …
        )
        =
        f
        (
        0
        ,
        …
        )
      
    
    {\displaystyle f(0,\ldots )=f(0,\ldots )}
  
</li>
<li>if 
  
    
      
        
          x
          
            1
          
        
        =
        1
      
    
    {\displaystyle x_{1}=1}
  
 then 
  
    
      
        
          x
          
            1
          
        
        h
        =
        h
      
    
    {\displaystyle x_{1}h=h}
  
 and so 
  
    
      
        f
        (
        1
        ,
        …
        )
        =
        f
        (
        0
        ,
        …
        )
        ⊕
        f
        (
        0
        ,
        …
        )
        ⊕
        f
        (
        1
        ,
        …
        )
      
    
    {\displaystyle f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )}
  
</li></ul>
<p>Since both 
  
    
      
        g
      
    
    {\displaystyle g}
  
 and 
  
    
      
        h
      
    
    {\displaystyle h}
  
 have fewer arguments than 
  
    
      
        f
      
    
    {\displaystyle f}
  
 it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of 
  
    
      
        f
        (
        x
        ,
        y
        )
        =
        x
        ∨
        y
      
    
    {\displaystyle f(x,y)=x\lor y}
  
 (logical or):
</p>
<ul><li>
  
    
      
        f
        (
        x
        ,
        y
        )
        =
        f
        (
        0
        ,
        y
        )
        ⊕
        x
        (
        f
        (
        0
        ,
        y
        )
        ⊕
        f
        (
        1
        ,
        y
        )
        )
      
    
    {\displaystyle f(x,y)=f(0,y)\oplus x(f(0,y)\oplus f(1,y))}
  
</li>
<li>since 
  
    
      
        f
        (
        0
        ,
        y
        )
        =
        0
        ∨
        y
        =
        y
      
    
    {\displaystyle f(0,y)=0\lor y=y}
  
 and 
  
    
      
        f
        (
        1
        ,
        y
        )
        =
        1
        ∨
        y
        =
        1
      
    
    {\displaystyle f(1,y)=1\lor y=1}
  
</li>
<li>it follows that 
  
    
      
        f
        (
        x
        ,
        y
        )
        =
        y
        ⊕
        x
        (
        y
        ⊕
        1
        )
      
    
    {\displaystyle f(x,y)=y\oplus x(y\oplus 1)}
  
</li>
<li>by distribution, we get the final ANF: 
  
    
      
        f
        (
        x
        ,
        y
        )
        =
        y
        ⊕
        x
        y
        ⊕
        x
        =
        x
        ⊕
        y
        ⊕
        x
        y
      
    
    {\displaystyle f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy}
  
</li></ul>
<h2 id="see-also">See also</h2>

Wikimedia Commons has media related to Algebraic normal form.

<ul><li><a href="/facts/Reed%E2%80%93Muller_expansion/3s7knG9t">Reed–Muller expansion</a></li>
<li><a href="/facts/Zhegalkin_normal_form/etfekkPa">Zhegalkin normal form</a></li>
<li><a href="/facts/Boolean_function/uT7E8pqC">Boolean function</a></li>
<li><a href="/facts/Logical_graph/IMH9yIvX">Logical graph</a></li>
<li><a href="/facts/Zhegalkin_polynomial/etfekkPa">Zhegalkin polynomial</a></li>
<li><a href="/facts/Negation_normal_form/A0tjapJz">Negation normal form</a></li>
<li><a href="/facts/Conjunctive_normal_form/B3sY1lTW">Conjunctive normal form</a></li>
<li><a href="/facts/Disjunctive_normal_form/hsw2pRPu">Disjunctive normal form</a></li>
<li><a href="/facts/Karnaugh_map/saFd8oNl">Karnaugh map</a></li>
<li><a href="/facts/Boolean_ring/lgko4uqq">Boolean ring</a></li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li><a href="/facts/Ingo_Wegener/mg2dhvFt">Wegener, Ingo</a> (1987). <a href="http://ls2-www.cs.uni-dortmund.de/monographs/bluebook"><i>The complexity of Boolean functions</i></a>. <a href="/facts/Wiley-Teubner/53g3LqJc">Wiley-Teubner</a>. p. 6. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-519-02107-2.</li>
<li><a href="http://www.is.informatik.uni-duisburg.de/courses/infoa_ss03/slides/02-slides.pdf#page=34">"Presentation"</a> (PDF) (in German). <a href="/facts/University_of_Duisburg-Essen/2AGouBgx">University of Duisburg-Essen</a>. <a href="https://web.archive.org/web/20170420000915/http://www.is.informatik.uni-duisburg.de/courses/infoa_ss03/slides/02-slides.pdf#page=34">Archived</a> (PDF) from the original on 2017-04-20. Retrieved 2017-04-19.</li>
<li>Maxfield, Clive "Max" (2006-11-29). <a href="http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545">"Reed-Muller Logic"</a>. <i>Logic 101</i>. <a href="/facts/EETimes/XsxJNfCw">EETimes</a>. Part 3. <a href="https://web.archive.org/web/20170419235904/http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545">Archived</a> from the original on 2017-04-19. Retrieved 2017-04-19.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Steinbach, Bernd [in German]; Posthoff, Christian (2009). "Preface". Logic Functions and Equations - Examples and Exercises (1st ed.). Springer Science + Business Media B. V. p. xv. ISBN 978-1-4020-9594-8. LCCN 2008941076. <a href="978-1-4020-9594-8" target="_blank">978-1-4020-9594-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>WolframAlpha NOT-equivalence demonstration: ¬a = 1 ⊕ a <a href="http://www.wolframalpha.com/input/?i=simplify+1+xor+a" target="_blank">http://www.wolframalpha.com/input/?i=simplify+1+xor+a</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>WolframAlpha AND-equivalence demonstration: (a ⊕ b)(c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd <a href="http://www.wolframalpha.com/input/?i=%28a+xor+b%29+and+%28c+xor+d%29+in+anf" target="_blank">http://www.wolframalpha.com/input/?i=%28a+xor+b%29+and+%28c+xor+d%29+in+anf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>From De Morgan's laws <a href="/wiki/De_Morgan%27s_laws" target="_blank">/wiki/De_Morgan%27s_laws</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>WolframAlpha OR-equivalence demonstration: a + b = a ⊕ b ⊕ ab <a href="http://www.wolframalpha.com/input/?i=simplify+a+xor+b+xor+%28a+and+b%29" target="_blank">http://www.wolframalpha.com/input/?i=simplify+a+xor+b+xor+%28a+and+b%29</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Algebraic normal form open-in-new

Algebraic normal form