sheng/Logic Gates
From CDS 130
1. Objectives
 Explain what a logic circuit and logic table are
 Explain how logic circuits can be combined to do more complex calculations and to manipulate binary numbers
 Be able to explain how electronic switches are used to create simple logic circuits
2. Motivation
 We are getting closer to being able to do science with a computer ... now that we know how binary numbers work, we need to make machines that can compute
 George Dyson at the birth of the computer
neuron analogy  

The equivalent to the atom in chemistry (the most basic component of which everything is built upon) in computers is the transistor.

3. Prequestions
Q: How do we build a one bit adding machine?
4. Slides
4.1. Introduction
Related:
 "The Tinkertoy Computer" http://www.amazon.com/gp/product/071672491X
4.2. Transistor Overview

From www.coltecnica.com on July 04 2014 06:03:07.

4.3. The hydraulic analogy
When thinking about electronics, it is often easier to think in terms of water flow, or a "hydraulic analogy", because water is something that is more familiar. It is said that the transistor can be used as an amplifier and switch. Explain how this contraption can be used to amplify a "signal". See also 
From www.satcurefocus.com on June 21 2017 13:43:18.

4.4. Logic Circuits
 Using transistors, we can create logic circuits
 Each circuit has one output and several inputs
 The relationship between the inputs and the output determines the type of circuit
4.5. Logic Tables
 Logic tables are used to define the inputs and outputs of logic circuits
 Each input and output has two possible states
 We sometimes use
 1 or 0
 true or false
 on or off
 high or low
 All of the above representations are equivalent!
4.6. AND Gate

The diagram of the AND gate looks like a capital letter D with two "prongs" on the left (the inputs) and one "prong" on the right (the output). The inputs are either 0 (also known as "false") or 1 (also known as "true"). The thing to remember about the AND gate is this: if either of the inputs is 0, then the output of the AND gate is 0. Thus, in order to get an AND gate to output 1, both inputs to it must be 1.
4.7. Question
Use the hydraulic contraption to build an AND gate.
4.8. Answer
4.9. Another example
Water flows into one, both, or none of the two white tubes at the top. Why does it produce an AND and XOR logic? See also [1].
4.10. NAND Gate
All digital logic circuits you need can be built from NAND gates. If you build a faster NAND gate, the world will beat a path to your door.
NAND stands for "Negated AND". Thus, the output of the NAND gate is the negation, or reverse of the output of an AND gate with the same inputs (0 negated equals 1, and 1 negated equals 0). The negation is symbolized by the small circle on the right "prong".


4.11. OR Gate

If either of the inputs is 1, then the output of the OR gate is 1. Thus, in order to get an OR gate to output 0, both inputs to it must be 0.
4.12. OR Gate using NANDs

4.13. NOR Gate

NOR stands for "Negated OR". Thus, the output of the NOR gate is the negation, or reverse of the output of an OR gate with the same inputs.
4.14. NOR Gate using NANDs
Verify that this will give the correct logic table for a NOR Gate.

4.15. XOR Gates
 XOR stands for "eXclusive OR". (A.K.A. EOR)
 An XOR gate will output 1 only if one of the inputs is 1 and the other input 0.
 If both inputs are the same (1 and 1, or 0 and 0), then XOR outputs 0.

How does this device work? See also [2].
4.16. Adding Binary Numbers
 When adding two binary numbers
 the secondmost complex operation is 1+1=10
 the most complex operation is 1+1+1=11
 11 only happens when we carry data from a previous column
 You can think of the problem as
carry in + Digit A + Digit B = result + carry out
 If you can do this operation, you can repeat it to add any two binary numbers
Recall from previous module:
 Use the same principles as adding two decimal numbers
 Add the two digits
 Carry the results to the next column
1 1 0 1 1 0 + 0 0 1 1 1 _________ 0 1
Because 1+1 = 10 in binary
4.17. Adding Binary Numbers
Two XOR gates, three NAND gates  or 16 transistors
4.18. Binary Addition Sample Problem
If A = 1, B = 0, and carry in = 1:
carry in 1 A => 1 + B + 0 ____ _____
4.19. Question
How would you configure a set of gates to add
carry in A + B C ____
4.20. Another Adding Machine
Create with Scratch [3].
5. Questions
5.1. NAND Gates
In the image below, two NAND Gates are shown. One of the inputs to each of the NAND gates is set to 1
. If B = 0 and A = 0, what will the outputs X
and Y
be? For reference, the logic table for a NAND gate is shown below.
 X = 1, Y = 1
 X = 1, Y = 0
 X = 0, Y = 1
 X = 0, Y = 0

5.2. Combination of NANDs
In the image below, four NANDS are connected and three of the inputs are set to 1
. What are the values of Z
and Output
if B = 0 and A = 0? For reference, the logic table associated with a NAND gate is shown.
 Z = 1, Output = 0
 Z = 0, Output = 0
 Z = 1, Output = 1
 Z = 0, Output = 1

5.3. Logic Circuits I
For the two problems given below, determine the values of W, X, Y and Z. Logic table references are provided to assist you.
5.3.1. Part 1
If: A = 0, B = 0, C = 1
 W =1, X =1, Y = 0, Z = 1
 W =1, X =1, Y = 1, Z = 1
 W =1, X =0, Y = 1, Z = 1
 W =1, X =0, Y = 1, Z = 0
 W =1, X =1, Y = 0, Z = 0
5.3.2. Part 2
If: A = 0, B = 1, C = 0
 W =1, X =1, Y = 0, Z = 1
 W =1, X =1, Y = 1, Z = 1
 W =1, X =0, Y = 1, Z = 1
 W =1, X =0, Y = 1, Z = 0
 W =1, X =1, Y = 0, Z = 0



5.4. Logic Circuits II
5.4.1. Part 1
If A =0, B =0, C = 1,
 W =0, X =1, Y = 0, Z = 1
 W =1, X =1, Y = 0, Z = 1
 W =0, X =1, Y = 1, Z = 1
 W =1, X =0, Y = 1, Z = 1
 W =1, X =1, Y = 0, Z = 0
5.4.2. Part 2
A =0, B =1, C = 0,
 W =0, X =1, Y = 0, Z = 1
 W =1, X =1, Y = 0, Z = 1
 W =0, X =1, Y = 1, Z = 1
 W =1, X =0, Y = 1, Z = 1
 W =1, X =1, Y = 0, Z = 0


5.5. Consider the following logic circuit, with inputs A, B, C and D, and outputs X and Y. Which output CANNOT BE COMPUTED for ANY assignment of 1 or 0 to inputs A, B, C and D? (Note: Each of the four inputs, A, B, C and D must be assigned a value of either 1 or 0)
A. Output X = 0 and Y = 0 cannot be computed 
B. Output X = 0 and Y = 1 cannot be computed 
C. Output X = 1 and Y = 0 cannot be computed 
D. Output X = 1 and Y = 1 cannot be computed 
E. All four outputs can be computed 
5.6. Consider the following logic circuit, with inputs A, B, C and D, and outputs X, Y and Z. For this circuit, some outputs can be computed and some outputs cannot be computed. Which of the following outputs CANNOT be computed?
A. Output X = 0, Y = 0, and Z = 0 cannot be computed 
B. Output X = 1, Y = 0, and Z = 0 cannot be computed 
C. Output X = 1, Y = 0, and Z = 1 cannot be computed 
D. Output X = 1, Y = 1, and Z = 1 cannot be computed 
E. Output X = 1, Y = 1, and Z = 0 cannot be computed 
5.7. Logic Gates
Consider the following logic circuit, with inputs A, B, C and D, and outputs X and Y. Which output CANNOT BE COMPUTED for ANY assignment of 1 or 0 to inputs A, B, C and D? (Note: Each of the four inputs, A, B, C and D must be assigned a value of either 1 or 0)
A. Output X = 0 and Y = 0 cannot be computed 
B. Output X = 0 and Y = 1 cannot be computed 
C. Output X = 1 and Y = 0 cannot be computed 
D. Output X = 1 and Y = 1 cannot be computed 
E. All four outputs can be computed 
5.8. Logic Gates
Consider the following logic circuit, with inputs A, B, C and D, and outputs X, Y and Z. For this circuit, some outputs can be computed and some outputs cannot be computed. Which of the following outputs CANNOT be computed?
A. Output X = 0, Y = 0, and Z = 0 cannot be computed 
B. Output X = 1, Y = 0, and Z = 0 cannot be computed 
C. Output X = 1, Y = 0, and Z = 1 cannot be computed 
D. Output X = 1, Y = 1, and Z = 1 cannot be computed 
E. Output X = 1, Y = 1, and Z = 0 cannot be computed 