Turing Complete

简介

逻辑运算

与(AND): AB

或(OR): A+B

非(N): A'

与非门(NAND): (AB)'

或非门(NOR): (A+B)'

异或门(XOR): A'B+AB' = A (xor) B

同或门(XNOR): AB+'A'B

三路或(OR3): A+B+C

三路与(AND3): ABC

基本运算定律

• 优先级:
• 交换律: 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

解法

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

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,
• 输出: Z.
• 输入输出关系: 当有奇数个输入为1时, 输出为1; 否则为0.
• 限制: 最多只能用3个元件

解法

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 = A^B^C^D+^AB^C^D+^A^BC^D+^A^B^CD+ABC^D+ABCD+AB^CD+A^BCD+^ABCD

E=(A^B+^AB)

F=(C^D+^CD)

Z=^EF+E^F

信号计数

题目描述

• 输入: 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
10

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

参考