retagged by
16,328 views
29 votes
29 votes
Consider the minterm list form of a Boolean function $F$ given below.

$$F(P, Q, R, S) = \Sigma m(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)$$

Here, $m$ denotes a minterm and $d$ denotes a don't care term. The number of essential prime implicants of the function $F$ is ___
retagged by

3 Answers

Best answer
54 votes
54 votes

Implicant: Any product term $p$ in SOP form such that $p\implies f$ is an implicant of $f.$ So, we have $9$ implicants for $F$ here one corresponding to each $1$ or $d$ in the K-map. 

 

Prime Implicant: A minimal implicant is called a prime implicant (no extra literals than required).  So, we have $5$ prime implicants for $F- \{ \bar ABD, \bar B \bar D, A \bar B, \bar ACD, \bar BC\}.$ (for each $1$ or $d$ in $K-map$ try to combine with near by $1s$ and do not care conditions)

Essential Prime Implicant: A prime implicant which cannot be replaced by any other for getting the output. i.e., essential prime implicants cover the output that no other combination of other prime implicants can. In K-map, this means an essential prime implicant must cover a $1$ $\textbf{(we do not consider don't care as essential})$ which is not covered by any other prime implicant. Here, we have $3$ essential prime implicants corresponding to $3$ selections shown in the below $K-map$. 

So, $3$ Essential Prime Implicants. 

edited by
26 votes
26 votes

Here we can treat $d$(don't cares) as $1$


Implicants are group of $1$s... they can be single $1$s or pairs or quads or octates.i.e. any subcube.

Implicants formed by taking each $1$ and $d$ as individuals are $11$ as shown below.

Implicants formed by taking  $1$ and $d$ as pairs are $14$ as shown below.

Implicants formed by taking  $1$ and $d$ as quadruples are $4$ as shown below.

we can't form any octate using $1$ and $d$

$\therefore$ Total number of implicants formed by taking  $1$ and $d$ $=11+14+4=29$


A prime implicant is a rectangle of 1, 2, 4, 8, … 1’s or $d$’s not included in any one larger rectangle.

Thus, from the point of view of finding prime implicants, $d$’s (don’t cares) are treated as 1’s.

So we have $6$ possible prime implicants as shown below.


An essential prime implicant is a prime implicant that covers at least one $1$ not covered by any other prime implicant .

Don’t cares ($d$’s) do not make a prime implicant essential.

So we have $3$ essential prime implicants as shown below.

$\therefore$ There are $3$ essential prime implicants.

edited by
3 votes
3 votes

Lets's try with Quine-McCluskey method.

 

$\\ \underline{0|}\\ 2|\\ \underline{8|}\\ 3|\\ 5|\\ 9|\\ 10|\\ \underline{12|}\\ 7|\\ 11|\\ \underline{14|}$           $\\ 0,2(2)|\\ \underline{0,8(8)|}\\ 2,3(1)|\\ 2,10(8)|\\ 8,9(1)|\\ 8,10(2)|\\ \underline{8,12(4)|}\\ 3,7(4)|\times\\ 3,11(8)|\\ 5,7(2)|\times\\ 9,11(2)|\\ 10,11(1)|\\ 10,14(4)|\\ 12,14(2)|\\$        $\\ \underline{0,2,8,10(2,8)|}\times\\ 2,3,10,11(1,8)|\times\\ 8,9,10,11(1,2)|\times\\ 8,10,12,14(2,4)|\times\\$

$6\ Prime\ Implicants.$


  $0$ $2$ $5$ $7$ $9$ $11$
$3,7(4)$       $\times$    
$5,7(2)$     $\times$ $\times$    
$0,2,8,10(2,8)$ $\times$ $\times$        
$2,3,10,11(1,8)$   $\times$       $\times$
$8,9,10,11(1,2)$         $\times$ $\times$
$8,10,12,14(2,4)$            

$3\ EPI$

$5,7(2):A'BD+0,2,8,10(2,8):B'D'+8,9,10,11(1,2):AB'$

 

Reference: M. Morris Mano

Answer:

Related questions

24 votes
24 votes
3 answers
1
41 votes
41 votes
9 answers
3