Equivalence classes of Boolean functions

From Wikiversity
Jump to navigation Jump to search

The number of Boolean functions with arity is (Sloane'sA001146).   (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 Sloane'sA000231
faction input permutation (P) symmetric Sloane'sA003180
big (BEC) clan input negation and permutation (NP) hyperoctahedral Sloane'sA000616
greater small input and output negation (NN)
greater big input negation and permutation, output negation (NPN)


input negation and permutation[edit | edit source]

negation (N) family small[edit | edit source]

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 Sloane'sA227722 = 0, 1, 3, 5, 6, 7, 15, 17, 18...

permutation (P) faction[edit | edit source]

Functions can be turned into each other by permuting inputs.

negation and permutation (NP) clan big[edit | edit source]

(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 Sloane'sA227723 = 0, 1, 3, 6, 7, 15...

extension with complement[edit | edit source]

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[edit | edit source]

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)[edit | edit source]

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

negation, permutation and complement (NPN) greater big[edit | edit source]

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

This N is a complete NPN: 1110 1000


extension with half-complement[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]


Walsh[edit | edit source]

The Boolean function
has the Walsh spectrum
and the binary Walsh spectrum .
Walsh spectra of 8 functions in the same sec

They have different Walsh spectra, but all have the b.W.s.

Binary Walsh spectrum[edit | edit source]

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[edit | edit source]

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: