三值模糊逻辑下给定算子能否生成所有Q²→Q函数？

答案是不能——给定的算子集合加上真值集合$Q = {0, \frac{1}{2}, 1}$无法生成所有从$Q^2$到$Q$的函数。下面是具体的推理过程：

核心观察：经典二值输入的输出限制 #

先看所有给定算子在输入为经典二值（即$(p,q) \in {(0,0), (0,1), (1,0), (1,1)}$）时的输出：

• $0 ∧ 1 = 0$，$0 ∨ 1 = 1$
• $¬0 = 1$，$¬1 = 0$
• $0 → 1 = 1$，$1 → 0 = 0$
• $0 ↔ 1 = 0$，$0 ⊕ 1 = 1$

可以发现，所有算子在经典二值输入下的输出只能是0或1，永远不会产生中间值$\frac{1}{2}$。而任何由这些算子组合出来的表达式，必然继承这个特性——只要输入是经典二值对，输出就只能是0或1。

构造无法生成的函数 #

考虑这样一个二元函数$f: Q^2 \to Q$：
$$
f(p,q) =
\begin{cases}
\frac{1}{2} & \text{当 } (p,q) = (0,1) \
0 & \text{其他情况}
\end{cases}
$$

根据上面的观察，任何给定算子组合的表达式在$(0,1)$处的输出只能是0或1，完全无法得到$\frac{1}{2}$。而这个函数$f$在$(0,1)$处的输出恰好是$\frac{1}{2}$，因此它无法被给定的算子集合生成。

总结 #

由于存在至少一个无法被生成的二元函数，所以给定的算子集合加上$Q$不具备函数完全性，不能生成所有从$Q^2$到$Q$的函数。

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