2

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.

Mark Fischler
  • 41,743
  • is there any typo in your fomula? please note that it only differs in $B \cdot C = A' C$. – RGS Nov 10 '16 at 16:51
  • Definitely no typo - just triple checked from a Sample Exam I'm working through. That threw me off too. –  Nov 10 '16 at 16:56
  • is there any known relation between $A, A', B, B', C$ or $C'$? Because if there is none, I suspect that is very false. – RGS Nov 10 '16 at 16:58
  • @RSerrao I just worked this numerically on paper. This works, and the statement is not false. – DBPriGuy Nov 10 '16 at 16:59
  • 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. –  Nov 10 '16 at 17:00
  • Hint: try the absorption property. I think I may have it, give me a few – DBPriGuy Nov 10 '16 at 17:04
  • Notice that $A \cdot B + A' \cdot B' = A \cdot B + A' \cdot B'$ is **always true. So if $B' \not = C$ your statement is false – RGS Nov 10 '16 at 17:10

2 Answers2

2

$$\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.

Mark Fischler
  • 41,743
  • 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? –  Nov 10 '16 at 17:56
  • 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? –  Nov 10 '16 at 18:01
  • Yes, in general $(X+X\cdot C) = X$. – Mark Fischler Nov 10 '16 at 18:22
1

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.

DBPriGuy
  • 183
  • 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? –  Nov 10 '16 at 17:58
  • 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) – Bram28 Nov 10 '16 at 18:21
  • @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 – DBPriGuy Nov 10 '16 at 18:46