Equivalence classes of Boolean functions
There are various ways that Boolean functions can be ordered in equivalence classes by common properties.
Some appear quite often, and are given all kinds of quirky names by all kinds of authors - including my humble self.
Small[edit]
Small equivalence class (sec)[edit]
It could also be called hyperrectangular equivalence class, as the permutations are from Z_{2}^{arity}.
Functions belong to the same sec when they can be expressed by each other by negating arguments.
The 2-ary functions in this table belong to the same sec when they appear in the same row,
e.g. NAND , converse implication , implication and OR .
Each sec can be denoted by the smallest number corresponding to one of its functions, which leads to A227722 = 0, 1, 3, 5, 6, 7, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 51, 53, 54, 55, 60, 61, 63, 85, 86, 87, 90, 91, 95, 102, 103, 105, 107, 111, 119, 123, 125, 126, 127, 255...
This is a sec of 3-ary Boolean functions, containing 8 functions:
sec matrix[edit]
- Category on Commons: Sec matrices of Boolean functions
A sec matrix is a symmetric binary square matrix of size 2^n, that has the n-ary Boolean functions in one sec as its rows.
It is a bitwise XOR (or nimber addition) table with a set of numbers replaced by ones, and all other numbers replaced by zeros.
The example files shown in this article contain 8x8 sec matrices.
Greater small equivalence class (gsec)[edit]
Every sec has a complement. Together the complements form a gsec.
This is a gsec, containing 16 functions:
Some secs are self complementary, an thus complete gsecs on their own, e.g. this one.
Greatest small equivalence class (ggsec)[edit]
The gsec shown above is related to another one.
Each function in one gsec is the half-complement of a function in the other one.
W.l.o.g. two functions shall be called half-complements when the left halves of their vectors are equal and the right halves are complements.
Together they form the following ggsec, containing 32 functions:
Some gsecs are complete ggsecs on their own. Three secs are even complete ggsecs, e.g. this one.
Big[edit]
Big equivalence class (bec)[edit]
It could also be called hyperoctahedral equivalence class, as the permutations are from the symmetry group of the arity-cube.
Functions belong to the same bec, when they can be expressed by each other by negating and by permuting arguments.
Graphically, permuting arguments corresponds to turning and reflecting Venn diagrams.
Each bec can be denoted by the smallest number corresponding to one of its functions, which leads to A227723 = 0, 1, 3, 6, 7, 15, 22, 23, 24, 25, 27, 30, 31, 60, 61, 63, 105, 107, 111, 126, 127, 255...
These secs form a bec (denoted by the number 7 in the above sequence), containing 24 functions:
Some secs are complete becs, e.g. this or this one.
These 24 secs of 4-ary Boolean functions form a bec, containing 16 * 24 = 384 functions:
File:1111 0000 1001 1100 Boolean function 16*24.svg
There are 2, 3, 6, 22, 402 ... becs of 0, 1, 2, 3, 4 ... -ary Boolean functions ( A000616).
Greater big equivalence class (gbec)[edit]
Every bec has a complement. Together they form a gbec.
This is a gbec, containing 48 functions:
This sec is a complete bec, and even a complete gbec: File:Boolean functions like 1110 1000.svg
These two becs of 4-ary Boolean functions are complements, and thus form a gbec, containing 2 * 16 * 24 = 768 functions:
File:1111 0000 1001 1100 Boolean function 16*24.svg
File:1100 0110 1111 0000 Boolean function 16*24.svg
This bec is self complementary, and thus a complete gbec:
File:1110 0011 1100 0001 Boolean function 16*24.svg
Greatest big equivalence class (ggbec)[edit]
The gbec shown above contains the functions of 3 gsecs (displayed in the same columns).
Adding all the functions of the corresponding ggsecs gives ggbec O, containing 128 functions.
Walsh[edit]
Binary Walsh spectrum[edit]
The Walsh spectrum of a Boolean function is the product of its binary string with a Walsh matrix.
The binary Walsh spectrum is the product of its binary string with a binary Walsh matrix, using F_{2} operations (mod 2).
In the files like the one to the right the b.W.s. is always shown with red and white squares. White stands for 0 and red for 1.
It happens to be always an exclusive or of unnegated arguments, i.e. a row of a binary Walsh matrix. (compare)
Walsh equivalence class (wec)[edit]
All n-ary Boolean functions with odd weight belong to the same wec, therefore called O.
n-ary Boolean functions with even weight belong to wecs E0...En:
Their binary Walsh spectrum is a row of a binary Walsh matrix.
If the row number (between 0 and 2^n-1) has weight w (in binary it has w ones), than the function belongs to wec Ew.
Examples:
- 1-ary Boolean functions have wecs O and E0 and E1:
Walsh spectra of 1-ary functions | |||||
---|---|---|---|---|---|
function | Walsh spectrum | binary W. s. | wec | ||
0 1 2 3 |
[0 0] [1 0] [0 1] [1 1] |
[ 0 0] [ 1 1] [ 1 -1] [ 2 0] |
[0 0] [0 0] [0 1] [0 1] |
0 0 1 1 |
E0 O O E1 |
- 2-ary Boolean functions have wecs O and E0...E2:
Walsh spectra of 2-ary functions | ||||||
---|---|---|---|---|---|---|
function | Walsh spectrum | binary W. s. | wec |
O: white | ||
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
[0 0 0 0] [1 0 0 0] [0 1 0 0] [1 1 0 0] [0 0 1 0] [1 0 1 0] [0 1 1 0] [1 1 1 0] [0 0 0 1] [1 0 0 1] [0 1 0 1] [1 1 0 1] [0 0 1 1] [1 0 1 1] [0 1 1 1] [1 1 1 1] |
[ 0 0 0 0] [ 1 1 1 1] [ 1 -1 1 -1] [ 2 0 2 0] [ 1 1 -1 -1] [ 2 2 0 0] [ 2 0 0 -2] [ 3 1 1 -1] [ 1 -1 -1 1] [ 2 0 0 2] [ 2 -2 0 0] [ 3 -1 1 1] [ 2 0 -2 0] [ 3 1 -1 1] [ 3 -1 -1 -1] [ 4 0 0 0] |
[0 0 0 0] [0 0 0 0] [0 1 0 1] [0 1 0 1] [0 0 1 1] [0 0 1 1] [0 1 1 0] [0 1 1 0] [0 1 1 0] [0 1 1 0] [0 0 1 1] [0 0 1 1] [0 1 0 1] [0 1 0 1] [0 0 0 0] [0 0 0 0] |
0 0 1 1 2 2 3 3 3 3 2 2 1 1 0 0 |
E0 O O E1 O E1 E2 O O E2 E1 O E1 O O E0 | |
Calculated with this Python script |
- 3-ary Boolean functions have wecs O and E0...E3: 3-ary_Boolean_functions#Walsh spectrum
- 4-ary Boolean functions have wecs O and E0...E4: 4-ary_Boolean_functions#wec