Mentors of Boolean functions

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

Ж 93   ↦   Ж 93

Ж 128   ↦   Ж 151

Ж 249   ↦   Ж 239

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.

Ж 24 ↦ Ж 25

Ж 93 ↦ Ж 93

Ж 128 ↦ Ж 150

Ж 249 ↦ Ж 238

Walsh permutations

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

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

3-ary

Ж:   twins

Ч:   T to T

Ю:   T to Z

Я:   Z to T

Ш:   Z to Z

Щ:   beginning of senior Ш

code

# vectors of the Walsh permutations vector_zhe = [255, 170, 204, 136, 240, 160, 192, 128] vector_che = [151, 107, 109, 158, 121, 182, 214, 233] vector_yu = [233, 189, 219, 158, 231, 182, 214, 151] vector_ya = [255, 170, 204, 119, 240, 95, 63, 233] vector_sha = [ 1, 2, 4, 9, 16, 33, 65, 151] vector_shcha = [ 1, 2, 4, 9, 16, 33, 65, 150] # sequences perm_zhe = [0, 255, 170, 85, 204, 51, 102, 153, 136, 119, 34, 221, 68, 187, 238, 17, 240, 15, 90, 165, 60, 195, 150, 105, 120, 135, 210, 45, 180, 75, 30, 225, 160, 95, 10, 245, 108, 147, 198, 57, 40, 215, 130, 125, 228, 27, 78, 177, 80, 175, 250, 5, 156, 99, 54, 201, 216, 39, 114, 141, 20, 235, 190, 65, 192, 63, 106, 149, 12, 243, 166, 89, 72, 183, 226, 29, 132, 123, 46, 209, 48, 207, 154, 101, 252, 3, 86, 169, 184, 71, 18, 237, 116, 139, 222, 33, 96, 159, 202, 53, 172, 83, 6, 249, 232, 23, 66, 189, 36, 219, 142, 113, 144, 111, 58, 197, 92, 163, 246, 9, 24, 231, 178, 77, 212, 43, 126, 129, 128, 127, 42, 213, 76, 179, 230, 25, 8, 247, 162, 93, 196, 59, 110, 145, 112, 143, 218, 37, 188, 67, 22, 233, 248, 7, 82, 173, 52, 203, 158, 97, 32, 223, 138, 117, 236, 19, 70, 185, 168, 87, 2, 253, 100, 155, 206, 49, 208, 47, 122, 133, 28, 227, 182, 73, 88, 167, 242, 13, 148, 107, 62, 193, 64, 191, 234, 21, 140, 115, 38, 217, 200, 55, 98, 157, 4, 251, 174, 81, 176, 79, 26, 229, 124, 131, 214, 41, 56, 199, 146, 109, 244, 11, 94, 161, 224, 31, 74, 181, 44, 211, 134, 121, 104, 151, 194, 61, 164, 91, 14, 241, 16, 239, 186, 69, 220, 35, 118, 137, 152, 103, 50, 205, 84, 171, 254, 1] perm_che = [0, 151, 107, 252, 109, 250, 6, 145, 158, 9, 245, 98, 243, 100, 152, 15, 121, 238, 18, 133, 20, 131, 127, 232, 231, 112, 140, 27, 138, 29, 225, 118, 182, 33, 221, 74, 219, 76, 176, 39, 40, 191, 67, 212, 69, 210, 46, 185, 207, 88, 164, 51, 162, 53, 201, 94, 81, 198, 58, 173, 60, 171, 87, 192, 214, 65, 189, 42, 187, 44, 208, 71, 72, 223, 35, 180, 37, 178, 78, 217, 175, 56, 196, 83, 194, 85, 169, 62, 49, 166, 90, 205, 92, 203, 55, 160, 96, 247, 11, 156, 13, 154, 102, 241, 254, 105, 149, 2, 147, 4, 248, 111, 25, 142, 114, 229, 116, 227, 31, 136, 135, 16, 236, 123, 234, 125, 129, 22, 233, 126, 130, 21, 132, 19, 239, 120, 119, 224, 28, 139, 26, 141, 113, 230, 144, 7, 251, 108, 253, 106, 150, 1, 14, 153, 101, 242, 99, 244, 8, 159, 95, 200, 52, 163, 50, 165, 89, 206, 193, 86, 170, 61, 172, 59, 199, 80, 38, 177, 77, 218, 75, 220, 32, 183, 184, 47, 211, 68, 213, 66, 190, 41, 63, 168, 84, 195, 82, 197, 57, 174, 161, 54, 202, 93, 204, 91, 167, 48, 70, 209, 45, 186, 43, 188, 64, 215, 216, 79, 179, 36, 181, 34, 222, 73, 137, 30, 226, 117, 228, 115, 143, 24, 23, 128, 124, 235, 122, 237, 17, 134, 240, 103, 155, 12, 157, 10, 246, 97, 110, 249, 5, 146, 3, 148, 104, 255] perm_yu = [0, 233, 189, 84, 219, 50, 102, 143, 158, 119, 35, 202, 69, 172, 248, 17, 231, 14, 90, 179, 60, 213, 129, 104, 121, 144, 196, 45, 162, 75, 31, 246, 182, 95, 11, 226, 109, 132, 208, 57, 40, 193, 149, 124, 243, 26, 78, 167, 81, 184, 236, 5, 138, 99, 55, 222, 207, 38, 114, 155, 20, 253, 169, 64, 214, 63, 107, 130, 13, 228, 176, 89, 72, 161, 245, 28, 147, 122, 46, 199, 49, 216, 140, 101, 234, 3, 87, 190, 175, 70, 18, 251, 116, 157, 201, 32, 96, 137, 221, 52, 187, 82, 6, 239, 254, 23, 67, 170, 37, 204, 152, 113, 135, 110, 58, 211, 92, 181, 225, 8, 25, 240, 164, 77, 194, 43, 127, 150, 151, 126, 42, 195, 76, 165, 241, 24, 9, 224, 180, 93, 210, 59, 111, 134, 112, 153, 205, 36, 171, 66, 22, 255, 238, 7, 83, 186, 53, 220, 136, 97, 33, 200, 156, 117, 250, 19, 71, 174, 191, 86, 2, 235, 100, 141, 217, 48, 198, 47, 123, 146, 29, 244, 160, 73, 88, 177, 229, 12, 131, 106, 62, 215, 65, 168, 252, 21, 154, 115, 39, 206, 223, 54, 98, 139, 4, 237, 185, 80, 166, 79, 27, 242, 125, 148, 192, 41, 56, 209, 133, 108, 227, 10, 94, 183, 247, 30, 74, 163, 44, 197, 145, 120, 105, 128, 212, 61, 178, 91, 15, 230, 16, 249, 173, 68, 203, 34, 118, 159, 142, 103, 51, 218, 85, 188, 232, 1] perm_ya = [0, 255, 170, 85, 204, 51, 102, 153, 119, 136, 221, 34, 187, 68, 17, 238, 240, 15, 90, 165, 60, 195, 150, 105, 135, 120, 45, 210, 75, 180, 225, 30, 95, 160, 245, 10, 147, 108, 57, 198, 40, 215, 130, 125, 228, 27, 78, 177, 175, 80, 5, 250, 99, 156, 201, 54, 216, 39, 114, 141, 20, 235, 190, 65, 63, 192, 149, 106, 243, 12, 89, 166, 72, 183, 226, 29, 132, 123, 46, 209, 207, 48, 101, 154, 3, 252, 169, 86, 184, 71, 18, 237, 116, 139, 222, 33, 96, 159, 202, 53, 172, 83, 6, 249, 23, 232, 189, 66, 219, 36, 113, 142, 144, 111, 58, 197, 92, 163, 246, 9, 231, 24, 77, 178, 43, 212, 129, 126, 233, 22, 67, 188, 37, 218, 143, 112, 158, 97, 52, 203, 82, 173, 248, 7, 25, 230, 179, 76, 213, 42, 127, 128, 110, 145, 196, 59, 162, 93, 8, 247, 182, 73, 28, 227, 122, 133, 208, 47, 193, 62, 107, 148, 13, 242, 167, 88, 70, 185, 236, 19, 138, 117, 32, 223, 49, 206, 155, 100, 253, 2, 87, 168, 214, 41, 124, 131, 26, 229, 176, 79, 161, 94, 11, 244, 109, 146, 199, 56, 38, 217, 140, 115, 234, 21, 64, 191, 81, 174, 251, 4, 157, 98, 55, 200, 137, 118, 35, 220, 69, 186, 239, 16, 254, 1, 84, 171, 50, 205, 152, 103, 121, 134, 211, 44, 181, 74, 31, 224, 14, 241, 164, 91, 194, 61, 104, 151] perm_sha = [0, 1, 2, 3, 4, 5, 6, 7, 9, 8, 11, 10, 13, 12, 15, 14, 16, 17, 18, 19, 20, 21, 22, 23, 25, 24, 27, 26, 29, 28, 31, 30, 33, 32, 35, 34, 37, 36, 39, 38, 40, 41, 42, 43, 44, 45, 46, 47, 49, 48, 51, 50, 53, 52, 55, 54, 56, 57, 58, 59, 60, 61, 62, 63, 65, 64, 67, 66, 69, 68, 71, 70, 72, 73, 74, 75, 76, 77, 78, 79, 81, 80, 83, 82, 85, 84, 87, 86, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 105, 104, 107, 106, 109, 108, 111, 110, 112, 113, 114, 115, 116, 117, 118, 119, 121, 120, 123, 122, 125, 124, 127, 126, 151, 150, 149, 148, 147, 146, 145, 144, 158, 159, 156, 157, 154, 155, 152, 153, 135, 134, 133, 132, 131, 130, 129, 128, 142, 143, 140, 141, 138, 139, 136, 137, 182, 183, 180, 181, 178, 179, 176, 177, 191, 190, 189, 188, 187, 186, 185, 184, 166, 167, 164, 165, 162, 163, 160, 161, 175, 174, 173, 172, 171, 170, 169, 168, 214, 215, 212, 213, 210, 211, 208, 209, 223, 222, 221, 220, 219, 218, 217, 216, 198, 199, 196, 197, 194, 195, 192, 193, 207, 206, 205, 204, 203, 202, 201, 200, 247, 246, 245, 244, 243, 242, 241, 240, 254, 255, 252, 253, 250, 251, 248, 249, 231, 230, 229, 228, 227, 226, 225, 224, 238, 239, 236, 237, 234, 235, 232, 233] perm_shcha = [0, 1, 2, 3, 4, 5, 6, 7, 9, 8, 11, 10, 13, 12, 15, 14, 16, 17, 18, 19, 20, 21, 22, 23, 25, 24, 27, 26, 29, 28, 31, 30, 33, 32, 35, 34, 37, 36, 39, 38, 40, 41, 42, 43, 44, 45, 46, 47, 49, 48, 51, 50, 53, 52, 55, 54, 56, 57, 58, 59, 60, 61, 62, 63, 65, 64, 67, 66, 69, 68, 71, 70, 72, 73, 74, 75, 76, 77, 78, 79, 81, 80, 83, 82, 85, 84, 87, 86, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 105, 104, 107, 106, 109, 108, 111, 110, 112, 113, 114, 115, 116, 117, 118, 119, 121, 120, 123, 122, 125, 124, 127, 126, 150, 151, 148, 149, 146, 147, 144, 145, 159, 158, 157, 156, 155, 154, 153, 152, 134, 135, 132, 133, 130, 131, 128, 129, 143, 142, 141, 140, 139, 138, 137, 136, 183, 182, 181, 180, 179, 178, 177, 176, 190, 191, 188, 189, 186, 187, 184, 185, 167, 166, 165, 164, 163, 162, 161, 160, 174, 175, 172, 173, 170, 171, 168, 169, 215, 214, 213, 212, 211, 210, 209, 208, 222, 223, 220, 221, 218, 219, 216, 217, 199, 198, 197, 196, 195, 194, 193, 192, 206, 207, 204, 205, 202, 203, 200, 201, 246, 247, 244, 245, 242, 243, 240, 241, 255, 254, 253, 252, 251, 250, 249, 248, 230, 231, 228, 229, 226, 227, 224, 225, 239, 238, 237, 236, 235, 234, 233, 232]

Place 199 can be used to check, if the permutations are correct:        Ж(199) = 217        Ч(199) = 174    Ю(199) = 206    Я(199) = 79    Ш(199) = 209        Щ(199) = 208

4-ary

Ж

Ч:   T to T

Ю:   T to Z

Я:   Z to T

Ш:   Z to Z

Щ

relationship between the matrix patterns
The red family matrix has the pattern of Ч. The green matrix shows the twins of the red rows, and has the pattern of Ю and Я. The blue matrix shows the twins of the green columns, and has the pattern of Ш.

code

# vectors of the Walsh permutations vector_zhe = [65535, 43690, 52428, 34952, 61680, 41120, 49344, 32896, 65280, 43520, 52224, 34816, 61440, 40960, 49152, 32768] vector_che = [ 6015, 11199, 19935, 36591, 29175, 45819, 54525, 59646, 32535, 48939, 57165, 61326, 63345, 64434, 64980, 65256] vector_yu = [59521, 48321, 55969, 40945, 59017, 47053, 55211, 38654, 59497, 48253, 55931, 40814, 58991, 46970, 55164, 38504] vector_ya = [65535, 43690, 52428, 30583, 61680, 24415, 16191, 5654, 65280, 22015, 13311, 4454, 4095, 1370, 828, 65256] vector_sha = [ 1, 2, 4, 9, 16, 33, 65, 150, 256, 513, 1025, 2310, 4097, 8466, 16660, 38504] vector_shcha = [ 1, 2, 4, 9, 16, 33, 65, 150, 256, 513, 1025, 2310, 4097, 8466, 16660, 38505]

details

Fixed points of Ч by weight

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