How Does $AB{\sim} C + {\sim}ABC + {\sim} A {\sim}B{\sim} C$ Turn into $(A+C+{\sim}B)(B+{\sim}A)(B+{\sim} C)({\sim} A+{\sim} C)$?

Question

I'm trying to figure out this Boolean algebra question and I cannot for the life of me figure it out. I know that the answer is $(A+C+{\sim} B)(B+{\sim}A)(B+{\sim} C)({\sim} A+ {\sim} C)$ but I can't find the steps to take it there from the original question of AB∼C+∼ABC+∼A∼B∼C.

Figured I would see if any of you knew.

Thanks

Answer 1

Attack the problem from the right side.

The distributive law is $(X + Y) Z = XZ + YZ$

Apply this law to $(A+C+{\sim}B)(B+∼A)(B+{\sim}C)(∼A+{\sim}C)$ until you can no longer. You will end up with a very long expression of the form $ABB{\sim}A + A{\sim}AB{\sim}A + ... + {\sim}B{\sim}A{\sim}C{\sim}C$

Then simplify that using the laws:

• $X{\sim}X = 0$
• $X + X = X$
• $XX = X$
• $0 + X = X$
• $0 X = 0$
• $XY = YX$
• $X + Y = Y + X$

and what will come out the other end is the left expression.

If you want to go from the left expression to the right expression, well, now you've got a set of steps that goes from right to left, so just reverse it.

Answer 2

Do you remember FOIL from algebra when dealing with numbers? It's that:

$$(a+b)(c+d)=ac+ad+bc+bd$$

Well, the same holds in a Boolean algebra. Moreover, it generalizes:

$$(a+b)(c+d+e)=ac+ad+ae+bc+bd+be$$

See how that works? You just multiply one variable from the one term with each one of the variables from the other term.

Notice how we can apply this to the first two terms of your RHS (right hand side):

$$(A + C +B')(B+A')=AB+AA'+CB+CA'+B'B+B'A'$$

(p.s. when working with $+$ and $\cdot$, I much prefer working with $P'$ for negation rather than ~)

Now, as Eric indicated, at this point you can simplify:

$$AB+AA'+CB+CA'+B'B+B'A'$$

$$=AB+0+CB+CA'+0+ B'A'$$

$$=AB+CB+CA'+B'A'$$

Ok, now multiply this with $B+C'$, again canceling any term where you get a variable and its negation ... and then with $A'+C'$

Now, it also holds that:

$$(a+b)(c+d)(e+f)=ace+acf+ade+adf+bce+bcf+bde+bdf$$

Again, see how that works? You multiply each one variable from each one of the terms with each other: you get each possible combination.

So, you could have done something like this in one big ass huge step as well, starting with your RHS: you would have gotten $3\cdot 2\cdot 2 \cdot 2=24$ terms .... but all that would simplify to just the three terms from your LHS.

Now, you asked whether you couldn't start with the LHS and end up with the HS. Well, first of all, if you can figure out how to go from the RHS to the LHS, then you can just reverse that process to go from LHS to RHS, since they are all equivalences.

However, you can also do this. As it turns out, in Boolean algebra it also holds that:

$$ab+cd=(a+c)(a+d)(b+c)(b+d)$$

This is a little less intuitive, because this of course isn't true for numbers (which is why both Eric and I recommended going from RHS to LHS), but again, in a boolean algebra it does hold true, and so you could start with your LHS and do this:

$$ABC'+A'BC+A'B'C'=(A+A'+A')(A+A'+B')(A+A'+C')(A+B+A) ....$$

And so now you would have gotten $3 \cdot 3 \cdot 3 =27$ terms, but this time you have that $A + A'=1$, and so any term with a variable and its negation disappears ... and you should end up with just the $4$ terms of your RHS.