ELEN 500
Spring 1999
Midterm Exam
1. (11 points) For the function
f(w,x,y,z) = w'xyz + wyz' + wxy + w'y'z + w'xy'z + wx'y' + wx'z'
find the Prime Implicants using the tabular method.
solution:
|
w'x'y'z check wx'y'z' check |
w'y'z x'y'z wx'z' wx'y' |
|
w'xy'z check wx'yz' check wx'y'z check |
w'xz wyz' |
|
w'xyz check wxyz' check |
xyz wxy |
|
wxyz check |
2. (10 points) for the following constraint matrix, find the minimum covering, assuming an
equal cost for each Prime Implicant.
|
p1 |
p2 |
p3 |
p4 |
p5 |
p6 |
|
|
m1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
m2 |
0 |
1 |
0 |
1 |
1 |
1 |
|
m3 |
1 |
1 |
1 |
0 |
0 |
0 |
|
m4 |
0 |
0 |
1 |
1 |
0 |
0 |
|
m5 |
0 |
0 |
0 |
0 |
1 |
0 |
|
m6 |
0 |
0 |
0 |
0 |
0 |
1 |
solution:
P5 is essential, so it is included.
P6 is essential, so it is included.
P1 is essential, so it is included.
That covers rows: m1, m2, m3, m5 and m6.
Either P3 or P4 can cover m4, so there are two possible solutions:
P1P3P5P6
OR
P1P4P5P6
3. For the graph
3a (4 points) List the edges. (C,D), (C,E), (E,G), (E,F), (A,F), (A,B), (F,B), (B,E)
3b (2 points) Is this graph a DAG? NO (it has a cycle B-E-F-B)
3c (2 points) List the source vertices. A, C
3d (2 points) List the sink vertices. D, G
4. Consider a set A with n elements, and a set B with m elements.
4a.(2 points) What is the complexity of an algorithm to only enumerate (that is list) all of the elements of A.
O(n)
4b.(2 points) What is the complexity of an algorithm to only enumerate all of the elements of B.
O(m)
4c. (3 points) What is the complexity of an algorithm to only enumerate all of the elements of AxA.
O(n2)
4d. (3 points) What is the complexity of an algorithm to only enumerate all of the elements of BxA.
O(m*n)
5. Given A = {a, b, c, d, e, f} and the Relation R is a subset of A2 defined as
R = {(a,a), (b,b), (c,c), (d,d), (e,e), (f,f), (a,b), (b,a), (a,c), (c,a),(b,c), (c,b), (d,e), (e,d)}.
5a (5 points) Show that R is an equivalence relation.
solution:
|
a |
b |
c |
d |
e |
f |
|
|
a |
R |
R |
R |
|||
|
b |
R |
R |
R |
|||
|
c |
R |
R |
R |
|||
|
d |
R |
R |
||||
|
e |
R |
R |
||||
|
f |
R |
It is Reflexive (xRx) because all diagonal element are present, ie (a,a), (b,b), (c,c), (d,d), (e,e), (f,f).
It is symetric (if xRy then yRx) because (a,b) and (b,a), (a,c) and (c,a), (b,c) and (c,a), (d,e), and (e,d)
It is transitive (iv xRy and yRz, then xRz) for (a,b) and (b,c) with (a,c).
Therfore it is an equivalence relation.
5b. (3 points) What are (that is list) the equivalence classes induced by the relation R?
The three equivalence classes are:
{a, b,c}
{d,e}
and
{f}
6. (10 points) What is the set of Don't Care Conditions (both Sat and Obs) for F(x,y) and G(x,y) in terms of x and y?
|
ABC |
x |
y |
other input to NAND on G |
|
000 |
0 |
1 |
0 |
|
001 |
0 |
0 |
0 |
|
010 |
0 |
1 |
0 |
|
011 |
0 |
1 |
0 |
|
100 |
0 |
1 |
1 |
|
101 |
0 |
0 |
0 |
|
110 |
1 |
1 |
1 |
|
111 |
1 |
1 |
0 |
Since xy = 10 never occurs the Dsat (input don't cares) for both F and G is xy'.
Since F is a primary output, the Osat (outpout don't cares) for F is null or the empty set.
Since G is blocked for all xy = 00 the Osat (output don't cares) for G is x'y', or if you
noticed that all y = 0 the Osat is y'.
7. (9 points) The following three functions are equal. What is the technology independent cost of each?
f(w,x,y,z) = w'y' + xy'z + wxz + wxy + wyz cost = 5 terms and 14 literals
f(w,x,y,z) = w'x'y'z' + w'x'y'z + w'xy'z' + w'xy'z + wx'yz' + wxy'z + wxyz' + wxyz cost = 8 terms and 32 literals
f(w,x,y,z) = w'y' + wxz + wyz cost = 3 terms and 8 literals
8) For a function with a constraint equation of
(P1 + P2 + P3)(P1 + P4)(P2 + P3)(P3 + P6)P5(P4 + P6)
8a (6 points) If all of the Prime Implicants have an equal cost of 1, what is the minimum solution?
(that is which Prime Implicants make up the solution)
P3 P4 P5
8b. (2 points) what is the cost of the solution for 8a? 3
8c (4 points), if the cost of P1 = P2 = P4 = P6 = 1, and the cost of P5 = P3 =3, then what is a minimum solution?
P1 P2 P5 P6
or
P2 P4 P5 P6
8d.(2 points) what is the cost of the solution for 8c? 6
9. (10 points) For the set A = {0, a, b, 1} list the power set.
{null, {0}, {a}, {b}, {1}, {0,a}, {0,b}, {0,1}, {a,b}, {a,1}, {b,1}
{0,a,b}, {0,a,1}, {0,b,1}, {a,b,1}, {0,a,b,1}}
10 (8 points) List all possible Boolean functions of 2 variables over the base set B = {0, 1}?
(hint, see cover of book)
0,
xy, x'y', x'y, xy',
x, x', y, y', x'y'+xy, x'y + xy',
x + y, x' + y, x + y', x' + y'
1