Equivalence classes of Boolean functions

The number of Boolean functions with arity $\leq n$ is $2^{2^{n}}$ ( 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 $C_{2}^{n}$	$2^{n}$	A000231
faction	permutation	symmetric $S_{n}$	$n!$	A003180 = 2 ·  A000612
clan	negation, permutation	hyperoctahedral $C_{2}^{n}\cdot S_{n}$	$2^{n}\cdot n!$	A000616
super-family	negation, complement		$2^{n+1}$
super-clan	negation, permutation, complement		$2^{n+1}\cdot n!$

See also Integer sequences related to Boolean functions.

equivalence classes based on similarity

basic (negation and permutation)

family (negation)

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 $2^{n}\times 2^{n}$ matrix whose rows (and columns) are the truth tables of $n$-ary functions in the same family.
family of 3-ary functions, at the bottom the 8×8 family matrix	family matrix of a 4-ary function, containing each function twice	A family matrix is a bitwise XOR table with integers replaced by binary values.
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)

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)

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)

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)

Every family has a complement. Together they form a super-family.
This family is a complete super-family: 1110 0001

super-faction (permutation, complement)

Every faction has a complement. Together they form a super-faction.   (Every super-faction contains two factions.)

super-clan (negation, permutation, complement)

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)

The two families on the left form a super-family. The family on the right is a super-family on its own. Together these two super-families form an ultra-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)

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)

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

family

clan

super family

super clan

ultra family

Partitions into blocks of equal size

parity, depravity, quadrants

quadrants

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

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)

All truth tables in this family have the consul with index 6.

Dull tribes of 3-ary truth tables are marked with four colors.

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 F₂ 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

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

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: dark blue 1: light blue 2: green Calculated with this Python script
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

• 3-ary: 3-ary_Boolean_functions#Walsh spectrum
• 4-ary: 4-ary_Boolean_functions#wec