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).

Families

edit

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.
medusa and farofe
 
 

Factions

edit

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
 
 

Clans

edit