Kauppasivu
Turing Complete
Kaikki Keskustelut Kuvakaappaukset Taideteokset Suoratoistot Videot Uutiset Oppaat Arvostelut

Turing Complete

Kauppasivu
Turing Complete > Oppaat > Käyttäjän qwerty oppaat
Ei tarpeeksi arvosteluja
Turing Complete: Basic Logic-Solution
Tekijältä qwerty
Solution and explanation for levels in "Basic Logic".
This guide is subject to change.
   
Palkinto
Lisää suosikkeihin
Lisätty suosikkeihin
Poista suosikeista
Tekijä
qwerty
Paikalla
Luokat: Läpipeluut
Languages: englanti
Julkaistu
Päivitetty
13.11.2023 klo 13.33
21.11.2023 klo 5.14
1,071 Uniikkeja kävijöitä
9 Nykyiset suosikit
Opashakemisto
Yleiskuva
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 
Kommentit
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.