In section 4.10.1 we showed how the ∗-product operation can be used to find the prime impl...

In section 4.10.1 we showed how the ∗-product operation can be used to find the prime implicants of a given function f. Another possibility is to find the prime implicants by expanding the implicants in the initial cover of the function. An implicant is expanded by removing one literal to create a larger implicant (in terms of the number of vertices covered). A larger implicant is valid only if it does not include any vertices for which f = 0. The largest valid implicants obtained in the process of expansion are the prime implicants. Figure P4.1 illustrates the expansion of the implicant ₁x₂x₃ of the function in Figure 4.9, which is also used in Example 4.16. Note from Figure 4.9 that

Figure P4.1 Expansion of implicant ₁x₂x₃.

In Figure P4.1 the word NO is used to indicate that the expanded term is not valid, because it includes one or more vertices from . From the graph it is clear that the largest valid implicants that arise from this expansion are x₂x₃ and ₁; they are prime implicants of f.

Expand the other four implicants given in the initial cover in Example 4.14 to find all prime implicants of f. What is the relative complexity of this procedure compared to the ∗-product technique?

Example 4.14

The don’t-care minterms are included in the initial list in the same way as the minterms for which f = 1. Consider the function

We encourage the reader to derive a Karnaugh map for this function as an aid in visualizing the derivation that follows. Figure 4.38 depicts the generation of prime implicants, producing the result

The initial prime implicant cover table is shown in Figure 4.39a. The don’t-care minterms are not included in the table because they do not have to be covered. There are no essential prime implicants. Examining this table, we see that column 8 has check marks in the same rows as column 9. Moreover, column 9 has an additional check mark in row p₅. Hence column 9 dominates column 8. We refer to this as the concept of column dominance. When one column dominates another, we can remove the dominating column, which is column 9 in this case. Note that this is in contrast to rows where we remove dominated (rather than dominating) rows. The reason is that when we choose a prime implicant to cover the minterm that corresponds to the dominated column, this prime implicant will also cover the minterm corresponding to the dominating column. In our example, choosing either p₄ or p₆ covers both minterms 8 and 9. Similarly, column 13 dominates column 5, hence column 13 can be deleted.

After removing columns 9 and 13, we obtain the reduced table in Figure 4.39b. In this table row p₄ dominates p₆ and row p₇ dominates p₅. This means that p₅ and p₆ can be removed, giving the table in Figure 4.39c. Now, p₄ and p₇ are essential to cover minterms 8 and 5, respectively. Thus, the table in Figure 4.39d is obtained, from which it is obvious that p₂ covers the remaining minterms 2 and 6. Note that row p₂ dominates both rows p₁ and p₃.

The final cover is

and the function is implemented as

Figure 4.38 Generation of prime implicants for the function in Example 4.14.

Figure 4.39 Selection of a cover for the function in Example 4.14.

Example 4.16 Consider the function f (x₁, x₂, x₃) of Figure 4.9. Assume that f is initially specified as a set of vertices that correspond to the minterms, m₀, m₁, m₂, m₃, and m₇. Hence let the initial cover be C⁰ = {000, 001, 010, 011, 111}. Using the ∗-operation to generate a new set of cubes, we obtain G¹ = {00x, 0x0, 0x1, 01x, x11}. Then C¹ = C⁰ ∪ G¹ – redundant cubes. Observe that each cube in C⁰ is included in one of the cubes in G¹; therefore, all cubes in C⁰ are redundant. Thus C¹ = G¹.

The next step is to apply the ∗-operation to the cubes in C¹, which yields G² = {000, 001, 0xx, 0x1, 010, 01x, 011}. Note that all of these cubes are included in the cube 0xx; therefore, all but 0xx are redundant. Now it is easy to see that

since all cubes of C¹, except x11, are redundant because they are covered by 0xx.

Applying the ∗-operation to C² yields G³ = {011} and

Since C³ = C², the conclusion is that the prime implicants of f are the cubes {x11, 0xx}, which represent the product terms x₂x₃ and ₁. This is the same set of prime implicants that we derived using a Karnaugh map in Figure 4.9.

Observe that the derivation of prime implicants in this example is similar to the tabular method explained in section 4.9 because the starting point was a function, f, given as a set of minterms.

Figure 4.9 Three-variable function f (x₁, x₂, x₃) = Σm(0, 1, 2, 3, 7).