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!

Difficult Logic Gate Puzzle Using Only 2 Input NAND Gates

  1. Feb 27, 2015 #1
    1. The problem statement, all variables and given/known data

    Impliment the expression which is already in minimum sum of products form using only two-input NAND gates. No gate may be used as a NOT. All inputs are available both uncomplemented and complemented. (The number of gates required is shown in parentheses.)

    f = ab'd' + bde' + bc'd + a'ce (10 gates)

    2. Relevant equations

    (ab)' = a' + b'
    (a')' = a
    (a+b) = a'b'

    3. The attempt at a solution

    first my idea was to try and work in reverse by imagining that the end result had come out of a NAND gate and then getting an idea of what the inputs might be. I spend a lot of time on that and gave up because I wasn't going to have the right number of gates.

    second idea. I tried to manipulate the original equation by hand to see if i could toggle any variables or do anything that would help me. I gave up on that because I couldn't get a grasp on what exactly I was doing.

    third idea. I first tried drawing the equation with AND and NOT gates and then tried to convert them to only NAND gates but I just keep getting lost.

    During this time i've tried to use my textbook, but it doesn't have a good example with all these restrictions that I have to implement.

    I wouldn't mind putting some more effort into some method or even something I've already tried if I had some direction as to how to go about solving something like this.

    Thanks
     
    Last edited by a moderator: Mar 5, 2015
  2. jcsd
  3. Feb 27, 2015 #2

    jedishrfu

    Staff: Mentor

    the curious thing is that it takes three NAND gates to construct an OR gate and in your example you have three plus signs.

    Have you tried designing it like you had AND and OR gates and then replace them with the NAND equivalents and then go through and eliminate redundant gates ie two NAND inverters in a row.

    In other words, you allow NAND gates as inverters initially and then remove them from the final circuit.

    Perhaps if you start to construct it from that viewpoint you'll figure it out.

    Here's some more info on NAND logic

    http://en.m.wikipedia.org/wiki/NAND_logic
     
    Last edited: Feb 27, 2015
  4. Mar 5, 2015 #3
    Thanks for your response. I figured it out but it took me a while.

    Here's a picture of how to solve it.

    First I had to find out that there are two ways of representing a nand gate one which resembles or as well as the one that resembles and.

    Then the trick is to use algebraic manipulation to get the terms in pairs of two where the operations are alternating between and and or as you go deeper into the expression.

    For example. Notice how the final expression has two terms sharing an or operation. Looking at one of the terms notice how its the and of two operations. Going deeper into one of those two terms notice how its two terms sharing an or symbol. This is the key to solving this type of problem.

    There is no algorithm that will get your terms this way. It can only be done by trial and error, but at least you can know what you are looking for.

    After we have our final expression written out in a way that is known to work we will draw using logical and and or gates.

    Then add the nots to make all of the gates nand gates and be sure to negate literals which are going into a or type nand gate.

    That's it!!
     

    Attached Files:

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

Have something to add?
Draft saved Draft deleted