Turing Complete Turing Complete: Basic Logic-Solution

Quick Notes

NOT GatesNOT gates (inverters) are 1-input gates that output the value opposite of the input. The negation of A is denoted by [A] (complement).

A[A]0110

AND GatesAND gates are 2-input gates that output 1 if both two inputs are 1. The conjunction of A and B is denoted by AB (product).

ABAB000100010111

OR GatesOR gates are 2-input gates that output 1 if one of two inputs is 1. The disjunction of A and B is denoted by A+B (sum).

ABA+B000101011111

XOR GatesXOR gates are 2-input gates that output 1 if two inputs are different. The exclusive disjunction of A and B is denoted by A{+}B (direct sum).

ABA{+}B000101011110

Useful PropertiesPropertyNOTANDORXORCommutativityAB=BAA+B=B+AA{+}B=B{+}AAssociativity(AB)C=A(BC)(A+B)+C=A+(B+C)(A{+}B){+}C=A{+}(B{+}C)DistributivityOR: A(B+C)=AB+AC

XOR: A(B{+}C)=AB{+}ACAND: A+BC=(A+B)(A+C)IdentityA1=AA+0=AA{+}0=AAbsorptionA0=0A+1=1InversionA{+}1=[A]ComplementA[A]=0A+[A]=1A{+}[A]=1DoublingAA=AA+A=AA{+}A=0Negation

De Morgan's Law[[A]]=ANAND

[AB]=[A]+[B]NOR

[A+B]=[A][B]XNOR

[A{+}B]=[A]{+}B=A{+}[B]

Links

https://steamcommunity.com/sharedfiles/filedetails/?id=3058316651

NAND Gate

Turing Complete: Basic Logic-Solution image 18

NAND is the negation of AND, so the output is inverted.

NOT Gate

Turing Complete: Basic Logic-Solution image 21

AA=A, so [AA]=[A].

AND Gate

Turing Complete: Basic Logic-Solution image 24

The double negation of a value remains unchanged.

OR Gate

Turing Complete: Basic Logic-Solution image 27

[A+B]=[A][B], so A+B=[[A][B]] and both inputs are inverted.

NOR Gate

Turing Complete: Basic Logic-Solution image 30

NOR is the negation of OR, so the output is inverted.

Always On

Turing Complete: Basic Logic-Solution image 33

A+[A]=1.

Second Tick

Turing Complete: Basic Logic-Solution image 36

The output is 1 only if A=1 and B=0, so A[B] satisfies the requirement.

XOR Gate

Turing Complete: Basic Logic-Solution image 39

Turing Complete: Basic Logic-Solution image 40

XOR means the output is 1 when either one of two inputs is 1 but not both, so the desired circuit should be (A+B)[AB].

4 NAND Gates We can simplify the expression

(A+B)[AB] as below:

(A+B)[AB]

A[AB]+B[AB] (distributive property)

[[A[AB]+B[AB]]] (double negation)

[[A[AB]][B[AB]]] (De Morgan's law)

Bigger AND Gate

Turing Complete: Basic Logic-Solution image 50

A0=0, so the output of bigger AND is 0 if one of its inputs is 0.

Bigger OR Gate

Turing Complete: Basic Logic-Solution image 53

A+1=1, so the output of bigger OR is 1 if one of its inputs is 1.

XNOR Gate

Turing Complete: Basic Logic-Solution image 56

XNOR is the negation of XOR, so the output is inverted.

Source: https://steamcommunity.com/sharedfiles/filedetails/?id=3078668306

Turing Complete: Basic Logic-Solution