Prime implicants and disjunctive minimal form

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Form Prime
In summary, the conversation discusses the method of Quine-McCluskey for determining prime implicants and finding a disjunctive minimal form for a given switching function. The conversation also covers the process of creating a primterm table and selecting essential prime implicants. The final solution involves three different minimal disjunctive forms that cover all 1's in the Karnaugh map.
  • #1
mathmari
Gold Member
MHB
5,049
7
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.

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)
 

Attachments

  • Midterme.JPG
    Midterme.JPG
    24 KB · Views: 85
  • Primtabelle.JPG
    Primtabelle.JPG
    11.8 KB · Views: 80
  • Spalten.JPG
    Spalten.JPG
    5.3 KB · Views: 84
  • zeilen.JPG
    zeilen.JPG
    3.6 KB · Views: 87
Last edited by a moderator:
Physics news on Phys.org
  • #2
mathmari said:
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)

mathmari said:
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)

mathmari said:
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)
 
  • #3
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)
 

Attachments

  • karnaugh5.png
    karnaugh5.png
    2.5 KB · Views: 74
  • #4
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)
 
  • #5
Oh yes.
Those are indeed 3 different minimal disjunctive forms that cover the 1's exactly. (Nod)
 
  • #6
Klaas van Aarsen said:
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)
 
  • #7
mathmari said:
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)
 

Attachments

  • karnaugh5_with_p1.png
    karnaugh5_with_p1.png
    2.6 KB · Views: 74
  • karnaugh5_with_p3.png
    karnaugh5_with_p3.png
    2.5 KB · Views: 67

FAQ: Prime implicants and disjunctive minimal form

1. What are prime implicants?

Prime implicants are the essential terms or combinations of terms in a Boolean function that cannot be further simplified or reduced.

2. How do you find prime implicants?

Prime implicants can be found by creating a Karnaugh map for the Boolean function and grouping together adjacent 1s until all possible combinations have been exhausted.

3. What is a disjunctive minimal form?

A disjunctive minimal form is the most simplified expression of a Boolean function, where all possible prime implicants have been included in the final expression.

4. How do you convert a Boolean function to its disjunctive minimal form?

To convert a Boolean function to its disjunctive minimal form, you must first find all the prime implicants and then combine them using the OR operator to create a single expression.

5. Why is finding the disjunctive minimal form important?

Finding the disjunctive minimal form allows for a more efficient representation of a Boolean function, making it easier to analyze and manipulate in logical operations.

Similar threads

Replies
22
Views
3K
Back
Top