# Karnaugh map: What values to combine?

I have obtained the Karnaugh diagram (pictured below) and now I'm trying to obtain the Boolean expression of K3 through this diagram. My inputs are Q1, Q2 and Q3. I'm trying to "group" 1's and X's together (where the X stands for the don't-care-variable). Now I'm not sure in what way I can group these 1's and X's. Can my groups overlap? Or should they be separate? I know the groups can only be the size of a power of 2. Here are the options:

Original table:

Option 1:

Option 2:

Option 3:

Can someone explain to me which "boxing" of values I should use to obtain my Boolean expression? Are my boxes allowed to overlap? Maybe there are other options for grouping this diagram?

Any help is appreciated! :)

• Neither. Take the top row (Q3=0) and the left/right edges (Q1=0) Commented Mar 23, 2021 at 16:54
• @EugeneSh. Thanks! Do you mean to take a 2x2 block for Q1=0? Is it then in general true that you should take the largest block possible? Commented Mar 23, 2021 at 16:58
• @Math420 Yes. You always want to scoop up the largest blocks possible. Even if they overlap each other.
– jonk
Commented Mar 23, 2021 at 16:58
• This page summarizes it better than a comment (or an average answer) would do: ee.surrey.ac.uk/Projects/Labview/minimisation/karrules.html Commented Mar 23, 2021 at 16:59

The goal is to cover all '1's with blocks as large as possible. Overlapping boxes is permitted. All three of your options will result in a working solution, but none of them are optimal.

This problem can be solved with two blocks.

• Short, sweet, and to the point without giving away the answer.
– TimB
Commented Mar 23, 2021 at 17:24

Can my groups overlap?

Yes. You are going to "or" together the groups, so they can overlap.

Or should they be separate?

They can overlap since you'll "or" them all together eventually.

Can someone explain to me which "boxing" of values I should use to obtain my Boolean expression?

Depends on your design constraints. They all are valid. Typically you want the one with the fewest and biggest boxes since it will result in fewer gates. Each box is and and gate that will have to be or-ed together.

There's another option that you might not have learned yet. This is kind of a trick question in that you can solve the problem either by covering all the 1s with the fewest boxes possible, or you can cover the zeros with the fewest boxes possible, then invert the output.

Since you only have 1 zero, you can do $$\\overline{Q_1 Q_2 Q_3}\$$.

The red and blue boxes in option 1 are redundant. Only 2 boxes (or terms) are needed. Overlapping is certainly allowed, and sometimes desirable; in some cases an extra overlapping term is needed to eliminate hazards (which cause can glitches) when transitioning between non-overlapping terms.