Store Page
Turing Complete
All Discussions Screenshots Artwork Broadcasts Videos News Guides Reviews

Turing Complete

Store Page
Turing Complete > Guides > qwerty's Guides
Not enough ratings
Turing Complete: Basic Logic-Solution
By qwerty
Solution and explanation for levels in "Basic Logic".
This guide is subject to change.
   
Award
Favorite
Favorited
Unfavorite
Created by
qwerty
Online
Category: Walkthroughs
Languages: English
Posted
Updated
13 Nov, 2023 @ 1:33pm
21 Nov, 2023 @ 5:14am
1,053 Unique Visitors
9 Current Favorites
Guide Index
Overview
Quick Notes 
Links 
NAND Gate 
NOT Gate 
AND Gate 
OR Gate 
NOR Gate 
Always On 
Second Tick 
XOR Gate 
Bigger AND Gate 
Bigger OR Gate 
XNOR Gate 
Comments
Quick Notes
NOT Gates
NOT 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]
0
1
1
0

AND Gates
AND 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).
A
B
AB
0
0
0
1
0
0
0
1
0
1
1
1

OR Gates
OR 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).
A
B
A+B
0
0
0
1
0
1
0
1
1
1
1
1

XOR Gates
XOR 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).
A
B
A{+}B
0
0
0
1
0
1
0
1
1
1
1
0

Useful Properties
Property
NOT
AND
OR
XOR
Commutativity
AB=BA
A+B=B+A
A{+}B=B{+}A
Associativity
(AB)C=A(BC)
(A+B)+C=A+(B+C)
(A{+}B){+}C=A{+}(B{+}C)
Distributivity
OR: A(B+C)=AB+AC
XOR: A(B{+}C)=AB{+}AC
AND: A+BC=(A+B)(A+C)
Identity
A1=A
A+0=A
A{+}0=A
Absorption
A0=0
A+1=1
Inversion
A{+}1=[A]
Complement
A[A]=0
A+[A]=1
A{+}[A]=1
Doubling
AA=A
A+A=A
A{+}A=0
Negation
De Morgan's Law
[[A]]=A
NAND
[AB]=[A]+[B]
NOR
[A+B]=[A][B]
XNOR
[A{+}B]=[A]{+}B=A{+}[B]
NAND Gate
NAND is the negation of AND, so the output is inverted.
NOT Gate
AA=A, so [AA]=[A].
AND Gate
The double negation of a value remains unchanged.
OR Gate
[A+B]=[A][B], so A+B=[[A][B]] and both inputs are inverted.
NOR Gate
NOR is the negation of OR, so the output is inverted.
Always On
A+[A]=1.
Second Tick
The output is 1 only if A=1 and B=0, so A[B] satisfies the requirement.
XOR Gate
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
A0=0, so the output of bigger AND is 0 if one of its inputs is 0.
Bigger OR Gate
A+1=1, so the output of bigger OR is 1 if one of its inputs is 1.
XNOR Gate
XNOR is the negation of XOR, so the output is inverted.