图灵完备攻略：第一部分——基础逻辑电路搭建（附带游戏压缩包）

作者在学习计算机组成原理时了解到了一款名为图灵完备的游戏，这是一款学习处理器架构的游戏，在游戏中你需要从门电路开始，最终搭建出属于自己的计算机。由于学习计算机组成原理的最后目的就是想让我们学会如何搭建一个CPU，因此这款游戏可以作为想要构建属于自己的CPU的前置练习，来使我们深入了解计算机组成原理。在网上该游戏的攻略不完整且讲解不全面，官网的教程还都在youtube上，所以作者决定开一个专栏同时加上自身的理解来详细的解释这款游戏的解题思路。专栏共分为八篇文章，这是第一篇文章，解释游戏中的基础逻辑电路搭建。注意，本文假设读者不懂一点电路知识，但需要了解一点点基础的编程知识，一切从零做起。

一、前言

游戏的背景是你被外星人绑架了，只要你具备造一台电脑的智力水平就可以不被吃掉。

游戏的开局很简单，只需要把输入与输出相连即可

二、 与非门

在这关我们需要通过改变输入来得到输出，然后将屏幕下方的真值表补充完整，也很简单。

三、非门

通过上一关后，外星人会告诉我们通过与非门就能够搭建出一个完整的计算机。在这关我们需要利用右上角我们已有的与非门根据真值表搭建出非门。对照与非门的真值表，我们可以发现第一列与第四列的输入输出很符合我们的需求，所以直接把输入都接到一个与非门上即可，同样很简单。

四、与门

到这里开始有了一点难度，同样，先观察真值表，与我们现有门的真值表进行比对，我们会发现与门和与非门的真值表有些特殊的关系，没错，它们的真值表是相反的（非门的真值表只有一个输入，暂时不做对比 ），由此我们可以得到一个思路，如何将与非门的真值表做反转处理（即NOT）呢，很简单，直接在与非门后面接上一个非门不就好了，负负得正嘛，与非门串联非门不就把非字消下去了。

五、或非门

这里我们还是先观察真值表，与现有门对比后发现，这或非门的真值表和与门的真值表是对称的关系，由此我们就可以思考，如何在与门的基础上将其真值表反转呢，问题简化一下，发现只需要将第一列与第四列取反即可，因为只有这两列不同。 这时我们想到，在与门中，输入两红输出红（0低电平），输入两绿输出绿（1高电平），如果我们将输入的两红在半路上转换成两绿不就行了，同理把输入的两绿在半路转换成两红。因此只需要在输入分别接上两个非门或者与非门（单输入的情况下与非门等价于非门）即可，我这里选用与非门。

七、或门

同样先观察真值表，我们发现这个或门的真值表和或非门是相反的关系，和与非门是对称的关系，通过我们上一步总结的经验，相反关系转换只需转换输出，对称关系转换只需转换输入，我们只需要将或非门输出中的非门拆掉即可。

八、高电平

通过前面的七关我们发现了一些规律，现在我们将规律总结一下。我们发现，与非门和与门是相反关系，和或门是对称关系；或非门和或门是相反关系，和与门是对称关系；相反关系的转换只需要转换输出；对称关系的转换只需要转换输入。恭喜你，当你得到这四条规律后将它们组合在一起就是著名的德·摩根定律。

这个词条在通关高电平后才会出现，而你，我的朋友，你提前一步总结出来了，下面就让我们快速通关高电平进入下一关吧。观察真值表发现，这关需要无论输入是什么颜色，最后都要输出绿色，我们可以感觉到，这关有两种种大同小异的解法，一种是在与非门的基础上改进，另一种是在或非门的基础上改进，按照使用最少电路元气件的原则，我们以与非门为例（或非门同理），只要与非门不出现两绿的输入，不就可以一直输出绿了，化简问题，只要与非门的两个输入一直相反，就可以一直输出绿色，因此找到两个相反关系的门不就可以了，显然根据我们刚刚总结的定律，或门和或非门分别连接即可。

九、第二刻

通过上一关我们了解到，原来绿色的叫高电平，那么同理，红色的就是低电平。第二刻这关开始有难度了，我们需要好好理解我们总结的定律才行。通过观察真值表我们发现，这里似乎引入了条件判断，即只有第二个输入为低电平，且第一个输入为高电平时， 才输出绿。既然难度升级了，那么我们的思维也要升级，索性就不通过真值表来看了，直接通过逻辑思维解决。解法如下：如果第二刻输入为低电平，即代表有机会输出为高电平，此时我们就可以去判断第一刻的电平了，否则没有必要去判断第一刻的电平。这里我们引入编程中的true和false的概念，高电平代表true，低电平代表false，将与门作为最终判断的门，只有它的的输入都为true时，输出才会为true。第一刻直接连到与门上即可，因为第一刻输入为true时逻辑上也是true，那第二刻怎么办才能将实际上的false转换为逻辑上的true呢，很简单，通过与非门或者非门即可完成转换。

十、异或门

上一关我们学会了如何对真值表进行抽象去搭建逻辑电路，抽象的技巧很重要，毕竟计算机就是根据一层一层的抽象搭建起来的。这一关我们来到了异或门 ，游戏开局就告诉了我们，这关有一定难度，不过既然都玩上这个游戏了，说明我们都是喜欢挑战的人类。

还是先观察真值表，我们发现本关是当第一刻与第二刻的输入不同时输出true，否则输出false。根据我们之前的条件判断语句的设计思路，使用与门作为条件判断门，然后开始构思如何才能当两个输入不同时输出true，相同时输出false。根据提示，我们得知可以将一个输出连接到两个输入上，那么这样我们就可以将两个输入关联起来，使得它们的输入都可以影响到对方的输出。我们发现与非门和或门的真值表，当输入不同时都会输出true，而当两个高电平与非门会输出false，或门输出true；两个低电平或门输出true，与非门输出false（德·摩根定律中的对称关系），由此，问题解决，在输入不同时，总有一个门输出为false，输入相同时，总是输出true。

十一、三路或门

上一关其实还有很多种不同的解法，读者可以自行探索，比如如何只用与非门实现异或门（提示，当一个组合门的真值表与现有门的真值表相同时是可以直接用这个真值表代替的，作者称之为化简）。这一关是三路或门，很简单用或门逐级递归即可。（这个递归思想要好好理解）

十二、三路与门

同上一关解法。

十三、同或门

同或门的真值表与异或门的真值表相反，我们在异或门的最后的判断输出中加上一个非门即可，这里作者用的是异或门的另一种实现方式，感兴趣的读者可以试着看能不能将这个电路化简。

十四、总结

到这，我们的第一部分——基础逻辑电路搭建就完成了，我们获得了所有的基础逻辑电路，靠着这些我们就可以步入下一部分，存储器和算术运算了，下一部分作者打算拆成两部分去分别讲解。