Equivalence classes of Boolean functions

The number of Boolean functions with arity $\leq n$ is $2^{2^{n}}$ ( 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 $C_{2}^{n}$	$2^{n}$	A000231
	faction	input permutation (P)	symmetric $S_{n}$	$n!$	A003180
big (BEC)	clan	input negation and permutation (NP)	hyperoctahedral $C_{2}^{n}\cdot S_{n}$	$2^{n}\cdot n!$	A000616
greater small		input and output negation (NN)		$2^{n+1}$
greater big		input negation and permutation, output negation (NPN)		$2^{n+1}\cdot n!$

input negation and permutation

negation (N) family small

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 $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.

permutation (P) faction

Functions can be turned into each other by permuting inputs.

negation and permutation (NP) clan big

(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

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

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)

Every P has a complement. Together they form a PN.

negation, permutation and complement (NPN) greater big

Every NP has a complement. Together they form an NPN.

This N is a complete NPN: 1110 1000

extension with half-complement

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

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

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

small

big

greater small

greater big

greatest small

Walsh

The Boolean function $\scriptstyle (1,0,1,0,0,1,1,0)$
has the Walsh spectrum $\scriptstyle (4,2,0,-2,0,2,0,2)$
and the binary Walsh spectrum $\scriptstyle (0,1,0,1,0,1,0,1)$.

Walsh spectra of 8 functions in the same sec

They have different Walsh spectra, but all have the b.W.s. $\scriptstyle (0,1,1,0,1,0,0,1)$

Binary Walsh spectrum

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

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 E0: dark blue E1: light blue E2: green
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