Logic Gates
From ComputingForScientists
Contents 
1. Logic Gates
1.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
1.2. Motivation
 The next component needed for computing after the transistor is the logic gate.
1.3. Logic Gate Use
Using transistors, we can create logic gates. Each gate has several inputs and one output. The relationship between the inputs and the output determines the type of gate. This relationship is defined by a logic table.
1.4. Logic Tables
Logic tables are used to define the inputs and outputs of logic circuits. Each input and output has two possible states: 1
or 0
, true
or false
, on
or off
, and high
or low
. All of these representations are equivalent.
1.5. Logic Circuit Analogy
Previously, we used a hydraulic analogy to help understand how a transistor worked. We use a "circuit analogy" to help us understand how a neuron works. An active research area uses everything we know about logic and computers and attempts to use this to help us understand how the brain works using a "computer analogy". The last panel shows how a neuron can be conceptualized as a logic circuit. On the lefthand side are the inputs (in this class, we deal mostly with circuits that have two inputs). The righthand side is the output.
From www.doc.ic.ac.uk on May 18 2019 13:24:33.
Sketch of a synapse.  From www.doc.ic.ac.uk on May 18 2019 13:24:34.
Sketch of a neuron.  
From www.doc.ic.ac.uk on May 18 2019 13:24:34.
Logic gate analogy of how a neuron works. 
1.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"). If either input is 0, then the output of the AND gate is 0. Thus, in order to get an AND gate to output 1, both inputs must be 1. The word AND is not an acronym. The word is capitalized to indicate that we mean a logic gate instead of the english word "and". 
1.7. Using an AND gate
The following is a screenshot showing a set of four circuits created using Logicly (we will use this program in class). Note that the on/off switches are "on" when the switch is in what we normally call the "off" position for a light switch. (Similar to the operation of the electric chair switch [1]).
1.8. Mechanical Analogy
Water flows into one, both, or none of the two white tubes at the top. When water is flowing into both inputs, the streams intersect and the "AND" bucket fills up. When water is only flowing though one input, the stream overshoots the "AND" bucket.
See also [2]. ("XOR = Exclusive OR ")
1.9. NAND Gate
All digital logic circuits you need can be built from NAND gates.
NAND stands for "Negated AND". The output of the NAND gate is the negation, or reverse, of the output of an AND gate. The negation is symbolized by the small circle on the output. The logic table for the NAND gate is created by swapping 1s with 0s and 0s with 1s in the output column.


1.10. OR Gate

If either input is 1, then the output of the OR gate is 1. Thus, in order to get an OR gate to output 0, both inputs must be 0.
1.11. Combining logic gates
Logic gates may be combined. In this example, there are four inputs, but we set two of them to always be 1
.
Here is an example of combining logic gates to get a logic table. There are two inputs (A and B) and one output. Note that this combination of NAND gates gives the same logic table as the OR gate. This means if you need an OR gate but only have NAND gates, you can still emulate an OR gate by combining the NAND gates as shown.

1.12. 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.
1.13. NOR Gate using NANDs
Verify that this will give the correct logic table for a NOR Gate.

1.14. 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.

2. Problems
2.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?
 X = 1, Y = 1
 X = 1, Y = 0
 X = 0, Y = 1
 X = 0, Y = 0
Answer 

X = 1, Y = 1 
2.2. Logic Gate Combinations
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

Answer 

D. Z = 0, Output = 1. 
2.3. Logic Gate Combinations
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 = 1
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

Answer 

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

2.5. Logic Gates
Two AND, two NOT, and an OR gate connected as shown in the image. In contrast to gates you have used previously, a NOT gate has only one input and one output. If the input to the NOT gate is 0, the output is 1. If the input is 1, the output is 0. (Ignore the faint rectangle next to the OR gate. It is a printing artifact.)
 Generate a table with a columns labeled
A
,B
,Output
.  For each of the possible combinations of
A
andB
, enter the corresponding value forOutput
.
[[ image:AND_NOT_OR1.png400px]]
Answer 

2.6. Logic Gates
Below are two AND, two NOT, and an OR gate connected.
[[ image:AND_NOT_OR1.png400px]] The logic table for the NOT gate is given. In contrast to gates you have used previously, a NOT gate has only one input and one output. If the input to the NOT gate is 0, the output is 1. If the input is 1, the output is 0. 
[[ Image:ORchart.png400px]] 
Answer 

2.7. Logic Circuits
For the two problems given below, determine the values of W, X, Y and Z.
2.7.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
Answer 

W =1, X =1, Y = 0, Z = 1 
2.7.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
Answer 

W =1, X =1, Y = 0, Z = 1 
2.8. Logic Circuits
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 
Answer 

Output X = 1 and Y = 0 cannot be computed 
2.9. Logic Circuits
 Write down the logic table for the OR, AND, and NAND gates.
 Write down the logic table corresponding to the image shown.
Answer  

OR
AND
NAND
For this image:

2.10. Logic Circuits
 Write down the logic table for the OR, AND, and NAND gates.
 Write down the logic table corresponding to the image shown.
Answer  

OR
AND
NAND
For this image:

2.11. Logic Circuits
What are A & B?
Answer 

A = 1 and B = 1 
3. Activities
3.1. Using logic.ly
http://logic.ly/demo is a program that allows you to combine logic gates and switches. Each of the four configurations shown correspond to a row in the AND logic table. The "both switches off" case corresponds to the first row in the logic table. The "both switches on" case corresponds to the last row in the logic table. Here is how to translate the numbers in the table to the symbols in the diagram:

AND logic table

 Start up http://logic.ly/demo and wire together gates, switches, and bulbs as on the image in #Using_logic.ly. Verify that the four switch configurations give the same result as that shown in the image.
 Figure out the XNOR logic table by connecting switches to an XNOR gate and then writing down what various configurations of the switches (input) gives for the light bulb (output).
 Verify that the table for the 1bit adder is correct by selecting the onebit adder and flipping the switches into different configurations.
This video shows how to do the first two steps.
Answer  

 0: switch OFF or light bulb OFF  1: swich ON or light bulb ON 
3.2. Bird brain
In this problem, you will practice translating a set of statements about a system (a bird) to a logic diagram. Read [3] and answer the following question.
Create a circuit using http://logic.ly/demo that reproduces Table 2 at [4]. Label the inputs and outputs appropriately (That is, tell me what a switch in the on or off position corresponds to in Table 2. What does a lit/unlit bulb correspond to in Table 2?.)
Answer 

4. Resources
 How Brain Science Will Change Computing [5]
 "The Tinkertoy Computer" [6]
 This unusual video describes how to create an OR gate in a video game [7].
Sorry about the "Demo mode" overlay on the video. I have a license for the software on a computer that is at the office.