群论应用：布尔函数计数

抽象代数由于其抽象的特性，初学时往往难以理解。本文介绍群论的一个应用：布尔函数计数。

Burnside 引理

在分析群对于集合作用时，Burnside 引理是一个非常重要的定理：

Burnside 引理

设有限群 $G$ 作用于有限集 $X$ 上，则 $X$ 在 $G$ 作用下的轨道数目为

$$N = \frac{1}{|G|} \sum_{g \in G} \chi(g)$$

其中 $\chi(g)$ 为元素 $g$ 在 $X$ 上的不动点数目。

对于这一引理的证明，有许多参考¹²，这里不再赘述。

布尔函数计数问题

问题背景

布尔函数是一类重要的函数，满足 $\mathbb{F}_2^n \to \mathbb{F}_2$ 的映射形式。通常我们用 0 和 1 来表示 $\mathbb{F}_2$ 中的两个元素，而 $\mathbb{F}_2^n$ 中的元素可以用长度为 $n$ 的二进制串来表示。一些常见的 2 元布尔函数及其真值表如下：

1. 逻辑与：$f(x, y) = x \land y$

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

2. 逻辑或：$f(x, y) = x \lor y$

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

3. 逻辑同或：$f(x, y) = x \odot y$

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

布尔函数还可以用开关线路来表示，如下图所示：

可以看出来这三个开关线路中两个开关是可以交换的，即有些布尔函数在自变量的置换下是等价的。因此便引出了布尔函数的计数问题：对于 $n$ 元布尔函数，有多少个本质不同的布尔函数？

观察 2 元布尔函数

我们先来看看所有的 $2$ 元布尔函数的真值表：

$f(x, y)$	(0,0)	(0,1)	(1,0)	(1,1)
$f_{1}$	0	0	0	0
$f_{2}$	0	0	0	1
$f_{3}$	0	0	1	0
$f_{4}$	0	0	1	1
$f_{5}$	0	1	0	0
$f_{6}$	0	1	0	1
$f_{7}$	0	1	1	0
$f_{8}$	0	1	1	1
$f_{9}$	1	0	0	0
$f_{10}$	1	0	0	1
$f_{11}$	1	0	1	0
$f_{12}$	1	0	1	1
$f_{13}$	1	1	0	0
$f_{14}$	1	1	0	1
$f_{15}$	1	1	1	0
$f_{16}$	1	1	1	1

考虑两个元素的置换，即置换群 $S_2 = \{ (1), (12) \}$，那么符合 $f_i (x, y) = f_j (y, x)$ 的布尔函数被认为是实质相同的。可以看出，上表中符合该条件的成对布尔函数有：

• $f_3$ 和 $f_5$
• $f_4$ 和 $f_6$
• $f_{11}$ 和 $f_{13}$
• $f_{12}$ 和 $f_{14}$

因此，$2$ 元布尔函数的本质不同的函数个数为 $16 - 4 = 12$。

那么如何用 Burnside 引理来分析呢？将 $S_2$ 中元素按置换类型分类计数，并列出其作用于 $F = \{ f_1, \cdots, f_{16} \}$ 上的不动点数目：

置换类型	个数	$\chi(g)$
$1^2$	1	$2^{2 \times 2} = 16$
$2^1$	1	$2^3 = 8$

对 $1^2$ 类型的置换，不动点的数目即先对每个自变量进行选择 ($2 \times 2$ 共 4 个)，再对结果进行选择，因此有 $2^4 = 16$ 个不动点；对 $2^1$ 类型的置换，不动点的数目即先对捆绑在一起的 2 个自变量进行选择 (00、01 和 10、11 共 $3$ 个)，再对结果进行选择，因此有 $2^3 = 8$ 个不动点。

因此，由 Burnside 引理，$2$ 元布尔函数的本质不同的函数个数为：

$$N = \frac{1}{2} (1 \times 16 + 1 \times 8) = 12$$

3 元布尔函数

对于 $3$ 元布尔函数，我们直接将 $S_3$ 的元素按置换类型分类计数：

置换类型	个数	$\chi(g)$
$1^3$	1	$2^{2^3} = 256$
$1^1 2^1$	3	$2^{2 \times 3} = 64$
$3^1$	2	$2^4 = 16$

与 $2$ 元布尔函数相比，$3$ 元布尔函数的表中出现了 $3^1$ 类型的置换。考虑将 3 个自变量捆绑后在循环移位下本质不同的组合有 4 个：000、001、011、111，因此有 $2^4 = 16$ 个不动点。

因此，由 Burnside 引理，$3$ 元布尔函数的本质不同的函数个数为：

$$N = \frac{1}{3!} (1 \times 256 + 3 \times 64 + 2 \times 16) = 80$$

更一般的情形

显然，对于 $n$ 元布尔函数，我们的任务都是在对 $S_n$ 中元素按类型分类后寻找不动点的数目。而这里的不动点数目则拆分为了每个轮换对应的组合的数目。例如，$4-$轮换对应了 6 个组合：0000、0001、0011、0101、0111、1111，因此一个 $4^1 \cdots$ 的置换会对应于 $2^{6 \times \cdots}$ 的不动点数目。

另：或许找这种组合对应于一个类似的应用问题，但我暂时还没有想到。

Footnotes

1. https://en.wikipedia.org/wiki/Burnside%27s_lemma ↩

2. 胡冠章 应用近世代数[M]. 第 3 版. 版. 北京: 清华大学出版社, 2006. ↩