Studies of Boolean functions

dummy

Ж
ANF   matrix   twins
noble   gentle
smallest Zhegalkin index
2-ary functions ordered in a Hasse diagram. Truth tables in red, Zhegalkin indices in green.

Zhegalkin twins are truth tables of the same length, that correspond to a column and its index in a finite Zhegalkin matrix.
For a given arity, one can also describe two integers or Boolean functions as Zhegalkin twins. (For truth tables the arity is implied by their length.)

Calculation

edit

These images show how one truth table is calculated from the other. (One could describe it as a bitwise XOR of variadic ANDs.)
Here the red patterns are meant as Boolean functions, while the green patterns are meant as their Zhegalkin indices.

The red pattern represents a truth table, which continues periodically. The green bit-pattern represents an integer, and continues with zeros.

The least significant green bit of the green pattern is on top. That of the red pattern is on the left.
One can see, that the LSBs of both patterns are equal. Also that changing the green LSB will change all red bits.

 
Ж 143 to TT 145   (reverse)
 
Ж 22 to TT 150   (reverse)
 
Ж 30 to TT 30

Equivalence classes

edit

See Smallest Zhegalkin index for details.

farofe
 
Family matrix of farofe in red. Green rows are twins of red rows, and blue columns are twins of green columns.
 
Faction matrix of farofe in red. Green rows are twins of red rows. The resulting matrix also describes a faction. The twin relationship is not just one between Boolean functions, but between factions.
 
Patrons of the twins on the left. This is a noble faction, i.e. it is its own twin. (This is a faction of noble Boolean functions, and each of them is its own twin.)

Selections by equal place

edit

These images show half the columns of the 8×256 matrix. They are selected by the truth value of one row.   (There are also images for other rows, e.g. false rows in the lower matrix)
The columns of the upper long matrix are to be understood as Zhegalkin indeces, and the columns below as truth tables.
The rows are linear Boolean functions, and the small matrices on the left show their Walsh indices. (If the row is a negated Walsh function, its first entry is true.)
The file with even/evil functions shows the complements of the odd/odious functions. (Complements have opposite parity as well as opposite depravity.)

depravity
evil

The weight of the Zhegalkin index is even. The last place of the truth table is false.
 


Variadic logical connectives

edit

The pairs of matrices shown in the following boxes are twins. This is shorthand for the fact, that their rows are Zhegalkin twins. (Compare Zhegalkin matrix.)

The left side of each pair shows the truth tables of variadic logical connectives. (Compare these 16×16 matrices, which also show the arguments.)

Some of them are unusual, and have unusual names:
SAND (a.k.a. minimal negation operator) could be called all but one. Its reflection SNOR could be called no but one.
The name XOR is used for the parity function. The reflection of not XOR is called XAND. (Because the reflection of not OR is AND.)
GAND is SAND extended by AND. Its reflection GNOR is SNOR extended by not OR.
In ESAND and OSAND this extension happens only for an even or odd number of arguments. Their reflections are ESNOR and OSNOR.
EQ makes sense as generalization of the biconditional, and is true if all arguments have the same truth value (but not if there are no arguments).

The right side of each pair is a lower triangular matrix. Its entries are part of the Sierpinski triangle, which is the twin of not OR.

Each of these triangles is symmetric to another one (in two cases to itself). Only the triangle rows are symmetric (not the matrix rows).
Pairs with symmetric triangles are in the same box, e.g.:    XOR / OSAND,    SNOR / OSNOR

Some triangles are relative complements in the Sierpinski triangle:    TRUE / OR,    AND / EQ,    GNOR / SNOR,    OSNOR / ESNOR