1. Home
2. Academy
3. Digital Logic from Zero
4. Volume 02

2.1 AND, OR and NOT

Three gates can build any logic circuit there is. An AND gate gives 1 only when all its inputs are 1. An OR gate gives 1 when at least one input is 1. A NOT gate turns 0 into 1 and 1 into 0.

Volume 00 found AND and OR hiding in two switches and a lamp. This volume gives each gate its symbol, its truth table and a short way to write it down. Figure 2.1 shows the first three.

AND

The output of an AND gate is 1 only when every input is 1. We write it with a dot, Y = A·B, and read it as "Y equals A and B".

A car that starts only when the key is turned and the brake is pressed is following an AND rule.

OR

The output of an OR gate is 1 when at least one input is 1. We write it with a plus sign, Y = A + B, and read it as "Y equals A or B".

A car's courtesy light that comes on when either front door is open is following an OR rule.

in logic, 1 + 1 = 1

NOT

A NOT gate has one input, and its output is always the opposite. It is also called an inverter. We write it with a small mark after the letter, Y = A', and read it as "Y equals not A". Many books draw a bar over the letter instead; both mean the same.

The small circle on the front of the NOT symbol is called a bubble. Wherever you see one on a gate, it means the signal is inverted at that point.

More than two inputs

AND and OR gates can have more inputs, and the rules stay the same. A three-input AND needs all three inputs to be 1, while a three-input OR needs just one:

AND is 1 on just the last row. OR is 0 on just the first.

2.2 NAND, NOR, XOR and XNOR

Four more gates complete the set. NAND and NOR are AND and OR with the output inverted. XOR gives 1 when its inputs differ, and XNOR gives 1 when they are the same.

Here are all four in one truth table:

NAND and NOR

NAND means "not AND". Its column is the AND column with every bit flipped, so it gives 0 only when all its inputs are 1. We write it Y = (A·B)', with the bracket showing that the whole AND is inverted.

NOR means "not OR". It gives 1 only when all its inputs are 0, and we write it Y = (A + B)'.

These two look like afterthoughts, but they are the most important gates of all. Sub-module 2.4 shows why.

XOR and XNOR

XOR, short for exclusive OR, gives 1 when its inputs are different. It is like OR, except that it excludes the row where both inputs are 1. We write it Y = A ⊕ B.

XNOR is XOR inverted: it gives 1 when the inputs are the same. We write it Y = A ⊙ B. You have met it before. It is exactly the staircase light from Volume 00, where the lamp lit when both switches pointed the same way:

XNOR is the staircase rule of Volume 00: True

It is also the "same or different" rule that turned binary into Gray code in Volume 01. That rule was XOR all along.

XOR with more inputs

A three-input XOR gives 1 when an odd number of its inputs are 1. That makes it the gate that calculates a parity bit:

XOR as a switchable inverter

Look at the XOR rows again. When B is 0, the output equals A. When B is 1, the output is A inverted. So one input of an XOR can switch inversion on and off for the other. Applied to four bits at once:

1011 XOR 0000 = 1011
1011 XOR 1111 = 0100
1011 XOR 0110 = 1101

A 0 in the second number leaves a bit alone, and a 1 flips it. Volume 06 uses exactly this to build a circuit that can both add and subtract.

2.3 Truth tables and timing diagrams

A truth table and a timing diagram show the same facts in two ways. A truth table lists every input pattern once. A timing diagram shows the patterns in the order they happen - and it can show things a truth table cannot, because real gates take time.

Building a truth table, column by column

To find the truth table of a circuit with several gates, add a column for each gate's output and work from the inputs towards the output. Take the circuit in Figure 2.3, which ANDs A and B, then ORs the result with C.

First fill the A·B column, which is 1 only where A and B are both 1. Then OR it with C: Y is 1 wherever A·B is 1 or C is 1.

The same circuit over time

Figure 2.4 shows the same circuit while its inputs change. Each column of the timing diagram is one row of the truth table, in the order it happened.

Gates take time

So far every output has changed at the same instant as its inputs. Real gates are not that quick. A gate's output changes a short time after its input does, and that time is the gate's propagation delay.

Figure 2.5 shows a NOT gate whose delay is one time step. Every change of the output comes one step after the change of the input that caused it:

A changes at 3, 6 and 9; Y changes at 4, 7, 10

A glitch

The delay has a surprising result. On paper, A·A' is always 0, because A and A' can never both be 1:

Now build it: A goes straight into an AND gate, and also through a NOT gate into the AND's other input. When A rises, the NOT gate takes a step to catch up. For that one step, both AND inputs are 1:

That short, unwanted pulse is a glitch. The truth table is still right about where the output settles. The timing diagram shows what happens on the way there. Volume 04 explains when glitches happen and how to design them out.

2.4 Universal gates: everything from NAND

NAND on its own can build every other gate, and so can NOR. That is why they are called universal gates, and why real chips are built mostly from them.

NOT, AND and OR from NAND

A NAND with both inputs joined together is a NOT gate, because (A·A)' is just A'. A NAND followed by that NOT undoes the inversion and gives AND. And inverting both inputs of a NAND gives OR, as Figure 2.7 shows.

Why does the bottom circuit give OR? A NAND gives 1 unless both its inputs are 1. Its inputs here are A' and B', which are both 1 only when A and B are both 0. So the output is 1 unless A and B are both 0 - and that is exactly OR. Volume 03 turns this reasoning into a rule, De Morgan's theorem.

XOR from four NANDs

Even XOR can be built from NANDs. Figure 2.8 uses four, and the simulator behind this page checked all four input rows.

How many gates each one takes

How many NAND gates does each gate need at the very least? A program tried every possible network of one NAND, then two, then three, and so on, until it found each gate. It did the same for NOR:

NAND and NOR mirror each other. What is cheap from one is dear from the other, and the table shows it row by row.

Why real chips love NAND

Inside a CMOS chip, a gate is built from transistors. A NAND gate is the natural shape: a 2-input NAND takes 4 transistors, while a 2-input AND is a NAND followed by a NOT, which takes 6. So chip designers think in NANDs and NORs, and the tools that turn a design into gates do the same.

2.5 Gates on real chips

Real gates come packed several to a chip. The 7400 series puts two to six gates in one package, with two pins for power. Every chip has a datasheet that says which pin does what and how fast it is.

Today most logic lives inside large chips, such as processors and FPGAs, where millions of gates share one piece of silicon. But the small logic chips of the 7400 series are still made. They are the easiest way to build real gates on a breadboard and watch them work.

The 7400: four NANDs in one package

The first chip of the family, the 7400, holds four 2-input NAND gates in a 14-pin dual in-line package. Its pinout says which pin is which:

Other members of the family hold the other gates. The 7402 holds four NOR gates, the 7404 six inverters, the 7408 four AND gates, the 7432 four OR gates and the 7486 four XOR gates. Modern versions add letters, as in 74HC00, which name the family of transistors inside. Volume 09 compares those families.

Two rules for real chips

1. Power every chip. A logic chip does nothing until VCC and GND are connected, even though no circuit diagram of gates shows those pins.
2. Never leave an input unconnected. An open input on a CMOS chip floats to any voltage, often into the forbidden zone from Volume 00. Tie every unused input to 0 or to 1.

Delays add up

A datasheet also gives each gate's propagation delay. For a 74HC chip running from 5 V it is roughly ten nanoseconds; inside a modern processor, a gate switches in picoseconds. When gates are joined one after another, their delays add:

a chain of 5 gates at 10 ns each takes 50 ns

The longest chain of gates in a circuit decides how fast it can go. The course on static timing analysis is all about that chain.

What you learned

• AND gives 1 only when all inputs are 1, OR when at least one is 1, and NOT inverts. They are written A·B, A + B and A'.
• In logic, + means OR, so 1 + 1 = 1.
• NAND and NOR are AND and OR with the output inverted; a bubble on a symbol always means "invert".
• XOR gives 1 when its inputs differ, XNOR when they are the same, and a many-input XOR gives the parity of its inputs.
• To find a circuit's truth table, add a column for each gate and work from the inputs to the output.
• Every gate has a propagation delay, and delays can make glitches that no truth table shows.
• NAND alone can build every gate, and so can NOR: AND takes 2 NANDs, OR takes 3 and XOR takes 4.
• Logic chips need power on their VCC and GND pins, unused inputs must be tied, and pinouts must be checked in the datasheet.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• AND gate
• OR gate
• NOT gate (inverter)
• Bubble
• NAND gate
• NOR gate
• XOR gate
• XNOR gate
• Parity bit
• Propagation delay
• Glitch
• Universal gate
• 7400 series
• DIP (dual in-line package)
• Pinout
• Datasheet

Practice

Y = D·S + P

1011 XOR 0110 = 1101

Interview corner

Volume 03 gives these gates an algebra of their own, so that a circuit can be simplified on paper before a single gate is placed.