Editing Algebraic normal form (section)

== 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>