1. For the formula f= xy + x’y’z + xy’z’
(a) Find the prime implicants of f using the tabular method.
x y z f minterms 0 0 0 0 0 0 1 1 x'y'z 0 1 0 0 0 1 1 0 1 0 0 1 xy'z' 1 0 1 0 1 1 0 1 xyz' 1 1 1 1 xyz x'y'z xz' p1 = x'y'z, p2=xz', p3= xy xy’z’ * _____ xyz’ * xy _____ xyz *(b) Build a constraint matrix and find a subset of prime implicants that covers all the minterms of f.
p1 p2 p3
x’y’z 1 0 0
xy’z 0 1 0
xyz’ 0 1 1
xyz 0 0 1
Cover is p1p2p3
Solve the following covering problem
p1 p2 p3 p4 p5
m1 1 1 1 0 0
m2 1 1 0 1 0
m3 1 1 0 0 1
m4 1 0 1 1 0
m5 1 0 1 0 1
m6 1 0 0 1 1
m7 0 1 1 1 0
m8 0 1 1 0 1
m9 0 1 0 1 1
m10 0 0 1 1 1
by applying the branch and bound method. All columns have unit costs.
When splitting, choose the longest column and, in case of ties,
choose the column of lowest index. Also, when two columns dominate
each other, retain the one with the lower index.
Draw the search tree, and indicate for each node the lower bound,
computed with the maximal independent set method.
Solution: The matrix is cyclic since there are no
essential columns, row dominance or column dominance.
It has no independent rows, so from Theorem 4.8.1, the Lower bound
for the number of columns that cover the cyclic matrix is 2.
The upper bound is 6 since there could never be 6 p-vectors
in the solution set.
Each column has length 6, so we choose the column of lowest
index, p1, as the splitting variable.
First assume p1=1, ie, assume p1 is part of the solution.
Eliminate column p1 and the first 6 rows
of the matrix since p1 covers these minterms. This leaves
the following matrix:
p2 p3 p4 p5
m7 1 1 1 0
m8 1 1 0 1
m9 1 0 1 1
m10 0 1 1 1
This matrix is cyclic so split on p2. Eliminating column p2
and rows 7,8, & 9 leaves
p3 p4 p5
m10 1 1 1
This yields the covering solution of p1p2(p3+p4+p5) all of
which have a cost of 3 prime implicants.
The lower bound is 2, so there may be a cheaper solution if
we do not include p2 in the solution.
Set p2=0 and eliminate column p2 in the second
matrix above to yield
p3 p4 p5
m7 1 1 0
m8 1 0 1
m9 0 1 1
m10 1 1 1
Row 10 dominates rows 7, 8, & 9 so we eliminate row 10 to yield
p3 p4 p5
m7 1 1 0
m8 1 0 1
m9 0 1 1
This matrix is cyclic so split on p3 to obtain
p4 p5
m9 1 1
Hence the solution on this branch is p1p3(p4+p5). All of
these solutions have cost = 3 and the lower bound is 2.
So backtrack one step to assume
p3=0,yielding
p4 p5
m7 1 0
m8 0 1
m9 1 1
m9 dominates therfore eliminate it to yield
two essential columns p4 and p5.
The solution is p1p4p5 whose cost is 3, so perhaps we will
find a solution of length 2 (the lower bound) on the right
side of the search tree.
Go back to the top of the tree and assume p1=0.
Eliminating column p1 yields
p2 p3 p4 p5
m1 1 1 0 0
m2 1 0 1 0
m3 1 0 0 1
m4 0 1 1 0
m5 0 1 0 1
m6 0 0 1 1
m7 1 1 1 0
m8 1 1 0 1
m9 1 0 1 1
m10 0 1 1 1
Row 10 dominates rows 4 and 5 therefore eliminate row 10.
p2 p3 p4 p5
m1 1 1 0 0
m2 1 0 1 0
m3 1 0 0 1
m4 0 1 1 0
m5 0 1 0 1
m6 0 0 1 1
m7 1 1 1 0
m8 1 1 0 1
m9 1 0 1 1
This matrix is cyclic. So split on p2 and assume p2=1. We can
eliminate rows m1,m2,m3,m7,m8,m9 and row p2 to yield
p3 p4 p5
m4 1 1 0
m5 1 0 1
m6 0 1 1
This matrix is cyclic so split on p3 and assume p3=1 to get
p4 p5
m6 1 1
yielding the solutions p2p3(p4+p5) which have cost = 3.
So backtrack one step and assume p3=0 to yield
p4 p5
m4 1 0
m5 0 1
m6 1 1
m6 dominates so eliminate it to produce two
essential columns p4 and p5
so the solution is p2p4p5 which has cost = 3.
Hence we must once again backtrack and assume p2=0
yielding the matrix
p3 p4 p5
m1 1 0 0
m2 0 1 0
m3 0 0 1
m4 1 1 0
m5 1 0 1
m6 0 1 1
m7 1 1 0
m8 1 0 1
m9 0 1 1
P3, P4, & P5 are essential in this matrix to cover m1,
m2, and m3, respectively. So the solution is
p3p4p5 which has cost=3.
We have traversed the entire tree and all solutions have
cost = 3. Any 3 of the 5 prime implicants will cover
this set of 10 minterms.
