居然自己做出来了所以说还是很简单的 23333

Problem

定义布尔的乘运算为 AND ，加运算为 OR 。定义一个 DNF （析取范式）为一个布尔函数，返回值为若干个若干个变量的积的和，例如 $f(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3$ 即为一 DNF 。注意这里定义的 DNF 没有 NOT 。

定义一个对称函数为：接受若干个布尔量，返回一个布尔量，且参数的顺序与返回值是无关的。例如 $f(x_1, x_2) = x_1 x_2$ 即为一对称函数。

我们说一个函数 A 能用另一个函数 B 表达，当且仅当存在一组参数列表之间的对应关系 $y_1 = x_{a_1}, y_2 = x_{a_2}, \dots, y_m = x_{a_m}$ ，使得 $A(x_1, x_2, \dots, x_n) = B(y_1, y_2, \dots, y_m)$ 。例如函数 $A(x_1, x_2, x_3)$ 表示求 $x_1, x_2, x_3$ 的众数，可以得到 $A(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3 + x_3 x_1$ ，令 $B(x_1, x_2, x_3, x_4, x_5, x_6) = x_1 x_2 + x_3 x_4 + x_5 x_6$ ，可以知道 A 能被 B 表达。

现在有两个问题：

1. 对于所有的 DNF ，都可以找到一个对称函数使得其能表达这个 DNF ？
2. 对于所有的对称函数，都可以找到一个 DNF 使得其能表达这个对称函数？

题目似乎很绕……→_→

Solution

考虑任意一个对称函数，由于参数顺序是无关的，所以对于这个对称函数我们只关心它的参数中有多少个 1 有多少个 0 。换而言之，一个对称函数 A 等价于一个二元函数 $f(a, b)$ ，其中 $a$ 表示参数中 1 的个数， $b$ 表示参数 0 的个数。

再考虑一个 DNF 。可以发现 DNF 的值不会随变量的递增而递减，也就是说对于两组参数 $x_1, x_2, \dots, x_n$ 和 $y_1, y_2, \dots, y_n$ ，如果满足 $f(x_1, x_2, \dots, x_n) = 1$ 且 $x_1 \leq y_1, x_2 \leq y_2, \dots, x_n \leq y_n$ ，则一定有 $f(y_1, y_2, \dots, y_n = 1$ 。

所以 DNF 能表达的函数就少得多，考虑一个简单的对称函数 $f(x)$ 表示 NOT x ，可以发现 $f$ 是递减的，用 DNF 就表达不出来。所以问题二是错的，上面说的 $f$ 就是个反例。

而对于任意一个 DNF ，所有不同的参数列表是有限的。假设一个 DNF 有 $n$ 个参数，则有 $2^n$ 中不同的参数列表。考虑一个二元非布尔函数 $f(a, b)$ 保证 $a + b= 2^n$ 。那么 $f$ 就可以完整的表达整个 DNF ：我们对 DNF 的 $n$ 个参数进行二进制编码，可以确定一个 $[0, 2^n)$ 之间的数作为 $a$ ， $f$ 根据输入的 $a$ 的即可返回答案。具体如何进行编码呢？我们让 $x_i$ 出现的 $2^{i - 1}$ 次即可。举个例子，一个 DNF $A(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3$ ，我们构造的对应方式即为 $B(x_1, x_2, x_2, x_3, x_3, x_3, x_3)$ ，可以知道，一定存在一个 B 使得 B 能够表达出 A 。

nonsense

明天早上要去深圳。不能太坑队友了是不，所以可能暂时不会更新了 →_→