Question

Use \({\bf{K}}\)-maps to find a minimal expansion as a Boolean sum of Boolean products of Boolean functions that have as input the binary code for each decimal digit and produce as output \({\bf{1}}\) if and only if the digit corresponding to the input is

\({\bf{a)}}\)odd.

\({\bf{b)}}\)not divisible by \({\bf{3}}\).

\({\bf{c)}}\)not \({\bf{4,5,}}\) or \({\bf{6}}\).

Short answer

\({\bf{a)}}\)The minimal expansion is \({\bf{z}}\)

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

\({\bf{c)}}\) The minimal expansion is \({\bf{\bar x + yz}}\)

Step-by-step solution

Definition

To reduce the number of terms in a Boolean expression that representing a circuit, need to find terms to combine. There is a graphical method, called a Karnaugh map or K-map, for finding terms that can be combined for Boolean functions involving with 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.

Finding the minimal expansion

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{w}}\) and \({\bf{x}}\).We place a \({\bf{d}}\) in the first row and in the first two cells of the second row of the \({\bf{K}}\)-map.An input will be odd if the last digit is odd, which occurs if the last digit is \({\bf{z}}\).Thus, we need to place all \({\bf{1}}\)'s in the columns \(\frac{{{\bf{yz}}}}{{{\bf{\bar yz}}}}\) (not in already filled cells!).

All ones form a block together (note: any \({\bf{d}}\)'s can be used to form the block as well), because all \({\bf{1}}\)'s occur in the columns containing \({\bf{z}}\) (and these columns contain no empty cells).Thus, the minimal expansion is then \({\bf{z}}\). Therefore, the minimal expansion \({\bf{ = z}}\)

Finding the minimal expansion

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{w}}\) and \({\bf{x}}\). We place a \({\bf{d}}\) (representing don't care) in the first row and in the first two cells of the second row of the \({\bf{K}}\)-map. The input will be divisible by \({\bf{3}}\) if the digit is \({\bf{0}}\)\({\bf{(}}\)\({\bf{0000}}\) or equivalently \({\bf{\bar w\bar x\bar z}}\)\({\bf{)}}\), \({\bf{3}}\)\({\bf{(0011}}\) or equivalently \({\bf{\bar w\bar xyz),6}}\)\({\bf{(0110}}\) or equivalently \({\bf{\bar wxy\bar z}}\)\({\bf{)}}\), \({\bf{9(1001}}\) or equivalently \({\bf{w\bar x\bar yz),}}\)\({\bf{12}}\)\({\bf{(1100}}\) or equivalently \({\bf{wx\bar y\bar z)}}\) or \({\bf{15}}\)\({\bf{(1111}}\)or equivalently \({\bf{wxyz)}}\). Place a \({\bf{1}}\) in the cells of the \({\bf{K}}\)-map for the numbers not divisible by \({\bf{3}}\) (and that don't contain a \({\bf{d}}\) ).

\({\bf{w\bar x\bar y\bar z}}\)is contained in the block \({\bf{w\bar z}}\) (which is the largest block containing the cell and other cells with \({\bf{1's/d's}}\)). \({\bf{\bar w\bar xy\bar z}}\) is contained in the block \({\bf{\bar xy\bar z}}\) (which is the largest block containing the cell and other cells with \({\bf{1's/d's}}\)). \({\bf{\bar wxyz}}\) is contained in the block \({\bf{xz}}\) (which is the largest block containing the cell and other cells with \({\bf{1's/d's}}\)). \({\bf{\bar wx\bar y\bar z}}\) is contained in the block \({\bf{x\bar y}}\) (which is the largest block containing the cell and other cells with \({\bf{1's/d's}}\)). \({\bf{\bar w\bar x\bar yz}}\) is contained in the block \({\bf{\bar w\bar yz}}\) (which is the largest block containing the cell and other cells with \({\bf{1's/d's}}\)). The Minimal expansion is then the sum of these blocks.

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

Step 4:Finding the minimal expansion

A \({\bf{K}}\)-map for a function in four variables is a table with four columns \({\bf{yz,y}}\) four rows \({\bf{wx,w\bar x,\bar w\bar x}}\) and \({\bf{\bar wx}}\); which contains all possible combinations of \({\bf{w}}\) and \({\bf{x}}\). We place a \({\bf{d}}\) (representing don't care) in the first row and in the first two cells of the second row of the \({\bf{K}}\)-map. The input will be \(4{\bf{,5}}\) or \({\bf{6}}\) if the digit is \(4\)\({\bf{( 0100}}\) or equivalently \({\bf{\bar wx\bar y\bar z),}}\)\({\bf{5 (0101}}\) or equivalently \({\bf{\bar wx\bar yz),}}\)\({\bf{6(0110}}\) or equivalently \({\bf{\bar wxy\bar z)}}\). Place a \({\bf{1}}\) in the cells of the \({\bf{K}}\)-map for the numbers that are not \({\bf{4,5}}\)or \({\bf{6}}\) (and that don't contain a \({\bf{d}}\) ).

Note that all ones (and \({\bf{d's}}\)) in the second and third row of the table form a block \({\bf{\bar x}}\). Only \({\bf{\bar wxyz}}\) will not be included in that block. However, the largest block containing \({\bf{\bar wxyz}}\) is \({\bf{yz}}\) (as the column \({\bf{yz}}\) contains only \({\bf{d's}}\) and \({\bf{1's}}\)).

Therefore, The Minimal expansion is then the sum of these blocks.

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