技术问询：用指定常量与联结词构造n元布尔函数的数量是否正确

先直接给明确结论：你提到的两个数量完全不是$2^{23}$和$2^{24}$——这两个数其实分别是3变量和4变量的所有布尔函数的总数，但你给出的两组常量+联结词集合都不具备生成所有布尔函数的能力，只能构造布尔函数的一个子集，下面详细拆解：

一、集合${0, 1, \wedge}$能构造的布尔函数数量 #

这个集合里只有常量0、1和合取（逻辑与）运算，它能生成的布尔函数有个核心特征：单调递增——意思是，如果某个变量赋值组合让函数输出1，那么任何“更真”的赋值（把其中一些0改成1）也一定会让函数输出1。

具体来说，每个可构造的函数要么是常量0，要么是某个变量子集的合取（空子集的合取就是常量1，单个变量的合取就是变量本身，多个变量的合取就是它们的与运算）。

对于$n$个输入变量$x_1, \dots, x_n$，这类函数的总数是$2^n + 1$：

• 空子集对应常量1，共1个；
• 所有非空子集（共$2^n - 1$个）对应不同的合取式；
• 加上常量0，总共$1 + (2^n - 1) + 1 = 2^n + 1$个。

举个例子，当$n=3$时，只能生成9个函数，远小于$2^{23}=256$（3变量所有布尔函数的总数）。

二、集合${0, 1, \lnot, \oplus}$能构造的布尔函数数量 #

$\oplus$是异或（逻辑模2加法），$\lnot$是否定。其实你可以发现，$\lnot x$完全可以用$x \oplus 1$来表示（x=0时输出1，x=1时输出0），所以这个集合的表达能力等价于${0,1,\oplus}$。

它能生成的是仿射布尔函数，所有函数都可以写成如下形式：
$$f(x_1, \dots, x_n) = a_0 \oplus a_1 x_1 \oplus a_2 x_2 \oplus \dots \oplus a_n x_n$$
其中$a_0, a_1, \dots, a_n$都是0或1（$a_0$是常量项，$a_i$是变量$x_i$的系数）。

每个仿射函数由这$n+1$个系数唯一确定，每个系数有2种选择，所以总数量是$2^{n+1}$：

• 比如$n=4$时，只能生成$2^{{4+1}=32$个函数，远小于$2}{2^4}=65536$（4变量所有布尔函数的总数）。

为什么你的初始猜测不对？ #

$2^{2k}$这个数值的意义是k个变量的所有布尔函数总数——因为每个布尔函数本质是从${0,1}^{k$到${0,1}$的映射，总共有$2}{2^k}$种可能。但你给出的两组集合都不是功能完备的：

• ${0,1,\wedge}$缺少否定或析取运算，无法生成非单调的函数（比如$\lnot x_1$就构造不出来）；
• ${0,1,\lnot,\oplus}$缺少合取或析取运算，无法生成非线性的函数（比如$x_1 \wedge x_2$就构造不出来）。

所以这两个集合能构造的布尔函数数量远小于你提到的数值。

内容的提问来源于stack exchange，提问作者Homaniac