logic - xor 和 not 门在逻辑上是否完整

Question

异或门和非门在逻辑上是否完整。换句话说，我们可以使用它们来实现逻辑电路吗？

Answer 1

NOR 和 NAND 是唯一功能完整的单例门集。因此，XOR 本身在功能上并不完整（或与 NOT 一起，因为如上所述 NOT 可以使用 XOR 创建）。

XOR 可以补充到两个元素功能完整的门集。应该添加（左或右）含义。

您可以在 Wernick, William (1942) “Complete Sets of Logical Functions”中找到有关此类集合的更多信息，美国数学学会汇刊 51：117-32。

Answer 2

所有基本逻辑门都可以用非门创建。如果输入之一永久为零，则异或门充当非门。

AND：NOT(NOT(A) OR NOT(B))
OR：（可以简单地将电线连接在一起，也可以使用一些二极管）
NAND：NOT(A) OR NOT(B)
XOR：NOT(NOT(A ) OR NOT(NOT(A) OR NOT(B))) OR NOT(NOT(NOT(A) OR NOT(B)) OR NOT(B)) 等。