Turing Complete

简介

图灵完备（Turing Complete）是一款计算机知识的模拟类游戏，游戏提供了从最基础逻辑门开始到完整计算机硬件的仿真模拟，

逻辑运算

与(AND): AB, A,B同时为1，结果才为1，否则为0；

或(OR): A+B，A,B任一为1，结果就为1，否则为0；

非(N): A'， 结果取反；

与非门(NAND): (AB)'，A，B先与后反

或非门(NOR): (A+B)'，A，B先或后反

异或门(XOR): A'B+AB' = A (xor) B，A，B不同时结果为1，相同为0；

同或门(XNOR): AB+'A'B，A，B相同时结果为1，不同为0；

三路或(OR3): A+B+C，A，B，C3个任意为1，结果为1，全部为0时才为0；

三路与(AND3): ABC，A，B，C3个全为1时结果为1，否则为0；

基本运算定律

• 优先级: ' > * > +
• 交换律: a+b=b+a, ab=ba
• 结合律: (a+b)+c=a+(b+c), a(bc)=(ab)c
• 分配律: a(b+c)=ab+ac, (a+b)c=ac+bc
• 反演律(德摩根定律): (a+b+c)'=a'b'c', (abc)'=a'+b'+c'
• 吸收律: a+ab=a, a(a+b)=a
• 幂等律: a+a=a, a*a=a
• 对合律: a''=a
• 互补律: a+a'=1, a*a'=0
• 幺元律: a+0=a, a*1=a
• 极元律: a+1=1, a*0=0

真值表法

方法1：以真值表内输出端“1”为准

1. 从真值表内找输出端为1的各行;
2. 把每行的输入变量写成与(*)的形式, 遇到0的输入变量上加非号;
3. 把各与项相或(+)，即得逻辑函数的表达式。

方法2：以真值表内输出端“0”为准

1. 从真值表内找输出端为0的各行;
2. 把每行的输入变量写成或(+)的形式，遇到1的输入变量上加非号;
3. 把各或项相与(*)，即得逻辑函数表达式。

最后化简，在实际运用过程中，哪个方法简便就采用哪种。

各关解法

成对的麻烦

题目描述

总共4个输入A,B,C,D, 一个输出. 当有2个或以上输入为1时, 输出1, 否则输出0

解法

根据真值表, 求得表达式:

1
2
3

Z = ABCD +
    A'BCD+AB'CD+ABC'D+ABCD' +
    ABC'D'+AB'CD'+AB'C'D+A'BCD'+A'BC'D+A'B'CD

奇数个信号

题目描述

• 输入: A, B, C, D,
• 输出: Z.
• 输入输出关系: 当有奇数个输入为1时, 输出为1; 否则为0.
• 限制: 最多只能用3个元件

解法

1
2
3
4
5

Z = (A+B+C+D)(A'+'B+C+D)(A'+B+C'+D)(A'+B+C+D')(A+'B+C'+D)(A+B'+C+D')(A+B+C'+D')(A'+B'+C'+D')
Z = AB'C'D'+A'BC'D'+A'B'CD'+A'B'C'D+A'BCD+AB'CD+ABC'D+ABCD'
E = A'B+AB'
F = C'D+CD'
Z=E'F+EF'

信号计数

题目描述

• 输入: A,B,C,D
• 输出: X, Y, Z
• 输入输出关系:

真值表:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

X = AB'C'D'+A'BCD + BA'C'D'+CA'B'D' + DA'B'C'+D'ABC + C'ABD+B'ACD (奇数个)
  = A(B+C+D)'+A'(BCD)
   +B(A+C+D)'+B'(ACD)
   +C(A+B+D)'+C'(ABD)
   +D(A+B+C)'+D'(ABC) 

Y = (A+B+C+D)(A'+B+C+D)(A+B'+C+D)(A+B+C'+D)(A+B+C+D')(A'+B'+C'+D')
  = (A+(B+C+D))(A(BCD))'(A'+(B+C+D))(B'+(A+C+D))(C'+(A+B+D))(D'+(A+B+C))

Z = ABCD = A(BCD)

全加器

题目描述

• 输入: A, B, C
• 输出: SUM, CAR.
• 输入输出关系: SUM = (A+B+C) MOD 2, CAR = FLOOR( (A+B+C) / 2 )
• 限制: 无

真值表

解法

1
2
3
4
5
6
7
8
9

SUM = AB'C'+BA'C'+CA'B'+ABC
    = A'(BC'+B'C) + A(B'C' + BC)
    = A'(B XOR C) + A(B NXOR C)

CAR = C'AB + B'AC + A'BC + ABC
    = C'AB + B'AC + BC(A'+A)
    = C'AB + B'AC + BC
    = A(C'B+B'C) + BC
    = A(B XOR C) + BC

参考