Difficult Logic Gate Puzzle Using Only 2 Input NAND Gates

[Alxb577]

Homework Statement

[/B]
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)

Homework Equations

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

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

 

[jedishrfu]

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

 

[Alxb577]

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!