0
\$\begingroup\$

So im re-learning a bit of computer architecture/boolean algebra (For the nand2tetris coursera course).

Watching some videos on it one of the problems presented was: F=AB+A′C+BC

The explanation provided was:

  1. =AB+A′C+BC(A+A′)
  2. =AB+A′C+ABC+A′BC
  3. =AB+ABC+A′C+A′BC
  4. =AB(1+C)+A′C(1+B)
  5. =AB+A′C

So I understand that 1 = A+A` (Although im still a bit confused about where/when you decide to randomly toss that in. I understand up to the point of: =AB(1+C)+A′C(1+B)

Where exactly is the 1+C and 1+B coming from? My best guess is the ABC is being moved to be closer to AB (at the beginning) and then doing...something i've not come across yet? It looks like maybe a distributive law......but where is the 1 coming from?

To me this would look like x=AB and then X+X.X+C which would be X+C so AB+C (Not sure where the 1 is coming from in (1+C)

Can anyone explain the steps? Also as a side question: I read that boolean algebra problems are something that you can't really have a computer solve and just sorta takes experience looking at a lot of them? So I hope it gets easier as I look at more.

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

Where exactly is the 1+C and 1+B coming from?

AB + ABC    =    AB.1 + AB.C    =    AB.(1 + C)

A′C + A′BC  =   A′C.1 + A′C.B   =    A′C,(1 + B)
\$\endgroup\$
6
  • \$\begingroup\$ I guess im not familiar what rule where you can just add an .1 on? I know A.1 always equals A. But how would you intuitively know to just do this I guess? \$\endgroup\$
    – msmith1114
    Commented May 3 at 13:35
  • \$\begingroup\$ Regard it as a multiplication by 1 @msmith1114 <-- if I added 1 on it would make it different. Have you studied Karnaugh maps yet? \$\endgroup\$
    – Andy aka
    Commented May 3 at 13:36
  • \$\begingroup\$ Not yet, im more curious about when the intuition is to add an and 1 onto something is the main issue im running into now. Is figuring out WHEN to do something that isn't so obvious. \$\endgroup\$
    – msmith1114
    Commented May 3 at 13:45
  • \$\begingroup\$ @msmith1114 I think learning about Karnaugh maps will provide you with a bit more intuition. Step 1 is the tricky one. \$\endgroup\$
    – Andy aka
    Commented May 3 at 13:52
  • \$\begingroup\$ Step 1 in the original example? \$\endgroup\$
    – msmith1114
    Commented May 3 at 14:21
2
\$\begingroup\$

There are a couple of intuitive approaches, only in the sense of whether or not you consider the brute force expansion of all the terms as being intuitive.

the logic cube (or hypercube)

But before doing that, let's look at the cube:

\$\quad\quad\$enter image description here

Just to get oriented to the above cube, \$A=0\$ corresponds to the top face, \$A=1\$ to the bottom face, \$B=0\$ to the left side face, \$B=1\$ to the right side face, and \$C=0\$ to the front face and \$C=1\$ to the back face (back face of the cube is odd and the front face is even.)

I've identified the "1" values with red dots. From this perspective, it's very easy to see half the cube vertices are occupied and that there are three line segments:

  1. intersection of back face (\$C=1\$) and top face (\$A=0\$); and,
  2. intersection of back face (\$C=1\$) and right side face (\$B=1\$); and,
  3. intersection of bottom face (\$A=1\$) and right side face (\$B=1\$.)

On the face of it (pun intended), that would seem to then just be \$\overline{A}C+BC+AB\$. But you should also be able quickly see that only two of these line segments are really needed. #2 isn't needed, since #1 and #3 already cover all the red dots. There's no need for #2! It doesn't cover any red dots that haven't already been covered by #1 and #3.

So the simplified logic must be \$\overline{A}C+AB\$.

There is some intuition to be found here. The line segment we did not need was the one that connected between the other two line segments. So it must be that logic simplification includes some idea of overlapping coverage and that finding terms to be removed would be well-served by finding those parts that connect other regions, as they are more likely to be removable.

Or, conversely, that if you can identify regions that appear more isolated (disconnected from the rest) then those regions (segments, faces, cubes, and so on) are more likely to stick around and be needed. Fully disconnected regions clearly must be included, as they cannot be covered by other regions.

And this suggests another viewpoint, that of inverting the cube (hypercube, perhaps?) sense so that you use red dots for the '0' values instead of the '1' values. Often as not, this new viewpoint is as easy or easier to solve than its converse.

That's just to get some intuition for a moment. The above expands into hypercubes of dimension N and in finding N-1 hypercubes where all their vertices are occupied by "1". If none of those, then in finding N-2 hypercubes where all their vertices are occupied by "1". Etc. And when those are found, to observe or look for those N-M hypercubes that appear to connect others that are disconnected.

k-maps

Putting this into a k-map gives:

\$\quad\quad\quad\quad\$enter image description here

And here the goal is to find the largest circles you can make and to eliminate the ones that just duplicate coverage.

For example, here's the fuller k-map with all three edges from the above hypercube circled:

\$\quad\quad\quad\quad\$enter image description here

But one of those edges is obviously not needed.

brute force algebra

Let's get back to brute force in this case. I'll start by simply listing out all the red dots. No short cuts here. Just a brute force expansion of the logic:

$$\begin{align*} F&=\overline{A}\,\overline{B}\,C+\overline{A}\,B\,C+A\,B\,\overline{C}+A\,B\,C \\\\ &=\overline{A}\,\overline{B}\,C+\overline{A}\,B\,C+A\,B\left(\overline{C}+C\right) \\\\ &=\overline{A}\left(\overline{B}+B\right)C+A\,B\,\left(\overline{C}+C\right) \\\\ &=\overline{A}\,C+A\,B \end{align*}$$

You already understand that \$\overline{A}+A=1\$. So I'm sure you can follow the above, well.

Often times, it helps to just expand the logic expression so that all of the terms are exposed in their fuller glory. You can then look for these simplifications more easily, from an algebraic point of view.

Take note that their explanation was completely unnecessary. And, in fact, the long way around the barn. Simply expanding out all the terms and collecting them at two places was easier to see and took fewer steps.

So one more thing you should realize from this is that you don't have to agree with someone else's approach. And you don't have to produce it. If you see better another way, then use what works better for you. That's part of the process of developing intuition. And your intuition doesn't have to be the same as that of others!! There isn't only one way.

Tattoo that on your arm so you don't forget it.

summary

Keep in mind that there's no magic formula. A great deal of effort and thought has gone into the process of logic minimization and even the well-known Espresso process is, itself, imperfect. It will find results that are demonstrably not the best minimization. But it mostly works.

K-maps help. Algebra helps. Hypercubes help. Learning all these ways to see, give you more intuition over time. There is no magic wand to it. But if you spend some time, many things will become much clearer to you.

leaving you with a problem

Inspect the following \$N=5\$ hypercube:

enter image description here

(Keep in mind that each vertex of the left 4D hypercube connect by a single line to their corresponding vertex on the right 4D hypercube. I didn't draw in that line because the image gets a bit busy when I try that. You just need to keep it in mind.)

The minimization here involves four faces (no 3D cubes or 4D hypercubes) plus one line segment. Can you find them?

As a clue, can you see a relatively isolated line segment somewhere?

final notes

I hope the above gives you some idea of how to develop your intuition.

(Neemann's Digital was used in the production of some of the above images.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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