ic
Section 8.3 Minimization
671
1
1
1
1
1
1
1
1
1
1
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
figure 8.33
example 27
Figure 8.34a shows the unique two-square and four-square blocks. The remaining
two unused marked squares can be assigned to two-square blocks in two different
ways, as shown in parts (b) and (c). Assigning them together to a single two-square
block is more efficient because it produces a sum-of-products form with three
terms rather than four. The minimal sum-of-products expression is
x 1 x 3 + x 1 ′x 2 x 3 ′ + x 2 ′x 3 ′x 4 ′
1
1
1
1
1
(a)
(b)
1
1
1
1
1
1
1
1
1
1
1
(c)
1
1
1
1
1
1
1
1
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
figure 8.34
example 28
Consider the map of Figure 8.35a. Here the two unique four-square blocks determined by the squares with * have been chosen. In Figure 8.35b, the remaining unmarked squares, for which there was a choice of blocks, are combined into blocks
as efficiently as possible. The resulting sum-of-products form is
x 1 x 3 + x 1 ′x 3 ′ + x 3 x 4 + x 1 ′x 2 + x 1 x 2 ′x 4 ′