The Gateway to Computer Science Excellence
+9 votes
14k views

What are the prime implicants and essential prime implicants for the below questions ?

F(w, x, y, z) = ∑(1,2,5,7,12) + d(0,9,13)

Explain by drawing K-map.

Also explain the prime implicants and essential prime implicants with don't care condition .
in Digital Logic by Active (1.5k points)
retagged by | 14k views
+2
essential prime inplicant-  (5,7) (0,2) (12,13) (1,5,9,13)

prime implicants- essential prime implicants + (0,1)  ???

2 Answers

+19 votes
Best answer

K Map's with don't cares

A prime implicant is a rectangle of 1, 2, 4, 8, … 1’s or X’s not included in any one larger rectangle. Thus, from the point of view of finding prime implicants, X’s (don’t cares) are treated as 1’s.

An essential prime implicant is a prime implicant that covers at least one 1 not covered by any other prime implicant (as always). Don’t cares (X’s) do not make a prime implicant essential.

 

Here in the image prime implicants are marked with a rectangle.

Essential prime implicants have 1*.



This blue rectangle is not essential prime implicant because here there is no 1 which is only covered by single prime implicant. There is don't care(X) which is only covered by blue rectangle but in essential prime implicant, we only want a 1 which is not covered by another prime implicant. 

Answer: 5 Prime implicants and 3 Essential prime implicants.

Good reads.
https://gateoverflow.in/80983/no-of-essential-prime-implicants
http://www-ee.ccny.cuny.edu/wwwn/yltian/Courses/EE210/EE210-Lecture7.pdf

by Boss (16.3k points)
selected by
+4
Yes, it is correct.

EPI is at position  8, 13 and 3 .

And there are only 3 EPI as we can see clearly from the diagram .

Total 5 Prime Implicants  are possible .
0
@Hemant Parihar, I have a doubt in the question which you posted as the first link.

In that if you see the K map of "vishwa ratna" which is the second answer, he has considered number 2 as essential PI. But the "1" at position "1001" can be covered by "X" above it and together it is a prime implicant. So how second one is essential prime implicant ?
+2
Yes, I also think it should not be an essential prime implicant. 7 PI and 2 EPI. Let Habib confirm it. :)
0
@Hemant Parihar, According to your definition of prime implicant, if we consider all don't cares as 1's, then will a group of 4 don't cares (only don't cares) form a prime implicant? I don't think so.
+1
@xylene it is not my definition, It is given the pdf link :) . Also I see few answer using this.

I also think that it should not be a prime implicants. Because we actually want to cover 1's. And we add don't care to it only when we are forming the big cube so that less literal in a term.

But I don't find any resource on it, If you find one do share :).
0
@Hemant Parihar, Can you please share the link where they have actually used don't cares like that ? I have not seen it anywhere till now. Even in the pdf link there is no example showing this.
+1
Done @Hemant..:) ..
0

If the only one don't care is left in a group then it is considered as the PI or not ...See the last answer given by shruthi , 

at position 10 01 there is a don't care , so tell me it is EPI or PI

0 votes

prime implicant is the no. of all possible larger size subcube in k-map

essential prime implicant is the no. of larger size subcube which at least one cell without overlapping 

here red one define E.P.I.

and red and yellow combined shows P.I.

by Boss (12.2k points)
+1

@pawan, I have a doubt?
 

Are you sure this is essential prime implicant because here there is no 1 which is not covered by any other prime implicant? We don't care about X (don't care).

I agree that it will be preferred over the yellow marked prime implement because it has less literal.

0
I think (0,1) is not Prime emplicant.
0
yes becoz on my view to write minimal expression, essential prime implicant must present   in every possible minimal expression.and u know it will be prefer over yellow marked.

correct me someone if something wrong,,,,
+1

@Pawan I don't think so it is prime implicant.
Let the question is this. 

F(w, x, y, z) = ∑(1,2, 3, 5,7,12) + d(0,9,13)

only 3 is added in Sigma part.
Try it and say your answer. 

+2

essential prime implicant must present   in every possible minimal expression

No, EPI is not like that !

@pawan

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

So at position 13, 8,3 have EPI .

see the best answer, it is correct .

0
thanks for pointing my mistake .....
+1
@Bikram

Sir,

The best answer is correct, but what about the statement "every minimal expression should contain all essential prime implicants", isn't it true?
0

I think essential prime implicant must be present in minimal expression..

Why not? @Bikram

0
Why not ...
0

Sir in above comment you have told that

No, EPI is not like that !

0
essential prime implicant must present in every possible minimal expression No, EPI is not like that !

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

So at position 13, 8,3 have EPI .

I don't think so it is prime implicant. see the best answer, it is correct .

Let the question is this. F(w, x, y, z) = ∑(1,2, 3, 5,7,12) + d(0,9,13) only 3 is added in Sigma part.

Try it and say your answer .

  https://gateoverflow.in/80983/no-of-essential-prime-implicants
–1

@Bikram  

$F=\Sigma(1,2,3,5,7,12)+d(0,9,13)$

3EPI and 4PI

 

0

Sir, i don't have any doubt in calculating PI and EPI and yes this answer is not correct and selected one is right..

But, I was asking that-

 if there are some EPIs present then they all must be present in minimal expression along with some necessary prime implicant.

Because if we exclude any epi then the 'atleast one 1 which is not covered by any other prime implicant' is missed from our expression. 

Correct?

0
K Map's with don't cares

A prime implicant is a rectangle of 1, 2, 4, 8, … 1’s or X’s not included in any one larger rectangle. Thus, from the point of view of finding prime implicants, X’s (don’t cares) are treated as 1’s.

An essential prime implicant is a prime implicant that covers at least one 1 not covered by any other prime implicant (as always). Don’t cares (X’s) do not make a prime implicant essential.

https://cse.sc.edu/~hoskinsw/classes/csce211/LecturesF15/Lecture8.pdf

  https://gateoverflow.in/232643/epi-question?show=232643

http://media-lab.ccny.cuny.edu/wordpress/YLTCCNYHomepage/Courses/EE210/EE210-Lecture7.pdf

Here in the image prime implicants are marked with a rectangle. Essential prime implicants have 1*. This blue rectangle is not essential prime implicant because here there is no 1 which is only covered by single prime implicant. There is don't care(X) which is only covered by blue rectangle but in essential prime implicant, we only want a 1 which is not covered by another prime implicant.

 

5 Prime implicants and 3 Essential prime implicants.
0

What's wrong in this-

I don't found any error in this..

It is for $F=\Sigma(1,2,3,5,7,12)+d(0,9,13)$

Only $I,II,III$  are EPI and 4th group is considered as PI.

0

5 Prime implicants and 3 Essential prime implicants

Right for actual question..

But that (image in above comment) is other function).. it is just reply to your comment--

Let the question is this. F(w, x, y, z) = ∑(1,2, 3, 5,7,12) + d(0,9,13) only 3 is added in Sigma part.

 

Try it and say your answer .

0
F(w, x, y, z) = ∑(1,2,5,7,12) + d(0,9,13)

Explain by drawing K-map.

Also explain the prime implicants and essential prime implicants with don't care condition .

https://gateoverflow.in/?qa=blob&qa_blobid=5414455466690637946

Here in the image prime implicants are marked with a rectangle.

Essential prime implicants have 1*.

https://gateoverflow.in/?qa=blob&qa_blobid=5893376068232915243

This blue rectangle is not essential prime implicant because here there is no 1 which is only covered by single prime implicant.

There is don't care(X) which is only covered by blue rectangle but in essential prime implicant, we only want a 1 which is not covered by another prime implicant.

 

5 Prime implicants and 3 Essential prime implicants.....
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,578 answers
195,772 comments
101,772 users