Algebraic normal form

Studies of Boolean functions

Ж

ANF   matrix   twins

noble   gentle

smallest Zhegalkin index

The algebraic normal form (ANF) is a canonical normal form of a Boolean function.

Variadic XOR (left) and AND (right)

From ANF to truth table

From truth table to ANF

It is a XOR formula of AND formulas, like this:

$a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)$

Here it shall be abbreviated like this:

${\Bigl [}\left(a\right),\left(b\right),\left(a,b\right),\left(a,b,c\right){\Bigr ]}$

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

The empty XOR is false:

${\Bigl [}~{\Bigr ]}~~\iff ~~0$

XOR containing empty AND is true:

${\Bigl [}\left(~\right){\Bigr ]}~~\iff ~~1$

XOR containing unary AND is an atomic statement:

${\Bigl [}\left(a\right){\Bigr ]}~~\iff ~~a$

The presence of empty AND works as a negator:

${\Bigl [}\left(~\right),\left(a\right){\Bigr ]}~~\iff ~~\neg a$

So the negation of the introductory example is this:

${\Bigl [}\left(~\right),\left(a\right),\left(b\right),\left(a,b\right),\left(a,b,c\right){\Bigr ]}$

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$	${\Bigl [}~{\Bigr ]}$	${\Bigl \{}~{\Bigl \}}$	${\Bigl \{}~{\Bigl \}}$	empty sum 0	$0$
$1$	${\Bigl [}\left(~\right){\Bigr ]}$	${\Bigl \{}\{~\}{\Bigl \}}$	${\Bigl \{}0{\Bigl \}}$	$2^{0}$	$1$
$a$	${\Bigl [}\left(a\right){\Bigr ]}$	${\Bigl \{}\{0\}{\Bigl \}}$	${\Bigl \{}1{\Bigl \}}$	$2^{1}$	$2$
$\neg a$	${\Bigl [}\left(~\right),\left(a\right){\Bigr ]}$	${\Bigl \{}\{~\},\{0\}{\Bigl \}}$	${\Bigl \{}0,1{\Bigl \}}$	$2^{0}+2^{1}$	$3$
$b$	${\Bigl [}\left(b\right){\Bigr ]}$	${\Bigl \{}\{1\}{\Bigl \}}$	${\Bigl \{}2{\Bigl \}}$	$2^{2}$	$4$
$\neg b$	${\Bigl [}\left(~\right),\left(b\right){\Bigr ]}$	${\Bigl \{}\{~\},\{1\}{\Bigl \}}$	${\Bigl \{}0,2{\Bigl \}}$	$2^{0}+2^{2}$	$5$
$a\oplus b$	${\Bigl [}\left(a\right),\left(b\right){\Bigr ]}$	${\Bigl \{}\{0\},\{1\}{\Bigl \}}$	${\Bigl \{}1,2{\Bigl \}}$	$2^{1}+2^{2}$	$6$
$a\leftrightarrow b$	${\Bigl [}\left(~\right),\left(a\right),\left(b\right){\Bigr ]}$	${\Bigl \{}\{~\},\{0\},\{1\}{\Bigl \}}$	${\Bigl \{}0,1,2{\Bigl \}}$	$2^{0}+2^{1}+2^{2}$	$7$
$a\land b$	${\Bigl [}\left(a,b\right){\Bigr ]}$	${\Bigl \{}\{0,1\}{\Bigl \}}$	${\Bigl \{}3{\Bigl \}}$	$2^{3}$	$8$
$\neg a\lor \neg b$	${\Bigl [}\left(~\right),\left(a,b\right){\Bigr ]}$	${\Bigl \{}\{~\},\{0,1\}{\Bigl \}}$	${\Bigl \{}0,3{\Bigl \}}$	$2^{0}+2^{3}$	$9$
$a\land \neg b$	${\Bigl [}\left(a\right),\left(a,b\right){\Bigr ]}$	${\Bigl \{}\{0\},\{0,1\}{\Bigl \}}$	${\Bigl \{}1,3{\Bigl \}}$	$2^{1}+2^{3}$	$10$
$\neg a\lor b$	${\Bigl [}\left(~\right),\left(a\right),\left(a,b\right){\Bigr ]}$	${\Bigl \{}\{~\},\{0\},\{0,1\}{\Bigl \}}$	${\Bigl \{}0,1,3{\Bigl \}}$	$2^{0}+2^{1}+2^{3}$	$11$
$\neg a\land b$	${\Bigl [}\left(b\right),\left(a,b\right){\Bigr ]}$	${\Bigl \{}\{1\},\{0,1\}{\Bigl \}}$	${\Bigl \{}2,3{\Bigl \}}$	$2^{2}+2^{3}$	$12$
$a\lor \neg b$	${\Bigl [}\left(~\right),\left(b\right),\left(a,b\right){\Bigr ]}$	${\Bigl \{}\{~\},\{1\},\{0,1\}{\Bigl \}}$	${\Bigl \{}0,2,3{\Bigl \}}$	$2^{0}+2^{2}+2^{3}$	$13$
$a\lor b$	${\Bigl [}\left(a\right),\left(b\right),\left(a,b\right){\Bigr ]}$	${\Bigl \{}\{0\},\{1\},\{0,1\}{\Bigl \}}$	${\Bigl \{}1,2,3{\Bigl \}}$	$2^{1}+2^{2}+2^{3}$	$14$
$\neg a\land \neg b$	${\Bigl [}\left(~\right),\left(a\right),\left(b\right),\left(a,b\right){\Bigr ]}$	${\Bigl \{}\{~\},\{0\},\{1\},\{0,1\}{\Bigl \}}$	${\Bigl \{}0,1,2,3{\Bigl \}}$	$2^{0}+2^{1}+2^{2}+2^{3}$	$15$
$\left(\neg a\lor \neg b\lor \neg c\right)\land \left(a\lor b\right)$	${\Bigl [}\left(a\right),\left(b\right),\left(a,b\right),\left(a,b,c\right){\Bigr ]}$	${\Bigl \{}\{0\},\{1\},\{0,1\},\{0,1,2\}{\Bigl \}}$	${\Bigl \{}1,2,3,7{\Bigl \}}$	$2^{1}+2^{2}+2^{3}+2^{7}$	$142$
$\left(a\land b\land c\right)\lor \left(\neg a\land \neg b\right)$	${\Bigl [}\left(~\right),\left(a\right),\left(b\right),\left(a,b\right),\left(a,b,c\right){\Bigr ]}$	${\Bigl \{}\{~\},\{0\},\{1\},\{0,1\},\{0,1,2\}{\Bigl \}}$	${\Bigl \{}0,1,2,3,7{\Bigl \}}$	$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 rational 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) ${\tfrac {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