Content deleted Content added
Added section on ANF |
More on the ANF, neatened formula, algebraic degree. |
||
Line 13:
A boolean function can be written uniquely as a sum ([[Exclusive or|XOR]]) of products ([[Logical_conjunction|AND]]). This is known as the [[Algebraic Normal Form]] (ANF).
<math>\begin{matrix} f(x_1, x_2, \ldots , x_n) = & a_0 \oplus \\ & a_1x_1 \oplus a_2x_2 \oplus \ldots \oplus a_nx_n \oplus \\ & a_{1,2}x_1x_2 \oplus a_{n-1,n}x_{n-1}x_n \oplus \\ & \ldots \\ & \oplus a_{1,2,\ldots,n}x_1x_2\ldots x_n \end{matrix}</math>
The values of the sequence <math>a_0,a_1,\ldots,a_{1,2,\ldots,n}</math> can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of <math>x_i</math> that appear in a product term. Thus <math>f(x_1,x_2,x_3) = x_1 \oplus x_3</math> has degree 1 (linear), whereas <math>f(x_1,x_2,x_3) = x_1 \oplus x_1x_2x_3</math> has degree 3 (cubic).
==See also==
| |||