Basic Gates Built From Nand Gates

Question

I am just starting to learn the basics of gates via the first chapter of "The Elements of computing Systems". The first project is to implement a bunch of the basic (and, not, or, etc) gates using Nand gates as the base.

I am managing to get them eventually, but honestly I am doing it through intuition and trial and error. Is this pretty much how you have do it at a entry level, or are there some basic boolean logic (manipulations?) I could learn that would help my understanding of building things up from Nand gates?

Answer 1

If your book is any good, it should mention Karnaugh mapping. Karnaugh mapping is about grouping like values (like all ones or all zeros) on a map consisting of rows and columns of logical combinations.

If you can group logical combinations like that you can simplify your logical function as given in this example.

Another method which works better for me is to work with truth tables. On the left you write all logical combinations of the inputs. For 3 inputs that would be

A B C
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Note that this table becomes rather long if you have many inputs: \$2^N\$ lines. On the right you write the output(s). For example

A B C Y
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

With some exercise you often can see a pattern in the output. In this case for the first four lines, where A = 0, Y = B XOR C. For the rest, where A = 1, Y = NOT (B XOR C), or, combined: Y = A XOR B XOR C. (This can be used to create a parity bit)

---

Jeff mentions how you can use DeMorgan's Law to create an OR gate from NANDs. This XOR gate is also basic:

Answer 2

Surprising no one's mentioned DeMorgan's Law. This gives you a couple of useful transformations:

!(A * B) = !A + !B
!(A + B) = !A * !B

This lets you flip between AND and OR functions, with a simultaneous inversion in the inputs and outputs. Making an inverter from a NAND is easy, just tie the inputs together. Invert the NAND (with your freshly minted inverter) and you have AND; apply DeMorgan's Law and you have an OR with everything inverted; apply inverters to just the inputs of that and you have NOR; invert the output, you have OR.

Of course building this way you will end up with a non-optimal result, and K maps are one tool to help you reduce your system to something simpler that accomplishes the same function.

Answer 3

I think what you are looking for are Karnaugh Maps:

The Karnaugh map (K-map for short), Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions. The Karnaugh map reduces the need for extensive calculations by taking advantage of humans' pattern-recognition capability, permitting the rapid identification and elimination of potential race conditions.

In a Karnaugh map the boolean variables are transferred (generally from a truth table) and ordered according to the principles of Gray code in which only one variable changes in between adjacent squares. Once the table is generated and the output possibilities are transcribed, the data is arranged into the largest possible groups containing 2n cells (n=0,1,2,3...) and the minterm is generated through the axiom laws of boolean algebra.

Once you have two basic gates you can combine them together to make a third, then use Karnaugh maps to reduce the number of NAND gates you need to make it.

Answer 4

There are a few important principles.

The first principle (not sure if it has a name) is if you connect together all the inputs of an and/or gate you get a gate that passes the input signal through unchanged. Similarly if you set all but one of the inputs of an AND gate to 1 or all but one the inputs of an OR gate to 0 you also get a gate that passes the input through unchanged. It should follow pretty obviously from here how you can turn a NAND or NOR gate into an inverter.

The second principle is known as "de-morgan's theorem", basically if you add inverters to the inputs and outputs of an AND gate you turn it into an OR gate and vice-versa. Putting this together with the first principle it should be pretty easy to see how you can make an AND, OR or NOR gate out of NAND gates.

The third principle which also follows from de-morgan's therem and which is important in dealing with more complex cases is that NAND followed by NAND is equivilent to AND followed by OR.

This gives us a strategy, if we can express something in terms of AND followed by OR (known as "sum of products" form, since OR is considered analagous to addition and AND is considered analagous to multiplication. we can implement it with at most three layers of NAND gates. The first layer used as inverters, the second layer used to perform the AND function and the third layer used to perform the OR function.

And we can express anything in "sum of products form", just go down the truth table, if the output is 0 ignore the line, if the output is 1 write a term representing that line. Lets try and use this to build an XOR.

The truth table for an XOR looks like

A B Q
0 0 0
1 0 1
0 1 1
1 1 0

So now we can write out our equation in sum of products form.

$$ Q = A \oplus B = A.\overline{B} + B.\overline{A}$$

In more complex cases we may want to simplify the sum of products form by combining terms before we implement it with NAND gates. There are various techniques for doing this but they don't help with XOR. The sum of products form is already minimal. So lets go ahead and translate it to NAND gates.

$$ Q = \overline{\overline{A.\overline{B}} . \overline{B.\overline{A}}}= \overline{\overline{A.\overline{B.B}} . \overline{B.\overline{A.A}}} = \overline{\overline{A.\overline{1.B}} . \overline{B.\overline{1.A}}}$$

So now we have a valid implementation of XOR using NAND gates. I think if you were doing it for yourself you would be more than entitled to stop here.

However there is one trick left we can use to simplify the NAND gate implementation of XOR. It turns out that in the above formula rather than replacing \$\overline{A}\$ with \$\overline{A.A}\$ or \$\overline{1.A}\$ and replacing \$\overline{B}\$ with \$\overline{B.B}\$ or \$\overline{1.B}\$ we can replace both of them with \$\overline{A.B}\$. We can do this because the value of \$\overline{A}\$ only matters when \$B\$ is 1 and the value of \$\overline{B}\$ only matters when \$A\$ is one.

$$ Q = \overline{\overline{A.\overline{A.B}} . \overline{B.\overline{A.B}}}$$