Smallest Zhegalkin index

Studies of Boolean functions

dummy

Ж

ANF   matrix   twins

noble   gentle

smallest Zhegalkin index

An equivalence class of Boolean functions often needs a representative, i.e. a unique function that can be calculated from any member.
The one with the smallest Zhegalkin index seems like a natural choice.

The most important equivalence classes are probably those based on negation (families), permutation (factions) or both (clans).

Euler diagrams of example functions
medusa and farofe Farofe is true in the same places as medusa, except place 3. nisuke and nitako Nitako is true in the same places as nisuke, except place 5. totoro and levana These two functions share most places. But in totoro 6 is true, while in levana 7 is true.

Families

Each of these images shows a red family matrix.
The rows of the green matrix are the twins of the red rows.
The columns of the blue matrix are the twins of the green columns.
While the green matrix does not have an obvious pattern, that of its blue twin is very simple:

• Its possible entries are those of a top left Sierpinski triangle.
• The entries within that are equal to that of the top row in the same anti-diagonal.
• The top row is equal to that of the green matrix.

main diagonal and both diagonals

medusa and farofe

nisuke and nitako

totoro and levana

Factions

The rows of these 24×16 matrices are Boolean functions in the same faction. (Compare this matrix.)
While there is a difference between red and green matrices for families, this is not the case for factions. Both matrices describe factions. (It does not matter, which is red or green.)
This means, that not just functions, but whole factions can be described as each others Zhegalkin twins.

common
medusa and farofe nisuke and nitako totoro and levana

noble
Ж 2176 Ж 11464

Clans

medusa
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 weight 1 1 2 4 8 weight 2 3 5 6 12 10 9 weight 3 7 11 13 14

farofe
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 weight 1 1 2 4 8 weight 2 3 5 6 12 10 9 weight 3 7 11 13 14

nisuke
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 weight 1 1 2 4 8 weight 2 3 5 6 12 10 9 weight 3 7 11 13 14

nitako
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 weight 1 1 2 4 8 weight 2 3 5 6 12 10 9 weight 3 7 11 13 14

totoro
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 weight 1 1 2 4 8 weight 2 3 5 6 12 10 9 weight 3 7 11 13 14

levana
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 weight 1 1 2 4 8 weight 2 3 5 6 12 10 9 weight 3 7 11 13 14