Help understanding DeMorgans's Theorem.

Discussion in 'Math' started by atrumblood, Jul 16, 2012.

  1. atrumblood

    Thread Starter Member

    May 13, 2012
    59
    2
    So I am trying to get my head around DeMorgan's Theorem by simplifying the the attached logic gate diagram of an XOR Gate constructed of NAND Gates.

    The diagram converts to ((A(AB)')'((AB)'B)')'

    Sorry if that is hard to read I can't figure out how to do the over-score.

    Can someone walk me through how I would apply DeMorgan's Theorem and simplify this.
     
    • XOR.png
      XOR.png
      File size:
      9.8 KB
      Views:
      53
  2. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    I haven't done this in over 20 years. There are formal ways, but for simple problems like this, I used to just mentally move the inversion dots around in my head. If you see one dot on the output of a gate, don't be afraid to slide it over to the inputs of any gates connected to that output. Also, don't be afraid to insert 2 inverters anywhere where it helps you. Then you can slide one into a useful position and the other one becomes an inverter gate. Often that inverter can be absorbed into another gate.
     
    atrumblood likes this.
  3. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    By the way, are you sure this is correct?

    EDIT: I think it is correct. I had trouble reading it.
     
    Last edited: Jul 16, 2012
  4. atrumblood

    Thread Starter Member

    May 13, 2012
    59
    2
    Yeah I am pretty sure it is right. The answer I got was A(AB')+B(A'B), but I think it can be simplified further. I need to review the identities.
     
  5. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    So, what is your definition of simplification? Are you trying to get back to the most fundamental definition of XOR, AB'+A'B?

    If so, I would recommend an equation approach, rather than the graphical approach I mentioned above. I say this because I tried the graphical approach and one of the required steps is hard to see. However, when I used equations, it was obvious.
     
  6. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    Hmmm, yes, the original is correct. I just had trouble reading it.

    But, the answer you have does not look correct. Start over and i think you'll find your mistake.
     
  7. atrumblood

    Thread Starter Member

    May 13, 2012
    59
    2

    Ok I think I got it. I will try to type out the steps I took. Can you verify if I did it correctly?



    Starting with ((A(AB)')'((AB)'B)')'

    ((A(A'+B'))' (B(A'+B'))')'

    ((A'+(A''B''))(B'+(A''B'')))'

    (A''(A'''+B'''))+(B''(A'''+B'''))

    (A(A'+B'))+(B(A'+B'))

    AA' + AB' + BA' + BB'

    AA' and BB' cancel out to zero and I am left with

    AB' + BA'


    Sorry if that is a little messy. I was trying to keep things grouped up to avoid mistakes.
     
  8. WBahn

    Moderator

    Mar 31, 2012
    17,757
    4,800
    Normally I would walk you to the answer by asking questions, but I think I know you well enough to just show you.

    If you want to see if you can get it yourself with just some guiding questions, don't look below the SPOILER line until you've taken a shot at it.

    Starting point (i.e., the equation directly from the 4-NAND implementation):
    <br />
Y\;=\; \bar{ \bar{ \left[ A \left( \bar{AB} \right) \right]} \; \bar{ \left[ B \left( \bar{AB} \right) \right]}}<br />

    Q1) What do you get if you apply DeMorgan's Theorem to the final operation (the output NAND gate in the schematic)?

    Q2) What to you then get if you apply DeMorgan's Theorem to the first operation (the NAND gate that gets both A and B in the schematic)?

    Q3) What do you then get if you distribute the AND operations over the OR operations?

    Q4) If you haven't already, what do you get when you recognize that T*T' is always false?

    ==============SPOILER============================================

    First, apply DeMorgan to the final operations:

    <br />
Y\;=\; A \left( \bar{AB} \right) \; + \; B \left( \bar{AB} \right)<br />

    Now apply DeMorgan to the terms in parentheses:

    <br />
Y\;=\; A \left( \bar{A}+\bar{B} \right) \; + \; B \left( \bar{A}+\bar{B} \right)<br />

    Now distribute out the factors:

    <br />
Y\;=\; A \bar{A} \; + \; A\bar{B} \; + \; B \bar{A} \; + \; B \bar{B}<br />

    Eliminate the terms that are identically zero:

    <br />
Y\;=\; A\bar{B} \; + \; B \bar{A}<br />

    And you now have, by definition, an XOR gate.
     
    atrumblood likes this.
  9. WBahn

    Moderator

    Mar 31, 2012
    17,757
    4,800
    Okay so far.

    Okay. I would recommend doing this in two steps, though, because it is a bit hard to follow what is going on. So

    ( (A(A'+B'))' (B(A'+B'))' )'
    ( (A'+(A'+B')') (B'+(A''+B')') )'
    ( (A'+A''B'') (B'+A''B'') )'

    At this point, go ahead and recognize that A''=A and B''=B

    ( (A'+AB) (B'+AB) )'

    The rest of your work looks fine, but I would have the same suggestions for the next steps. Only do one level of DeMorgan at a time. It's too hard for most people to follow multiple levels.

    Use spaces and also brackets and braces to make the groupings easier to see:

    { [A(AB)']' [(AB)'B]' }'
     
    atrumblood likes this.
  10. atrumblood

    Thread Starter Member

    May 13, 2012
    59
    2
    Thank you both for your help.

    Steveb, Thank you for pointing out to me that I had made a mistake. I think it all clicked when I went back over it.


    WBahn, As always I really appreciate the your great effort to teach me, and the advice you have to offer. It is always helpful in a big way to have your feedback to my desire to learn.
     
  11. atrumblood

    Thread Starter Member

    May 13, 2012
    59
    2
    AB'+BA'

    Attached is the original and simplified XOR gate. Just to show that I understand how to convert between the graphical and the arithmetic.
     
    • XOR.png
      XOR.png
      File size:
      11.2 KB
      Views:
      43
Loading...