Burnside’s Lemma

When analyzing the action of a group on a set, Burnside’s lemma is a very important theorem:

Burnside’s Lemma

Let a finite group act on a finite set , then the number of orbits of under the action of is

where is the number of fixed points of on .

There are many references for the proof of this lemma ¹², which will not be repeated here.

Boolean Function Counting Problem

Problem Background

Boolean functions are an important class of functions that satisfy the mapping form . Usually, we use 0 and 1 to represent the two elements in , and the elements in can be represented by a binary string of length . Some common 2-element boolean functions and their truth tables are as follows:

1. Logical AND:

   x	y	f(x, y)
   0	0	0
   0	1	0
   1	0	0
   1	1	1

2. Logical OR:

   x	y	f(x, y)
   0	0	0
   0	1	1
   1	0	1
   1	1	1

3. Logical XOR:

   x	y	f(x, y)
   0	0	0
   0	1	1
   1	0	1
   1	1	0

Boolean functions can also be represented by switch circuits, as shown in the following figure:

It can be seen that two switches in these three switch circuits can be exchanged. Some Boolean functions are equivalent under the permutation of the independent variables. Therefore, the counting problem of Boolean functions is raised: For an -variable Boolean function, how many essentially different Boolean functions are there?

Observing 2-variable Boolean Functions

Let’s first take a look at the truth tables of all 2-variable Boolean functions:

Consider the permutation of two elements, that is, the permutation group . Boolean functions that satisfy are essentially the same. It can be seen that the pairs of Boolean functions that meet this condition in the above table are:

• and
• and
• and
• and

Therefore, the number of essentially different 2-variable Boolean functions is .

So how to analyze it using Burnside’s lemma? Count the elements in by permutation type, and list the number of fixed points on that it acts on:

For the type of permutation, the number of fixed points is the number of choices for each independent variable ( in total) multiplied by the number of choices for the result. Therefore, there are fixed points in total. For the type of permutation, the number of fixed points is the number of choices for the two independent variables that are bound together (00, 01, and 10, 11, for a total of ) multiplied by the number of choices for the result. Therefore, there are fixed points in total.

Therefore, by Burnside’s lemma, the number of essentially different 2-variable Boolean functions is:

3-variable Boolean Functions

For 3-variable Boolean functions, we directly count the elements of S3 by permutation type:

Compared with 2-variable Boolean functions, the permutation type appears in the table of 3-variable Boolean functions. Considering the combinations of 3 independent variables bound together and essentially different under cyclic shifts, there are 4: 000, 001, 011, 111. Therefore, there are fixed points.

Therefore, by Burnside’s lemma, the number of essentially different 3-variable Boolean functions is:

More General Cases

For n-variable Boolean functions, our task is to classify the elements of by permutation type and find the number of fixed points for each cycle. The number of fixed points is then split into the number of combinations corresponding to each cycle. For example, a permutation corresponds to 6 combinations: 0000, 0001, 0011, 0101, 0111, 1111. Therefore, a permutation corresponds to fixed points.

Note: Perhaps finding these combinations corresponds to a similar application problem, but I haven’t thought of one yet.