NAND and NOR: the Universal Gates

Transcript

0:00Introduction

Hello everyone! Let us start with a small puzzle. Suppose you are given a box of logic gates, all of the same kind. No AND gates, no OR gates, no NOT gates. Could you still build any logic circuit you want? For two special gates, NAND and NOR, the answer is yes. Let us see exactly how. This idea comes up often in JEE, so let's begin.

0:26NAND and NOR: a NOT after the gate

So, first, here is the figure from the last lesson, with all five gates: OR, AND, NAND, NOR and NOT. Each has its symbol, its Boolean expression and its truth table, with the inputs A and B, and the output Y, okay? Today we need the third and the fourth, NAND and NOR. Notice the small circle, the bubble, at their outputs: the same bubble sits on the NOT gate at the far right. Right? NAND means an AND gate followed by a NOT gate. So on screen, Y equals A dot B, with a bar over the whole thing. The dot means AND, and the bar on top means NOT. Clear? Now tell me, for which inputs is the output of a NAND gate zero? Yes, exactly, the output is zero only when all the inputs are one. AND gives one only when A and B are both one, and then the NOT flips it to zero. So the NAND column in the figure reads one, one, one, zero. With me? Now NOR. It is an OR gate followed by a NOT gate. So, Y equals A plus B, with a bar over it. And remember, this plus means OR, not ordinary addition. Okay? So, your guess: for which inputs is the output of a NOR gate one? That is correct, the output is one only when all the inputs are zero. OR gives zero only for zero and zero, and the NOT turns it into one. So the NOR column reads one, zero, zero, zero. Got it?

2:04Universal gates: build everything from one kind

Now the big idea of this lesson. NAND and NOR are called universal gates, because NOT, AND and OR, and so any logic circuit, can be built from NAND gates alone, or from NOR gates alone. Right? Let us start with NOT. You have one NAND gate with two inputs, but only one signal, called A, to feed it. How would you turn this gate into a NOT gate? Yes, exactly, join the two inputs, like the top left drawing, where the dot joins the wires. Both inputs are now A, so the output is A dot A, with a bar. And A dot A is just A, since one and one gives one, and zero and zero gives zero. So the output equals A bar, a NOT from just one gate. Okay? Next, AND. Remember, NAND is an AND with a NOT after it. So how do we get a plain AND back? We put one more NOT after it: a second NAND with its inputs joined, as in the top right drawing. Two NOTs in a row give back the original signal, so the output is A dot B, the AND. Two NAND gates for an AND. Clear? Now OR, the clever one, in the bottom drawing. Two NAND gates, used as NOT gates, give A bar and B bar. Then a third NAND gives A bar dot B bar, with a long bar over everything, and on screen that equals A plus B, the OR. With me? Let me show you why this works. The product A bar dot B bar is one only when A and B are both zero. The long bar flips it, so the output is zero only when both inputs are zero, which is exactly OR. So OR needs three NAND gates. Got it?

3:52With NOR gates: the mirror image

Now NOR gates, in the box on the right of the figure. Join the two inputs of a NOR, and it becomes a NOT gate, just like the NAND, using just one gate. Okay? So tell me, from NOR gates, which one is easier to build, OR or AND? Yes, exactly, OR is easier, because NOR is just OR followed by NOT. So follow a NOR with a second NOR used as NOT. The two NOTs cancel, and you get A plus B, the OR. Two NOR gates. Right? AND is now the clever one. Two NOR gates invert A and B, and a third NOR takes A bar and B bar. Now, A bar plus B bar is zero only when A and B are both one, and the long bar flips it, so the output is A dot B, the AND. Three NOR gates. Clear? Here is a trick to remember these counts. NAND has AND hidden inside it, so AND costs two NAND gates, and OR costs three. NOR has OR hidden inside it, so OR costs two NOR gates, and AND costs three. Got it?

5:00Example 1: 1100 and 1010 bit by bit through NAND and NOR

Now the first example. Two four-bit numbers, A equals one one zero zero, and B equals one zero one zero, are applied bit by bit to a NAND gate, and to a NOR gate. Find the outputs. Pause the video and try it first. Done? Okay, let's check. Now, some students flip the bits of A and B first, and then combine them. Is that right? That would be wrong, and it is the trap here: the NOT in a NAND acts on the output, after the AND. So first AND the bits, place by place: one and one gives one, and every other pair gives zero. So the AND output is one zero zero zero. Right? Flip every bit, and the NAND output is zero one one one. The only zero is in the first place, where both inputs are one. With me? Now the NOR gate. First OR the bits, place by place: zero or zero gives zero, and every other pair gives one. So the OR output is one one one zero. Okay? Flip every bit, and the NOR output is zero zero zero one, with a one only in the last place, where both inputs are zero. Clear?

6:14Example 2: least number of NAND gates to make a NOR gate

Now a harder one. What is the least number of NAND gates needed to make a NOR gate? Pause the video and try it first. Done? Okay, let's check. Many students say: take one NAND, put a NOT after it, two gates, finished. But is that really a NOR? It is not, and that is the trap: a NAND followed by a NOT gives AND, as we saw, not NOR. So start from what NOR really is: OR followed by NOT, Y equals A plus B with a bar over it. Got it? Step one is the OR, which we built a moment ago from three NAND gates. Right? Step two is the NOT after it, and that is one more NAND with its inputs joined. With me? So the total is three plus one, which makes four NAND gates, and the answer is four. Okay? And by the mirror image, a NAND from NOR gates also needs four: three NOR gates for the AND, then one NOR as NOT. Clear?

7:17Quick revision: universal gates and the gate counts

So, quick revision. NAND is AND followed by NOT, and its output is zero only when all the inputs are one. NOR is OR followed by NOT, and its output is one only when all the inputs are zero. Both are universal gates: any circuit can be built from NAND alone, or from NOR alone, which answers our puzzle. And the counts. From NAND gates, NOT takes one gate, AND two, OR three, and NOR four. From NOR gates, NOT takes one gate, OR two, AND three, and NAND four. Now go and try the practice problems on this page. All the best!