computer-science - 还有哪些逻辑门可以添加到集合 {XOR} 中以形成通用集合？

Question

我遇到以下问题:

集合{XOR}不是完备集合，即XOR不是万能门。在集合中再加入一个逻辑门，使新集合成为完备集，并证明完备。

NOT门可以通过使用XOR来实现，And门可以通过的组合来表示>NOT 门和XOR 门。

我想不出我应该使用的第二个门。我是否只是简单地向集合中添加一个 OR 门，因为我觉得它没有回答问题。

另外，我想知道我对Universal Set的理解是否正确:A universal set should be able to represent {AND, OR, NOT}

编辑:不可能单独使用 XOR 门创建 And 门。

Answer 1

您不能单独使用 XOR 创建 AND 门(或 OR 门)，因此它不是通用集。XOR with AND 是一个通用集 - 这意味着您可以使用该集创建任何 bool 表达式。

您可以在此处找到更多信息: https://cseweb.ucsd.edu//classes/sp14/cse140-b/slides/140-sp14-lec6.pdf