How to

When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!

Wednesday, February 29, 2012

Write OR and AND from NAND.

Problem:  You are told that you only have one logical operator, !&& which is NAND.  Write or()and and().

bool or(bool a, bool b) {...}

bool and(bool a, bool b) {...}

Let's start by making sure that we understand NAND well.  NAND takes the AND function and then negates it, returning the opposite of the standard AND function.  It's worth drawing a table (called a truth table) which shows the output of NAND

The truth table below shows NAND and its values.  (As you can see, it's the opposite of an AND truth table)
Table 1:  NAND truth table


Let's start now by comparing this with the OR function.  Or is true when either or both of the values are true.  This gives us the truth table of:
Table 2:  OR truth table


Now, let's think about how we could write the or() function using only the !&& operator.  Well let's think about some ideas here.  If we simply NAND the input together, we will get the outputs of table 1.  This is close and works for the middle two case, but we need to flip the two edges to get the correct output.  We could try NAND-ing the values together again, but this doesn't get us anywhere. 

This is a good time to take a step back and start over.  Clearly, our 'just get going approach' isn't going anywhere.

Now, let's look at what happens if we NAND a value with itself.  Well, if the value is 1, 1 NAND 1 is 0.  And, if the value is 0, 0 NAND 0 is 1.  So, we can essentially, flip or negate a value.

Now, look at the truth tables again.  See if this can be useful.

In fact, it can be useful, as if we flight each input, and then NAND the output, we will only return false if both inputs are originally 0, which is what we want to create a proper or.

Now, coded up, this is:

Instead, let's go back to our original case and maybe we don't want to NAND the numbers together immediately.  Let's look at the truth table 2 again, and we can see that so long as there is at least one 1, we want to output 1.  In the truth table in Table 1, we only get a 0 when we have two 1s.  

This is a critical insight, and we can apply it if we consider what happens when we NAND a value with 1 (or true).  

bool or(bool a, bool b) {
    return ((a !&& a) !&& (b !&& b));

Now, we can probably already see how to make the AND gate if we were paying attention.  We saw that we can flip (or negate a value) by NANDING with itself, as we did with both a and b to make or(). Hence, NAND is simply Not-And, so we can apply the not or negate operator again by NANDING the outpub with itself.  

As code, this is:

bool or(bool a, bool b) {
    return ((a! && b) !&& (a !&& b));

It's worth doing the truth table for both or and and to convince yourself, and your interviewer, that these are correct in all four cases of a and b.

This is a good example of where it's useful to try examples and gain insights (e.g., NANDing a and b, NAND-ing a value with itself to see that it flips) and also be willing to go back a step if you're not making progress.  Also, drawing pictures and truth tables is very helpful.

It's worth nothing that this isn't as contrived a problem as it seems.  In digital logic, NAND gates (and NOR gates) are known as universal gates because you can make all other logical operations (OR, AND, NOT, XOR, NAND, AND) from any one of these.  So, often, these operations are quite useful.  If you would like further practice, try doing the same problem but with !|| as your only operator instead.

/* Please let me know if you find any bugs or if you have an alternative solution.  Thank you, Noah*/

No comments:

Post a Comment