0
\$\begingroup\$

I am struggling to convert the sum of maxterms:

((¬b ∧ ¬d) ∨ ((b ∧ (¬c ∧ d)) ∨ (¬a ∧ (b ∧ d))))

into a product of minterms.

I use Morgan and get this:

((¬b ∨ ¬d) ∧ ((b ∨ (¬c ∨ d)) ∧ (¬a ∨ (b ∨ d))))

which doesn't have an equivalent truth table. (btw, this is a very handy site that is helping me http://web.stanford.edu/class/cs103/tools/truth-table-tool/ )

I know drawing Karnaugh's make it easier to visualize, but I wanted to learn how to do the conversion algebrically, just using Morgan and distribution laws. Any good soul to enlight me on this puzzle?

thank you really much and sorry for the dumb question!

Martin

\$\endgroup\$
  • \$\begingroup\$ Why do it the hard way? \$\endgroup\$ – Sunnyskyguy EE75 Mar 10 '18 at 19:21
  • 1
    \$\begingroup\$ I wanna check if algebra really works :) \$\endgroup\$ – Martin Horst Mar 10 '18 at 19:37
  • \$\begingroup\$ @MartinHorst It does. Do you have any starting attempts? \$\endgroup\$ – jonk Mar 10 '18 at 19:54
  • \$\begingroup\$ Laws of Logic are irrefutable, yet many people don't know there are 144 fallacies dfined by Aristotle and Plato ( bad logic) Just be careful with your math on distribution together with de Morgan's Law. Boolean didn't invent logic he just made it simple with math symbols. I have never used your symbols however. ¬ ∧ v \$\endgroup\$ – Sunnyskyguy EE75 Mar 10 '18 at 19:54
  • \$\begingroup\$ Arghhh, that notation makes my eyes bleed! Where are pluses and dots and overbars?!? :-D @TonyStewart: those are the symbols used by mathematicians (who love doing it the hard way)! :-) \$\endgroup\$ – Lorenzo Donati Mar 10 '18 at 20:45
3
\$\begingroup\$

Start as follows:

$$\begin{align*} \overline{b}\:\overline{d} + b\: d\: \overline{c} + b\: d\: \overline{a}\tag{1}\\\\ \overline{\overline{\overline{b}\:\overline{d} + b\: d\: \overline{c} + b\: d\: \overline{a}}}\tag{2}\\\\ \overline{\overline{\overline{b}\:\overline{d}} \cdot \overline{b\: d\: \overline{c}} \cdot \overline{b\: d\: \overline{a}}}\tag{3}\\\\ \overline{(b+d) \cdot (\overline{b}+ \overline{d}+ c) \cdot (\overline{b}+ \overline{d}+ a)}\tag{4}\\\\ \overline{(b\:\overline{b}+ b\:\overline{d}+ b\:c+d\:\overline{b}+ d\:\overline{d}+ d\:c) \cdot (\overline{b}+ \overline{d}+ a)}\tag{5}\\\\ \overline{(b\:\overline{d}+ b\:c+d\:\overline{b}+ d\:c) \cdot (\overline{b}+ \overline{d}+ a)}\tag{6}\\\\ \overline{\overline{b}\:d+ \overline{b}\:d\:c+b\:\overline{d}+ \overline{d}\:b\:c+ a\:b\:\overline{d}+ a\:b\:c+a\:d\:\overline{b}+ a\:d\:c}\tag{7}\\\\ \overline{\overline{b}\:d+b\:\overline{d}+ c(\overline{b}\:d+ \overline{d}\:b)+ a(b\:\overline{d}+d\:\overline{b}+ b\:c+ d\:c)}\tag{8}\\\\ \overline{\overline{b}\:d+b\:\overline{d}+ a\:c(b+ d)}\tag{9} \end{align*}$$


NOTE

The last, going from (8) to (9) above, can be handled several ways. Rather than belabor things with algebra, I'll just explain in words.

It's pretty easy to see that if \$\overline{b}\:d+b\:\overline{d}\$ is true or false, then \$c(\overline{b}\:d+ \overline{d}\:b)\$ is irrelevant. If \$c\$ is false, then the earlier term \$\overline{b}\:d+b\:\overline{d}\$ still over-rides. And if \$c\$ is true, all it does is permit the additional factor \$\overline{b}\:d+b\:\overline{d}\$ to express itself. But it already has done so. So \$c(\overline{b}\:d+ \overline{d}\:b)\$ is entirely redundant. It can be removed. I could write this algebraically, adding opposite conditions and then simplifying, but I think these words are sufficent to get the point across.

A similar argument also says that the same terms, \$\overline{b}\:d+b\:\overline{d}\$, that are inside of \$ a(b\:\overline{d}+d\:\overline{b}+ b\:c+ d\:c) \$ are equally pointless and can be removed, reducing it down nicely.


At this point, there are two completely equivalent statements in (9) above. You can choose either one of them:

$$\begin{align*} \overline{\overline{b}\:d+b\:\overline{d}+ a\:b\:c}&=\overline{\overline{b}\:d+b\:\overline{d}+ a\:c\: d}\tag{10} \end{align*}$$

The reason should be obvious. Examine \$\overline{b}\:d+b\:\overline{d}+ a\:c(b+ d)\$. If \$b\$ is false and \$d\$ is true, then the first term picks that up. If \$b\$ is true and \$d\$ is false, then the second term picks that up. So the only way that matters for the third term is when either \$b\$ or \$d\$ is true. But none of this matters unless both of the first two terms are false. And the only remaining possibility is that if one of \$b\$ or \$d\$ is true, then the other must also be true. So you can neglect either one of them; your choice. Hence, (10) must be a true statement.

So I'll pick the left side now:

$$\begin{align*} \overline{\overline{b}\:d+b\:\overline{d}+ a\:b\:c}\tag{11}\\\\ (b+\overline{d})\cdot (\overline{b}+d)\cdot (\overline{a}+\overline{b}+\overline{c})\tag{12} \end{align*}$$

But you could just as well have picked the right side.

Algebra works.

Ask questions if you have any about the above process. I did a few things that you may consider "subtle" but are easily explained.

\$\endgroup\$
  • \$\begingroup\$ nice formatting \$\endgroup\$ – Sunnyskyguy EE75 Mar 10 '18 at 21:20
  • \$\begingroup\$ nice formatting! how did you do it? \$\endgroup\$ – Martin Horst Mar 12 '18 at 19:08
  • \$\begingroup\$ by the way: lines 5 and 6 are swapped. thank you so much for taking your time to solve this, now I got familiar with factoring boolean algebra :) \$\endgroup\$ – Martin Horst Mar 12 '18 at 19:10
  • \$\begingroup\$ would you please explain what was the simplification from lines 8 to 9? thanks in advance! \$\endgroup\$ – Martin Horst Mar 12 '18 at 19:18
  • \$\begingroup\$ @MartinHorst Sure. I'll update the answer. And no, lines 5 and 6 aren't swapped. They are in the order I wanted. \$\endgroup\$ – jonk Mar 12 '18 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.