Welcome to our community

Be a part of something great, join today!

Using Karnaugh Maps For This Function

shamieh

Active member
Sep 13, 2013
539
Find the minimum cost sum of products and product of sums forms for the function : $f$(x1,x2,x3 = \(\displaystyle \sum\)m(1,2,3,5)

I need to use Karnaugh Maps. How do I do this with a Karnaugh map, I understand how to get the rows and columns with a K map. But i don;t understand after that.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
Find the minimum cost sum of products and product of sums forms for the function : $f$(x1,x2,x3 = \(\displaystyle \sum\)m(1,2,3,5)
How do you measure cost?

I need to use Karnaugh Maps. How do I do this with a Karnaugh map, I understand how to get the rows and columns with a K map. But i don;t understand after that.
Could you explain more precisely what you understand and what you don't? You know how to get the rows and columns of what? Can you post (or at least describe) the Karnaugh map for this function?
 

shamieh

Active member
Sep 13, 2013
539
Please delete this post. I have created another, with a more details to question on a particular K-map problem. Please void this post.
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Please delete this post. I have created another, with a more details to question on a particular K-map problem. Please void this post.
I think it would be best to leave this topic, so that when you get your other question answered, you may want to revisit this topic and show what you learned by completing this question here for the benefit of our readers.
 

shamieh

Active member
Sep 13, 2013
539
Figured out how to use K-Maps! Can anyone check my work?

:D finally figured out how to use K-maps!

Can anyone check my work? Want to make sure I am doing it the right way.

Find the minimum cost Sum of Product form for the function $f$(x1,x2,x3) = \(\displaystyle \sum\)m(1,2,3,5)

I got x3x4! + x1!x2! Is this correct?

Thank you for your time,
Sham
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Re: Figured out how to use K-Maps! Can anyone check my work?

:D finally figured out how to use K-maps!

Can anyone check my work? Want to make sure I am doing it the right way.

Find the minimum cost Sum of Product form for the function $f$(x1,x2,x3) = \(\displaystyle \sum\)m(1,2,3,5)

I got x3x4! + x1!x2! Is this correct?

Thank you for your time,
Sham
Since this is the same question originally posted in this topic, I have merged the two topics to avoid redundancy.
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,197
Re: Figured out how to use K-Maps! Can anyone check my work?

:D finally figured out how to use K-maps!

Can anyone check my work? Want to make sure I am doing it the right way.

Find the minimum cost Sum of Product form for the function $f$(x1,x2,x3) = \(\displaystyle \sum\)m(1,2,3,5)

I got x3x4! + x1!x2! Is this correct?

Thank you for your time,
Sham
Where did the $x_4$ come from? I get $\bar{x}_1 x_2+\bar{x}_2 x_3$.
 

shamieh

Active member
Sep 13, 2013
539
Re: Figured out how to use K-Maps! Can anyone check my work?

Where did the $x_4$ come from? I get $\bar{x}_1 x_2+\bar{x}_2 x_3$.
Wait a minute, I'm an idiot. Was writing down the wrong numbers and was looking at another problem, let me re-work the problem.
 

shamieh

Active member
Sep 13, 2013
539
Find the minimum cost SOP and POS forms for the function $f$(x1,x2,x3,x4) = M(0,1,2,4,5,7,8,9,10,12,14,15)

by Truth table I put all 1's in the spot of the numbers. drew a karnaugh map and got

my KMAP
  1. 1 1 1 1 <---I grouped these 4 1's horizontally..Ialso grouped the 2 1s vertically.
  2. 1 1 0 1 <-- I grouped the 4 1's from the 1st and second row.
  3. 0 1 1 0 <---- I grouped 2 1s horizontally
  4. 1 0 1 1 <--- grouped 2 1s horizontally.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
Here is the Karnaugh map for ∑m(1,2,3,5).



(Yay, I learned to generate images with transparent background!)

Find the minimum cost SOP and POS forms for the function $f$(x1,x2,x3,x4) = M(0,1,2,4,5,7,8,9,10,12,14,15)

by Truth table I put all 1's in the spot of the numbers. drew a karnaugh map and got

my KMAP
  1. 1 1 1 1 <---I grouped these 4 1's horizontally..Ialso grouped the 2 1s vertically.
  2. 1 1 0 1 <-- I grouped the 4 1's from the 1st and second row.
  3. 0 1 1 0 <---- I grouped 2 1s horizontally
  4. 1 0 1 1 <--- grouped 2 1s horizontally.
The K-map is correct. Now you need to write the SOP and POS forms. Note that for POS you look at 0's in the K-map and the convention for writing maxterms is the opposite from that for minterms: 0 for a variable means no negation; 1 means negation.

Here is a nice online K-map generator. However, it only shows minimal SOP forms.
 

shamieh

Active member
Sep 13, 2013
539
Wow I love you. Can I ask you a question. Suppose I am grouping and I had a pair of 1 & d next to each other.. I noticed on this particular problem my teacher gave us, he didn't group that pair, and thus; left out a term. My question is, if there is a grouping to be made of 1's. Why would you not make that grouping? Because that d can just be a 1 right? So why not group that? Wouldn't it minimize your cost? Isn't that the whole point! To find all groupings? Otherwise aren't you missing something? Example Below. We are dealing with Sum of Products by the way just FYI.. NOTE: The x's are my don't cares or "d"s

KMAP.png
 
Last edited:

shamieh

Active member
Sep 13, 2013
539
Also, another question..When we are solving using a K-map for the Product of Sums do we evaluate our K-Map the exact same way except group the 0s? Or do we evaluate it differently?
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,197
Wow I love you. Can I ask you a question. Suppose I am grouping and I had a pair of 1 & d next to each other.. I noticed on this particular problem my teacher gave us, he didn't group that pair, and thus; left out a term. My question is, if there is a grouping to be made of 1's. Why would you not make that grouping?
It isn't always advantageous to make a 'd' a '1'. Clumping on K-maps works like this: they always have to be contiguous rectangles (they can wrap around, both horizontally and vertically), where the height and width are powers of 2. In your case, the 'd' in the $ABCD$ location allows you to form the more efficient term $BC$. However, the 'd' in the $ \bar{A} \bar{B}C \bar{D}$ position does not allow you to form a contiguous rectangle of width a power of 2 and height a power of 2 that includes any ones you can't already get from a different grouping. That is, the '1' in the $\bar{A} \bar{B} \bar{C} \bar{D}$ position you've already got from $\bar{B} \bar{C} \bar{D}$, and the '1' in the $\bar{A}BC \bar{D}$ position you've already gotten from the $BC$ term.

Because that d can just be a 1 right? So why not group that? Wouldn't it minimize your cost? Isn't that the whole point! To find all groupings? Otherwise aren't you missing something? Example Below. We are dealing with Sum of Products by the way just FYI.. NOTE: The x's are my don't cares or "d"s

View attachment 1402
Also, another question..When we are solving using a K-map for the Product of Sums do we evaluate our K-Map the exact same way except group the 0s? Or do we evaluate it differently?
I'll let the master, Evgeny.Makarov, answer that one, as I have no experience forming PoS from K-maps.
 

shamieh

Active member
Sep 13, 2013
539
Cool. I see now. I also found the answer out to my other question. Apparently you group all the zeros, but when you are evaluating, if you have 00 00 for example..and you have WXYZ for example... Instead of WXYZ (which you would put in a SOP form Kmap) you just read W!X!Y!Z! in a POS form kmap. Really pretty simple actually.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
Suppose I am grouping and I had a pair of 1 & d next to each other.. I noticed on this particular problem my teacher gave us, he didn't group that pair, and thus; left out a term.
Leaving out minterms is the whole point; it makes the resulting Boolean expression smaller. I agree with Adrian's explanation. If grouping a d with 1's leads to a bigger group (and thus smaller minterm) whose width and height are powers of 2, then it's a good thing; otherwise it's better to leave it as 0.

Apparently you group all the zeros, but when you are evaluating, if you have 00 00 for example..and you have WXYZ for example... Instead of WXYZ (which you would put in a SOP form Kmap) you just read W!X!Y!Z! in a POS form kmap.
Yes, you group zeros, but the rest is the other way around. With a SOP, 0 means a negation, so 0000 produces W!X!Y!Z!. With a POS, 1 means a negation, and besides terms are sums (it's a Product Of Sums). So, with a POS, 0000 produces W + X + Y + Z.

Basically, in constructing a POS, everything is dual compared to a SOP: instead of 1's in a truth table and a K-map, you look at 0's; instead of products, terms are sums, and instead of negations, 0's correspond to simple variables.