1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Boolean Algebra with NAND

  1. Nov 27, 2004 #1
    An example in the book asks us to implement the XOR (exclusive-or) function using only 2-input NAND gates.

    So:

    [tex]f = x_1 \overline{x_2} + \overline{x_1}x_2 [/tex]

    If we let [tex]\uparrow[/tex] represent the NAND function. That means that: [tex]f = (x_1 \uparrow \overline{x_2}) \uparrow (\overline{x_1} \uparrow x_2) [/tex]

    I follow everything up to that step. And then they attempt to decompose it by manipulating one of the terms.

    [tex] (x_1 \uparrow \overline{x_2} ) = \overline{x_1 \overline{x_2}} = \overline{x_1 (\overline{x_1} + \overline{x_2})} = x_1 \uparrow (\overline{x_1} + \overline{x_2}) = x_1 \uparrow (x_1 \uparrow x_2)[/tex]

    Can anyone please explain what exactly went on in that step? How did they go from the second equation to the third, and then the fourth? I understand the first and final steps, but that's it.

    Any help would be greatly appreciated!
     
  2. jcsd
  3. Nov 27, 2004 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Draw truth tables. If the left side of the second equation has the same truth table as the right side, you know it works. Also, if you have a text, see if they have some general laws that may have used in going from the first to second equation. Or, it shouldn't be too hard (using truth tables) to generalize some "laws" for yourself.
     
  4. Nov 27, 2004 #3

    Janitor

    User Avatar
    Science Advisor

    A variable AND its negation is always false. A variable OR false is just the variable itself. Those ideas plus DeMorgan's Law are being applied here.
     
  5. Nov 27, 2004 #4

    ehild

    User Avatar
    Homework Helper
    Gold Member

    To get the third equation from the second

    [tex] \overline{x_1 \overline{x_2}} = \overline{x_1 (\overline{x_1} + \overline{x_2})} [/tex]

    it was used that [tex] x_1 \overline{x_1}=0 [/tex]

    The fourth equation came from the third

    [tex] x_1 \uparrow (\overline{x_1} + \overline{x_2}) = x_1 \uparrow (x_1 \uparrow x_2)[/tex]

    by using Morgan's rule

    [tex] \overline{x_1} + \overline{x_2}= \overline {x_1 x_2} = x_1\uparrow x_2 [/tex]

    ehild
     
  6. Mar 4, 2010 #5
    You could draw a truth table to verify but I think you'll get more mileage from an intuitive understanding of the reasoning. Here goes:

    Ignoring one of the negations in the second expression we can just consider this conjunction: [tex]x_1 \overline{x_2}[/tex]

    If [tex]x_1[/tex] is false then the whole conjunction is false regardless of [tex]\overline{x_2}[/tex]. If however [tex]x_1[/tex] is true then the truth of the whole conjunction depends on [tex]\overline{x_2}[/tex] being true. I don't alter this dependence in any way if I replace [tex]\overline{x_2}[/tex] with a disjunction with any false expression:

    [tex]
    x_1 \overline{x_2}
    = x_1 (\bold{F} + \overline{x_2})
    [/tex]

    In this context, I can actually guarantee that [tex]\overline{x_1}[/tex] is false whenever [tex]\overline{x_2}[/tex] is relevant to evaluation. This guarantee comes from the observation that [tex]\overline{x_2}[/tex] is relevant only if [tex]x_1[/tex] is true in which case [tex]\overline{x_1}[/tex] must be false. Therefore:

    [tex]
    x_1 \overline{x_2}
    = x_1 (\bold{F} + \overline{x_2})
    = x_1 (\overline{x_1} + \overline{x_2})
    [/tex]

    Hope that clears up why the second step is valid. The third step is just replacing a negated conjunction with a NAND which is valid by definition.

     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Boolean Algebra with NAND
  1. Boolean Algebra (Replies: 0)

  2. Boolean Algebra (Replies: 5)

  3. Boolean algebra (Replies: 6)

Loading...