# [SOLVED]Karnaugh Diagram

#### mathmari

##### Well-known member
MHB Site Helper
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?

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:

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$$ ?

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

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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$$

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.

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.

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.

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.

#### mathmari

##### Well-known member
MHB Site Helper
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$$
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?

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.
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?

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.
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

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.

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.

#### mathmari

##### Well-known member
MHB Site Helper
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.
So, do we get the following?

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.
How exactly can we find the prime implicant from the above diagram? I haven't really understood that.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

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

#### mathmari

##### Well-known member
MHB Site Helper
Looks good to me.

What is the largest rectangle that fits into the marked cells? One that corresponds to a conjunction of 1 or 2 variables?
Do we get these two rectangles?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Do we get these two rectangles?
Yep.

Can we find another one with 2 variables?

#### mathmari

##### Well-known member
MHB Site Helper
Can we find another one with 2 variables?
Which one do you mean? I got stuck right now.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Which one do you mean? I got stuck right now.
Isn't there a 1x4 rectangle?

#### mathmari

##### Well-known member
MHB Site Helper
Isn't there a 1x4 rectangle?
So, do we have the following $4$ rectangles?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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?

#### mathmari

##### Well-known member
MHB Site Helper
But... can we write that 3x1 rectangle as a conjunction of 3 variables?
Is this 3x1 rectangle a conjuction of just 2 variables?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Is this 3x1 rectangle a conjunction of just 2 variables?
I don't think so.
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?

#### mathmari

##### Well-known member
MHB Site Helper
I don't think so.
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?
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

#### mathmari

##### Well-known member
MHB Site Helper
Yes.
Or 4x2 / 2x4. Those do not fit in this case though.
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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$ ?

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?

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

#### mathmari

##### Well-known member
MHB Site Helper
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$ ?

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?

EDIT: Oh wait, we can leave out one of the rectangles, can't we? And still have an exact cover?
So, we have to find rectangles so that all cells are covered, right?

Do we get then the following?

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

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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?

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?

#### mathmari

##### Well-known member
MHB Site Helper
Yes. Can we identify the expressions that correspond to them?
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?

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?
Yes. So, can we ignore that rectangle and we get still all the prime implicants?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

MHB Site Helper