PublicationsManuscripts

NPN equivalence classes of Boolean functions

Yuval Filmus

Two Boolean functions are NPN-equivalent if they can be reached from one another by permuting the inputs, negating some of the inputs, and possibly negating the output. The number of different equivalence classes for a given number of variables forms the sequence A000370, which starts 2, 4, 14, 222, 616126, for functions of 1 to 5 variables, respectively.

For $n$ up to 5, we have compiled a list of all NPN-equivalence classes of Boolean functions on $n$ variables. Each such function is given as a hexadecimal integer in which bit $i$ is the value at the $i$th input.