GATE CSE 2003 | Question: 45

Question

The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $\left(xy+xz'\right)$ is $4.$ What are the minimum possible literal counts of the product-of-sum and sum-of-product representations respectively of the function given by the following Karnaugh map? Here, $X$ denotes "don't care"

• A. $(11, 9)$
• B. $(9, 13)$
• C. $(9, 10)$
• D. $(11,11)$

Comments

I am getting 8 literals for SOP, top right most corner '1' can form a group of 4 with corners don't cares and remaining 1's forms a group of 2 so there are total of 2+3+3 literals for SOP. but answer given as (9,10).

---

you missed 1 one.

---

this is what i have done, plz tell me where i was wrong.

pink ink is for SOP = 2 + 3 + 3 = 8

blue ink is for POS = 2 + 2 + 2 + 3 = 9

---

Can we use the DONT CARE once included angain for grouping  ? Here d15 and d8 are grouped twice ? Is this possibe ?

---

if dont care has been used in pos than can't be used in sop .

since if we used don't care for pos that meas we are considering don't care as 0's ..

---

@gabbar sir
"if dont care has been used in pos than can't be used in sop ." This statement creating so much confusions. Do you have any standard books or any proofs justifying the statement .
AFAIK There is no such restrictions for dont care . Like if we are using one in POS we can use the same for SOP

---

Same don't care can be used both in SOP and POS . Moreover , minimum number of literals is not necessarilly unique.Hence we can go for option c since (9,8) is not in the options.For reference  Chapter 3 "Simplification of boolean function" - Digital Logic and Computer Design by Morris Mano

---

The same dont care can be used is pos and sop. When dont cares are included both pos and sop might represent different class of functions. Its completely valid.

---

im also getting 8 for sop? which one did I miss?

---

pehle SOP nikalna POS nikalne ki zarurat nhi hai, all sop's literal counts are different.

---

For SOP, we need to group 1's with giving the precedence for octet, quad,  pair, then single element, while grouping consider the don't care also
Similarlt For POS, we need to group 0's, giving the precedence for octet, quad,  pair, then single element
 Literal count for octet=1, quad=2, pair=3 and single =4 .
Above problem :
 product-of-sum (POS) we get three quad and one pair so total literal count = 3*2 + 1*3= 9.
sum-of-product (SOP) we get two quad and two pair so total literal count = 2*2 + 2*3 = 10.

Ans: (POS,SOP)= (9,10)

correct me if I wrong.

---

An important note is discussed HERE.

To All Students:

For this GATE 2003 question, simple conclusion is that answer is (9,8).. That's it.

The question maker missed it, gave wrong options & some students are forcibly trying to match with that wrong option. But in future GATE question, the question maker won't miss it. So, Always Follow Correct Concept.

---

Watch the Detailed Video Solution by clicking the below button..!

Watch Video Detailed Solution   

---

Group1:

SOP = 2+3+3 = 8

POS=2+2+2+3 = 9

Group2:

SOP = 2+2+3+3 = 10

POS = 2+2+2+3  = 9

Answer 1

We will be getting  two different grouping..

Grouping $1: (9,8)$ 

 

$\text{SOP}: 2 + 3 + 3 = 8$   

  $\text{POS}: 2 + 2 + 2 + 3 = 9$

 

 

 

GROUPING $2: (9,10)$

$\text{SOP}: 2 + 2 + 3 + 3 = 10$ 

  $\text{POS}: 2 + 2 + 2 + 3 = 9$

 

Both the grouping are correct representation of the function  $f(wxyz)$

PS: Some wrong beliefs about don't cares

1. "once you have assumed a don't care as '1' u can't use the same don't care for grouping zeros and vice versa"
2. "if don't care has been used in POS than can't be used in SOP"

Both these statements are wrong. Don't care simply means just don't care -- say we use don't care $d3$ for grouping $1$ in SOP we can use $d3$ for grouping 0 in POS. (The literals in SOP and POS may not be the same)

K-Map grouping is not unique. And the question says about minimal literals. So, the best answer would be (9,8) Since there is no option in GATE we can go with $(9,10)$ (the question setter might have missed Grouping 1)

Comments

According to Deepak Sir, if there are multiple solutions to a K-Map, the no of terms and no of literals must be same. So if there is a SOP with 3 terms and 9 literals, how can there be a SOP with 4 terms and 10 literals?

---

Because there are don't care. Though all the minimal expressions are equivalent they have different literal count.

---

@Sruja_Thakkar, The following paragraph is from "Introduction to Logic Design by Alan B. Marcovitz" book (Page 128, 3rd Edition):

"For a boolean function, all minimum SOP solutions must have the same number of terms and literals. If, for example, you find a minimum solution with three terms and seven literals, no solution with four terms is minimum, and no solution with three terms and eight literals is minimum."

Same is discussed HERE as well.

To All Students:

For this GATE 2003 question, simple conclusion is that answer is (9,8).. That's it.

The question maker missed it, gave wrong options & some students are forcibly trying to match with that wrong option. But in future GATE question, the question maker won't miss it. So, Always follow Correct Concept.

Answer 2

I am getting (9,8), 9 for POS and 8 for SOP.

Comments

No same don't care can be used both in SOP and POS . Moreover , minimum number of literals is not necessarilly unique.Hence we can go for option c since (9,8) is not in the options.For reference  Chapter 3 "implification of boolean function" - Digital Logic and Computer Design by Morris Mano

---

both are different function we can can use same dont care for both sop and pos .

@Bikram sir verify this pls

---

@Arjun sir

If these questions  come so should we answer

1)the best nearest answer

2)or should we refrain from answering such questions?

3)and also one more point, are marks awarded to all in such a situation or not?

Please help. All seniors please help us in this muddle.. It would be a great help:)

Answer 3

POS

(z'+w')(y'+z')(x'+w')(x+y'+w)

9 literals

SOP:

y'w'+yw+xyz'+x'y'z'

10 literals

ans is c

Comments

@Pooja Palod We can write SOP using 8 literal as well:

y'w'+xyz'+x'z'w  which is minimal and even in question it is mentioned that "What are the minimum possible literal counts of the product-of-sum and sum-of-product representations".

so, Answer should be (9,8) as it is minimum possible.

@Arjun Sir please look this question.

Correct me if I am wrong.

Answer 4

Do not make things too complicated.
since option have distinct pos, so find POS.
you'll get answer

 

Answer 5

I am getting 9 pos and 9 sop...

WHat's wrong??

Answer 6

answer is (9,8)

we know that in fn of 'n' variables , if we make a cube of 2^m cells
then m variables are removed and the expression has only n-m literals in it

SOP: (m0,m2,m8,m10) gives 2 literals

         (m4,m5) gives 3 literals

          (m2,m3) gives 3 literals

hence minimum number of literals for S.O.P is 8

POS: (M12,M13,M14,M15) gives 2 literals
 

          (M9,M13,M1,M15) gives 2 literals

         (M2,M6,M10,M14) gives 2 literals

         (M1,M9) gives 3 literals
hence minimum number of literals for POS is 9

 

and the answer is (9,8)