Equivalence classes of Boolean functions
The number of Boolean functions with arity is ( A001146).
Many of them are related to each other, and can be grouped in equivalence classes.
This article introduces the names family, faction and clan, as well as the prefixes super and ultra.
own names | equivalent under | group | maximum size | sequence |
---|---|---|---|---|
family | negation | hyperrectangular | A000231 | |
faction | permutation | symmetric | A003180 = 2 · A000612 | |
clan | negation, permutation | hyperoctahedral | A000616 | |
super-family | negation, complement | |||
super-clan | negation, permutation, complement |
See also Integer sequences related to Boolean functions.
equivalence classes based on similarity[edit | edit source]
basic (negation and permutation)[edit | edit source]
family (negation)[edit | edit source]
Functions can be turned into each other by negating inputs.
The 10 (exactly) 2-ary Boolean functions form three families, 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. |
faction (permutation)[edit | edit source]
Functions can be turned into each other by permuting inputs.
While families and clans can be self-complementary, factions can not. (Therefore the number of factions is always even.)
clan (negation, permutation)[edit | edit source]
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...
super (extension with complement)[edit | edit source]
Each Boolean function has a complement. So have the equivalence classes defined above.
Those defined here are the merge of two complements.
super-family (negation, complement)[edit | edit source]
Every family has a complement. Together they form a super-family.
This family is a complete super-family: 1110 0001
super-faction (permutation, complement)[edit | edit source]
Every faction has a complement. Together they form a super-faction. (Every super-faction contains two factions.)
super-clan (negation, permutation, complement)[edit | edit source]
Every clan has a complement. Together they form a super-clan.
This family is a complete super-clan: 1110 1000
ultra (extension with half-complement)[edit | edit source]
The two families on the left form a super-family. | ||
Each Boolean function has two half-complements. (The truth table is complemented on the left or on the right side.)
A super-family has a unique half-complement. Merging them gives an ultra-family.
As super-clans consist of super-families, they can be extended in the same way.
(Factions do not have a unique half-complement, so it does not seem useful to define ultra-factions.)
ultra-family (negation, complement, half-complement)[edit | edit source]
The functions in an ultra-family have symmetric positions in a hypercube graph (or the related matrix). See matrices.
This family is a complete ultra-family: 1100 1010 (better seen in its matrix)
ultra-clan (negation, permutation, complement, half-complement)[edit | edit source]
An ultra-clan is the merge of a super-clan and its half-complement.
It can also be seen as a merge of ultra-families, that are permutations of each other.
See here for a table of the 39 ultra-families of 4-ary Boolean functions.
Examples of extended families and clans[edit | edit source]
family |
---|
clan | ||
---|---|---|
super family | |
---|---|
super clan | |||
---|---|---|---|
ultra family | ||
---|---|---|
Partitions into blocks of equal size[edit | edit source]
parity, depravity, quadrants[edit | edit source]
even evil (0) | even odious (2) |
odd evil (1) | odd odious (3) |
The parity and depravity of a Boolean function are based on the first and last bit of its truth table.
It is even (odd), iff the first digit of the truth table is false (true). Its Zhegalkin index is also even (odd).
It is evil (odious), iff the last digit of the truth table is false. Its Zhegalkin index has even (odd) binary weight.
(These terms make sense for the Zhegalkin index, rather than the truth table.)
Parity and depravity partition the Boolean functions in halves. Together they partition them into quadrants.
sharpness[edit | edit source]
Truth tables with odd weight shall be called sharp. Those with even weight are dull.
(Unlike parity and depravity, this is only the property of a truth table – not of a Boolean function.)
consuls (binary Walsh spectra)[edit | edit source]
The Walsh spectrum of a truth table is its product with a Walsh matrix.
Its binary Walsh spectrum is its product with a binary Walsh matrix, using F2 operations (mod 2).
It is always a Walsh function, and shall be called consul. The term is also used for the integer denoting the Walsh function.
tribe[edit | edit source]
The consul weight is the binary weight of the consul. (E.g. consul 6 has consul weight 2.)
Ultra-clans with dull truth tables have a unique consul weight.
For n-ary truth tables they form the tribes 0...n.
Sharp truth tables form a tribe on their own.
examples[edit | edit source]
1-ary | |||||
---|---|---|---|---|---|
truth tables | Walsh spectra | consuls (A253315) | tribe | ||
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 |
0 s s 1 |
2-ary | ||||||
---|---|---|---|---|---|---|
truth tables | Walsh spectra | consuls (A253315) | tribes |
sharp: 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 |
0 s s 1 s 1 2 s s 2 1 s 1 s s 0 |