# boolean algebra - theorems

I have a homework question "Show the following is true using theorems. State which theorem you use at each step." This is just one of many problems I have! So, if you can help me with this one problem than I can apply what I learn to finish the rest. I don't want a handout; I just don't know where to start or what to do. I have looked through the different theorems in the book and I don't see how any would apply to this! Am i suppose to prove that the first part = the second?

$$A'BD' + BCD + ABC' + AB'D =\\ A'BD' + BCD + ABC' + AB'D + BC'D' + A'BC + ABD$$

Should I group two or more and work from there? Since, we are only working with '+' then I should only need these types of theorems?

I have a book that shows the different theorems. But it still doesn't help me tackle this problem. Are we to prove how the first part equals the second part? To me that's expanding and not reducing.

I can work either side i guess whichever is easier..

Here is a list of theorems the book provides \begin{align} & X + 0 = X&&\\ & X + 1 = 1&&\\ & X + X = X&&\\ & X + X' = 1&&\\ & X + Y = Y + X&&\\ & (X + Y) + Z = X +(Y + Z)&&\\ & X \times (X + Y) = X&&\\ & X \times Y + X \times Y' = X&& \end{align}

these are most of them. there are a few others.. The book i am using is digital logic - principles and practices.

-
Turning the LHS to the RHS or vice-versa should work. Now, what book is this that has your "list of theorems"? Is $'$ here NOT and $+$ OR? – J. M. Oct 22 '10 at 0:54
What is LHS and RHS? This is a digital logic class. theorems like X + 0 = X – Corey J Mattis Oct 22 '10 at 0:57
@Corey: "left hand" and "right hand" sides. :) – J. M. Oct 22 '10 at 1:04
Then indeed you should be reading the relations like "(condition) OR (FALSE) is condition" for the first one. – J. M. Oct 22 '10 at 1:06
So on the RHS you have ABC' + ABD. You probably have a distributive law like (X times Y) + (X times Z) = X times (Y + Z) so you can replace this pair (after bringing them together using your X+Y=Y+X. No guarantee this is the right start, but it is the sort of thing you want to do. Try to bring the two sides together. By the way, you probably need a + between AB'D and BC'D on the RHS. – Ross Millikan Oct 22 '10 at 1:40

Let's denote disjunctive form of the left hand side as $f_L$ and disjunctive form of the right hand side as $f_R$ .Note that we can write following:

$f_R=f_L+(BC'D'+A'BC+ABD)=f_L+B(C'D'+A'C+AD)=$

$=f_L+B(C'D'(A+A')+A'C(D+D')+AD(C+C')=$

$=f_L+B(AC'D'+A'C'D'+A'CD+A'CD'+ACD+AC'D)=$

$=f_L+B(AC'(D+D')+CD(A+A')+A'D'(C'+C))=$

$=f_L+B(AC'0+CD0+A'D'0)=$

$=f_L+B(0+0+0)=$

$=f_L+B0=$

$=f_L+0=f_L$

-
whatever we do $C'D'+A'C+AD$ is neither $0$, nor necessarily $B'$. – Tapu Jan 7 '12 at 19:12

Before answering your question I wish to mention the following 3 points for clarification:

1. By Show the following is true using theorems..." you are meant to show that the expression on left hand side is equal to the expression on right hand side, which is usually called (for brevity) LHS=RHS.

To show the equality you can start from any side (i.e., with the LHS or RHS),
which is convenient to you. For example, if you are to show $(x+1)^2=x^2+2x+1$, you can start with LHS as

$\begin{eqnarray*}\text{LHS}&=&(x+1)^2\\&=&(x+1).(x+1)\text{[by the definition of square]}\\&=&(x+1).x+(x+1).1\text{ [.' is distributive over +']}\\&=&x^2+x+x+1\text{ [.' is distributive over +']}\\&=&x^2+2x+1\\&=&\text{RHS} \end{eqnarray*}$

Note that the explanation within [ ] are the basic theorems (here properties of
2. Your book should have similar formulas for multiplication `.' (e.g., $x.y=y.x$ etc). If you can't remember it, here is a hint substitute $(+,0,1)$ by $(.,1,0)$ in the formulas you have already written. As an example, your first formula becomes $x.1=x$.
EDIT (answer, partly using @pedja's method): $\begin{eqnarray*}\text{RHS}&=&A'BD' + BCD + ABC' + AB'D + BC'D' + A'BC + ABD\\&=&B(A'D'+CD+AC'+\underbrace{C'D'+A'C+AD})+A'BD'\text{ [rearranging the terms]}\\&=&B(A'D'+CD+AC')+B\left\{C'D'(A+A')+A'C(D+D')+AD(C+C')\right\}\\&~&+A'BD'\text{ [using } x.1=x \text{ and } x+x'=1\text{]}\\&=&B(A'D'+CD+AC')+B\left\{AC'D'+A'C'D'+A'CD+A'CD'+ACD+AC'D\right\}\\&~&+A'BD'\text{ [using distributive property of . over + and rearranging]}\\&=&B(A'D'+CD+AC')+B\left\{A'D'(C'+C)+CD(A+A')+AC'(D+D')\right\}\\&~&+A'BD'\\&=&\underbrace{B(A'D'+CD+AC')}+\underbrace{B(A'D'+CD+AC')}+A'BD'\text{ [using } x+x'=1 \text{ and }x.1=x \text{]}\\&=&B(A'D'+CD+AC')+A'BD'\text{ [using }x+x=x\text{]} \\&=&A'BD' + BCD + ABC' + AB'D \text{ [multiplying and rearranging]}\\&=&\text{LHS} \end{eqnarray*}$