Turing Complete解法分享

【持续更新ing…】

前几天玩通了，但是感觉布线有点乱于是从头打一遍。正好做个笔记。

基础逻辑电路

原力觉醒

与非门(NAND)

Not And嘛,反过来的and操作，但是好像物理上更好实现，所以是整个数电的基础。

非门(NOT)

与门(AND)

Not(Not AND)

或非门(NOR)

注意到真值表和AND门刚好完全反过来。于是考虑对两个输入取非。

或门(OR)

NOR门去掉Not即可。

高电平(ON)

第二刻

观察输入可以发现仅在A = 1 B = 0输出1，即(A and not B)

异或门(XOR)

查询可以找到A xor B =( (A or not B ) and ( not A or B ) )

三路或门

三路与门

同或门(XNOR)

not xor.

算数运算

成对的麻烦

多于两个输出真，画出卡诺图、卡诺圈。

得到关系式P = AB + AC + AD + BC + BD + CD。

于是可以画出电路图

按理说应该是会有门更少的办法的（但是我懒嘛

奇数个信号

只有当奇数个输入1后输出才为1，只能用三个元件。

考虑xor的性质，a xor b xor b = a.所以如果很多个输入都xor了之后得到为0，说明输入有偶数个1，否则有奇数个1。

信号计数

输出有三位，分别考虑。

第一位可以用上题的方法，四个输入xor即可。

第二位是上上题的方法，

第三位将四个AND即可。

半加器

化简知道：Ci = A xor B, Ci+1 = A and B

全加器

同样，Ci = A xor B xor C, Ci+1 = AC + AB + BC

加倍

八位或

八位非

八位加法器

我没记错是有两种实现来着

同步进位加法器和异步进位加法器

1.异步进位：逐个相加即可。

2.同步进位：不太好设计（咕咕咕了

原理参考BV1aL41177Si

相反数

-x = not x +1

1位解码器

3位解码器

当然是用开关乱糊了

逻辑引擎

比较麻烦的是没有实现按位与然后需要重新画一遍。

存储器

奇变偶不变