Boolean Algebra reduction

I have a few problems that I'm currently trying to reduce but can't seem to go any further. I have the answers from the back of the book but don't know the steps to get there.

Forgive me as I'm very new to this and don't know how to put the proper notation on a computer.

Problem 1 (Asked our professor about this one and he couldn't figure it out)

W = (A nand B) or (A nor C)

The book lists the answer as:

W = not(A) or not(B), C = not connected

I use DeMorgan's Theorem to get

W = (not(A) or not(B)) or (not(A) and not(C))

That's as far as I can get and I'm not seeing any place where I can apply the laws/rules to reduce it any further. I used a truth table for both the starting equation and the final answer the book gives and they are the same but I just don't see how we reduce any further than what I have.

cytosis said:

I have a few problems that I'm currently trying to reduce but can't seem to go any further. I have the answers from the back of the book but don't know the steps to get there.

Forgive me as I'm very new to this and don't know how to put the proper notation on a computer.

Problem 1 (Asked our professor about this one and he couldn't figure it out)

W = (A nand B) or (A nor C)

The book lists the answer as:

W = not(A) or not(B), C = not connected

I use DeMorgan's Theorem to get

W = (not(A) or not(B)) or (not(A) and not(C))

That's as far as I can get and I'm not seeing any place where I can apply the laws/rules to reduce it any further. I used a truth table for both the starting equation and the final answer the book gives and they are the same but I just don't see how we reduce any further than what I have.

Click to expand...

Hello cytosis. Welcome to the forum!

You are correct when you say that

(A nand b) or (A nor C)

is equivalent to

(not(A) or not(B)) or (not(A) and not(C))

However, you can rearrange the expression as follows:

(not(A) or (not(A) and not(C))) or (not(B))

The expression inside the bold parentheses takes the form X+XY, which is equal to simply "X" (one of the basic rules of boolean algebra). Therefore,

...X......OR......X...AND...Y.......
(not(A) or (not(A) and not(C)))

simply becomes not(A). Then, you still have your "OR not(B), so the final comes out to

(not(A)) or (not(B))

"C" (rather, not(C)) has no place in the equation, so it is the same as being "not connected".

Regards,
Matt

Okay it sort of makes sense and now I have more questions, lol. What rule or law is it that is X+XY = X. I can't really relate it to any of the laws in my book. Here is a picture of those laws.

http://www.flickr.com/photos/80081798@N08/8027169303/in/photostream

Also I guess I'm having trouble understanding that you can "invade" one term's parenthesis. To my understanding when using DeMorgan's Theorem you have to put parenthesis around the term you are breaking the bar over. I guess I can't see how we can swap the AC with the B. Here is a picture with the correct answer with your help but I'm still a little hazy how we got there.

http://www.flickr.com/photos/80081798@N08/8027168929/in/photostream

Let me know if the images don't show up, they should all be set to public viewing though.

cytosis said:

Okay it sort of makes sense and now I have more questions, lol. What rule or law is it that is X+XY = X. I can't really relate it to any of the laws in my book. Here is a picture of those laws.

http://www.flickr.com/photos/80081798@N08/8027169303/in/photostream

Also I guess I'm having trouble understanding that you can "invade" one term's parenthesis. To my understanding when using DeMorgan's Theorem you have to put parenthesis around the term you are breaking the bar over. I guess I can't see how we can swap the AC with the B. Here is a picture with the correct answer with your help but I'm still a little hazy how we got there.

http://www.flickr.com/photos/80081798@N08/8027168929/in/photostream

Let me know if the images don't show up, they should all be set to public viewing though.

Click to expand...

X+XY (read X or X AND Y) is set up so that a boolean expression can be put in for "X" and one can be put in for "Y". I'll show you how you get X from X+XY first. Since your book uses A and B, I'll put it in the form A+AB.

Okay, so first let's break up the terms. According to Rule #2 in your book, A*1=A. Therefore, A=A*1. So let's put that in for the single A term:

(A*1)+AB

You can use Law #3 in your book to change that to

A(1+B)

(You distribute, and "factor"). From there, you use Rule #4 to take out the 1+B. You know that 1+ANYTHING equals 1, so you get:

A(1)

A AND 1 is simply A. So that is where we get the "rule" that A+AB = A.

Now, when you have A+B, that is the same thing as B+A (Law #1). Therefore, if you have three expressions, separated by "OR"s, you can put them in any order. I moved the (not(B)) to the far right earlier just so you would be able to see the X+XY format of the other two OR equations. Since not(A)not(C) was the X term, and not(A), not(B), and not(A)not(C) were all separated by "OR" symbols, they can be arranged into any order.

I think where your confusion is coming from is the A/B/C vs. X/Y/Z. I use A, B, and C for inputs, and X, Y, and Z for variables. You can put any combination of A/B/Cs in for X, and the same for Y and Z.

Have I lost you yet?

Okay I think I got it. I guess I was just thinking you needed parenthesis and that the "not(a) or not(b)" was 1 term. As for the proof of A+AB, that makes clear sense.

cytosis said:

Okay I think I got it. I guess I was just thinking you needed parenthesis and that the "not(a) or not(b)" was 1 term. As for the proof of A+AB, that makes clear sense.

Click to expand...

Glad to hear you were able to follow that mess

(not(a) or not(b)) or (not(c)) is the same as not(a) or not(b) or not(c). It's the same as with regular math, in this sense. (1+2)+3 gives the same answer as 1+2+3.

So you're set then? Any other questions?

For an intuitive feel for why A+AB = A, consider that if AB is true, then that requires that A be true. But if A is true, then it doesn't matter whether AB is true or not. Similarly, if A is false, then AB must also be false, regardless of what B is.

I'm concerned that your instructor couldn't work this problem. Admittedly, these types of questions are a bit tricky (and downright baffling for many, if not most, people new to the subject). But if your instructor is that new to the subject, then what are they doing being the instructor? Now, we have to allow that anyone can have a brain fart and be stumped by a problem that they could have solved easily that morning and that the solution will come to them five minutes after they walk away. Also, it's always possible that they got tasked to teach this course will little notice and are simply rusty with some of the subtleties of the fundamentals.

Note that the answer can be "simplified" a bit futher:

not(A) or not(B)

is the same as

(A nand B).

This is assuming that your are allowed to use gates other than AND, OR and NOT in your reductions.

In general, when asked to "simplify" or "reduce" a logic expression, the correct answer is "it depends"; They really need to define the metrics by which alternative solutions are to be judged, as there simply aren't any reasonable ones that can be implicitly assumed. For instance, the book's solution -- if implemented in CMOS -- will take ten transistors while the alternatice solution I offered will take four transistors and be three times faster.

WBahn said:

Note that the answer can be "simplified" a bit futher

Click to expand...

I believe the simplification was to eliminate any NAND or NOR operations, and was to break it down into its simplest parts. That tends to be what textbooks ask for nowadays.