1
$\begingroup$

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.

  • 0
    Are you sure the equation to be proved is typed correctly? Likewise with your list of theorems. (E.g the second-to-last one looks dubious to me, and in the last one, shouldn't x be X?) Also, like in usual high-school algebra, you can start with the LHS and try to manipulate it to get the RHS, or you could try to manipulate both sides, simplifying both until they become equal. (This is often easier if both sides are complicated.) Finally, to test with a truth table, you would try to show that the two sides are equal after assigning "TRUE" of "FALSE" to each of the variables independently.2010-10-23

2 Answers 2

1

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$

  • 0
    whatever we do $C'D'+A'C+AD$ is neither $0$, nor necessarily $B'$.2012-01-07
1

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
    addition and multiplications).

    I hope, now you can figure out what to do.

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

  3. Now start from the RHS and try to prove RHS=LHS. If you can't figure it out, let me know.


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*}