Having trouble showing the following relation:

$$A\cdot B + A'\cdot B' + B\cdot C = A\cdot B + A'\cdot B' + A'\cdot C $$ using Boolean Algebra. Any help is appreciated.

  • $\begingroup$ is there any typo in your fomula? please note that it only differs in $B \cdot C = A' C$. $\endgroup$ – RGS Nov 10 '16 at 16:51
  • $\begingroup$ Definitely no typo - just triple checked from a Sample Exam I'm working through. That threw me off too. $\endgroup$ – jamesmbcn Nov 10 '16 at 16:56
  • $\begingroup$ is there any known relation between $A, A', B, B', C$ or $C'$? Because if there is none, I suspect that is very false. $\endgroup$ – RGS Nov 10 '16 at 16:58
  • $\begingroup$ @RSerrao I just worked this numerically on paper. This works, and the statement is not false. $\endgroup$ – DBPriGuy Nov 10 '16 at 16:59
  • $\begingroup$ No relation given - just asked to prove it using Boolean Algebra or Perfect Induction. Induction isn't difficult, but I wasn't able to manage to show it using Algebra and hoping someone could help. $\endgroup$ – jamesmbcn Nov 10 '16 at 17:00

$$\begin{array}{rcl}(A+A')=1 &\mbox{ and } &(B+B')=1 \\ (A+A')\cdot(B+B')=1& \implies &(A\cdot B + A\cdot B' + A'\cdot B + A'\cdot B') =1\\ A\cdot B + A'\cdot B' +B\cdot C &=& (A\cdot B + A\cdot B' + A'\cdot B + A'\cdot B') \cdot (A\cdot B + A'\cdot B' +B\cdot C)\\ &=&(A\cdot B +0+A\cdot B\cdot C)+(0+0+0) \\ &&+ (0+0+A'\cdot B\cdot C) + (0+A'\cdot B' + 0)\\ &=& A\cdot B + A'\cdot B\cdot C + A'\cdot B' \\ &=& A\cdot B + A'\cdot( B\cdot C + B') \\ &=& A\cdot B + A'\cdot( C+B') \\ &=& A\cdot B + A'\cdot C + A'\cdot B'\\ A\cdot B + A'\cdot B' +A'\cdot C &=& (A\cdot B + A\cdot B' + A'\cdot B + A'\cdot B') \cdot (A\cdot B + A'\cdot B' +A'\cdot C)\\ &=&(A\cdot B +0+0)+(0+0+0) \\ &&+ (0+0+A'\cdot B\cdot C) + (0+A'\cdot B' + A'\cdot B'\cdot C)\\ &=& A\cdot B + A'\cdot (B'+B)\cdot C + A'\cdot B'\\ &=& A\cdot B + A'\cdot C + A'\cdot B'\\ \end{array} $$ And since they are both equal to $A\cdot B + A'\cdot C + A'\cdot B'$ they are equal to each other.

I have used, in the first half of this proof, $$ B\cdot C + B' = C+B' $$ which is much easier to prove if you don't already have it as a lemma.

  • $\begingroup$ Thanks for the help! Just one question - how did you simplify $A\cdot B\cdot C + A'\cdot B\cdot C$ to just $A'\cdot B\cdot C$ in your 4th line of working? $\endgroup$ – jamesmbcn Nov 10 '16 at 17:56
  • $\begingroup$ Actually I think I might understand - if $A\cdot B$ is on then the output is also on regardless of whether $A\cdot B\cdot C$ is on or not. Thus because the second term requires A and B to be on it is made redundant by the first term and we can ignore it. Is this the idea? $\endgroup$ – jamesmbcn Nov 10 '16 at 18:01
  • $\begingroup$ Yes, in general $(X+X\cdot C) = X$. $\endgroup$ – Mark Fischler Nov 10 '16 at 18:22

Okay, the thing with Boolean Algebra is, that sometimes it gets messier before it gets cleaner.

We start with:

$$A\cdot B + A'\cdot B' + B\cdot C$$

Note that the following is true in general:

$$A\cdot B = A\cdot B \cdot C + A \cdot B \cdot C'$$

So, with the starting expression:

$$A\cdot B + A'\cdot B' + B\cdot C = A\cdot B \cdot C + A \cdot B \cdot C' + A'\cdot B' \cdot C + A' \cdot B' \cdot C' + A\cdot B \cdot C + A' \cdot B \cdot C$$

If you do your reduction right from here, you should be able to prove the relation.

This is because:

$$A' \cdot B' \cdot C + A' \cdot B \cdot C = A' \cdot C$$

as per the inverse property.

  • $\begingroup$ Thanks a ton - that's a pretty neat 'trick' if you can call it that actually, I'll make a note of remembering it haha. I got to the point: $A\cdot B + A'\cdot C + (A+B+C)' + A\cdot B\cdot C$ but am not sure how to continue from here; any suggestions? $\endgroup$ – jamesmbcn Nov 10 '16 at 17:58
  • $\begingroup$ From what you have: $A \cdot B + A' \cdot C + (A + B + C)' + A \cdot B \cdot C = A \cdot B + A' \cdot B \cdot C + A' \cdot B' \cdot C + A' \cdot B' \cdot C' + A \cdot B \cdot C = A \cdot B + A' \cdot B' \cdot C + A' \cdot B' \cdot C' + A \cdot B \cdot C + A' \cdot B \cdot C = A \cdot B + A' \cdot B' + B \cdot C$ (again, using that 'trick', which is called Adjacency) $\endgroup$ – Bram28 Nov 10 '16 at 18:21
  • $\begingroup$ @jamesmbcn No need to use DeMorgan. Also, remember that $$A \cdot B + A\cdot B \cdot C = A \cdot B$$ since $$A \cdot B$$ encompasses the latter. Let me know if you are still stuck, and I can post the full solution $\endgroup$ – DBPriGuy Nov 10 '16 at 18:46

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.