# Minimizing Expression w/ Karnaugh Diagram

• MHB
• mathmari
In summary, the conversation is about finding a disjunctive normal form and minimizing it using a Karnaugh diagram. There is a discussion about labeling the edges and filling the diagram, as well as a question about whether all variables need to be present in each term of the expression. There is also a mention of a full disjunctive normal form and a question about the use of Gray code in Karnaugh diagrams.
mathmari
Gold Member
MHB
Hey!

I am looking the following:
Determine a disjunctive normal form for the expression $$x_1\left (\left (x_2x_3\lor \bar{x}_2x_4\right )\lor x_2\lor x_3x_4\right )\lor x_2\bar{x}_4\bar{\left (\bar{x}_1x_3\right )}\lor x_1x_3\bar{x}_4$$ and minimize it using a Karnaugh Diagram.

The above expression is equivalent to $$x_1x_2x_3\lor x_1\bar{x}_2x_4\lor x_1x_2\bar{x}_3x_4\lor x_2\bar{x}_4x_1\lor x_2\bar{x}_4\bar{x}_3\lor x_1x_3\bar{x}_4$$

Does each term has t contain all the variables? If yes, then if one variable is missing then we replace that by $x_i\lor \bar{x}_i$.

If we have to do that in that way and we simplify the expression and so we get: $$x_1x_2x_3x_4\lor x_1x_2x_3\bar{x}_4\lor x_1\bar{x}_2x_3x_4\lor x_1\bar{x}_2\bar{x}_3x_4\lor x_1x_1\bar{x}_3x_4\lor x_1x_2\bar{x}_3\bar{x}_4\lor \bar{x}_1x_2\bar{x}_3\bar{x}_4\lor x_1\bar{x}_2x_3\bar{x}_4$$

Is this a disjunctive normal form that we arelooking for? (Wondering)

To create the Karnaugh Diagram, is the form of that diagram always the same? I mean how we name the edges $x_1, x_2, x_3, x_4$, as for example:
View attachment 9007

To fill that diagramm do we need the expression to contain all the variables? I mean could we do that if we have the above expression in the form $$x_1x_2x_3\lor x_1\bar{x}_2x_4\lor x_1x_2\bar{x}_3x_4\lor x_2\bar{x}_4x_1\lor x_2\bar{x}_4\bar{x}_3\lor x_1x_3\bar{x}_4$$ ? (Wondering)

Could you explain to me that method? After filling that table how can we continue to determine the minimal expression? (Wondering)

#### Attachments

• K-diagramm.JPG
42 KB · Views: 80
mathmari said:
Hey!

I am looking the following:
Determine a disjunctive normal form for the expression $$x_1\left (\left (x_2x_3\lor \bar{x}_2x_4\right )\lor x_2\lor x_3x_4\right )\lor x_2\bar{x}_4\bar{\left (\bar{x}_1x_3\right )}\lor x_1x_3\bar{x}_4$$ and minimize it using a Karnaugh Diagram.

The above expression is equivalent to $$x_1x_2x_3\lor x_1\bar{x}_2x_4\lor x_1x_2\bar{x}_3x_4\lor x_2\bar{x}_4x_1\lor x_2\bar{x}_4\bar{x}_3\lor x_1x_3\bar{x}_4$$

Hi mathmari!

Shouldn't that be:
$$x_1x_2x_3\lor x_1\bar{x}_2x_4 \lor x_1x_2\lor x_1x_3x_4 \lor \bar{x}_1x_2\bar x_3\bar{x}_4\lor x_1x_3\bar{x}_4$$
(Worried)

mathmari said:
Does each term has t contain all the variables? If yes, then if one variable is missing then we replace that by $x_i\lor \bar{x}_i$.

If we have to do that in that way and we simplify the expression and so we get: $$x_1x_2x_3x_4\lor x_1x_2x_3\bar{x}_4\lor x_1\bar{x}_2x_3x_4\lor x_1\bar{x}_2\bar{x}_3x_4\lor x_1x_1\bar{x}_3x_4\lor x_1x_2\bar{x}_3\bar{x}_4\lor \bar{x}_1x_2\bar{x}_3\bar{x}_4\lor x_1\bar{x}_2x_3\bar{x}_4$$

Is this a disjunctive normal form that we are looking for?

We do not need for every variable to occur exactly once in a disjunctive normal form.
Instead you found a so called _full disjunctive normal form_.
It is not necessary for a Karnaugh diagram. (Nerd)

mathmari said:
To create the Karnaugh Diagram, is the form of that diagram always the same? I mean how we name the edges $x_1, x_2, x_3, x_4$, as for example:

I believe we are free to label the edge as we desire. It only needs to be clear how we do it.
So the shape of your diagram looks fine. (Happy)

mathmari said:
To fill that diagramm do we need the expression to contain all the variables? I mean could we do that if we have the above expression in the form $$x_1x_2x_3\lor x_1\bar{x}_2x_4\lor x_1x_2\bar{x}_3x_4\lor x_2\bar{x}_4x_1\lor x_2\bar{x}_4\bar{x}_3\lor x_1x_3\bar{x}_4$$ ?

Yes. That expression is good enough.
Is it the correct expression though? See my earlier comment.

mathmari said:
Could you explain to me that method? After filling that table how can we continue to determine the minimal expression?

Find the cells that correspond to a disjunctive term and fill them with ones.
Repeat for each of the disjunctive terms.

To find the minimal expression, find the simplest possible expressions that cover part of those cells with ones.
Keep finding more of them until all ones are covered.
Then try to see if some of those expressions can be simplified even more, covering more ones. (Thinking)

Klaas van Aarsen said:
Shouldn't that be:
$$x_1x_2x_3\lor x_1\bar{x}_2x_4 \lor x_1x_2\lor x_1x_3x_4 \lor \bar{x}_1x_2\bar x_3\bar{x}_4\lor x_1x_3\bar{x}_4$$
(Worried)

At my first post I had a typo... The expression had a $\lor$ that shouldn't be there. The correct expression is \begin{equation*}x_1\left (\left (x_2x_3\lor \bar{x}_2x_4\right )\lor x_2 \bar{x}_3x_4\right )\lor x_2\bar{x}_4\overline{\left (\bar{x}_1x_3\right )}\lor x_1x_3\bar{x}_4\end{equation*}

For that one the expression I wrote in my previous post was correct, or not? (Wondering)
Klaas van Aarsen said:
We do not need for every variable to occur exactly once in a disjunctive normal form.
Instead you found a so called _full disjunctive normal form_.
It is not necessary for a Karnaugh diagram. (Nerd)

Considering the equivalent expression \begin{equation*}x_1x_2x_3\lor x_1\bar{x}_2x_4\lor x_1x_2\bar{x}_3x_4\lor x_2\bar{x}_4x_1\lor x_2\bar{x}_4\bar{x}_3\lor x_1x_3\bar{x}_4\end{equation*}
We want to mark the cells that represent each of the terms $x_1x_2x_3, \ \ x_1\bar{x}_2x_4,\ \ x_1x_2\bar{x}_3x_4, \ \ x_2\bar{x}_4x_1, \ \ x_2\bar{x}_4\bar{x}_3, \ \ x_1x_3\bar{x}_4$, or not? (Wondering)

But how can we do that if at one term there aren't all variables? (Wondering)
Klaas van Aarsen said:
I believe we are free to label the edge as we desire. It only needs to be clear how we do it.
So the shape of your diagram looks fine. (Happy)

I though so, because in Wikipedia there is the following:
"The row and column indices are ordered in Gray code rather than binary numerical order. Gray code ensures that only one variable changes between each pair of adjacent cells."

What does this mean? (Wondering)

mathmari said:
At my first post I had a typo... The expression had a $\lor$ that shouldn't be there. The correct expression is \begin{equation*}x_1\left (\left (x_2x_3\lor \bar{x}_2x_4\right )\lor x_2 \bar{x}_3x_4\right )\lor x_2\bar{x}_4\overline{\left (\bar{x}_1x_3\right )}\lor x_1x_3\bar{x}_4\end{equation*}

For that one the expression I wrote in my previous post was correct, or not?

Yes. (Nod)

mathmari said:
Considering the equivalent expression \begin{equation*}x_1x_2x_3\lor x_1\bar{x}_2x_4\lor x_1x_2\bar{x}_3x_4\lor x_2\bar{x}_4x_1\lor x_2\bar{x}_4\bar{x}_3\lor x_1x_3\bar{x}_4\end{equation*}
We want to mark the cells that represent each of the terms $x_1x_2x_3, \ \ x_1\bar{x}_2x_4,\ \ x_1x_2\bar{x}_3x_4, \ \ x_2\bar{x}_4x_1, \ \ x_2\bar{x}_4\bar{x}_3, \ \ x_1x_3\bar{x}_4$, or not?

But how can we do that if at one term there aren't all variables?

If a term contains all variables, then it corresponds to a single cell. We put a 1 in that cell to represent it.

Consider for example $x_1$, it corresponds to all cells where $x_1=1$. It's a rectangle of 8 cells.
$\bar x_3$ also corresponds to a rectangle of 8 cells. Just a different one.
$x_1\bar x_3$ corresponds to the rectangle that is the intersection of those 2 rectangles. It contains 4 cells.

So for each term we find the corresponding rectangle and fill it with ones.
The result is the union of all those rectangles. (Thinking)

mathmari said:
I though so, because in Wikipedia there is the following:
"The row and column indices are ordered in Gray code rather than binary numerical order. Gray code ensures that only one variable changes between each pair of adjacent cells."

What does this mean?

A gray code sequence is for instance 000, 001, 011, 010, 110, 111, 101, 100.
Note that every step there is exactly one digit that switches from 0 to 1 or vice versa.

In the Karnaugh diagram we use the sequence 00, 01, 11, 10 on each side.
It encodes where each of the variables is 0 respectively 1.

Graphically each of the variables corresponds to a rectangle of 8 cells.
The gray code sequence means that none of those rectangles share a boundary.
When we move from one cell to then next, we always cross exactly one of those rectangle boundaries.
It makes it easier to spot simplified coverings with rectangles that are as big as possible.
When we find the biggest rectangles that cover all ones, we have found a prime implicant. (Thinking)

Klaas van Aarsen said:
If a term contains all variables, then it corresponds to a single cell. We put a 1 in that cell to represent it.

Consider for example $x_1$, it corresponds to all cells where $x_1=1$. It's a rectangle of 8 cells.
$\bar x_3$ also corresponds to a rectangle of 8 cells. Just a different one.
$x_1\bar x_3$ corresponds to the rectangle that is the intersection of those 2 rectangles. It contains 4 cells.

So for each term we find the corresponding rectangle and fill it with ones.
The result is the union of all those rectangles. (Thinking)

So, do we get the following?
View attachment 9008

Klaas van Aarsen said:
A gray code sequence is for instance 000, 001, 011, 010, 110, 111, 101, 100.
Note that every step there is exactly one digit that switches from 0 to 1 or vice versa.

In the Karnaugh diagram we use the sequence 00, 01, 11, 10 on each side.
It encodes where each of the variables is 0 respectively 1.

Graphically each of the variables corresponds to a rectangle of 8 cells.
The gray code sequence means that none of those rectangles share a boundary.
When we move from one cell to then next, we always cross exactly one of those rectangle boundaries.
It makes it easier to spot simplified coverings with rectangles that are as big as possible.
When we find the biggest rectangles that cover all ones, we have found a prime implicant. (Thinking)

How exactly can we find the prime implicant from the above diagram? I haven't really understood that. (Wondering)

#### Attachments

• K-Dia.JPG
93.6 KB · Views: 76
mathmari said:
So, do we get the following?

How exactly can we find the prime implicant from the above diagram? I haven't really understood that.

Looks good to me. (Nod)

What is the largest rectangle that fits into the marked cells? One that corresponds to a conjunction of 1 or 2 variables? (Wondering)

Klaas van Aarsen said:
Looks good to me. (Nod)

What is the largest rectangle that fits into the marked cells? One that corresponds to a conjunction of 1 or 2 variables? (Wondering)

Do we get these two rectangles? (Wondering)

View attachment 9010

#### Attachments

• rect.JPG
98.7 KB · Views: 77
mathmari said:
Do we get these two rectangles?

Yep. (Nod)

Can we find another one with 2 variables? (Wondering)

Klaas van Aarsen said:
Can we find another one with 2 variables? (Wondering)

Which one do you mean? I got stuck right now. (Wondering)

mathmari said:
Which one do you mean? I got stuck right now.

Isn't there a 1x4 rectangle? (Wondering)

Klaas van Aarsen said:
Isn't there a 1x4 rectangle? (Wondering)

So, do we have the following $4$ rectangles? (Wondering)

View attachment 9011

#### Attachments

• rectangles.JPG
99.4 KB · Views: 69
mathmari said:
So, do we have the following $4$ rectangles?

You found the 1x4 rectangle!
But... can we write that 3x1 rectangle as a conjunction of 3 variables? (Worried)

Klaas van Aarsen said:
But... can we write that 3x1 rectangle as a conjunction of 3 variables? (Worried)

Is this 3x1 rectangle a conjuction of just 2 variables? (Wondering)

mathmari said:
Is this 3x1 rectangle a conjunction of just 2 variables?

I don't think so. (Shake)
One variable gives us a rectangle of 8 cells. Either 2x4 or 4x2.
Although it may 'go over the border and around to the other side'. That is, it can also be for instance two rectangles of each 1x4.
Two variables gives us a rectangle of 4 cells: 2x2 or 4x1 or 1x4.
Three variables gives us a rectangle of 2 cells: 1x2 or 2x1.
Four variables gives us a rectangle of 1 cell.
Don't they? (Wondering)

Klaas van Aarsen said:
I don't think so. (Shake)
One variable gives us a rectangle of 8 cells. Either 2x4 or 4x2.
Although it may 'go over the border and around to the other side'. That is, it can also be for instance two rectangles of each 1x4.
Two variables gives us a rectangle of 4 cells: 2x2 or 4x1 or 1x4.
Three variables gives us a rectangle of 2 cells: 1x2 or 2x1.
Four variables gives us a rectangle of 1 cell.
Don't they? (Wondering)

So, if the given expression contains 4 variables, as in this case, are we looking for 2x2 or 4x1, 1x4, 1x2 or 2x1 and 1x1 rectangles in the diagram? (Wondering)

mathmari said:
So, if the given expression contains 4 variables, as in this case, are we looking for 2x2 or 4x1, 1x4, 1x2 or 2x1 and 1x1 rectangles in the diagram?

Yes.
Or 4x2 / 2x4. Those do not fit in this case though. (Thinking)

Klaas van Aarsen said:
Yes.
Or 4x2 / 2x4. Those do not fit in this case though. (Thinking)

Therefore, in a general case we are looking for 2x2, 2x4, 4x2, 4x1, 1x4, 1x2, 2x1 and 1x1 rectangles, aren't we?

So, in this case we are considering the following rectangles, right? (Wondering)

View attachment 9013

How do we continue now? Do these 3 rectangles represent 3 prime implicants? (Wondering)

#### Attachments

• k_d.JPG
97.9 KB · Views: 68
mathmari said:
Therefore, in a general case we are looking for 2x2, 2x4, 4x2, 4x1, 1x4, 1x2, 2x1 and 1x1 rectangles, aren't we?

So, in this case we are considering the following rectangles, right?

How do we continue now? Do these 3 rectangles represent 3 prime implicants?

Yes.
We need a 4th rectangle to cover the 2nd cell don't we?
Perhaps we can use $x_2\bar x_3\bar x_4$ ? (Wondering)

Together those 4 rectangles form a prime implicant yes.
If we leave out any of the rectangles or if we enlarge one of them, then they do not form an exact cover any more do they? (Thinking)

EDIT: Oh wait, we can leave out one of the rectangles, can't we? And still have an exact cover? (Thinking)

Klaas van Aarsen said:
Yes.
We need a 4th rectangle to cover the 2nd cell don't we?
Perhaps we can use $x_2\bar x_3\bar x_4$ ? (Wondering)

Together those 4 rectangles form a prime implicant yes.
If we leave out any of the rectangles or if we enlarge one of them, then they do not form an exact cover any more do they? (Thinking)

EDIT: Oh wait, we can leave out one of the rectangles, can't we? And still have an exact cover? (Thinking)

So, we have to find rectangles so that all cells are covered, right?

Do we get then the following?

View attachment 9017 Could you explain to me further what you mean at the Edit? (Wondering)

#### Attachments

• rect_K.JPG
97.7 KB · Views: 78
mathmari said:
So, we have to find rectangles so that all cells are covered, right?

Do we get then the following?

Yes. Can we identify the expressions that correspond to them? (Thinking)

mathmari said:
Could you explain to me further what you mean at the Edit?

Suppose we leave out the rectangle in the center. The one that is identified by $x_1x_2$. Do we still cover all the required cells then? (Wondering)

Klaas van Aarsen said:
Yes. Can we identify the expressions that correspond to them? (Thinking)

We get the terms $x_2\bar{x}_3\bar{x}_4, \ \ x_1x_3, \ \ x_1x_4$ and so the expression $x_2\bar{x}_3\bar{x}_4\lor x_1x_3 \lor x_1x_4$.

Is that correct? (Wondering)
Klaas van Aarsen said:
Suppose we leave out the rectangle in the center. The one that is identified by $x_1x_2$. Do we still cover all the required cells then? (Wondering)

Yes. So, can we ignore that rectangle and we get still all the prime implicants? (Wondering)

mathmari said:
We get the terms $x_2\bar{x}_3\bar{x}_4, \ \ x_1x_3, \ \ x_1x_4$ and so the expression $x_2\bar{x}_3\bar{x}_4\lor x_1x_3 \lor x_1x_4$.

Is that correct?

Yes. So, can we ignore that rectangle and we get still all the prime implicants?

Yep. All correct. (Happy)

Klaas van Aarsen said:
Yep. All correct. (Happy)

Great! Thank you so much! (Mmm)

## What is a Karnaugh diagram?

A Karnaugh diagram, also known as a K-map, is a graphical method used to simplify Boolean algebra expressions. It is a tool commonly used in digital logic design to minimize the number of logic gates needed to implement a logic function.

## Why is minimizing expression important?

Minimizing expression is important because it reduces the complexity of a logic function, making it easier to design and implement in digital circuits. It also reduces the cost and power consumption of the circuit.

## How do you create a Karnaugh diagram?

To create a Karnaugh diagram, you first need to write the truth table for the given logic function. Then, group together adjacent cells that have a value of 1 in the truth table. Finally, write the simplified expression by identifying the patterns in the grouped cells.

## What are the advantages of using a Karnaugh diagram?

One of the main advantages of using a Karnaugh diagram is that it provides a visual representation of the logic function, making it easier to identify patterns and simplify the expression. It also eliminates the need for complex Boolean algebra calculations.

## Are there any limitations to using a Karnaugh diagram?

Yes, there are some limitations to using a Karnaugh diagram. It can only be used for simplifying Boolean expressions with up to 6 variables. It also requires the truth table to be complete and accurate, otherwise, the simplified expression may be incorrect.