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
    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`?2010-10-22
  • 0
    What is LHS and RHS? This is a digital logic class. theorems like X + 0 = X2010-10-22
  • 0
    @Corey: "left hand" and "right hand" sides. :)2010-10-22
  • 0
    Then indeed you should be reading the relations like "`(condition) OR (FALSE)` is `condition`" for the first one.2010-10-22
  • 0
    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.2010-10-22
  • 0
    I am confused about LHS and RHS. do i have to work both sides? do they have to equal eachother? Do i work the left side to make it equal the right side thats there now?2010-10-22
  • 0
    Also, all the theorems are two variables this problem is 3 so that throws me off big time..2010-10-22
  • 0
    Another thing: even before you begin the symbolic manipulations, it might help to construct a truth table first.2010-10-22
  • 0
    I dont understand a truth table for a 3 variable logic function. I understand AND, OR, NOT truth tables.2010-10-22
  • 0
    would i construct a truth tables with all zeros except for NOTS?2010-10-22
  • 0
    Well, it would help you to know that you can take eight triples from the set `{TRUE,FALSE}`, e.g. `(TRUE,FALSE,TRUE)`.2010-10-22
  • 0
    What do you mean TRUE, FALSE? 1 = true, zero = false? "you can take eight triples from the set" i have no idea what you are talking about?2010-10-22
  • 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*}$