Answer to Question #280329 in Discrete Mathematics for Tommy

Question

Construct a K-map for F(x, y, z) = xz + yz + xyz. Use this K-map to find the implicants, prime

implicants, and essential prime implicants of F(x, y, z).

Answer 1

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

We place a 1 in the cell(s) corresponding to each term in the given sum $x z+y z+x y \bar{z}$ :

$- xz$ place a 1 in the cells corresponding to row x and columns yz/yˉ​z (as these are the two columns that contain a z )

- y z : place a 1 in all cells of the column y z

- $x y \bar{z}$ : place a 1 in the cell corresponding to row x and column $y \bar{z}$

An implicant is the product of literals corresponding to a block of all $1 \mathrm{~s}$ .

- Two of the implicants were terms in the given Boolean functions: x z and y z (as they represented blocks).

- One of the blocks is then still missing: the block created by xyz and $x y \bar{z}$ , which is the block xy (as both terms have xy in common).

- Each cell also represents an implicant.

$\text { Implicants }=x y z, x y \bar{z}, x \bar{y} z, \bar{x} y z, x y, x z, y z$

A prime implicant is an implicant that is not contained in another implicant.

- The implicants $x y z, x y \bar{z}, x \bar{y} z, \bar{x} y z$ are not prime implicants, since they are contained in at least one of the blocks x y, x z, y z.

- Since each of the implicants xy, xz, yz 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.

Prime Implicants $=x y, x z, y z$

Step 2

An essential prime implicant is a largest prime implicant that is the only block containing some cell of the K-map.

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

- xz is the only prime implicant that contains the cell $x \bar{y} z$ and thus xz is an essential prime implicant.

- yz is the only prime implicant that contains the cell $\bar{x} y z$ and thus yz is an essential prime implicant.

Essential prime Implicants =$x y, x z, y z$

Result:

$\begin{aligned} &\text { Implicants }=x y z, x y \bar{z}, x \bar{y} z, \bar{x} y z, x y, x z, y z \\ &\text { Prime Implicants }=x y, x z, y z \\ &\text { Essential prime Implicants }=x y, x z, y z \end{aligned}$