Equivalence classes of Boolean functions
The number of Boolean functions with arity is ( A001146). (For higher arities this is a very large number.)
Many of them are related to each other, and can be grouped in equivalence classes.
This article has long used a set of idiosyncratic names for some of the most important equivalence classes.
own names | equivalent under | group | maximum size | sequence | |
---|---|---|---|---|---|
old | new | ||||
small (SEC) | family | input negation (N) | hyperrectangular | A000231 | |
faction | input permutation (P) | symmetric | A003180 | ||
big (BEC) | clan | input negation and permutation (NP) | hyperoctahedral | A000616 | |
greater small | input and output negation (NN) | ||||
greater big | input negation and permutation, output negation (NPN) |
input negation and permutation[edit | edit source]
negation (N) family small[edit | edit source]
Functions can be turned into each other by negating inputs.
The 10 functions with arity (exactly) 2 form 3 N, whose representative functions are AND, OR and XOR. (See this table of 2-ary functions, where equivalents are in the same row.)
The lexicographically smallest truth tables are encoded in A227722 = 0, 1, 3, 5, 6, 7, 15, 17, 18...
family matrix | ||
---|---|---|
A family matrix is a symmetric binary matrix whose rows (and columns) are the truth tables of -ary functions in the same family. | ||
See also: Family matrices of Boolean functions (Commons) Each file in 4-ary Boolean functions; BEC (24 × 16×16) contains 24 family matrices. |
permutation (P) faction[edit | edit source]
Functions can be turned into each other by permuting inputs.
negation and permutation (NP) clan big[edit | edit source]
(Not to be confused with NP-equivalence in the complexity sense.)
Functions can be turned into each other by negating and permuting inputs.
The lexicographically smallest truth tables are encoded in A227723 = 0, 1, 3, 6, 7, 15...
extension with complement[edit | edit source]
Each Boolean function has a complement (often described as output negation).
The three types of equivalence classes defined above also have complements.
Those defined here are the merge of two complements.
negation and complement (NN) greater small[edit | edit source]
Every N has a complement. Together the complements form an NN.
(Some N are self-complementary, an thus complete NN on their own, e.g. 1110 0001.)
permutation and complement (PN)[edit | edit source]
Every P has a complement. Together they form a PN.
negation, permutation and complement (NPN) greater big[edit | edit source]
Every NP has a complement. Together they form an NPN.
This N is a complete NPN: 1110 1000
extension with half-complement[edit | edit source]
two half-complementary NN, forming one NNH | ||
Each Boolean function has two half-complements. One of them is complementary in the left and equal in the right half of the truth table.
The three types of equivalence classes defined above have unique half-complements.
Those defined here are the merge of two half-complements.
These equivalence classes are not very intuitive, and quite possibly not useful.
But the symmetry of otherwise unrelated NN seems at least of aesthetic interest.
negation, complement and half-complement (NNH) greatest small[edit | edit source]
The functions in an NNH have symmetric positions in a hypercube graph (or the related matrix). See here.
Among the 3-ary Boolean functions, there are three N that are complete NNH. One is 1100 1010.
negation, permutation, complement and half-complement (NPNH) greatest big[edit | edit source]
Merge of NNH that are permutations of each other.
See here for a table of the 39 NPNH of 4-ary Boolean functions.
Example of nested equivalence classes[edit | edit source]
small |
---|
big | ||
---|---|---|
greater small | |
---|---|
greater big | ||
---|---|---|
greatest small | |
---|---|
Walsh[edit | edit source]
Binary Walsh spectrum[edit | edit source]
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)
tribe Walsh EC[edit | edit source]
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