SM242 Week 2 (Notes based on Epp Chapter 1)
I. Logic (continued)
20. Logic Gates Consider the circuit below which has 2 switches in series:
S1 S2
Light
When will the light turn on?
We can represent the light's operation using a table:
S1 S2 Light
open open off
open shut off
shut open off
shut shut on
Change the words open and off to F and the words shut and on to T and the table becomes
S1 S2 Light This is the truth table for the logical connective.
F F F We can say that the circuit above corresponds
F T F to S1 S2.
T F F
T T T
Now consider the circuit that has 2 switches in parallel.
S1
S2 Light
When will the light turn on?
We can represent the light's operation using a table
S1 S2 Light
open open off
open shut on
shut open on
shut shut on
Changing the words open and off to F and the words shut and on to T and the table becomes
S1 S2 Light
F F F
F T T This is the truth table for the logical connective.
T F T We can say that the circuit above corresponds to S1 S2.
T T T
Notes:
· Usually, when designing circuits, the symbol 0 is used to denote F and the symbol 1 is used to denote T.
· A compound expression as we are using it here (in the context of logic circuits) is called a Boolean expression. We will develop a more formal definition of a Boolean expression later in the course.
To a Computer Scientist, the computer’s hardware is comprised of digital logic circuits. Digital logic circuits are built from just a handful of primitive elements, called logic gates, combined in various ways.
In a digital logic circuit, only two values may be present. The values may be and + 5 volts. Or the values may be 0.5 and 3.5 volts. Or the values may be… you get the picture. To allow consideration of all of these possibilities, we will say that digital logic circuits allow the presence of two logical values: 0 and 1.
So, signals in a digital logic circuit take on the values of 0 or 1. Logic gates are devices which compute functions of these binary signals.
In this course we will consider three logic gates that are used to construct digital logic circuits:
A. Not gate (inverter) Has one input and one output. If the input, P, is 1, the output is 0. If the input is 0, the output is 1.
Inverter or NOT gate
P ~P
0 1 Corresponds to the ~ connective
1 0
B. And gate – has two inputs and one output. If both inputs, say P and Q, are both 1 then the output is 1. Otherwise, the output is 0.
AND gate
P Q
0 0 0
0 1 0 Corresponds to the connective
1 0 0
1 1 1
C) Or gate – has two inputs and one output. If either or both inputs, say P and Q, are 1, the output is 1. Otherwise, the output is 0.
OR gate
P Q
0 0 0
0 1 1 Corresponds to the connective.
1 0 1
1 1 1
21. Combinational circuits
A. A combinational circuit is a digital logic circuit whose output is determined only by the current values of the inputs (with no dependence on past input values). A combinational circuit is built up by combining our three basic logic gates with the following provisos:
· The output of a gate may not eventually feed back to that same gate.
· The output lines from 2 different gates cannot be combined.
The following are not combinational circuits:
B. Example. The air conditioning plant on a ship is controlled by a logic circuit. The air conditioner will turn on (logical “1”) if the temperature is above 80°F (logical “1”). If the motor is overheating (logical “1”), however, a signal is sent to turn the air conditioner off. Sketch (within the box) the logic circuit to accomplish this design.
temp > 80°F
air conditioner
motor overheating
Answer:
C. Our study of combinational circuits will involve five (very much related!) tasks
· (Task 1) Given a digital logic circuit, write the corresponding Boolean expression.
· (Task 2) Given a Boolean expression, draw a digital logic circuit that represents this expression.
· (Task 3) Given a digital logic circuit, construct the corresponding truth table.
· (Task 4) Given a truth table, construct a digital logic circuit that implements this truth table.
· (Task 5) Given a digital logic circuit, design a simpler digital logic circuit that performs the equivalent function.
TASK 1: Given a digital logic circuit, write the corresponding Boolean expression.
The Boolean expression corresponding to a digital logic circuit can be determined by evaluating the effect of the logic gates on the input expressions.
Example: Determine the Boolean expression corresponding to the digital logic circuit shown.
Example. Write the Boolean expression for the logic circuit shown below.
Evaluating the effect of the logic gates on the input expressions, we see:
TASK 2: Given an expression, draw a digital logic circuit that represents this expression.
The basic approach is to write the expression on the right side of the page. Draw the circuit from right to left, by working from the outermost part of the expression.
Example: Construct a digital logic circuit that will implement the Boolean expression (p ~ q) ~ p
At the highest level, we are
Now, let’s continue to deconstruct this by looking at the top term,
Finally,
Example: Draw a digital logic circuit that represents the Boolean expression x (y ~ (x ~ z))
TASK 3: Given a digital logic circuit, construct the corresponding truth table.
There are many convenient ways to do this. We can determine the corresponding Boolean expression (TASK 1) and construct a truth table as we did in Week 1. Or, alternatively, we can trace through the circuit for each possible combination of input values.
Example: Construct the truth table corresponding to the circuit shown.
Substitute p = 0 and q = 0 and r = 0 and trace through the circuit gate by gate. Repeat this for the other combinations of input values. The resulting truth table is
p q output
Example. Construct the truth table for the circuit shown below.
p q output
Have you seen this truth table before?
Example. Write the Boolean expression for the logic circuit shown below, and then construct the truth table for it.
Evaluating the effect of the logic gates on the input expressions, we see that the output is:
How many rows will be in this truth table?
The truth table is
p q r
Aside an aside (and not related to the example above), note that for AND gates and OR gates, we will allow more than two inputs. For a multi-input AND gate, the output is one if ALL of the inputs are 1. For a multi-input OR gate, the output is 1 is ANY one of the inputs is a 1 (or if more than one input is a 1). The example below shows what we mean.
Example. Design a digital logic circuit to implement the Boolean expression if:
(a) You only have 2-input gates available.
(b) You have gates with any number of inputs allowed.
TASK 4: Given a truth table, construct a digital logic circuit that implements this truth table.
Suppose the input expressions are .
a. Identify the rows of the truth table that have an output of 1.
b. For each such row, form the Boolean expression.
where if in this row, and if in this row.
c. After step b., we will have one Boolean expression corresponding to each row that had an output of 1. Take the disjunction of all these Boolean expressions. The resulting expression has the truth table under evaluation. (As an aside, an expression such as this, which is a disjunction of several terms, where each of these terms is a conjunction of irreducible expressions, is said to be disjunctive normal form.)
d. Form the digital logic circuit from this Boolean expression using the technique discussed in TASK 2 above.
Example: Construct a logic circuit for the truth table shown.
p q output
0 0 0
0 1 1
1 0 0
1 1 1
Solution:
p q output
0 0 0
0 1 1
1 0 0
1 1 1
Example: Construct a logic circuit for the truth table shown.
A B C Output
TASK 5: Given a digital logic circuit, design a simpler digital logic circuit that performs the equivalent function.
a. Find the Boolean expression that corresponds to this logic circuit (TASK 1 above).
b. Use the Table on page 14 of the text to find a simpler logically equivalent Boolean expression.
c. Given this simpler Boolean expression, draw the digital logic circuit that represents this expression (TASK 2 above). This simpler circuit will perform precisely the same way as the original (more complex) circuit.
Example. Suppose we find that a logic circuit has the Boolean expression
Can this circuit be simplified?
Note: In IC220 (Computer Architecture and Organization) you will learn an important additional technique (the Karnaugh Map) to accomplish TASK 5 above.
22. Examples
Question 1 You have been tasked with designing the sprinkler system for the Commanding Officer’s stateroom. The CO’s stateroom has three smoke alarms. Since the CO will be very angry if his stateroom is drenched by a false or spurious alarm, you decide that the sprinkler system will not be activated by any single smoke alarm. The sprinkler system will activate if any two of the smoke alarms activate (or if all three activate).
a. Write a truth table that describes how the sprinkler operation will depend on the status of the three smoke alarms. (Clearly state what you intend by logical 1 and logical 0.)
b. Based on your truth table, design the digital logical circuit.
Let logical 1 mean the alarm/sprinkler is on.
Question 2 Let’s pretend that there are four midshipman who are very good friends (remember, this is just pretending). Their names are:
MIDN Miller
MIDN Porter
MIDN Lees
MIDN Wolz
Although they are all good friends, MIDN Lees and MIDN Wolz are youngsters, so they “kinda-sorta” get, shall we say, “outvoted” when it comes to some decision-making.
Our four midshipmen always eat dinner together. In fact, they always eat dinner together in one of two locations: King Hall or California Pizza Kitchen (CPK). Each day, at 1645, they take a vote to decide where all four will eat. The voting works as follows:
· If there is a clear majority, the majority wins.
· If there is a tie vote, they all eat in King Hall with one exception: If MIDN Miller and MIDN Porter agree on CPK, they pull rank and their choice (CPK) wins out.
Design a digital logic circuit that will allow our four midshipmen to cast their votes electronically. Based on the votes, the logic circuit will decide (based on the rules above) where our midshipmen will be eating dinner that day. (To make our task of grading easier, please use the following convention: Let 1 denote a vote for CPK and 0 denote a vote for King Hall.)
Let 1 = CPK, 0 = King Hall
23. Number Representations
A. Decimal Integers and Decimal Notation
The decimal number system has 10 digits (0,1,2,3…9). Since it is based on 10 distinct symbols, we say the base is 10. In decimal notation, we write a number as a string of digits. To interpret a decimal number, we multiply each digit by the power of 10 associated with that digit’s position.
Example: Consider the decimal number: 6349.
This number is:
6 3 4 9
B. The Binary Number System
The binary number system has two digits (0 and 1). The base is two. Just as with decimal notation, we write a number as a string of digits, but now each digit is 0 or 1. To interpret a binary number, we multiply each digit by the power of 2 associated with that digit’s position.
Example: Consider the binary number 1011.
This number is:
1 0 1 1 =
C. Converting a binary number to a decimal number
To convert a binary number to a decimal number, write the binary number as a sum of powers of 2.
Example: Express the binary number 1011 as a decimal number.
Note: We must be careful that the base is understood. When we say “11” above, we mean the number 11 in base 10, not the number 11 in base 2. If the base is not clear from context, it can be made explicit by including the base as a subscript as in:
Example: Express the binary number 110110 as a decimal number.
D. Converting a decimal integer to a binary number
1. Method 1. Express the decimal number as a sum of powers of 2. To do this:
i. find the highest power of two less than or equal to the decimal number. The binary representation will have a one in this position.
ii. Now subtract this power of two from the original decimal number.
iii. If this new decimal number is zero, we’re done. Otherwise return to step i. above.
Example: Convert the decimal number 78 to binary.
Think to yourself: Self, what is the largest power of 2 that is less than or equal to 78.
is a power of 2 that is less than 78, but is it the largest?
So, the binary representation of 78 will have a one in the position:
______
Now, subtracting 64 from our number 78 gives . Thus, 14 is now the number we are working with.