Prime implicants and disjunctive minimal form

[mathmari]

Hey!

I am looking the follwong exercise:

Using the method of Quine-McCluskey, determine the prime implicants for the following switching function and find a disjunctive minimal form. If available, also specify all other disjoint minimal forms.

The switching function is:
\begin{align*}f(x_1, x_2, x_3, x_4, x_5)&=\bar{x}_1\bar{x}_2\bar{x}_3\bar{x}_4\bar{x}_5\lor \bar{x}_1x_2\bar{x}_3\bar{x}_4\bar{x}_5\lor \bar{x}_1\bar{x}_2\bar{x}_3\bar{x}_4x_5\lor \bar{x}_1x_2\bar{x}_3x_4\bar{x}_5 \\ & \lor \bar{x}_1x_2\bar{x}_3\bar{x}_4x_5 \lor x_1x_2\bar{x}_3x_4\bar{x}_5\lor \bar{x}_1x_2x_3x_4\bar{x}_5 \lor \bar{x}_1x_2x_3x_4x_5 \\ & \lor x_1x_2\bar{x}_3x_4x_5\end{align*} I have done the following:

It holds that $\bar{x}=x^0$ and $x=x_1$. So we get the following:
\begin{align*}f(x_1, x_2, x_3, x_4, x_5)&=x_1^0x_2^0x_3^0x_4^0x_5^0\lor x_1^0x_2^1x_3^0x_4^0x_5^0\lor x_1^0x_2^0x_3^0x_4^0x_5^1\lor x_1^0x_2^1x_3^0x_4^1x_5^0 \\ & \lor x_1^0x_2^1x_3^0x_4^0x_5^1 \lor x_1^1x_2^1x_3^0x_4^1x_5^0\lor x_1^0x_2^1x_3^1x_4^1x_5^0\lor x_1^0x_2^1x_3^1x_4^1x_5^1 \\ & \lor x_1^1x_2^1x_3^0x_4^1x_5^1\end{align*}

We create the following table using the weights and we try to merge the midterms.

View attachment 9290

Therefore we get six primterms:
\begin{align*}&p_1=m_2+m_4=x_1^0x_2^1x_3^0x_5^0=\bar{x}_1x_2\bar{x}_3\bar{x}_5 \\ &p_2=m_4+m_6=x_2\bar{x}_3x_4\bar{x}_5 \\ &p_3=m_4+m_7=\bar{x}_1x_2x_4\bar{x}_5 \\ &p_4=m_6+m_9=x_1x_2\bar{x}_3x_4 \\ &p_5=m_7+m_8=\bar{x}_1x_2x_3x_4 \\ &p_6=m_1+m_2+m_3+m_5=\bar{x}_1\bar{x}_3\bar{x}_4\end{align*} The primterm table is then the following:

View attachment 9291

We can delete the columns $m_2, m_3, m_5$ because of $m_1$. We can delete also the columns $m_4,m_9$ because of $m_6$. We can delete also the columns $m_7$ because of $m_8$.

Then the table looks as follows:

View attachment 9292

We can delete the rows $p_1$ and $p_3$ since these are empty. We can delete also the row $p_2$ because of $p_4$ and so we get:

View attachment 9293

Do we get from that that the primterms are $p_4, p_5, p_6$? Are these the essential prime implicants?

How do we get the disjunctive minimal form from that? Do the selected primary terms simply have to be linked by disjunction? (Wondering)

 

[I like Serena]

Hey!
We can delete the rows $p_1$ and $p_3$ since these are empty. We can delete also the row $p_2$ because of $p_4$ and so we get:

Hey mathmari!

Are you sure that we can delete $p_2$?
I think $p_2$ is an essential prime implicant as well. (Thinking)

Do we get from that that the primterms are $p_4, p_5, p_6$? Are these the essential prime implicants?

I believe the essential prime implicants are $p_2, p_4, p_5, p_6$. (Thinking)

How do we get the disjunctive minimal form from that? Do the selected primary terms simply have to be linked by disjunction?

Yes.
So I believe the disjunctive minimal form is:
$$p_2+p_4+p_5+p_6 = x_2\bar x_3 x_4 \bar x_5 + x_1 x_2 \bar x_3 x_4 + \bar x_1 x_2 x_3 x_4 + \bar x_1 \bar x_3 \bar x_4$$
And I'm afraid that if we leave out $p_2$, that we don't 'cover' the original expression. (Worried)

 

[I like Serena]

The Karnaugh map is:
View attachment 9294

The colored rectangles correspond to your primterms.
As you can see, we cannot leave out one of those rectangles, since otherwise not all 1's are covered. (Thinking)

 

[mathmari]

I read now some notes that I found to understand better the part of disjunctive minimal form.

From the last step of #1 we get the essential prime implicants $p_4, p_5, p_6$, or not?
(How do you get also $p_2$ ? Do we not delete either $p_2$ or $p_4$ ? )

From the remaining prime implicants we are looking for a minimal number of prime implicants, such that all minterms are covered.

At the primterm table we delete the rows of $p_4, p_5, p_6$ and the respective columns, that corresponds to the minterms that are covered, i.e. $m_1, m_2, m_3, m_5, m_6, m_7, m_8, m_9$.

The only minterm that is not covered is $m_4$. This is covered by either $p_1$ or $p_2$ or $p_3$.

Would that mean that there are $3$ different minimal disjunctive forms, which are the following:

• $$p_4\lor p_5\lor p_6\lor p_1$$
• $$p_4\lor p_5\lor p_6\lor p_2$$
• $$p_4\lor p_5\lor p_6\lor p_3$$

Is that correct? (Wondering)

 

[I like Serena]

Oh yes.
Those are indeed 3 different minimal disjunctive forms that cover the 1's exactly. (Nod)

 

[mathmari]

Oh yes.
Those are indeed 3 different minimal disjunctive forms that cover the 1's exactly. (Nod)

Ok! So is that the solution of the problem? (Wondering)

 

[I like Serena]

Ok! So is that the solution of the problem?

I can see that the version with $p_1$ corresponds to:
View attachment 9295

And the version with $p_3$ corresponds to:
View attachment 9296

I think these are indeed all the possibilities. (Nod)