Permutations of Boolean functions

Studies of Boolean functions

Analogous to hard and soft properties of Boolean functions, there are also hard and soft permutations.

A permutation is hard, when the domain is the infinite set of all Boolean functions.   E.g. from BF to its complement.
A permutation is soft, when the domain is the finite set of BF with a given arity.   E.g. from BF to its twin.

Each BF can be represented by its truth table or its Zhegalkin index.
Therefore, each permutation of BF can be represented by four permutations of integers.
The one between Zhegalkin indices shall be denoted by a letter. For those ^from/_to truth tables an apostrophe shall be added to its ^left/_right.

Interesting permutations of BF are often Walsh permutations. Each corresponds to an invertible binary matrix of size $2^{arity}$, called its compression matrix.
The complement is a notable permutation that is not.   (Neither is the dual, because it involves the complement.)

The following boxes show the compression matrices of some Walsh permutations for arities 3 and 4:

twin from T from Z to T to Z lector from T from Z to T to Z serrator from T from Z to T to Z reverse from T from Z to T to Z mentor from T from Z to T to Z serrator inverse from T from Z to T to Z

twin from T from Z to T to Z lector from T from Z to T to Z serrator from T from Z to T to Z reverse from T from Z to T to Z mentor from T from Z to T to Z serrator inverse from T from Z to T to Z

The compression matrices are arranged in a 2×2 array. Adjacent ^rows/_columns are swaps in the ^Sierpinski/_Zhegalkin permutation.

four compression matrices arranged in a 2×2 array S and Z denote the Sierpinski triangles. The binary pattern is that for the the serrator permutation.

upper and lower Sierpinski triangles J denotes the exchange matrix.

’P’ = Z · ’P = P’ · Z = Z · P · Z between truth tables ’P = Z · ’P’ = P · Z = Z · P’ · Z truth tables → Zhegalkin indices P’ = Z · P = ’P’ · Z = Z · ’P · Z Zhegalkin indices → truth tables P = Z · P’ = ’P · Z = Z · ’P’ · Z between Zhegalkin indices

details
These four matrix products show the relationships between adjacent matrices in the 2×2 array. Those above/below show the relationship between adjacent rows/colums. Above the matrices related to P are rotated by 90°. (Compare the image on the right.) F rotated 90° to the right is FT·J.

Zhegalkin permutation   (twin)

This is the soft permutation between twins, linking truth tables and Zhegalkin indices.
Its compression matrix is the lower Sierpinski triangle.

Sierpinski permutation   (reverse)

The reverse of a BF is that with the reversed truth table. This is a hard permutation.
The Sierpinski permutation is that between the corresponding Zhegalkin indices.
Its compression matrix is the upper Sierpinski triangle.

c:Category:8-ary Walsh functions in octeract matrix, Boolf prop/3-ary/reverse splice

from T to T from T to Z from Z to T from Z to Z

Lector and mentor

The lector permutation is hard. (The mentor permutation is almost hard.) Both are self-inverse.

Serrator

The serrator permutation is hard.

Moser permutation

The Moser permutation is hard. It swaps latitude and longitude, so it is self-inverse. The fixed points are related to those of the serrator permutation.

c:Category:Boolean functions; Moser permutation

from T to T from T to Z from Z to T from Z to Z