• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q25E

Expert-verified
Found in: Page 842

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Use the Quine–McCluskey method to simplify the sum-of-products expansions in Exercise $$14$$.

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

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

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

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

See the step by step solution

## Step 1:Definition

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.

## Step 2: Quine-McCluskey method

$${\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}}$$

## Step 3: Using Quine-McCluskey method

$${\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}}$$

## Step 4: Using Quine-McCluskey method

$${\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}}$$

## Step 5:Using Quine-McCluskey method

$${\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}}$$.