Review L: Logic & circuits
printable version
L1:
[1]
// L2:
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
// L3:
[1]
[2]
[3]
[4]
[5]
[6]
Problem L1.1
For each of the following circuits, write
a truth table tabulating the circuit's output for each combination of
inputs.
a. 

b. 

a. 
  b. 
x  y  z  out 
0  0  0  0 
0  0  1  1 
0  1  0  1 
0  1  1  1 
1  0  0  0 
1  0  1  1 
1  1  0  0 
1  1  1  0 

Problem L2.1
For the following circuit, write the Boolean expression that
most closely corresponds to the circuit.
(x + y) x
Problem L2.2
For each of the following Boolean expressions,
draw the logic circuit corresponding most closely to it.
a. 
x + y + x 
b. 
x y + x y 
a. 

b. 

Problem L2.3
For each of the following Boolean expressions,
draw the logic circuit corresponding most closely to it.
a. 
w x + x y 
b. 
x (y z + y z) 
a. 

b. 

Problem L2.4
For each of the following Boolean expressions, write
a truth table tabulating the expression's value
for each combination of variable values.
a. 
x + x + y 
b. 
x y + x + z 
a. 
 b. 
x  y  z  out 
0  0  0  1 
0  0  1  0 
0  1  0  1 
0  1  1  0 
1  0  0  0 
1  0  1  0 
1  1  0  1 
1  1  1  1 

Problem L2.5
Consider the following C statement.
if (!(a < b && b < c)) between = 0;
a. Rewrite the if
condition to an
equivalent condition without using the NOT operator !
.
b. What is the name of the Boolean algebra law that this
illustrates?
a. if (a >= b  b >= c) between = 0;
b. DeMorgan's law
Problem L2.6
For each of the following,
what is the equivalent twooperator Boolean expression
according to DeMorgan's laws?
a. x y without “multiplication”
b. x + y without “addition”
Problem L2.8
What is the unminimized sumofproducts expression for the
following truth tables? (Use multiplication for AND, addition for
OR.)
a. 
 b. 
 c. 
x  y  z  out 
0  0  0  1 
0  0  1  1 
0  1  0  0 
0  1  1  0 
1  0  0  0 
1  0  1  1 
1  1  0  0 
1  1  1  0 

a. 
x y
+ x y 
b. 
x y
+ x y
+ x y 
c. 
x y z
+ x y z
+ x y z 
Problem L2.9
For the following truth table,
write the unminimized sumofproducts expression
and draw the corresponding circuit.
x  y  z  out 
0  0  0  0 
0  0  1  0 
0  1  0  1 
0  1  1  0 
1  0  0  1 
1  0  1  0 
1  1  0  0 
1  1  1  0 
The unminimized sumofproducts expression is
x y z + x y z.
Problem L2.10
Using AND, OR, and NOT gates, design a circuit
that takes three inputs i_{3}, i_{2}, and i_{1} and
two outputs p_{1} p_{0}
that are 11 (that is, both p_{1} and p_{0} are 1) when i_{3} is 1,
10 (p_{1} is 1, p_{0} is 0) when i_{3} is 0 but i_{2} is 1,
01 when i_{3} and i_{2} are 0 but i_{1} is 1,
and 00 when all inputs are 0.
(Incidentally, a component like this — computing the first 1 among
an ordered list of inputs — is called a priority encoder.)
i_{3}  i_{2}  i_{1}  p_{1}  p_{0} 
1  x  x  1  1 
0  1  x  1  0 
0  0  1  0  1 
0  0  0  0  0 
Problem L3.1
What is the depth of the following circuit?
3 (The path from x or y through the OR
gate, NOT gate, and AND gate goes through three gates. There is
another path from x just through the NOT and AND
gates, but it is shorter.)
Problem L3.2
Given the below Karnaugh map, identify the corresponding minimized
Boolean expression.
w x y + x z + x y
Problem L3.3
Draw a Karnaugh map corresponding to the following truth table,
and derive a minimized Boolean expression for the function.
x  y  z  out 
0  0  0  1 
0  0  1  0 
0  1  0  1 
0  1  1  0 
1  0  0  1 
1  0  1  0 
1  1  0  0 
1  1  1  1 
The resulting expression is
x z
+ y z
+ x y z.
Problem L3.4
Draw a Karnaugh map corresponding to each of the following truth
tables, and derive a minimized Boolean expression for the function
for each.
a. 
x  y  z  out 
0  0  0  0 
0  0  1  1 
0  1  0  0 
0  1  1  1 
1  0  0  0 
1  0  1  1 
1  1  0  1 
1  1  1  1 
 b. 
x  y  z  out 
0  0  0  1 
0  0  1  1 
0  1  0  1 
0  1  1  0 
1  0  0  1 
1  0  1  0 
1  1  0  1 
1  1  1  0 

a. 
The resulting expression is
z + x y.

b. 
The resulting expression is
z + x y.

Problem L3.5
The following truth table computes the 2's bit of the product of
two 2bit inputs. Draw a Karnaugh map and indicate a
minimized sumofproducts expression corresponding to the
Karnaugh map. (You do not need to draw the circuit.)
x_{1} 
x_{0} 
y_{1} 
y_{0} 
p_{1} 
0  0  0  0  0 
0  0  0  1  0 
0  0  1  0  0 
0  0  1  1  0 
0  1  0  0  0 
0  1  0  1  0 
0  1  1  0  1 
0  1  1  1  1 


x_{1} 
x_{0} 
y_{1} 
y_{0} 
p_{1} 
1  0  0  0  0 
1  0  0  1  1 
1  0  1  0  0 
1  0  1  1  1 
1  1  0  0  0 
1  1  0  1  1 
1  1  1  0  1 
1  1  1  1  0 

x_{1} y_{1} y_{0} + x_{1} x_{0} y_{0} + x_{1} x_{0} y_{1} + x_{0} y_{1} y_{0}
Problem L3.6
Design a circuit with three inputs, and which
outputs 1 precisely when at least two of the inputs are 1.
(You'll want to draw a Karnaugh map and to derive a circuit
from that.)
Truth table: 
a  b  c  out 
0  0  0  0 
0  0  1  0 
0  1  0  0 
0  1  1  1 
1  0  0  0 
1  0  1  1 
1  1  0  1 
1  1  1  1 

Karnaugh map: 

Boolean expression: 
Output is
a b + a c + b c

Circuit: 
