AND、OR、NOT能否表示任意真值表？三输入NAND/NOR完备性探究

1. AND、OR、NOT能否表示任意真值表？ #

绝对可以！这三个门的组合是功能完备的——意思就是它们能生成所有可能的布尔函数（对应所有真值表）。

原因很简单：我们知道NAND和NOR各自都是完备的，而用AND、OR、NOT可以轻松模拟出这两个门：

• NAND(a,b) = NOT(AND(a,b))
• NOR(a,b) = NOT(OR(a,b))

既然NAND/NOR能覆盖所有真值表，那通过这三个门的组合自然也能做到。举个实际例子，要实现异或（XOR），可以写成OR(AND(a, NOT(b)), AND(NOT(a), b))——完全用这三个门拼出来。

2. 三输入场景下NAND、NOR是否仍具备完备性？ #

这里得分情况讨论，但通常遵循标准的完备性规则（允许将门的多个输入连接到同一个信号，或使用常量输入如0/1）时，三输入NAND和NOR依然是完备的。不过如果限制不能短路输入、不能用常量，那它们就不完备了，原因如下：

允许输入短路/常量的情况 #

三输入NAND（记作NAND3(a,b,c)）可以通过以下方式生成基础门：

• 生成NOT：把三个输入都接同一个信号x，即NAND3(x,x,x) = NOT(x)（当x=1时，三个输入都是1，NAND输出0；x=0时输出1，正好是取反）
• 生成双输入NAND：把两个输入接同一个信号，比如NAND3(a,a,b) = NOT(AND(a,a,b)) = NOT(AND(a,b)) = NAND(a,b)

有了NOT和双输入NAND，就和双输入NAND的完备性逻辑一致了，自然能生成所有真值表。三输入NOR的情况同理，NOR3(x,x,x)=NOT(x)，NOR3(a,a,b)=NOR(a,b)，同样具备完备性。

不允许输入短路/常量的情况 #

这种限制下，我们没法生成单输入的NOT函数——因为三输入门必须接三个不同的输入信号，没法把它们合并成一个。没有NOT的话，很多基础布尔函数（比如简单的取反）都无法实现，更别说覆盖所有真值表了，所以此时三输入NAND/NOR是不完备的。

不过绝大多数数字逻辑的讨论里，都是允许输入短路的，所以默认三输入NAND/NOR依然具备完备性。

内容的提问来源于stack exchange，提问作者jg mr chapb