Equivalence classes of Boolean functions

From Wikiversity
Jump to navigation Jump to search

There are various ways that Boolean functions can be ordered in equivalence classes by common properties.
Some appear quite often, and are given all kinds of quirky names by all kinds of authors - including my humble self.

Small[edit]

Small equivalence class (sec)[edit]

Functions belong to the same sec when they can be expressed by each other by negating arguments.

The 2-ary functions in this table belong to the same sec when they appear in the same row,
e.g. NAND , converse implication , implication and OR .

Each sec can be denoted by the smallest number corresponding to one of its functions, which leads to Sloane'sA227722 = 0, 1, 3, 5, 6, 7, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 51, 53, 54, 55, 60, 61, 63, 85, 86, 87, 90, 91, 95, 102, 103, 105, 107, 111, 119, 123, 125, 126, 127, 255...

This is a sec of 3-ary Boolean functions, containing 8 functions:

Boolean functions like 1000 0000.svg

sec matrix[edit]

Category on Commons: Sec matrices of Boolean functions

A sec matrix is a symmetric binary square matrix of size 2^n, that has the n-ary Boolean functions in one sec as its rows.
It is a bitwise XOR (or nimber addition) table with a set of numbers replaced by ones, and all other numbers replaced by zeros.
The example files shown in this article contain 8x8 sec matrices.

Greater small equivalence class (gsec)[edit]

Every sec has a complement. Together the complements form a gsec.
This is a gsec, containing 16 functions:

Boolean functions like 1000 0000.svg Boolean functions like 1111 1110.svg

Some secs are self complementary, an thus complete gsecs on their own, e.g. this one.

Greatest small equivalence class (ggsec)[edit]

The gsec shown above is related to another one.
Each function in one gsec is the half-complement of a function in the other one.
W.l.o.g. two functions shall be called half-complements when the left halves of their vectors are equal and the right halves are complements.
Together they form the following ggsec, containing 32 functions:

Boolean functions like 1000 0000.svg Boolean functions like 1111 1110.svg
Boolean functions like 1110 0000.svg Boolean functions like 1111 1000.svg

Some gsecs are complete ggsecs on their own. Three secs are even complete ggsecs, e.g. this one.

Big[edit]

Big equivalence class (bec)[edit]

Functions belong to the same bec, when they can be expressed by each other by negating and by permuting arguments.
Graphically, permuting arguments corresponds to turning 0011 0101 0001 1011 0100 0111 and reflecting 0011 0101 0101 0011 Venn diagrams.

Each bec can be denoted by the smallest number corresponding to one of its functions, which leads to Sloane'sA227723 = 0, 1, 3, 6, 7, 15, 22, 23, 24, 25, 27, 30, 31, 60, 61, 63, 105, 107, 111, 126, 127, 255...

These secs form a bec (denoted by the number 7 in the above sequence), containing 24 functions:

Boolean functions like 1110 0000.svg Boolean functions like 1100 1000.svg Boolean functions like 1010 1000.svg

Some secs are complete becs, e.g. this or this one.


These 24 secs of 4-ary Boolean functions form a bec, containing 16 * 24 = 384 functions:
File:1111 0000 1001 1100 Boolean function 16*24.svg

There are 2, 3, 6, 22, 402 ... becs of 0, 1, 2, 3, 4 ... -ary Boolean functions (Sloane'sA000616).

Greater big equivalence class (gbec)[edit]

Every bec has a complement. Together they form a gbec.
This is a gbec, containing 48 functions:

Boolean functions like 1110 0000.svg Boolean functions like 1100 1000.svg Boolean functions like 1010 1000.svg
Boolean functions like 1111 1000.svg Boolean functions like 1110 1100.svg Boolean functions like 1110 1010.svg


This sec is a complete bec, and even a complete gbec: File:Boolean functions like 1110 1000.svg

These two becs of 4-ary Boolean functions are complements, and thus form a gbec, containing 2 * 16 * 24 = 768 functions:
File:1111 0000 1001 1100 Boolean function 16*24.svg
File:1100 0110 1111 0000 Boolean function 16*24.svg

This bec is self complementary, and thus a complete gbec:
File:1110 0011 1100 0001 Boolean function 16*24.svg

Greatest big equivalence class (ggbec)[edit]

The gbec shown above contains the functions of 3 gsecs (displayed in the same columns).
Adding all the functions of the corresponding ggsecs gives ggbec O, containing 128 functions.


Walsh[edit]

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]

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)

Walsh equivalence class (wec)[edit]

wecs of 3-ary Boolean functions
O white
E0, E3 red
E1, E2 gray

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: