# Equivalence classes of Boolean functions

The number of Boolean functions with arity $\leq n$ is $2^{2^{n}}$ ().   (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}$ faction input permutation (P) symmetric $S_{n}$ $n!$ big (BEC) clan input negation and permutation (NP) hyperoctahedral $C_{2}^{n}\cdot S_{n}$ $2^{n}\cdot n!$ 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 = 0, 1, 3, 5, 6, 7, 15, 17, 18...

### 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 = 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

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.

## Walsh The Boolean function ( 1 , 0 , 1 , 0 , 0 , 1 , 1 , 0 ) {\displaystyle \scriptstyle (1,0,1,0,0,1,1,0)} has the Walsh spectrum ( 4 , 2 , 0 , − 2 , 0 , 2 , 0 , 2 ) {\displaystyle \scriptstyle (4,2,0,-2,0,2,0,2)} and the binary Walsh spectrum ( 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 ) {\displaystyle \scriptstyle (0,1,0,1,0,1,0,1)} . Walsh spectra of 8 functions in the same secThey have different Walsh spectra, but all have the b.W.s. ( 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 ) {\displaystyle \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 F2 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:
• 2-ary Boolean functions have wecs O and E0...E2: