Jump to content

Mentors of Boolean functions

From Wikiversity
Studies of Boolean functions


The mentor is a rather dubious property of a truth table. But it seems surprisingly interesting.
It is found in three steps: Creating a family matrix, getting the senior nobles of its rows, and getting their prefects.
The first digits of the prefects form the mentor.

Ж 24     Ж 25

A Boolean function has a unique mentor for a given arity. (In other terms: The truth tables form a bijection.)
The mentor map forms a Walsh permutation. (Similar to the twin map, which forms the Zhegalkin permutation.)
As a BF can be denoted by its truth table (red) and by its Zhegalkin index (green), there are actually four different Walsh permutations.
In all there are six, which shall be denoted by Cyrillic letters:     Ж (Zhe),     Ч (Che), Ш (Sha),   Ю (Yu), Я (Ya),     Щ (Shcha)
(While Ж on its own is the permutation, Ж followed by an integer is a Boolean function identified by its Zhegalkin index.)

Ч = Ж·Ш·Ж = Я·Ж = Ж·Ю       map between truth tables
Ш = Ж·Ч·Ж = Ю·Ж = Ж·Я       map between Zhegalkin indices

Ю = Ж·Я·Ж = Ш·Ж = Ж·Ч       map from truth tables to Zhegalkin indices
Я = Ж·Ю·Ж = Ч·Ж = Ж·Ш       map from Zhegalkin indices to truth tables

Ч and Ш are both self-inverse. Ю and Я are inverse to each other.




The mentor is not simply a bijection between Boolean functions, but between the truth tables for a given arity.
The permutation from Zhegalkin indices to those of their n-ary mentors is Шn. The beginning of Шn+1 is Щn.
These two permutations are very similar. They are equal in the first half, and differ by exchanged neighbors in the second.
Boolean functions with Zhegalkin indices 2·n and 2·n+1 are complements. So while there is no mentor permutation between Boolean functions, there is one between pairs of complements.

The following images show the 4-ary equivalents of the 3-ary mentors illustrated above.

Walsh permutations

[edit | edit source]

The square matrix of Щ is part of a top right Sierpinki triangle. Its diagonals follow a negated XOR pattern.
That of Ш is almost the same, but with the top right entry inverted.
That of Ч is a family matrix.

2-ary

[edit | edit source]

Ч = Ш = I, the neutral permutation.     Ю = Я = Ж.     Щ = (0, 1, 2, 3,   4, 5, 6, 7,   9, 8, 11, 10,   13, 12, 15, 14)

3-ary

[edit | edit source]

4-ary

[edit | edit source]
Ж
Ч:   T to T
Ю:   T to Z
Я:   Z to T
Ш:   Z to Z
Щ

details

[edit | edit source]

Fixed points of Ч by weight

[edit | edit source]
0,  2,  4,  6, 8      sum
1, 12, 38, 12, 1       64
 
0,  2,  4,   6,   8,  10, 12, 14, 16         sum
1,  0, 60, 256, 390, 256, 60,  0,  1        1024