Turing Complete解法分享

【持续更新ing…】

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

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

Not(Not AND)

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

NOR门去掉Not即可。

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

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

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

当然是用开关乱糊了

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