NOT, and joining gates together
The gate that flips a bit, and what happens when one gate feeds another.
The gate that says no
AND and OR combine inputs. The third gate does something simpler: it takes one input and outputs the opposite. A 1 in gives a 0 out, and a 0 in gives a 1 out. It is called NOT, and its truth table has just two rows, because one input can only be in two states.
The symbol is a triangle pointing in the direction the signal travels, with a small circle on its tip. That circle is worth knowing on its own, because it turns up on other gates too.
NOT is also called an inverter, because it inverts the signal. Putting two NOT gates in a row gets you back where you started: a 1 becomes 0 and then 1 again. That sounds pointless, and as logic it is, but it is the first hint that gates can be connected to each other, which is the real subject of this lesson.
Gates feed gates
A gate's output is a wire carrying a 1 or a 0. An input of another gate is a wire expecting a 1 or a 0. So the one can be connected to the other, and now you have a circuit of two gates in which the second one works on the first one's answer. There is no limit to this. A processor is a few billion gates connected this way, and every one of them is doing nothing more than applying its own small rule to whatever arrives on its inputs.
The wire between two gates deserves a moment's thought. It is not an input you control and it is not the final output. It carries an intermediate value: a result that exists only to be fed into the next gate. When you work out a circuit by hand, you write that value on the wire, and then the next gate has everything it needs.
Here is a circuit of three gates. a and b go into an AND; its output goes through a NOT; and that result goes into an OR together with c. Try all the combinations and watch the table.
Working a circuit out step by step
The method is always the same, however big the circuit gets. Start at the inputs, find a gate whose inputs are all known, work out its output from its rule, and write that value on its output wire. Now another gate has all its inputs known. Keep going until you reach the output. You never have to hold more than one gate in your head at a time.
Worked example. In the circuit above, what is the output when a = 1, b = 1 and c = 0?
The AND gate has a = 1 and b = 1. Both are 1, so its output is 1. Write 1 on the wire leaving it. The NOT gate receives that 1 and flips it: 0. Write 0 on its output wire. The OR gate now has 0 from the NOT and c = 0. At least one 1? No. Its output is 0, so the circuit outputs 0. Set the widget to 1, 1, 0 and check: the output lamp is off.
Common mistake: working from the output end
It is tempting to start at the gate nearest the output, since that is the one you want the answer from. But that gate cannot be worked out until its inputs are known, and one of them comes from an earlier gate. Start where the named inputs go in and move towards the output; each step then only needs values you already have.
Why?: why bother with NOT at all?
AND and OR can only ever say "yes" more often as you turn more inputs on. Neither can express "when the door is closed" if what the sensor gives you is "the door is open". NOT is what lets a circuit act on the absence of something. Without it, whole families of decisions would be out of reach. With it, and with AND and OR, every decision that can be written as a truth table can be built. The rest of the seven gates are conveniences.
What to remember
- NOT has one input and outputs the opposite of it. Two NOTs in a row cancel out.
- The bubble on a symbol means "invert here", on NOT and on any other gate it appears on.
- Gates connect: the output wire of one gate can be an input wire of another.
- The wire between two gates carries an intermediate value. Write it down as you go.
- To work out a circuit, start at the inputs and settle one gate at a time until you reach the output.
Check yourself
Get 5 right in a row and the lesson is done. A wrong answer costs the run, not the lesson.
b goes through a NOT gate. Its output and a go into an OR gate. What is the final output when a = 0, b = 1?
a ∨ ¬b
Already know this? and come back to the quiz any time.