In Section 8.4.2 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 P8.1 illustrates the expansion of the minterm x1x2x3 of the function used in Example 8.14. 

In Figure P8.1 the word NO is used to indicate that the expanded term is not valid, because it includes one or more vertices from f . From the graph it is clear that the largest valid implicants that arise from this expansion are x2x3 and x1; they are prime implicants of f.
Expand the other four minterms given in the initial cover in Example 8.14 to find all prime implicants of f. What is the relative complexity of this procedure compared to the ∗-product technique?

Transcribed Image Text:

f = x₁x₂x3 + x₁x2x3 + X1X2X3