Question

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

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

Short answer

\((a)\)The minimum expansion for the sum-of-product is \(\bar x\)

\((b)\)The minimum expansion for the sum-of-product is \(x\)

\((c)\) The minimum expansion for the sum-of-product is \(1\)

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.

\(K{\bf{ - }}\)map for a function in two variables is basically a table with two columns \({\bf{y}}\) and \({\bf{\bar y}}\)and two rows \({\bf{x}}\) and \({\bf{\bar x}}\).

Placing the values in the cell

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

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

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

We note that both ones occur in the row of \({\bf{\bar x}}\), which means that the minimum expansion for the sum-of-product is \({\bf{\bar x}}\).

Placing the values in the cell

\(K{\bf{ - }}\)map for a function in two variables is basically a table with two columns \({\bf{y}}\) and \({\bf{\bar y}}\)and two rows \({\bf{x}}\) and \({\bf{\bar x}}\).

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

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

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

We note that both ones occur in the row of \({\bf{x}}\), which means that the minimum expansion for the sum-of-product is \({\bf{x}}\).

Placing the values in the cell

\(K{\bf{ - }}\)map for a function in two variables is basically a table with two columns \({\bf{y}}\) and \({\bf{\bar y}}\)and two rows \({\bf{x}}\) and \({\bf{\bar x}}\).

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

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

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

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

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

One notes that there is a \(1\) in each cell of the \(K{\bf{ - }}\)map, which means that the Boolean function will give a \(1\) for all possible values of \({\bf{x}}\) and \({\bf{y}}\). This then implies that the minimum expansion for the sum-of-product is \(1\).