Question

Construct a \({\bf{K}}\)-map for \({\bf{F(x,y,z) = xz + yz + xy\bar z}}{\bf{.}}\) Use this \({\bf{K - }}\)map to find the implicants, prime implicants, and essential prime implicants of \({\bf{F(x,y,z)}}\).

Short answer

The K-map for the given expression

Implicants \({\bf{ = xyz,xy\bar z,x\bar yz,\bar xyz,xy,xz,yz}}\).

Prime Implicants \({\bf{ = x y, x z, y z}}\).

Essential prime Implicants \({\bf{ = x y, x z, y z}}\).

Step-by-step solution

Step 1: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. It will first illustrate how K-maps are used to simplify expansions of Boolean functions in two variables. It will continue by showing how K-maps can be used to minimize Boolean functions in three variables and then in four variables. Then it will describe the concepts that can be used to extend K-maps to minimize Boolean functions in more than four variables.

Finding the implicants

Given:\({\bf{F(x,y,z) = xz + yz + xy\bar z}}\)

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)}}\).It places a \({\bf{1}}\) in the cell(s) corresponding to each term in the given sum \({\bf{xz + yz + xy\bar z}}{\bf{.}}\).

\({\bf{xz}}\): place a \({\bf{1}}\) in the cells corresponding to row \({\bf{x}}\) and columns \(\frac{{{\bf{yz}}}}{{{\bf{\bar yz}}}}\) (as these are the two columns that contain a \({\bf{z}}\) ).

\({\bf{yz}}\): place a \({\bf{1}}\) in all cells of the column \({\bf{yz}}\).

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

An implicant is the product of literals corresponding to a block of all \({\bf{1's}}\).Two of the implicants were terms in the given Boolean functions: \({\bf{xz}}\) and \({\bf{yz}}\) (as they represented blocks).One of the blocks is then still missing: the block created by \({\bf{xyz}}\) and \({\bf{xy\bar z}}\), which is the block \({\bf{xy}}\) (as both terms have \({\bf{xy}}\) in common).Each cell also represents an implicant.

Implicants\({\bf{ = xyz,xy\bar z,x\bar yz,\bar xyz,xy,xz,yz}}\).

Finding the prime implicants

If an implicant is not contained in another implicant then it is called a prime implicant.

The implicants \({\bf{xyz,}}\)\({\bf{xy\bar z,}}\)\({\bf{x\bar yz,}}\)\({\bf{\bar xyz}}\) are not prime implicants, since they are contained in at least one of the blocks \({\bf{x y, x z, y z}}\).

Since each of the implicants \({\bf{x y, x z, y z}}\) consist of two cells and since there are no implicants corresponding with more cells, none of the implicants are contained in the block of another implication and thus these implicants are all prime implicants due to the implication.

Prime Implicants\({\bf{ = x y, x z, y z}}\).

Finding the essential prime implicants

An essential prime implicant is a largest prime implicant that is the only block containing some cell of the \({\bf{K}}\)-map.

\({\bf{x y}}\)is the only prime implicant that contains the cell \({\bf{xy\bar z}}\) and thus \({\bf{x y}}\) is an essential prime implicant.

\({\bf{x z}}\)is the only prime implicant that contains the cell \({\bf{x\bar yz}}\) and thus\({\bf{ x z}}\) is an essential prime implicant.

\({\bf{y z}}\)is the only prime implicant that contains the cell \({\bf{\bar xyz}}\) and thus \({\bf{y z}}\) is an essential prime implicant.

Essential prime Implicants\({\bf{ = x y, x z, y z}}\).