Welcome to our community

Be a part of something great, join today!

Prime implicants and disjunctive minimal form

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
Hey!! :eek:

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.

Midterme.JPG

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:

Primtabelle.JPG

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:

Spalten.JPG

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:

zeilen.JPG

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)
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
Hey!! :eek:
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
The Karnaugh map is:
karnaugh5.png

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

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
Oh yes.
Those are indeed 3 different minimal disjunctive forms that cover the 1's exactly. (Nod)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,008

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
Ok! So is that the solution of the problem?
I can see that the version with $p_1$ corresponds to:
karnaugh5_with_p1.png

And the version with $p_3$ corresponds to:
karnaugh5_with_p3.png

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