Equivalence classes of Boolean functions

From Wikiversity
Jump to navigation Jump to search

The number of Boolean functions with arity is (Sloane'sA001146).
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 Sloane'sA000231
faction permutation symmetric Sloane'sA003180 = 2 · Sloane'sA000612
clan negation, permutation hyperoctahedral Sloane'sA000616
super-family negation, complement
super-clan negation, permutation, complement

See also Integer sequences related to Boolean functions.


equivalence classes based on similarity[edit | edit source]

basic (negation and permutation)[edit | edit source]

family (negation)[edit | edit source]

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

faction (permutation)[edit | edit source]

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

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


super (extension with complement)[edit | edit source]

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

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

super-faction (permutation, complement)[edit | edit source]

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

super-clan (negation, permutation, complement)[edit | edit source]

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

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

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

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

Partitions into blocks of equal size[edit | edit source]

parity, depravity, quadrants[edit | edit source]

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

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

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

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