ELEN 500
Winter 1999
Midterm Exam
For the function f(w,x,y,z) = w'xyz + wyz' + wxy + w'y'z + w'xy'z + wx'y' + wx'z' + x'y'z
1. (10 points) Using Boole's Expansion Theorem, find the minterms of f(w,x,y,z). [ Hint: There are 8 minterms].
SOLUTION:
|
w |
x |
y |
z |
f(w,x,y,z) |
minterms |
|
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
1 |
1 |
w'x'y'z |
|
0 |
0 |
1 |
0 |
0 |
|
|
0 |
0 |
1 |
1 |
0 |
|
|
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
1 |
w'xy'z |
|
0 |
1 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
1 |
1 |
w'xyz |
|
1 |
0 |
0 |
0 |
1 |
wx'y'z' |
|
1 |
0 |
0 |
1 |
1 |
wx'y'z |
|
1 |
0 |
1 |
0 |
1 |
wx'yz' |
|
1 |
0 |
1 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
wxyz' |
|
1 |
1 |
1 |
1 |
1 |
wxyz |
SOLUTION:
|
m1 =w'x'y'z * m2 =wx'y'z' * |
w'y'z = p1 x'y'z = p2 wx'y' = p3 wx'z' = p4 |
|
m3= w'xy'z * m4 =wx'y'z * m5 =wx'yz' * |
w'xz = p5 wyz' = p6 |
|
m6 =w'xyz * m7 =wxyz' * |
xyz = p7 wxy = p8 |
|
m8 =wxyz * |
3. (10 points) Construct the constraint matrix of prime implicants which cover the minterms of f(w,x,y,z).
SOLUTION:
|
w'y'z |
x'y'z |
wx'y' |
wx'z' |
w'xz |
wyz' |
xyz |
wxy |
|
|
p1 |
p2 |
p3 |
p4 |
p5 |
p6 |
p7 |
p8 |
|
|
m1=w'x'y'z |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
m2=wx'y'z' |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
m3=w'xy'z |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
m4=wx'y'z |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
m5=wx'yz' |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
m6=w'xyz |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
m7=wxyz' |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
m8=wxyz |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
4. (10 points) Solve the constraint matrix using the branch and bound technique. [ Hint: The minimum number of prime implicants which cover the minterms is 4.]
SOLUTION:
There are no essential columns, no row dominance and no column dominance therefore the matrix is cyclic.
Choose P1 as part of the solution. We can then eleminate column p1 and rows m1 and m3 which P1 covers to get
|
x'y'z |
wx'y' |
wx'z' |
w'xz |
wyz' |
xyz |
wxy |
|
|
p2 |
p3 |
p4 |
p5 |
p6 |
p7 |
p8 |
|
|
m2=wx'y'z' |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
m4=wx'y'z |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
m5=wx'yz' |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
m6=w'xyz |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
m7=wxyz' |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
m8=wxyz |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
There are no essential columns and no row dominance. However p7 dominates p5 therefore we can eliminate p5 and p3 dominates p2 so we eliminate p2 to get
|
wx'y' |
wx'z' |
wyz' |
xyz |
wxy |
|
|
p3 |
p4 |
p6 |
p7 |
p8 |
|
|
m2=wx'y'z' |
1 |
1 |
0 |
0 |
0 |
|
m4=wx'y'z |
1 |
0 |
0 |
0 |
0 |
|
m5=wx'yz' |
0 |
1 |
1 |
0 |
0 |
|
m6=w'xyz |
0 |
0 |
0 |
1 |
0 |
|
m7=wxyz' |
0 |
0 |
1 |
0 |
1 |
|
m8=wxyz |
0 |
0 |
0 |
1 |
1 |
In this matrix both p3 and p7 are essential. So we eleminate columns p3 and p7 and all the rows that they cover to get
|
wx'z' |
wyz' |
wxy |
|
|
p4 |
p6 |
p8 |
|
|
m5=wx'yz' |
1 |
1 |
0 |
|
m7=wxyz' |
0 |
1 |
1 |
Column p6 dominates p4 and p8 which can be eliminated. So p6 is required in the solution to cover m5 and m7. The final solution is p1p3p6p7 which has a cost of 4.
5. (10 points). Compute and compare two figures of merit for the original function and for the synthesized solution.
Original Function f(w,x,y,z) = w'xyz + wyz' + wxy + w'y'z + w'xy'z + wx'y' + wx'z' + x'y'z has 8 terms and 26 literals. The reduced function f(w,x,y,z) = p1 + p3 + p6 + p7 = w'y'z + wx'y' + wyz' + xyz has 4 terms and 12 literals.
6. (5 points) Let B = { O , {a}, {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {a,b,c,d} } and let the meet and join be the set intersection and union of the elements of B.
(a) Is B a Boolean Algebra? No
(b) Why or why not? According to Stone's Representation Theorem, the cardinality of the carrier of a Boolean algebra must be a power of 2 . The cardinality of the above set B is 11 which is not a power of 2.
7. (16 points) What is the set of Don't Care Conditions for f(x,y) and g(x,y)?
SOLUTION:
|
A |
B |
C |
x |
y |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
1 |
(a) From this truth table, we see that the combination (x,y) = (0,0) never occurs to the input of the subcircuit f(x,y). Therefore Dfsat = {x'y'}. Because f is a primary output of the circuit nothing can block us from observing the value of f therefore Dfobs is the null set.
(b) Also, we see that the combination (x,y) = (0,0) never occurs to the input of the subcircuit g(x,y). Therefore Dgsat = {x'y'}. The value of g(x,y) cannot be observed at a primary output of the circuit whenever y is 0, therefore Dgobs = {y'}.
8. Draw the graph for the set of edges {(a,b), (c,d), (a,f), (e,f), (e,g), (c,e)}
SOLUTION:
(a) Graph (4 points)
(b) (2 points) How many vertices are in this graph? 6
(c) (2 points) List the source vertices. {A,C}
(d) (2 points) List the sink vertices. {B, D, F, G}
9. For a set A with n elements
(a) (5 points) What is the complexity of an algorithm to only enumerate all the elements of A?
SOLUTION: O(n)
(b) (10 points) What is the complexity of an algorithm to only enumerate all the elements of the power set of A?
SOLUTION: O(2n)
(b) ( 2 points) What is the cardinality of A?
The cardinality of A is the number of elements
in A, which is n.
(c) (2 points) What is the cardinality of 2A? The number of elements in 2A is 2n .