# Equivalence classes of Boolean functions

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 A227722 = 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:

*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:

Some *sec*s are self complementary, an thus complete *gsec*s 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:

Some *gsec*s are complete *ggsec*s on their own. Three *sec*s are even complete *ggsec*s, 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 and reflecting Venn diagrams.

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

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

Some *sec*s are complete *bec*s, e.g. **this** or **this one**.

These 24 *sec*s 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 ... *bec*s of 0, 1, 2, 3, 4 ... -ary Boolean functions ( A000616).

### Greater big equivalence class (*gbec*)[edit]

Every *bec* has a complement. Together they form a *gbec*.

This is a *gbec*, containing 48 functions:

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

These two *bec*s 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 *gsec*s (displayed in the same columns).

Adding all the functions of the corresponding *ggsec*s gives ** ggbec O**, containing 128 functions.

## Walsh[edit]

### 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 **F**_{2} 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]

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 *wec*s **E0**...**E n**:

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*

**E**.

*w***Examples:**

- For 3-ary Boolean functions each
*wec*is also a*ggbec*: 3-ary_Boolean_functions#ggbec - 4-ary_Boolean_functions#wec