# Prime implicants and disjunctive minimal form

#### mathmari

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

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:

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:

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:

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?

Last edited:

#### Klaas van Aarsen

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

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

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.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
The Karnaugh map is:

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.

#### mathmari

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

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Oh yes.
Those are indeed 3 different minimal disjunctive forms that cover the 1's exactly.

#### mathmari

##### Well-known member
MHB Site Helper
Oh yes.
Those are indeed 3 different minimal disjunctive forms that cover the 1's exactly.
Ok! So is that the solution of the problem?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Ok! So is that the solution of the problem?
I can see that the version with $p_1$ corresponds to:

And the version with $p_3$ corresponds to:

I think these are indeed all the possibilities.