# 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

# 3. Pre-questions

Q: How do we build a one bit adding machine?

# 4. Slides

Related:

## 4.2. Transistor Overview

 A positive voltage in the BASE cases a big current in the COLLECTOR there is also a small current through the base, but usually less than 1% of the collector's current Changes in Current can be changed into changes in Voltage The use of simple resistors let us build positive and negative switches 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.satcure-focus.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

Input A Input B Output
0 0 0
0 1 0
1 0 0
1 1 1

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

From upload.wikimedia.org on June 25 2017 14:55:27.

## 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".

Input A Input B Output
0 0 1
0 1 1
1 0 1
1 1 0
Input A Input B Output
0 0 0
0 1 0
1 0 0
1 1 1

## 4.11. OR Gate

Input A Input B Output
0 0 0
0 1 1
1 0 1
1 1 1

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

Input A Input B Output
0 0 1
0 1 1
1 0 1
1 1 0

## 4.13. NOR Gate

Input A Input B Output
0 0 1
0 1 0
1 0 0
1 1 0

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.

Input A Input B Output
0 0 1
0 1 1
1 0 1
1 1 0

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

Input A Input B Output
0 0 0
0 1 1
1 0 1
1 1 0
From upload.wikimedia.org on June 25 2017 14:55:27.

• When adding two binary numbers
• the second-most 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
• 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

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
____



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.

1. X = 1, Y = 1
2. X = 1, Y = 0
3. X = 0, Y = 1
4. X = 0, Y = 0

Input A Input B Output
0 0 1
0 1 1
1 0 1
1 1 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.

1. Z = 1, Output = 0
2. Z = 0, Output = 0
3. Z = 1, Output = 1
4. Z = 0, Output = 1

Input A Input B Output
0 0 1
0 1 1
1 0 1
1 1 0

## 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

1. W =1, X =1, Y = 0, Z = 1
2. W =1, X =1, Y = 1, Z = 1
3. W =1, X =0, Y = 1, Z = 1
4. W =1, X =0, Y = 1, Z = 0
5. W =1, X =1, Y = 0, Z = 0

### 5.3.2. Part 2

If: A = 0, B = 1, C = 0

1. W =1, X =1, Y = 0, Z = 1
2. W =1, X =1, Y = 1, Z = 1
3. W =1, X =0, Y = 1, Z = 1
4. W =1, X =0, Y = 1, Z = 0
5. W =1, X =1, Y = 0, Z = 0
Input A Input B Output
0 0 0
0 1 0
1 0 0
1 1 1
Input A Input B Output
0 0 1
0 1 1
1 0 1
1 1 0
Input A Input B Output
0 0 0
0 1 1
1 0 1
1 1 1

## 5.4. Logic Circuits II

### 5.4.1. Part 1

If A =0, B =0, C = 1,

1. W =0, X =1, Y = 0, Z = 1
2. W =1, X =1, Y = 0, Z = 1
3. W =0, X =1, Y = 1, Z = 1
4. W =1, X =0, Y = 1, Z = 1
5. W =1, X =1, Y = 0, Z = 0

### 5.4.2. Part 2

A =0, B =1, C = 0,

1. W =0, X =1, Y = 0, Z = 1
2. W =1, X =1, Y = 0, Z = 1
3. W =0, X =1, Y = 1, Z = 1
4. W =1, X =0, Y = 1, Z = 1
5. W =1, X =1, Y = 0, Z = 0
Input A Input B Output
0 0 1
0 1 0
1 0 0
1 1 0
Input A Input B Output
0 0 1
0 1 1
1 0 1
1 1 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