Algebraic normal form

The Template:W (ANF) is a Template:W of a Boolean function.

It is a Template:W formula of Template:W formulas, like this:

$a\oplus b\oplus (a\wedge b)\oplus (a\wedge b\wedge c)$

Here it shall be abbreviated like this:

$[\left(a\right),\left(b\right),(a,b),(a,b,c)]$

Both operators are Template:W, i.e. they can have any number of arguments, including none or one.
XOR without arguments is false (Template:W 0). AND without arguments is true (Template:W 1).

The empty XOR is false:

$\left[\right]⟺0$

XOR containing empty AND is true:

$\left[\left(\right)\right]⟺1$

XOR containing unary AND is an atomic statement:

$\left[\left(a\right)\right]⟺a$

The presence of empty AND works as a Template:W:

$[\left(\right),\left(a\right)]⟺\mathrm{\neg }a$

So the negation of the introductory example is this:

$[\left(\right),\left(a\right),\left(b\right),(a,b),(a,b,c)]$

Each AND formula corresponds to a set of integers, which can be interpreted as a binary number.
Thus each XOR formula also corresponds to a set of integers, which can also be interpreted as a binary number.

$0$	$\left[\right]$	$\left\{\right\}$	$\left\{\right\}$	empty sum 0	$0$
$1$	$\left[\left(\right)\right]$	$\{\{\}\}$	$\left\{0\right\}$	$2^0$	$1$
$a$	$\left[\left(a\right)\right]$	$\{\{0\}\}$	$\left\{1\right\}$	$2^1$	$2$
$\mathrm{\neg }a$	$[\left(\right),\left(a\right)]$	$\{\{\},\{0\}\}$	$\{0,1\}$	$2^0+2^1$	$3$
$b$	$\left[\left(b\right)\right]$	$\{\{1\}\}$	$\left\{2\right\}$	$2^2$	$4$
$\mathrm{\neg }b$	$[\left(\right),\left(b\right)]$	$\{\{\},\{1\}\}$	$\{0,2\}$	$2^0+2^2$	$5$
$a\oplus b$	$[\left(a\right),\left(b\right)]$	$\{\{0\},\{1\}\}$	$\{1,2\}$	$2^1+2^2$	$6$
$a\leftrightarrow b$	$[\left(\right),\left(a\right),\left(b\right)]$	$\{\{\},\{0\},\{1\}\}$	$\{0,1,2\}$	$2^0+2^1+2^2$	$7$
$a\wedge b$	$\left[(a,b)\right]$	$\{\{0,1\}\}$	$\left\{3\right\}$	$2^3$	$8$
$\mathrm{\neg }a\vee \mathrm{\neg }b$	$[\left(\right),(a,b)]$	$\{\{\},\{0,1\}\}$	$\{0,3\}$	$2^0+2^3$	$9$
$a\wedge \mathrm{\neg }b$	$[\left(a\right),(a,b)]$	$\{\{0\},\{0,1\}\}$	$\{1,3\}$	$2^1+2^3$	$10$
$\mathrm{\neg }a\vee b$	$[\left(\right),\left(a\right),(a,b)]$	$\{\{\},\{0\},\{0,1\}\}$	$\{0,1,3\}$	$2^0+2^1+2^3$	$11$
$\mathrm{\neg }a\wedge b$	$[\left(b\right),(a,b)]$	$\{\{1\},\{0,1\}\}$	$\{2,3\}$	$2^2+2^3$	$12$
$a\vee \mathrm{\neg }b$	$[\left(\right),\left(b\right),(a,b)]$	$\{\{\},\{1\},\{0,1\}\}$	$\{0,2,3\}$	$2^0+2^2+2^3$	$13$
$a\vee b$	$[\left(a\right),\left(b\right),(a,b)]$	$\{\{0\},\{1\},\{0,1\}\}$	$\{1,2,3\}$	$2^1+2^2+2^3$	$14$
$\mathrm{\neg }a\wedge \mathrm{\neg }b$	$[\left(\right),\left(a\right),\left(b\right),(a,b)]$	$\{\{\},\{0\},\{1\},\{0,1\}\}$	$\{0,1,2,3\}$	$2^0+2^1+2^2+2^3$	$15$
$(\mathrm{\neg }a\vee \mathrm{\neg }b\vee \mathrm{\neg }c)\wedge (a\vee b)$	$[\left(a\right),\left(b\right),(a,b),(a,b,c)]$	$\{\{0\},\{1\},\{0,1\},\{0,1,2\}\}$	$\{1,2,3,7\}$	$2^1+2^2+2^3+2^7$	$142$
$(a\wedge b\wedge c)\vee (\mathrm{\neg }a\wedge \mathrm{\neg }b)$	$[\left(\right),\left(a\right),\left(b\right),(a,b),(a,b,c)]$	$\{\{\},\{0\},\{1\},\{0,1\},\{0,1,2\}\}$	$\{0,1,2,3,7\}$	$2^0+2^1+2^2+2^3+2^7$	$143$

In short, there is a bijection between the non-negative integers and algebraic normal forms.
While the truth tables for a given arity can be interpreted as integers, truth tables in general can only be assigned Template:W values between 0 and 1.
The ANF allows to assign every Boolean function (regardless of its arity) a unique integer, which shall be called its Zhegalkin index.

It has the interesting property, that its parity corresponds to the just mentioned fraction:
Boolean functions with an even (odd) Zhegalkin index have a rational value below (above) $\frac{1}{2}$.
Here is a list of examples: v:Studies of Euler diagrams/list

The Zhegalkin indices of Boolean functions in the same permutation equivalence class have the same binary weight.

For a specific arity each Boolean function can be interpreted as an integer.
So the map from integers to Boolean functions becomes a map from integers to integers, which is the Zhegalkin permutation.

See also: Zhegalkin matrix