Question

\({\bf{a)}}\)Explain how \({\bf{K}}\)-maps can be used to simplify sum-of products expansions in four Boolean variables.

\({\bf{b)}}\)Use a \({\bf{K}}\)-map to simplify the sum-of-products expansion \({\bf{wxyz + wxy\bar z + wx\bar yz + wx\bar y\bar z + w\bar xyz + w\bar x\bar yz + \bar wxyz + \bar w\bar xyz + \bar w\bar xy\bar z}}\)

Short answer

\(\left( {\bf{a}} \right)\)A \({\bf{K}}\) -map is a table that contains all possible terms in a sum-of-products expansion of a Boolean function. A \(1\) is placed in each cell that belongs to a term in the sum-of-products expansion. You determine the largest possible blocks that contain all \({\bf{l's}}\) (and no empty cells). The simplified sum-of-products expansion is the sum of the smallest possible number contained in at least one block.

\({\bf{(b)}}\) The simplified sum-of-products expansion is \({\bf{wx + wz + yz + \bar w\bar xy}}\)

Step-by-step solution

Definition

A sum-of-products expansion form of a Boolean function is a sum of minterms.

Using the sum-of-products expansion

(a)

A \({\bf{K}}\)-map is a table that contains all possible terms in a sum-of-products expansion of a Boolean function. A \({\bf{K}}\)-map for a function in four variables is a table with four columns \({\bf{yz,y\bar z,\bar y\bar z}}\) and \({\bf{\bar yz}}\); which contains all possible combinations of \({\bf{y}}\) and \({\bf{z}}\) and four rows \({\bf{wx,w\bar x,\bar w\bar x}}\) and \({\bf{\bar wx}}\); which contains all possible combinations of \({\bf{y}}\) and \({\bf{z}}\). A \(1\) is placed in each cell that belongs to a term in the sum-of-products expansion. You determine the largest possible blocks that contain all \({\bf{l's}}\) (and no empty cells). The simplified sum-of-products expansion is the sum of the smallest possible number of all \({\bf{l's}}\) are contained in one block.

Simplify the sum-of-products expansion

(b)

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

A \({\bf{K}}\)-map for a function in four variables is a table with four columns \({\bf{yz, y\bar z,\bar y\bar z}}\) and \({\bf{\bar yz}}\); which contains all possible combinations of \({\bf{y}}\) and \({\bf{z}}\) and four rows \({\bf{wx,w\bar x,\bar w\bar x}}\) and \({\bf{\bar wx}}\); which contains all possible combinations of \({\bf{y}}\) and \({\bf{z}}\).

You place a \(1\) in the cell corresponding to each term in the given sum \(\begin{array}{l}{\bf{wxyz + wxy\bar z + wx\bar yz + wx\bar y\bar z + w\bar xyz + w\bar x\bar yz + \bar wxyz + \bar w\bar xyz + \bar w\bar xy\bar z}}\\{\bf{\backslash ( = wx + wz + yz + \bar w\bar xy\backslash )}}\end{array}\).

\({\bf{wxyz}}\) : place a \(1\) in the cell corresponding to row \({\bf{wx}}\) and column \({\bf{yz}}\)

\({\bf{wxy\bar z}}\) : place a \(1\) in the cell corresponding to row \({\bf{wx}}\) and column \({\bf{y\bar z}}\)

\({\bf{wx\bar yz}}\) : place a \(1\) in the cell corresponding to row \({\bf{wx}}\) and column \({\bf{\bar yz}}\)

\({\bf{wx\bar y\bar z}}\) : place a \(1\) in the cell corresponding to row \({\bf{wx}}\) and column \({\bf{\bar y\bar z}}\)

\({\bf{w\bar xyz}}\) : place a \(1\) in the cell corresponding to row \({\bf{w\bar x}}\) and column \({\bf{yz}}\)

\({\bf{w\bar x\bar yz}}\) : place a \(1\) in the cell corresponding to row \({\bf{w\bar x}}\) and column \({\bf{\bar yz}}\)

\({\bf{\bar wxyz}}\) : place a \(1\) in the cell corresponding to row \({\bf{\bar wx}}\) and column \({\bf{yz}}\)

\({\bf{\bar w\bar xyz}}\) : place a \(1\) in the cell corresponding to row \({\bf{\bar w\bar x}}\) and col\({\bf{wx}}\)umn \({\bf{yz}}\)

\({\bf{\bar w\bar xy\bar z}}\) : place a \(1\) in the cell corresponding to row \({\bf{\bar w\bar x}}\) and column \({\bf{y\bar z}}\)

Simplify the sum-of-products expansion

The largest block containing \({\bf{\bar wxyz}}\) is the block \({\bf{yz}}\), since the entire column \({\bf{yz}}\) contains \({\bf{l's}}\).

The largest block containing \({\bf{wxy\bar z}}\) is the block , since the entire row \({\bf{wx}}\) contains \({\bf{l's}}\).

The largest block containing \({\bf{w\bar x\bar yz}}\) is the block \({\bf{wz}}\), since all cells corresponding to both \({\bf{w}}\) and \({\bf{z}}\) contain \({\bf{l's}}\).

The cell not included in the three blocks is \({\bf{\bar w\bar xy\bar z}}\). The largest block containing \({\bf{\bar w\bar xy\bar z}}\) is \({\bf{\bar w\bar xy}}\), since all cells corresponding to both \({\bf{\bar w\bar x}}\) and \({\bf{y}}\) contain \({\bf{l's}}\).

The simplified sum-of-products expansion is the sum of the previous blocks.

Therefore, the simplified sum-of-products expansion \({\bf{wx + wz + yz + \bar w\bar xy}}\).