Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Boolean Algebra Proof Statement

  1. Apr 3, 2012 #1
    1. The problem statement, all variables and given/known data
    Prove the identity of the following Boolean equation using algebraic manipulation:
    AD' + A'B + C'D + B'C = (A' + B' + C' + D')(A + B + C + D)

    2. Relevant equations

    DeMorgan's Theorem: (A + B)' = A'B'

    3. The attempt at a solution

    I tried simplifying the equation to the following:
    AD' + A'B + C'D + B'C = A'D + A'B + C'D+ B'C + (A'C + A'D + B'A + B'D + C'A + C'B + D'B + D'C)

    However, this doesn't appear to be going anywhere. What kills me is the fact that I have no way of knowing whether or not the path I'm following will turn out or not.

    My TA mentioned that the left hand side should be modified with OR statements (+), however I'm not sure where to begin. Any help would be greatly appreciated.
  2. jcsd
  3. Apr 3, 2012 #2


    User Avatar
    Gold Member

    Interesting. I can easily see w/ a Kmap that the statement is true, but like you, I draw a blank when trying to prove it algebraically. DeMorgan doesn't seem to help and I don't know what else to try. There's probably something simple that we're both forgetting or overlooking.
  4. Apr 3, 2012 #3
    I'm glad I'm not the only one who would have difficulty solving this proof. The problem is still open, for anyone who is willing to help me!
  5. Apr 4, 2012 #4
    Bumping for help.
  6. Apr 4, 2012 #5
    Well, from the K-map they are both equal to (ABCD + A'B'C'D)', which we know immediately anyway from applying DeMorgan a couple of times to the RHS.

    The K-map shows us there is plenty of overlap in the RHS, so we could try to unravel that...
    (A'+B'+C'+D')(A+B+C+D) = A'B + A'C + A'D + B'A + B'C + B'D + C'A + C'B + C'D + D'A + D'B + D'C

    What we might do is show that (for example) B'A is covered by AD' + C'D + B'C. So:
    AD' + C'D + B'C
    = AD' + AB'D' + C'D + AB'C'D + B'C + AB'CD
    = AD' + C'D + B'C + AB'(D' + C'D + CD)
    = AD' + C'D + B'C + AB'(D'+D)
    = AD' + C'D + B'C + AB'

    And we can similarly conjure the other terms required out of the LHS. But it's a long, long way round to do them all explicitly; there probably is a better method. Perhaps you could do this with some kind of general analysis of PQ'.
  7. Apr 6, 2012 #6


    User Avatar

    Staff: Mentor

    Focus on the left side, AD' + A'B + C'D + B'C

    ♦ Replace each AND with OR, you'll need to bring in some brackets

    ♦ Replace each red OR with AND

    ♦ Remove the brackets (i.e., "multiply it out") and tidy up, and you'll be left with the OR of two simple terms

    You should see your way to be able to finish now. :wink:
  8. Apr 6, 2012 #7


    User Avatar
    Gold Member

    I'm confused. If you have the term


    How, in terms of just the variables A and B, can you create an equivalent with no AND but any number of ORs ?
  9. Apr 7, 2012 #8
    Neat. I like it, 6 lines or so.

    by using DeMorgan's rule: AB' = (A'+B)'
    A and not-B = not-(not-A or B)
    Last edited: Apr 7, 2012
  10. Apr 7, 2012 #9


    User Avatar
    Gold Member

    well, yeah, but there is then a NOT over the whole thing, so you haven't quite separated out the terms individually. That's what I meant. As I said in my original post, I don't see how DeMorgan helps, but apparently I'm missing something.
  11. Apr 7, 2012 #10
    There is indeed a NOT over the whole thing - but no ANDs, which is all that was promised. :wink:

    Here's the first step of NascentOxygen's method, for enlightenment:
    AD' + A'B + C'D + B'C = (A' + D)' + (A + B')' + (B + C')' + (C + D')'
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook