By the end of this chapter you should be able to:
- Draw the distinctive-shape symbol for the AND, OR, NOT, NAND, NOR, XOR and XNOR gates from memory, and write the Boolean expression each one realises.
- Construct the truth table of any of the seven gates for two or more inputs, and identify a gate from a given output waveform.
- Explain why NAND and NOR, rather than AND and OR, are the primitive gates of a CMOS process.
- Use the exclusive-OR gate as an inequality detector, as a parity element and as a controlled inverter, and justify each use algebraically.
- Build a wide gate from two-input gates, and re-read the same physical device under positive and negative logic.
Chapters 1 to 4 fixed how quantities are written down in a two-valued alphabet. Nothing so far actually does anything with those bits. This chapter introduces the elements that do: the logic gates, seven of which account for essentially every combinational circuit in the rest of the course.
A gate is a small amplifier with a very particular transfer characteristic. Its output settles to one of two levels according to a rule applied to the levels at its inputs, and it settles there quickly and at full amplitude however marginal those inputs were. Everything in Parts 2 and 4 — adders, comparators, decoders, multiplexers, the arithmetic logic unit — is a wiring pattern over these seven parts.
1 The Gate as a Decision Element
A logic gate is a combinational circuit: its output is a function of the levels at its inputs at that moment, with no dependence on what was applied earlier. The output is therefore completely determined by the input pattern, which is what makes the truth table — every input combination and the output it produces — a complete specification. With \(n\) inputs there are \(2^n\) rows.
How many distinct gates could there be? An output column of \(2^n\) rows can be filled in \(2^{2^n}\) ways, giving 16 functions of two variables and 256 of three. Only a handful are named and manufactured, because the rest are more cheaply built from those: of the sixteen, six are the gates of this chapter, two are the constants 0 and 1, four ignore one input, and the last four are the rarely packaged inhibit and implication functions.
The symbols come from ANSI/IEEE Standard 91-1984, which defines two sets: the distinctive-shape symbols of Figure 5.1, whose outline alone gives the function, and the rectangular-outline symbols, in which every gate is a box with a qualifier such as & or ≥1 inside it. This course uses the distinctive shapes, as textbooks and data sheets do.
Three features of Figure 5.1 carry meaning. The flat back and semicircular front belong to AND; the curved back and pointed nose belong to OR; and the small circle at an output — the bubble — always means inversion, so each gate in the lower row is the gate above it with an inverter attached. The extra curved line across the inputs of the XOR shield distinguishes exclusive from inclusive OR, and it is the detail students most often leave out.
Positive logic is assumed throughout: the more positive voltage is logic 1. Complementation is written \(\overline{A}\) in equations and A′ in tables and figures, where an overbar is awkward to draw. The seven functions, in one place, are:
| A | B | A · B AND | A + B OR | (A · B)′ NAND | (A + B)′ NOR | A ⊕ B XOR | (A ⊕ B)′ XNOR | A′ NOT |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
Read it column by column rather than row by row. Each column is a complete definition of one gate, and every later result in this chapter is this table viewed from a different direction.
2 AND, OR and NOT: The Three Primitives
The three primitive operations have exact counterparts in a switch network, and the analogy makes the algebra of Chapter 6 feel inevitable rather than arbitrary.
The AND function is two switches in series feeding a lamp: it lights only if both are closed. The output is 1 only when every input is 1, so exactly one row of the \(2^n\)-row table gives a 1. It is written as a product, \(Y = A \cdot B\) or \(Y = AB\), and the notation is not an accident — over the values 0 and 1, Boolean AND and ordinary multiplication agree in all four rows.
The OR function is two switches in parallel: the lamp lights if either is closed, or both. The output is 0 only when every input is 0. It is written as a sum, \(Y = A + B\), and here the arithmetic analogy breaks in one place: \(1 + 1 = 1\), because there is no value above 1 to carry into. That single difference is why \(A + A = A\) is a theorem in Chapter 6 and nonsense in ordinary algebra.
The NOT function, or inverter, has one input and produces its complement, \(Y = \overline{A}\) — a single transistor stage in TTL, a complementary pair in CMOS.
A 1 kHz square wave must reach a counter only while a control line EN is high, and the counter must see a steady 0 the rest of the time. Which gate, and what happens if you choose NAND instead?
An AND gate with the clock on one input and EN on the other does exactly this: with \(EN = 1\), \(Y = 1 \cdot CLK = CLK\); with \(EN = 0\), \(Y = 0 \cdot CLK = 0\). The identities used, \(1 \cdot A = A\) and \(0 \cdot A = 0\), are the first postulates of Chapter 6.
A NAND gives \(Y = \overline{EN \cdot CLK}\). While enabled it passes an inverted clock, and while disabled it idles at 1 rather than 0. The inversion is harmless — it only changes which edge the counter responds to — but the idle level is not: the fall of EN produces a rising edge at the NAND output, and an edge-triggered counter gains a spurious count. Chapter 23 shows the same failure in ripple-counter reset logic.
The 74-series parts are the 7408 (quad two-input AND), the 7432 (quad OR) and the 7404 (hex inverter). A 14-pin package holds four two-input gates or six inverters, so gate count translates into package count in units of four or six, not one.
3 NAND and NOR: The Gates Silicon Prefers
NAND and NOR are AND and OR followed by an inverter: \(Y = \overline{AB}\) and \(Y = \overline{A + B}\). Nothing about them is new as a function, yet they are the gates a real process builds, and AND and OR are the ones that cost extra. That reversal is worth explaining.
A CMOS gate is a pull-down network of n-channel transistors with a complementary p-channel pull-up. Series n-channel devices pull the output low when all inputs are high — a NAND; parallel ones pull it low when any input is high — a NOR. Both are naturally inverting, because the pull-down network conducts when the inputs are asserted. A non-inverting AND needs an added inverter stage, so a two-input CMOS AND costs six transistors where the NAND costs four. Chapter 14 draws these networks; the consequence is that the inverting gates are the cheap ones.
The second reason is completeness: either gate alone realises all three primitives, so any function can be built from NAND gates alone or NOR gates alone. Chapter 10 gives the conversion procedure; for now, note that tying both inputs of a NAND together gives \(\overline{A \cdot A} = \overline{A}\).
A three-input NAND is \(\overline{ABC}\), which is 0 for exactly one input pattern. Feeding a two-input NAND's output into another two-input NAND gives \(\overline{\overline{AB} \cdot C}\), which by De Morgan is \(AB + \overline{C}\) — a completely different function that is 0 for three of the eight patterns. To widen an AND family correctly, cascade the non-inverting gates and invert once at the end. The same warning applies to NOR: \(\overline{\overline{A+B}+C}\) is \((A+B)\overline{C}\), not \(\overline{A+B+C}\).
The parts are the 7400 (quad two-input NAND) and 7402 (quad NOR), with the 7410, 7420 and 7430 giving three, four and eight inputs. There is no eight-input NOR, for the electrical reason set out in Chapter 13.
4 XOR and XNOR: Inequality, Parity and Controlled Inversion
The exclusive-OR outputs 1 when its inputs differ: \(Y = \overline{A}B + A\overline{B}\), written \(A \oplus B\). The exclusive-NOR is its complement, \(Y = \overline{A}\,\overline{B} + AB\), which is 1 when they agree. Neither is a primitive; both earn a symbol because the functions appear constantly. Four readings of the same gate are useful, and each is the entry point to a later chapter.
- Inequality detector. \(A \oplus B = 1\) exactly when \(A \neq B\), so XNOR is an equality detector; the comparator of Chapter 17 is one XNOR per bit position feeding an AND.
- Modulo-2 sum. \(A \oplus B\) is the sum bit of a half adder, with \(AB\) as the carry: XOR is binary addition with the carry taken elsewhere. Chapter 16 starts here.
- Parity element. XOR is associative, so a tree of XOR gates over \(n\) inputs gives 1 whenever an odd number of them is 1 — the parity generators of Chapter 17 and the Hamming encoder of Chapter 4.
- Controlled inverter. Since \(0 \oplus D = D\) and \(1 \oplus D = \overline{D}\), one input decides whether the other passes unchanged or complemented. The adder-subtractor of Chapter 16 is an adder with a row of XOR gates on one operand.
The identities behind those readings are worth memorising, and each is confirmed by a two-row table:
The first two are the controlled-inverter property. The last two say that XOR-ing a variable with itself destroys it — the basis of the parity check, in which a word XOR-ed with the parity bit computed from it gives 0 if nothing has changed.
Two four-bit words \(A_3A_2A_1A_0\) and \(B_3B_2B_1B_0\) are equal only if every bit position matches. Design a circuit whose output \(EQ\) is 1 exactly when the words are equal.
Position \(i\) matches when \(A_i \oplus B_i = 0\), that is when \(\overline{A_i \oplus B_i} = 1\). All four must match at once, so the XNOR outputs feed a four-input AND:
Five gates for a function whose truth table has \(2^8 = 256\) rows. Writing that table out and minimising it would be hopeless; recognising the structure gives the answer in one line. Chapter 17 extends the idea to greater-than and less-than.
One caution about wide gates. A multi-input XOR is the odd function, and a cascade of two-input XOR gates realises it correctly because XOR is associative. XNOR does not behave so conveniently: cascading two XNOR gates over three variables gives \(A \oplus B \oplus C\), the odd function, not the even function a true three-input XNOR would produce. The 7486 is a quad two-input XOR, and there is no standard wide XNOR.
5 Multi-Input Gates, Fan-In and Gate Delay
AND, OR, NAND, NOR and XOR all extend to more than two inputs by the same one-line rule as before: AND is 1 when every input is 1, OR is 0 when every input is 0, XOR is 1 when an odd number of inputs is 1, and NAND and NOR are the complements of the first two. The number of inputs a gate is built with is its fan-in.
Fan-in cannot grow without limit. A wide CMOS NAND puts many n-channel devices in series, and each one raises the on-resistance of the pull-down path, so the fall time grows roughly in proportion to fan-in while the rise time does not. The gate becomes slow and its threshold drifts. A process library therefore stops at about four inputs and builds anything wider from those, in one of two ways.
Both arrangements use three gates, and in general an \(n\)-input function needs \(n-1\) two-input gates however they are wired. What differs is the number of gate delays. The balanced tree has \(\lceil \log_2 n \rceil\) levels; the cascade has \(n-1\). For four inputs that is two against three, which hardly matters. For eight it is three against seven, and with 5 ns gates that is 15 ns against 35 ns on a path that may already be critical.
Only 7408 (AND) and 7404 (inverter) packages are available. Build \(Y = \overline{ABCDEFGH}\) and find its delay if each AND has \(t_{pd} = 7\ \text{ns}\) and the inverter 5 ns.
Seven AND gates form the tree — four take the inputs in pairs, two combine those, one combines the last two — and an inverter completes the NAND. That is two 7408 packages with one gate spare, plus one 7404.
Wired as a cascade the same seven gates give \(7 \times 7 + 5 = 54\ \text{ns}\) — more than twice as long for identical parts. When gate count is fixed, the tree costs nothing and buys speed.
Two practical points. An unused input must never be left floating: a floating TTL input reads as a noisy 1, and a floating CMOS input can leave both transistors partly on. Tie a spare AND or NAND input to logic 1 and a spare OR or NOR input to logic 0 — the values that leave the function unchanged. And tying two inputs of one gate together works logically, \(A \cdot A = A\), but doubles the load on whatever drives them.
6 Timing Diagrams: One Pair of Inputs, Seven Outputs
A truth table says what a gate does; it says nothing about when. A timing diagram plots input and output levels against time on a common axis, and it is the form in which a logic analyser or a simulator presents a circuit in the laboratory. Reading one fluently is a separate skill, acquired by driving every gate with the same pair of waveforms and comparing. Figure 5.4 does that, with inputs chosen so that the four combinations 00, 10, 01 and 11 each occur twice — the pattern repeats, so a mistake shows up as an asymmetry.
Check the traces against the columns of the table. The AND output is high only in the fourth and eighth slots, the two in which both inputs are high; the OR output is low only in the first and fifth; NAND and NOR are the exact mirror images, which is what an output bubble looks like drawn as a waveform. The XOR output is high in the slots where the inputs differ, and so runs at twice the frequency of the slower input — a fact used in frequency doublers and in phase detectors. Figure 5.4 has ideal vertical edges and no delay, which is how a truth table would draw it if it could. A real trace differs in three ways.
- Each output edge lags the input edge that caused it by \(t_{pd}\), and the rising and falling delays \(t_{PLH}\) and \(t_{PHL}\) are unequal — about 9 ns and 10 ns for a 74LS00.
- Edges have finite rise and fall times, so the transitions are ramps, not steps.
- Where two inputs change at nominally the same instant but arrive by paths of unequal delay, the output can produce a brief unwanted pulse — a glitch — though the steady-state algebra forbids it. Chapter 11 is devoted to these hazards, and they are visible only on a timing diagram.
That last point is why this section exists: a circuit can be algebraically correct and still fail, and the timing diagram is where the failure becomes visible.
7 Positive and Negative Logic
Everything so far has assumed the more positive voltage means 1. That assignment is a convention imposed by the reader, not a property of the circuit, and reversing it renames the function without changing a transistor. Consider a device whose measured behaviour is this: the output sits at the high voltage H unless both inputs are at H, when it goes to the low voltage L.
| Measured voltages | Positive logic (H = 1) | Negative logic (H = 0) | ||||||
|---|---|---|---|---|---|---|---|---|
| A | B | Y | A | B | Y | A | B | Y |
| L | L | H | 0 | 0 | 1 | 1 | 1 | 0 |
| L | H | H | 0 | 1 | 1 | 1 | 0 | 0 |
| H | L | H | 1 | 0 | 1 | 0 | 1 | 0 |
| H | H | L | 1 | 1 | 0 | 0 | 0 | 1 |
The centre block is a NAND: the output is 0 only for the pattern 11. Sort the right-hand block into the usual counting order 00, 01, 10, 11 and it reads 1, 0, 0, 0 — output 1 only for 00, which is a NOR. Same device, same measurements, two names.
A positive-logic AND is a negative-logic OR, a positive-logic NAND is a negative-logic NOR, and inversions are unaffected because complementing both the inputs and the output of an inverter leaves it an inverter. This is the same interchange that Chapter 6 derives algebraically as De Morgan's theorem and draws as bubble-pushing. Here it arises purely from relabelling.
The convention matters because active-low signals are everywhere. A chip select, an interrupt request and a bus enable are almost always asserted by being pulled low, since a totem-pole or open-drain output sinks current far more comfortably than it sources it; a data sheet marks such a signal \(\overline{CS}\) or CS#. A gate collecting several active-low requests is drawn as an OR with bubbles on its inputs and output — which, as De Morgan says, is physically a NAND. Chapter 10 develops this mixed-logic style; the bubbles state the assertion level, they do not add inverters.
8 Summary and Key Results
| Gate | Expression | Output is the odd one out when... | 74-series part |
|---|---|---|---|
| AND | \(Y = AB\) | 1 for exactly one pattern (11) | 7408 |
| OR | \(Y = A + B\) | 0 for exactly one pattern (00) | 7432 |
| NOT | \(Y = \overline{A}\) | single input; complement | 7404 |
| NAND | \(Y = \overline{AB}\) | 0 only for 11; functionally complete | 7400 |
| NOR | \(Y = \overline{A + B}\) | 1 only for 00; functionally complete | 7402 |
| XOR | \(Y = A \oplus B\) | 1 when the inputs differ; parity element | 7486 |
| XNOR | \(Y = \overline{A \oplus B}\) | 1 when the inputs agree; equality element | 74266 |
9 Common Mistakes
Two two-input NANDs in series give \(\overline{\overline{AB}\,C} = AB + \overline{C}\), not \(\overline{ABC}\): it is 0 for three of the eight patterns where the true three-input NAND is 0 for one. Cascade the non-inverting gate and invert once at the end, or use a genuine three-input part. The same error with NOR gives \((A+B)\overline{C}\).
The only difference between the OR and XOR symbols is the extra curved line across the inputs, and leaving it off turns an exclusive-OR into an inclusive-OR. The two agree in three rows of four and differ only when both inputs are 1, so the wrong symbol usually survives casual testing and fails on exactly one pattern — the hardest fault to find on a board.
An unconnected TTL input floats to about 1.4 V and behaves like a noisy 1; an unconnected CMOS input can sit near the threshold with both transistors conducting, drawing tens of milliamps. Tie spare AND and NAND inputs to \(V_{CC}\) through a resistor and spare OR and NOR inputs to ground — the values that leave the function unchanged.
10 Chapter Review
1. A two-input gate produces the output sequence
1 0 0 0for the input sequence \(AB = \) 00, 01, 10, 11. Name the gate and give two equivalent Boolean expressions for it.The output is 1 only when both inputs are 0, so it is a NOR gate: \(Y = \overline{A + B}\) from the definition, and \(Y = \overline{A}\,\overline{B}\) by De Morgan — the same gate read as an AND of complemented inputs.
2. Show that a NAND gate with both inputs tied together is an inverter, and explain the drawback of using it that way.
With both inputs at \(A\) the output is \(\overline{A \cdot A} = \overline{A}\), by idempotence \(A \cdot A = A\). It is a valid inverter, used constantly when a spare NAND is available. The drawback is loading: the driving signal now feeds two gate inputs, so it spends two unit loads of the driver's fan-out budget rather than one.
3. Four inputs are combined by three cascaded two-input XOR gates. For how many of the sixteen input combinations is the output 1, and why?
Eight. XOR is associative, so the cascade computes \(D_3 \oplus D_2 \oplus D_1 \oplus D_0\), which is 1 whenever an odd number of inputs is 1. There are \(\binom{4}{1} = 4\) combinations with one input high and \(\binom{4}{3} = 4\) with three — eight, exactly half of sixteen, as the odd function always is.
4. A 16-input AND function is required using only two-input AND gates with \(t_{pd} = 6\ \text{ns}\). Give the gate count and the delay for a balanced tree and for a cascade.
Either arrangement needs \(16 - 1 = 15\) gates. The tree has \(\lceil \log_2 16 \rceil = 4\) levels, giving \(4 \times 6 = 24\ \text{ns}\); the cascade has 15 levels, giving \(15 \times 6 = 90\ \text{ns}\) — nearly four times worse for identical hardware, since only the wiring differs.
5. A device outputs the low voltage whenever at least one of its two inputs is at the low voltage. What function is it under positive logic, and what under negative logic?
Under positive logic (H = 1) the output is 1 only when both inputs are 1 — an AND. Under negative logic (H = 0) the same rows re-labelled give 1 whenever at least one input is 1 — an OR. Interchanging the voltage assignments interchanges AND and OR.