ELEN 5000
Winter 1999
Homework Assignment 3
1. For the formula f = xy + y'z + xyz
(Note: this is the same function as problem 1, homework assignment 1)
(a) Find the prime implicants using the tabular method.
SOLUTION:
|
x |
y |
z |
f(x,y,z) |
minterms |
|
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
1 |
x'y'z |
|
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
1 |
xy'z |
|
1 |
1 |
0 |
1 |
xyz' |
|
1 |
1 |
1 |
1 |
xyz |
|
x'y'z * |
y'z |
|
xy'z * xyz' * |
xz xy |
|
xyz * |
|
Prime implicants are xz, xy, y'z
(b) Find the prime implicants using the iterated consensus method.
SOLUTION:
f = xy + y'z + xyz
= xy + y'z + xyz + xz (adding the consensus term for the first two terms of f)
= xy + y'z + xz (xz includes xyz so xyz can be deleted)
2. For the incompletely specified function f(x,y,z) represented by the interval [x'y, xz'+y] find the
prime implicants using the tabular method.
(Note: this is the same interval as Problem 2, homework assignment 2).
SOLUTION:
f = x'y
d= xz' + xy
|
x |
y |
z |
f |
minterms (f) |
d |
minterms (d) |
|
0 |
0 |
0 |
0 |
0 |
||
|
0 |
0 |
1 |
0 |
0 |
||
|
0 |
1 |
0 |
1 |
x'yz' |
0 |
|
|
0 |
1 |
1 |
1 |
x'yz |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
xy'z' |
|
|
1 |
0 |
1 |
0 |
0 |
||
|
1 |
1 |
0 |
0 |
1 |
xyz' |
|
|
1 |
1 |
1 |
0 |
1 |
xyz |
|
x'yz' * xy'z' d * |
x'y * yz' * xz' d |
y |
|
x'yz * xyz' d * |
yz * xy d * |
|
|
xyz * |
The term xz' is entirely contained in d hence it is not a prime implicant. The prime implicant of f is y.
3. Consider a function with n minterms.
(a) What is the minimum number of prime implicants it can have? ONE (or zero for n=0)
(b) What is the maximum number of prime implicants it can have? n