Question

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

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

Short answer

(a) A \(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 \(1\)'s (and no empty cells). The simplified sum-of-products expansion is then the sum of the smallest possible number of these blocks such that all \(1\)'s are contained in at least one block.

(b) The simplified sum-of-products expansion is \({\bf{x\bar y + yz + \bar y\bar z}}\).

Step-by-step solution

Definition

A sum-of-products expansion or disjunctive normal form of a Boolean function is the function written as a sum of minterms.

Using the sum-of-products expansion (a)

A \(K - \)map is a table that contains all possible terms in a sum-of-products expansion of a Boolean function. A \(K - \)map for a function in three variables is a table with four columns \(yz,y\bar z,\bar y\bar z\) and \(\bar yz\); which contains all possible combinations of \(y\) and \(z\) are two rows \(x,\bar x\). 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 \(1\)'s (and no empty cells). The simplified sum-of-products expansion is then the sum of the smallest possible number of these blocks such that all \(1\)'s are contained in at least one block.

Simplifying the sum-of-products expansion (b)

\(xyz + x\bar yz + x\bar y\bar z + \bar xyz + \bar x\bar y\bar z\)

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

Place a \(1\) in the cell corresponding to each term in the given sum \(xyz + x\bar yz + x\bar y\bar z + \bar xyz + \bar x\bar y\bar z\).

\(xyz\): place a \(1\) in the cell corresponding to row \(x\) and column \(yz\).

\(x\bar yz\): place a \(1\) in the cell corresponding to row \(x\) and column \(\bar yz\).

\(x\bar y\bar z\): place a \(1\) in the cell corresponding to row \(x\) and column \(\bar y\bar z\).

\(\bar xyz\): place a \(1\) in the cell corresponding to row \(\bar x\) and column \(yz\).

\(\bar x\bar y\bar z\): place a \(1\) in the cell corresponding to row \(\bar x\) and column \(\bar y\bar z\).

Simplifying the sum-of-products expansion

\(\bar xyz\)is only contained in the block \(yz\) (note that the column \(yz\) contains only \(1\)'s), when not considering the blocks of single cells.

\(\bar x\bar y\bar z\)is only contained in the block \(\bar y\bar z\) (note that the column \(\bar y\bar z\) contains only \(1\)'s), when not considering the blocks of single cells.

Here \(x\bar yz\) is the only cell not included in block. However, \(x\bar yz\) is contained in the blocks \(x\bar y\) and \(xz\), thus choose either one of the two blocks. Choose \(x\bar y\).

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

Therefore, the simplified sum-of-products expansion \( = x\bar y + yz + \bar y\bar z\).