Help Simplifying Boolean Algebra

Discussion in 'Homework Help' started by stuffed, Aug 22, 2008.

  1. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    I have an exam due in about four days, I have to simplify about 7 boolean statements similar to the one below, using the distributive method, I think, and the basic boolean laws. If someone would give me a hand simplifying the first one and kind of explain what they are doing i should be ok with the other 6. I've been trying this for a week.

    Where A' = not A, + equals or, AB= A*B

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

    If any one gets a chance and does it the commutative way the result should be AC+A'C'+B+D, I don't think you can simplify it that far using distributive. The Kmap answer is the same as outlined for commutative.

    Please help someone,
    Regards Aaron
     
  2. hgmjr

    Moderator

    Jan 28, 2005
    9,030
    214
    I reecommend you read teh material in the AAC ebook on Boolean Algebra to get a basic handle on the topic.

    hgmjr
     
  3. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    Well i downloaded that text book and i guess i'll just trawl through it, my text book here is pretty poor quality.

    And damnit i meant conjunctive and disjunctive not commutative, to many things starting with the same letter.

    Why do teachers always decide that it's a good idea to have a mathematics c assignment, a physics assignment and a chemistry assignment all due at the same time???? Damn i'll be glad to relax in a couple of weeks.

    Any help would be appreciated still, i just want basically a worked example so i can see kind of what i need to do.

    Thankyou everyone.
     
  4. hgmjr

    Moderator

    Jan 28, 2005
    9,030
    214
    You should find the ebook material very enlightening. The examples are worth the price of admission. Which is FREE.

    hgmjr
     
  5. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    So far i have this, i think i have gone wrong somewhere as i can't work out where to go next.

    A'B'C'D'+A'BC'D'+A'B'CD+AB'CD'+A'BCD'+ABCD'+A'B'C'D+AB'C'D
    =A'C'D'(B+B')+BCD'(A+A')+A'B'CD+AB'CD'+A'B'C'+AB'C'D
    =A'C'D'+CD'(B+AB')+A'B'CD+A'B'C'D+AB'C'D
    =A'C'D'+CD'(A+B)+A'B'CD+A'B'C'D+AB'C'D
    =A'C'D'+ACD'+BCD'+A'B'CD+A'B'C'D+AB'C'D
    =A'C'D'+ACD'+BCD'+A'B'D(C+C')+AB'C'D
    =A'C'D'+ACD'+BCD'+A'B'D+AB'C'D

    Any help at all?:confused:
     
  6. blazedaces

    Active Member

    Jul 24, 2008
    130
    0
    I tried KMapping that and I'm not getting that result at all. I can simplify your result further, but it ends up being CD + B'D + A'C'D'...

    I didn't double check your work though...

    If I put those variables on a KMAP with AB on the top and CD on the left, I get:

    1,1,0,0
    1,0,0,1
    1,0,0,0
    0,1,1,1

    Now... how exactly are you grouping those that you somehow get the result you claim should be the answer? Has it really been that long since I did boolean algebra (it certainly might be...)?

    -blazed
     
  7. Ratch

    New Member

    Mar 20, 2007
    1,068
    3
    stuffed,

    The ebook was not much help for what you wanted to do, was it? And it is not even wrong. It was free, so you got what you paid for. I don't know why teachers give students problems like simplying Boolean expressions algbraically. It is so silly. One cannot be sure that you have the simplest reduction by Boolean algebraic manipulation. Especially if it is a complicated expression with lots of terms. And many expressions sometimes have several different equivalent reductions like your does. Furthermore, unless the expression is relatively simple, you don't know how to combine the terms in order to get the best reduction. It is really hit and miss. So what you need to do is to K-map the expression, or when you advance further, use a tabulation method like the Quine-McCluskey method. Either way will get you the reduction answer with all the variations. Also the K-map or the QM method will give you hints on how to combine the terms algebraically so your homework has a continuity to the answer. Let's start with the example you presented.

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

    Good, you expanded it out. That is the first thing to do. Now reduce it using the K-map or QM. The possible reductions are:

    [A'B'D + B'C'D + ACD'] + A'B'C' +A'BD'

    or another reduction is

    [A'B'D + B'C'D + ACD'] + A'C'D' + A'BD'

    or still another

    [A'B'D + B'C'D + ACD']+ A'C'D' +BCD'

    Each of these three variations can be gotten from a K-map or a QM reduction. Notice that the K-map/QM gave us 7 prime implicants. The first three implicants I put in brackets are essential prime implicants. They absolutely have to be included in the reduced expression. Now lets manipulate your submitted expression to get the above answers.

    (A'B'CD + A'B'C'D) + (A'B'C'D + AB'C'D) + (AB'CD' + ABCD') + A'B'C'D' + A'BC'D' + A'BCD'
    3 1 1 9 10 14 0 4 6

    The numbers are the values of each of the terms. Unfortunately, this posting software removes the spacing between the numbers. Continuing...
    A'B'D + B'C'D + ACD' + A'B'C'D' + A'BC'D' + A'BCD'

    The last three terms have values of 0 4 6. Now notice that the all terms that are combined have a bit difference of 1, a value difference of a power of 2, and the value of the term with the smaller number of bits is less than the value of the term with the larger number of bits. Notice also that the value difference determines what variable is cancelled out--8=A, 4=B, 2=C, 1=D. So how many variations can we make from the remaining three terms?

    0,1 = A'B'C'
    4,6 = A'BD'

    another set is

    0,4 = A'C'D'
    4,6 = A'BD'

    and finally

    0,4 = A'C'D'
    6,14 = BCD'

    As you can see, we can get three sets of variations from the nonessential prime implicants. They match up with what was found by a K-map/QM operation.

    Ratch
     
    Last edited: Aug 23, 2008
  8. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    Thats great thank you very much i am not quite sure of some of the methodology, though, basically, i don't understand the term implicant?
    And with our kmaps, we have been told for a different Question though to do them like so
    [5 7 6 4]
    [ ]
    [9 8]
    [1 3 2 0]
    and to fill the spaces with 1's and then group 1's, which gives my kmap answer as supplied in my first post. So if i group with 0's instead i get the expression as you had, the one in brackets? Essential one? and then by algebra i find the non essential parts using your grouping method?

    That is my basic understanding of what you did, am i correct?
    Thankyou so much for your time, brilliant.
    Cheers, Aaron
     
  9. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    [5764]
    [____]
    [9__8]
    [1320]

    My mistake i forgot about their post software thingimy
     
  10. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    Now i'm sitting here and reading it again and trying to work out what i don't quite understand. I see what implicants are. But now i don't get how you assigned the values to each implicant and how they are different by one and how you group using them?

    The more i think the more questions come up, haha, sorry all.
     
  11. Ratch

    New Member

    Mar 20, 2007
    1,068
    3
    stuffed,

    (A'B'CD + A'B'C'D) + (A'B'C'D + AB'C'D) + (AB'CD' + ABCD') + A'B'C'D' + A'BC'D' + A'BCD'
    3 1 1 9 10 14 0 4 6

    A'B'C'D' = 0
    A'B'C'D = 1
    A'B'CD = 3
    A'BC'D' = 4
    A'BCD' = 6
    AB'C'D = 9
    AB'CD' = 10
    ABCD' = 14

    The above shows how I assigned a value to each term. I combined terms with values 1 and 3 together. One is binary 0001 and three is 0011. One and three differ by 1 bit and their value difference is 2, which is a power of two. So (A'B'C'D + A'B'CD) = A'B'D , which is the first essential prime implicant to be calculated. I knew I should combine those particular terms because I worked it out beforehand using either a K-map or the QM method. Is there anything you don't understand, or do you have any questions? Then look in the previous post and see if you can follow what I did better.

    Ratch
     
  12. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    Thanks so much mate. I'm pretty sure i get that now, just unsure completely how the values are assigned but i am sure i'll be able to work that out if a give it a little bit of time. Cheers again...brilliant. :D
     
  13. Ratch

    New Member

    Mar 20, 2007
    1,068
    3
    stuffed,

    Just remember that you have to use every term in the expression at least once, but you can use a term more than once if you need it. Using a term more than once does not change the value of the expression. When combining the expanded terms, remember to pair terms that are one bit different and a value difference of a power of 2, i.e. 2,4,8..etc. Terms like 3 and 4 won't work because although they have a power of 2 difference, their bits are more than 1 bit different. 6 and 4 will combine, as will 6 and 14. Oh, and did I mention, you can only use the terms from the expression?

    The purpose of this exercise is not to reduce the expression algebraically. Reducing an expression is best done with a K-map or the QM method. The purpose is to do your homework so that your instructor thinks you are a genius because you selected the correct terms to combine and reduce it to the simplest form or maybe several forms. He/she does not have to know you did the problem beforehand with better tools than direct Boolean algebraic manipulation. Again, ask if you have any questions.

    Ratch
     
    Last edited: Aug 23, 2008
  14. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    Thanks...if i really need anything else i'll ask tomorrow. I printed a whole heap of info on QM and that should help too. Thanks again
     
  15. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    I understand the main idea with finding the prime implicants and using the QM method but i can't seem to quite do the QM table thing properly to find the essential prime implicants for the following:

    A'B'C'D'(0)+AB'C'D'(8), A'BC'D'(4)+ABC'D'(12)+A'B'CD'(2)+ABCD'(14)+A'B'C'D(1)+AB'C'D(9)

    I have done the size 2 implicants and made the table thingy but i don't quite understand the table, If you could please explain how you use the QM method to find the essential prime implicants with working for the table that would be brilliant thanks in advance, I shall be back on in 13 hours and probably be up all night doing this so thanks again.

    What I basically mean is i don't know how to tell which ones are essential prime implicants in the table?

    Aaron
     
    Last edited: Aug 24, 2008
  16. Ratch

    New Member

    Mar 20, 2007
    1,068
    3
  17. stuffed

    Thread Starter Member

    Aug 22, 2008
    10
    0
    Thanks the wikipedia one was the one that confused me in the first place, but i found a really good explanation this morning to which explained it almost as well as you did, so now i am set. Thanks a heap. No questions iI am pretty sure i understand damned well now, your a great teacher. Again i can't say thanks enough. Thank you, thank you, thank you.
     
Loading...