The Quine–mccluskey Method
The Quine–MCCluskey Method: We have seen that K-maps can be used to produce minimal expansions of Boolean functions as Boolean sums of Boolean products. However, K-maps are awkward to use when there are more than four variables. Furthermore, the use of K-maps relies on visual inspection to identify terms to group. For these reasons there is a need for a procedure for simplifying sum-of-products expansions that can be mechanized. The Quine–McCluskey method is such a procedure. It can be used for Boolean functions in any number of variables. It was developed in the 1950s by W. V. Quine and E. J. McCluskey, Jr. Basically, the Quine–McCluskey method consists of two
parts. The first part finds those terms that are candidates for inclusion in a minimal expansion as a Boolean sum of Boolean products. The second part determines which of these terms to actually use. We will use Example 1 to illustrate how, by successively combining implicants into implicants with one fewer literal, this procedure works.
EXAMPLE 1 We will show how the Quine–McCluskey method can be used to find a minimal expansion equivalent to
We will represent the minterms in this expansion by bit strings. The first bit will be 1 if x occurs and 0 if x occurs. The second bit will be 1 if y occurs and 0 if y occurs. The third bit will be 1 if z occurs and 0 if z occurs.We then group these terms according to the number of 1s in the corresponding bit strings. This information is shown in Table 2.
Minterms that can be combined are those that differ in exactly one literal. Hence, two terms that can be combined differ by exactly one in the number of 1s in the bit strings that represent them. When two minterms are combined into a product, this product contains two literals. A product in two literals is represented using a dash to denote the variable that does not occur. For instance, the minterms xyz and x yz, represented by bit strings 101 and 001, can be combined into yz, represented by the string –01. All pairs of minterms that can be combined and the product formed from these combinations are shown in Table 3.
Next, all pairs of products of two literals that can be combined are combined into one literal. Two such products can be combined if they contain literals for the same two variables, and literals for only one of the two variables differ. In terms of the strings representing the products, these strings must have a dash in the same position and must differ in exactly one of the other two slots. We can combine the products yz and yz, represented by the strings –11 and –01, into z, represented by the string – –1.We show all the combinations of terms that can be formed in this way in Table 3.
In Table 3 we also indicate which terms have been used to form products with fewer literals; these terms will not be needed in a minimal expansion. The next step is to identify a minimal set of products needed to represent the Boolean function.We begin with all those products that were not used to construct products with fewer literals. Next, we form Table 4, which has a row for each candidate product formed by combining original terms, and a column for each original term; and we put an X in a position if the original term in the sum-of-products expansion was used to form this candidate product. In this case, we say that the candidate product covers the original minterm. We need to include at least one product that covers each of the original minterms. Consequently, whenever there is only one X in a column in the table, the product corresponding to the row this X is in must be used. From Table 4 we see that both z and x y are needed. Hence, the final answer is z x y.