Question

Use a \({\bf{K}}\)-map to find a minimal expansion as a Boolean sum of Boolean products of each of these functions in the variables \({\bf{x,y}}\), and \({\bf{z}}\).

\(\begin{array}{l}{\bf{a) \bar xyz + \bar x\bar yz}}\\{\bf{b) xyz + xy\bar z + \bar xyz + \bar xy\bar z}}\\{\bf{c) xy\bar z + x\bar yz + x\bar y\bar z + \bar xyz + \bar x\bar yz}}\\{\bf{d) xyz + x\bar yz + x\bar y\bar z + \bar xyz + \bar xy\bar z + \bar x\bar y\bar z}}\end{array}\)

Short answer

\({\bf{(a)}}\)The minimal expansion is \({\bf{\bar xz}}\)

\({\bf{(b) }}\)The minimal expansion is \({\bf{y}}\)

\({\bf{(c)}}\)The minimal expansion is \({\bf{\bar xz + x\bar y + x\bar z}}\)or \({\bf{\bar xz + x\bar z + \bar yz}}\)

\({\bf{(d)}}\) The minimal expansion is \({\bf{yz + x\bar y + \bar x\bar z}}\) or \({\bf{xz + \bar xy + \bar y\bar z}}\)

Step-by-step solution

Step 1:Definition

To reduce the number of terms in a Boolean expression representing a circuit, it is necessary to find terms to combine. There is a graphical method, called a Karnaugh map or K-map, for finding terms to combine for Boolean functions involving a relatively small number of variables. You will first illustrate how K-maps are used to simplify expansions of Boolean functions in two variables. You will continue by showing how K-maps can be used to minimize Boolean functions in three variables and then in four variables. Then you will describe the concepts that can be used to extend K-maps to minimize Boolean functions in more than four variables.

A \({\bf{K}}\)-map for a function in three 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 two rows \({\bf{x}}\) and \({\bf{\bar x}}\).

Finding the minimal expansion

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

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

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

Note that the two \({\bf{1}}\) 's form a block \({\bf{\bar xz}}\) (as both cells with a \({\bf{1}}\) have the variables \({\bf{\bar x}}\) and \({\bf{z}}\) in common) and thus the minimal expansion is \({\bf{\bar xz}}\).

Finding the minimal expansion

A \({\bf{K}}\)-map for a function in three 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 two rows \({\bf{x}}\) and \({\bf{\bar x}}\).

Place a \({\bf{1}}\) in the cell corresponding to each term in the given sum \({\bf{xyz + xy\bar z + \bar xyz + \bar xy\bar z}}\)

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

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

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

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

Note that the four \({\bf{1}}\)'s form a block \({\bf{y}}\) (as all \(4\) cells with a \(1\) have the variables \({\bf{y}}\) in common and there are no other cells with a \({\bf{y}}\) ) and thus the minimal expansion is \({\bf{y}}\).

Finding the minimal expansion

A \({\bf{K}}\)-map for a function in three 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 two rows \({\bf{x}}\) and \({\bf{\bar x}}\).

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

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

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

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

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

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

All ones do not form a block together, thus we will require multiple terms in the minimal expansion.

Note that \({\bf{\bar xyz}}\) and \({\bf{\bar x\bar yz}}\) form the block \({\bf{\bar xz}}\).

There are then three ones remaining (that are not present in a block) \({\bf{xy\bar z, x\bar y\bar z,x\bar yz}}\). These three ones form two blocks \({\bf{x\bar y}}\) and \({\bf{x\bar z}}\).

Thus, a minimal expansion is then the sum of these three blocks:

Minimal expansion \({\bf{ = \bar xz + x\bar y + x\bar z}}\)

Note: \({\bf{\bar xz + x\bar z + \bar yz}}\) is also a minimal expansion.

Step 5:Finding the minimal expansion

A \({\bf{K}}\)-map for a function in three 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 two rows \({\bf{x}}\) and \({\bf{\bar x}}\).

Place a \(1\) in the cell corresponding to each term in the given sum \({\bf{xyz + xy\bar z + \bar xy\bar z + \bar x\bar yz}}\)

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

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

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

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

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

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

All ones do not form a block together, thus we will require multiple terms in the minimal expansion.

We note that \({\bf{xyz}}\) and \({\bf{\bar xyz}}\) form the block \({\bf{yz}}\).

There are then four ones remaining (that are not present in a block yet) \({\bf{x\bar yz}}\), \({\bf{x\bar y\bar z}}\), \({\bf{\bar xy\bar z}}\), \({\bf{\bar x\bar y\bar z}}\). These four ones form two blocks \({\bf{x\bar y}}\) and \({\bf{\bar y\bar z}}\).

Thus, a minimal expansion is then the sum of these three blocks:

Minimal expansion \({\bf{ = yz + x\bar y + \bar x\bar z}}\)

Therefore,\({\bf{xz + \bar xy + \bar y\bar z}}\) is also a minimal expansion.