我儿子最近一直在玩Little Big Planet 2，我注意到游戏编辑器允许AND门，OR门和NO门......图灵完备吗？如果是这样，任何人都可以推荐一个资源来学习将这些原语变成更高级别的条件 if 吗？
问问题
13292 次
7 回答
8
一个与非门就足够了，一切都可以从它构建，所以你拥有的三个就足够了。这是一门从逻辑门到构建计算机，一直到编写操作系统的课程：计算系统的元素：从第一原理构建现代计算机
于 2011-02-05T19:08:01.473 回答
4
一个想法：你应该能够构建一个NAND 门，然后你可以构建一个 XOR 门。使用 XOR 和 AND，您可以构建一个半加器。结合半加器来构建一个全加器。这至少是一个开始。
NAND 和 NOR 是其他门的基本构建块，因此图灵完备性可能指日可待。
于 2011-02-05T19:05:38.120 回答
3
AND、OR 和 NOT 在功能上是完备的，即可以表达所有可能的真值表。我相信这也使它变得完整，因为您可以构建具有任何功能完整的门集的通用处理器
于 2011-02-05T19:06:32.813 回答
1
我知道我在这里比赛迟到了，但是是的。我玩 LBP2，它有 AND、OR、NOT、XOR、NAND、NOR。你也可以加减信号，游戏中也有做二进制的方法。
于 2014-12-28T05:33:59.200 回答
0
您需要的唯一门是 NOT 和 OR。使用这两个，您可以构建所有其他逻辑门。例如，NOT(OR(NOT|NOT)) 是 AND 门，OR(NOT|NOT) 是 NAND，NOT(OR()) 是 NOR，等等。难于制作（也是最实用的）是XOR，可以用与非门树构成，而这又可以用 NOT 和 OR 构成，如上所示。
于 2013-02-19T18:30:01.573 回答
0
您可以使用 NAND 或 NOR 门构建任何复杂的逻辑电路。
NAND 是一个 AND，在输出引脚上有一个 NOT。
NOR 是在输出引脚上带有 NOT 的 OR。
任何基于 NAND 的电路都可以完全使用 NOR 来重建，反之亦然。
因此，您可以构建仅给定与非门的任何逻辑电路。或者你可以只使用或非门。或者您可以使用 NOT 和 AND 门。或者您可以使用 NOT 和 OR 门。或者，您也可以使用 AND、NOT 和 OR 门：您当然可以通过使用所有三种类型的门创建最佳组合来减少晶体管的数量。
所有这些都可以通过布尔代数使用真值表来证明：真值表的任何组合都可以由上述门的组合构建。当有两个输入时，有 4 种可能的输入组合，给出 16 个可能的真值表。通过使用上述门的组合，您可以创建所有这 16 个真值表，因此，您不需要 16 个不同的门。当您添加更多输入和输出时，甚至当您创建寄存器和锁存器以创建内存位、CPU 寄存器和/或任何时序逻辑电路时，这一点都成立。
https://en.wikipedia.org/wiki/NAND_logic
于 2020-12-14T19:43:32.170 回答