Use the Quine–McCluskey method to simplify the sum-of-products expansions in Exercise \(14\).

It is seen that K-maps can be used to produce minimal expansions of Boolean functions as Boolean sums of Boolean products. 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. 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.

\({\bf{wxyz + wx\bar yz + wx\bar y\bar z + w\bar xy\bar z + w\bar x\bar yz}}\)

For every given term, replace a variable \({\bf{x}}\) by \(1\) and replace the complement of a variable \({\bf{\bar x}}\) by \(0\) to obtain the string.

\(\begin{array}{*{20}{r}}{{\bf{ INITIAL }}}&{{\bf{ Term }}}&{{\bf{ String }}}\\{\bf{1}}&{{\bf{wxyz}}}&{{\bf{1111}}}\\{\bf{2}}&{{\bf{wx\bar yz}}}&{{\bf{1101}}}\\{\bf{3}}&{{\bf{wx\bar y\bar z}}}&{{\bf{1100}}}\\{\bf{4}}&{{\bf{w\bar xy\bar z}}}&{{\bf{1010}}}\\{\bf{5}}&{{\bf{w\bar x\bar y}}}&{{\bf{1001}}}\end{array}\)

Step \(1\)Minterms that can differ exactly \(1\) position in the bit string are represented by a new string with a dash in that position (and thus are combined into the same group).

\(\begin{array}{*{20}{r}}{{\bf{ STEP 1 }}}&{{\bf{ Term }}}&{{\bf{ String }}}\\{{\bf{(1,2)}}}&{{\bf{wxz}}}&{{\bf{11 - 1}}}\\{{\bf{(2,3)}}}&{{\bf{wx\bar y}}}&{{\bf{110 - }}}\\{{\bf{(2,5)}}}&{{\bf{w\bar yz}}}&{{\bf{1 - 01}}}\end{array}\)

The strings in the last step do not differ by \(1\) bit (pairwise), thus the algorithm will discontinue.

The simplified sum-of-products expansion then is the sum of the least number of terms in the last step such that initial terms \(1\) to \(5\) are included.

All terms in step \(1\) need to be included (as the first term is the only term containing \(1\), the second term is the only term containing \(3\) and the third term is the only term containing \(5\)).

Only term \(4\) is then still missing, thus we add term \(4\) itself (as it didn't occur in any steps after the initial step).

Simplified sum-of-products expansion \({\bf{wxz + wx\bar y + w\bar yz + w\bar xy\bar z}}\)

\({\bf{wxy\bar z + wx\bar yz + w\bar xyz + \bar wx\bar yz + \bar w\bar xy\bar z + \bar w\bar x\bar yz}}\)

For every given term, replace a variable \({\bf{x}}\) by \(1\) and replace the complement of a variable \({\bf{\bar x}}\) by \({\bf{0}}\) to obtain the string.

\(\begin{array}{*{20}{c}}{{\bf{INITIAL}}}&{{\bf{Term}}}&{{\bf{String}}}\\{\bf{1}}&{{\bf{wxy\bar z}}}&{{\bf{1110}}}\\{\bf{2}}&{{\bf{wx\bar yz}}}&{{\bf{1101}}}\\{\bf{3}}&{{\bf{w\bar xyz}}}&{{\bf{1011}}}\\{\bf{4}}&{{\bf{\bar wx\bar yz}}}&{{\bf{0101}}}\\{\bf{5}}&{{\bf{\bar w\bar xy\bar z}}}&{{\bf{0010}}}\\{\bf{6}}&{{\bf{\bar w\bar x\bar yz}}}&{{\bf{0001}}}\end{array}\)

Step \(1\)Minterms that can differ exactly \(1\) position in the bit string are represented by a new string with a dash in that position (and thus are combined into the same group).

\(\begin{array}{*{20}{c}}{\;{\bf{STEP1}}}&{{\bf{Term}}}&{{\bf{String}}}\\{{\bf{(2,4)}}}&{{\bf{w\bar yz}}}&{{\bf{ - 101}}}\\{{\bf{(4,6)}}}&{{\bf{\bar w\bar yz}}}&{{\bf{0 - 01}}}\end{array}\)

The strings in the last step do not differ by \(1\) bit (pairwise), thus the algorithm will discontinue.

The simplified sum-of-products expansion then is the sum of the least number of terms in the last step such that initial terms \(1\) to \(6\) are included.

All terms in step \(1\) need to be included (as the first term is the only term containing \(2\) and the second term is the only term containing \(6\)).

Only terms \(1\),\(3\) and \(5\) are then still missing, thus we add the terms \(1\),\(3\) and \(5\) itself (as they didn't occur in any steps after the initial step).

Simplified sum-of-products expansion \({\bf{w\bar yz + \bar w\bar yz + wxy\bar z + w\bar xyz + \bar w\bar xy\bar z}}\)

\({\bf{wxyz + wxy\bar z + wx\bar yz + w\bar x\bar yz + w\bar x\bar y\bar z + \bar wx\bar yz + \bar w\bar xy\bar z + \bar w\bar x\bar yz}}\)

For every given term, replace a variable \({\bf{x}}\) by \(1\) and replace the complement of a variable \({\bf{\bar x}}\) by \(0\) to obtain the string.

\(\begin{array}{*{20}{c}}{{\bf{INITIAL}}}&{{\bf{Term}}}&{{\bf{String}}}\\{\bf{1}}&{{\bf{wxyz}}}&{{\bf{1111}}}\\{\bf{2}}&{{\bf{wxy\bar z}}}&{{\bf{1110}}}\\{\bf{3}}&{{\bf{wx\bar yz}}}&{{\bf{1101}}}\\{\bf{4}}&{{\bf{w\bar x\bar yz}}}&{{\bf{1001}}}\\{\bf{5}}&{{\bf{\bar wx\bar yz}}}&{{\bf{0101}}}\\{\bf{6}}&{{\bf{w\bar x\bar y\bar z}}}&{{\bf{1000}}}\\{\bf{7}}&{{\bf{\bar w\bar xy\bar z}}}&{{\bf{0010}}}\\{\bf{8}}&{{\bf{\bar w\bar x\bar yz}}}&{{\bf{0001}}}\end{array}\)

Step \(1\)Minterms that can differ exactly \(1\) position in the bit string are represented by a new string with a dash in that position (and thus are combined into the same group).

\(\begin{array}{*{20}{r}}{{\bf{ STEP 1 }}}&{{\bf{ Term }}}&{{\bf{ String }}}\\{{\bf{(1,2)}}}&{{\bf{wxy}}}&{{\bf{111 - }}}\\{{\bf{(1,3)}}}&{{\bf{wxz}}}&{{\bf{11 - 1}}}\\{{\bf{(3,4)}}}&{{\bf{w\bar yz}}}&{{\bf{1 - 01}}}\\{{\bf{(3,5)}}}&{{\bf{x\bar yz}}}&{{\bf{ - 101}}}\\{{\bf{(4,6)}}}&{{\bf{w\bar x\bar y}}}&{{\bf{100 - }}}\\{{\bf{(4,8)}}}&{{\bf{\bar x\bar yz}}}&{{\bf{ - 001}}}\\{{\bf{(5,8)}}}&{{\bf{\bar w\bar yz}}}&{{\bf{0 - 01}}}\end{array}\)

Step \(2\)Minterms that can differ exactly \(1\) position in the bit string are represented by a new string with a dash in that position (and thus are combined into the same group).

\(\begin{array}{*{20}{c}}{{\bf{ STEP 2 }}}&{{\bf{ Term }}}&{{\bf{ String }}}\\{{\bf{(3,4,5,8)}}}&{{\bf{\bar yz}}}&{{\bf{ - - 01}}}\end{array}\)

Only one string remains in the last step, thus the algorithm will discontinue.

The simplified sum-of-products expansion then is the sum of the least number of terms in the last step such that initial terms \(1\) to \(8\) are included.

The last step only included one term; thus, this term will definitely be included.

Terms \(1\), \(2\), \(6\) and \(7\) are still missing.

Terms \(1\),\(2\) and \(6\) can be added from step \(1\), by adding \((1,2)\) and \((4,6)\)

Term \(7\) was not present after the initial step, thus we need to add term \(7\) itself.

Simplified sum-of-products expansion \({\bf{\bar yz + wxy + w\bar x\bar y + \bar w\bar xy\bar z}}\)

\({\bf{wxyz + wxy\bar z + wx\bar yz + w\bar xyz + w\bar xy\bar z + \bar wxyz + \bar w\bar xyz + \bar w\bar xy\bar z + \bar w\bar x\bar yz}}\)

For every given term, replace a variable \({\bf{x}}\) by \(1\) and replace the complement of a variable \({\bf{\bar x}}\) by \({\bf{0}}\) to obtain the string.

\(\begin{array}{*{20}{c}}{{\bf{ INITIAL }}}&{{\bf{ Term }}}&{{\bf{ String }}}\\{\bf{1}}&{{\bf{wxyz}}}&{{\bf{1111}}}\\{\bf{2}}&{{\bf{wxy\bar z}}}&{{\bf{1110}}}\\{\bf{3}}&{{\bf{wx\bar yz}}}&{{\bf{1101}}}\\{\bf{4}}&{{\bf{w\bar xyz}}}&{{\bf{1011}}}\\{\bf{5}}&{{\bf{\bar wxyz}}}&{{\bf{0111}}}\\{\bf{6}}&{{\bf{w\bar xy\bar z}}}&{{\bf{1010}}}\\{\bf{7}}&{{\bf{\bar w\bar xyz}}}&{{\bf{0011}}}\\{\bf{8}}&{{\bf{\bar w\bar xy\bar z}}}&{{\bf{0010}}}\\{\bf{9}}&{{\bf{\bar w\bar x\bar yz}}}&{{\bf{0001}}}\end{array}\)

Step \(1\)Minterms that can differ exactly \(1\) position in the bit string are represented by a new string with a dash in that position (and thus are combined into the same group).

\(\begin{array}{*{20}{c}}{{\bf{STEP 1}}}&{{\bf{Term}}}&{{\bf{String}}}\\{{\bf{(1,3)}}}&{{\bf{wxz}}}&{{\bf{11 - 1}}}\\{{\bf{(1,2)}}}&{{\bf{wxy}}}&{{\bf{111 - }}}\\{{\bf{(1,4)}}}&{{\bf{wyz}}}&{{\bf{1 - 11}}}\\{{\bf{(1,5)}}}&{{\bf{xyz}}}&{{\bf{ - 111}}}\\{{\bf{(2,6)}}}&{{\bf{wy\bar z}}}&{{\bf{1 - 10}}}\\{{\bf{(4,6)}}}&{{\bf{w\bar xy}}}&{{\bf{101 - }}}\\{{\bf{(4,7)}}}&{{\bf{\bar xyz}}}&{{\bf{ - 011}}}\\{{\bf{(5,7)}}}&{{\bf{\bar wyz}}}&{{\bf{0 - 11}}}\\{{\bf{(6,8)}}}&{{\bf{\bar xy\bar z}}}&{{\bf{ - 010}}}\\{{\bf{(7,8)}}}&{{\bf{\bar w\bar xy}}}&{{\bf{001 - }}}\\{{\bf{(7,9)}}}&{{\bf{\bar w\bar xz}}}&{{\bf{00 - 1}}}\end{array}\)

\(\begin{array}{*{20}{c}}{{\bf{STEP 2}}}&{{\bf{Term}}}&{{\bf{String}}}\\{{\bf{(1,2,4,6)}}}&{{\bf{wy}}}&{{\bf{1 - 1 - }}}\\{{\bf{(1,4,5,7)}}}&{{\bf{yz}}}&{{\bf{ - - 11}}}\\{{\bf{(4,6,7,8)}}}&{{\bf{\bar xy}}}&{{\bf{ - 01 - }}}\end{array}\)

The strings in the last step do not differ by \(1\) bit (pairwise), thus the algorithm will discontinue.

The simplified sum-of-products expansion then is the sum of the least number of terms in the last step such that initial terms \(1\) to \(9\) are included.

All terms in step \(2\) need to be included (as the first term is the only term containing \(2\), the second term is the only term containing \(5\) and the third term is the only term containing \(8\)).

Only terms \(3\) and \(9\) are then still missing, thus we add the terms containing \(3\) and \(9\) from step \(1\), which are \({\bf{\bar w\bar xz(7,9)}}\) and \({\bf{wxz(1,3)}}\).

Simplified sum-of-products expansion\({\bf{wy + yz + \bar xy + \bar w\bar xz + wxz}}\).