Boolean Algebra simplification

Discussion in 'Homework Help' started by pixel1, Apr 13, 2013.

  1. pixel1

    Thread Starter New Member

    Apr 13, 2013
    4
    0
    Hi all,

    I'm trying to work out what working is required to get from this 9 term expression:

    A'BC'D + A'BCD' + A'BCD + AB'C'D + ABC'D + AB'CD' + AB'CD + ABCD' + ABCD

    to this term:

    AC + AD + BC + BD

    In my attempts, I have been able to reduce it down to BD + AC + ABCD but I'm not sure how to split up the 4 variable term into AD + BC.

    From the start, I cancelled out the 1st term with the 6th, and the 2nd term with the 4th leaving me with: A'BCD + ABC'D + AB'CD + ABCD' + ABCD

    In the new expression with 5 terms, I was able to reduce down A'BCD + ABC'D to BD and AB'CD + ABCD' to AC. Unfortunately I'm still left with ABCD at the end so am wondering what rule(s) of algebra I might be missing :rolleyes:

    Any help would be greatly appreciated :)
     
  2. screen1988

    Member

    Mar 7, 2013
    310
    3
    I think you are wrong here.
    A'BC'D + AB'CD ≠ 0
    A'BCD' + AB'C'D ≠ 0
    Therefore, you can't cancel out these terms.
    And A'BC'D is not equal to (AB'CD)'
    A'BCD' is not equal to (AB'C'D)'

    I think you can reduce this expression by using algebra rules but for me I would make a true table and it seems easier to get the result.
     
  3. WBahn

    Moderator

    Mar 31, 2012
    17,757
    4,800
    What do you mean by "I cancelled out the 1st term with the 6th"?

    1st term: A'BC'D
    6th term: AB'CD'

    How do these "cancel" in any way?

    While the following is wrong, we can use it to illustrate how you can simplify terms:

    BD + AC + ABCD

    Notice that the second term is completely contained in the third term, so if we factor it out we get

    BD + AC(1 + BD)

    And since 1 and anything is 1, this reduces to

    BD + AC

    Aslo note that if two terms share a common factor and if the part they don't share are complements of each other, then the complement can go away. For instance:

    AB'C'D + ABC'D

    They share the factor AC'D, so factoring that out we have

    AC'D(B'+B)

    But (B'+B) is 1, so this reduces to just

    AC'D

    Those two concepts should get you at least most of the way there. Do the best you can and if you don't make it all the way, post your work step by step and we will see if we can help you from there.
     
  4. pixel1

    Thread Starter New Member

    Apr 13, 2013
    4
    0
    Thanks for the help so far :)

    Ok, so I had thought that terms such as the 1st and 6th cancelled out because they were compliments of each other (A'BC'D + AB'CD') but I'll need to rethink this.

    WBahn, hopefully I've used the rule you mentioned correctly for starting to reduce the expression:

    A'BC'D + A'BCD' + A'BCD + AB'C'D + ABC'D + AB'CD' + AB'CD + ABCD' + ABCD
    (1st)____(2nd)____(3rd)____(4th)____(5th)____(6th)____(7th)____(8th)____(9th)

    A'BD(C'+C) + BCD'(A'+A) + AC'D(B+'B) + AB'C(D'+D) + ABCD
    (1st & 3rd)___(2nd & 8th)___(4th & 5th)___(6th & 7th)___(9th term)

    A'BD + BCD' + AC'D + AB'C + ABCD

    I'm hoping I'm on the right track now but I'm still not 100% sure how I'll get this reduced down to AC + AD + BC + BD
     
  5. WBahn

    Moderator

    Mar 31, 2012
    17,757
    4,800
    But they aren't complements of each other. In order to be complements, whenever one is true the other must be false and vice versa. While it is true that if one of them is true that the other must be false, it is also possible for both of them to be false. For instance, what if A=0 and B=0?

    You are doing fine, so far.

    The next steps are a bit less obvious, but are really using the same idea.

    First, you need to keep in mind that just because you combine a couple of terms you can still use the original terms again if you need to. This is because A = A + A, so look in the original terms to see which ones can combine with that 9th term. In fact, you will find four of them, so don't just settle for the first one you find. Write down all four. In fact, this goes for all the other terms that you combined as well. Go back and extract all of the three-factor terms that you can. If I'm counting correctly, you have a total of twelve pairs of four-factor terms that have three factors in common. Your simplified expression at this stage consists of the twelve three-factor terms (with any duplicates removed) and any four-factor terms that were not part of any of the pairs (and you shouldn't have any of those because we know we are heading toward a solution that doesn't have any).

    So, at this point, you will have an expression consisting of twelve three-factor terms instead of nine four-factor terms. It may seem like you are going the wrong way, but you have actually made a huge amount of progress.

    Now simply repeat this cycle and find all of the pairs of three-factor terms that have two factors in command and for which the remaining factors are complements. So group ABC' and AB'C but do not group ABC and ABD.

    Again, only those three-factor terms that are not a part of any of the pairs survive as three-factor terms in the next step and, again, there shouldn't be any of those. You should find eight such pairs and once you reduce those to a sum of eight two-factor terms you should find that four of them are duplicates and can be eliminated, leaving you with the four terms in the final answer.
     
    pixel1 likes this.
  6. pixel1

    Thread Starter New Member

    Apr 13, 2013
    4
    0
    Thanks WBahn!!!

    That was really helpful, I've been able to work through it now :) I didn't realise how much work was involved, but makes sense and gave the exact answer. This is what I did (typed this out in case it helps others too):

    1st term combined with 3rd & 5th = A'BD+BC'D
    2nd term combined with 3rd & 8th = A'BC+BCD'
    3rd term combined with 1st, 2nd & 9th = A'BD+A'BC+BCD
    4th term combined with 5th & 7th = AC'D+AB'D
    5th term combined with 1st, 4th & 9th = BC'D+AC'D+ABD
    6th term combined with 7th & 8th = AB'C+ACD'
    7th term combined with 4th, 6th & 9th = AB'D+AB'C+ACD
    8th term combined with 2nd, 6th & 9th = BCD'+ACD'+ABC
    9th term combined with 3rd, 5th, 7th & 8th = BCD+ABD+ACD+ABC

    With duplicates removed:
    A'BD+BC'D+A'BC+BCD'+BCD+AC'D+AB'D+ABD+AB'C+ACD'+ACD+ABC

    Reduced down to:
    BD + BD + BC + BC + AD + AD + AC + AC
    = BD + BC + AD + AC

    :)
     
  7. WBahn

    Moderator

    Mar 31, 2012
    17,757
    4,800
    Very good. About the only thing I would point out is that you can avoid most of the duplicates (all in the first round) by only looking for pairs involving later terms. So you look at all eight of the remaining terms when considering the first term, but when looking at the, say, fifth term you only need to consider the remaining four terms because any pairs that existed involving the first four terms would have been found already.

    Note that this approach is very algorithmic, meaning that it would be a pretty straightforward thing to write a program to perform this kind of simplification.
     
    pixel1 likes this.
Loading...