Minimizing Expression w/ Karnaugh Diagram

[mathmari]

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)

 

[I like Serena]

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)

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.
So we already had a disjunctive normal form.
Instead you found a so called _full disjunctive normal form_.
It is not necessary for a Karnaugh diagram. (Nerd)

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)

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. (Thinking)

 

[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)

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)

We do not need for every variable to occur exactly once in a disjunctive normal form.
So we already had 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)

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)

 

[I like Serena]

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)

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)

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)

 

[mathmari]

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

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)

 

[I like Serena]

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)

 

[mathmari]

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

 

[I like Serena]

Do we get these two rectangles?

Yep. (Nod)

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

 

[mathmari]

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

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

 

[I like Serena]

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

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

 

[mathmari]

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

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

View attachment 9011

 

[I like Serena]

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)

 

[mathmari]

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)

 

[I like Serena]

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)

 

[mathmari]

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)

 

[I like Serena]

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)

 

[mathmari]

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)

 

[I like Serena]

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)

 

[mathmari]

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)

 

[I like Serena]

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)

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)

 

[mathmari]

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)

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)

 

[I like Serena]

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)

 

[mathmari]

Yep. All correct. (Happy)

Great! Thank you so much! (Mmm)