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 a r i t y {\displaystyle 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  |  |
reverse
|  | from T  | from Z

|
|

to T  |  |
to Z  |  |
serrator
|  | from T  | from Z

|
|

to T  |  |
to Z  |  |
lector
|  | from T  | from Z

|
|

to T  |  |
to Z  |  |
mentor
|  | from T  | from Z

|
|

to T  |  |
to Z  |  |

| twin
|  | from T  | from Z

|
|

to T  |  |
to Z  |  |
reverse
|  | from T  | from Z

|
|

to T  |  |
to Z  |  |
serrator
|  | from T  | from Z

|
|

to T  |  |
to Z  |  |
lector
|  | from T  | from Z

|
|

to T  |  |
to Z  |  |
mentor
|  | 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)

[edit | edit source]

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

## Sierpinski permutation  (reverse)

[edit | edit source]

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

[edit | edit source]

The lector permutation is hard. (The mentor permutation is almost hard.)

## Serrator

[edit | edit source]

The serrator permutation is hard.