Logic Gates

Logic gates are the fundamental building blocks of every digital circuit. The processor executing this sentence, the RAM holding it, the SSD storing it, and the GPU rendering it are all — at the transistor level — vast oceans of a few simple gate types wired together. For the OCR H446 specification you must know AND, OR, NOT, NAND, NOR, and XOR gates: how each behaves, the standard symbol used to draw it, its truth table, and the Boolean expression it implements. You also need to understand functional completeness — the remarkable fact that NAND alone (or NOR alone) is enough to build any digital system.

This lesson treats the gate as the bridge between two layers of the course: the abstract algebra of Booleans (truth values manipulated by laws) and the concrete electronics of a circuit (voltages flowing through silicon). Get the gates secure here and the rest of 1.4.3 — truth tables, algebraic laws, De Morgan's, simplification — becomes a matter of fluent manipulation rather than memorisation.

---

Spec Mapping

This lesson addresses the logic-gate strand of OCR H446 section 1.4.3 (Boolean algebra):

• Recognising and using the six standard logic gates: AND, OR, NOT, NAND, NOR and XOR (exclusive OR).
• Knowing the behaviour of each gate expressed as a truth table and as a Boolean expression.
• Drawing and recognising the standard distinctive-shape symbols (and being aware that rectangular IEC symbols exist).
• Understanding that NAND and NOR are functionally complete (universal) — any Boolean function can be realised using only one of these gate types.

These ideas feed directly into the later 1.4.3 content on building and simplifying logic circuits, and they underpin the architecture topics in 1.1 (the ALU and control unit are nothing more than large, purposeful arrangements of these gates).

---

What Is a Logic Gate?

A logic gate is an electronic component that takes one or more binary inputs (0 or 1) and produces a single binary output determined by a fixed logical rule. The gate is the physical embodiment of a Boolean operation: where the algebra writes $Q = A \cdot B$Q=A⋅B, the hardware places an AND gate.

Concept	Detail
Inputs	Binary values: 0 (LOW / FALSE) or 1 (HIGH / TRUE)
Output	A single binary value fixed by the gate's rule
Voltage levels	Conventionally 0 V for logic 0, and 3.3 V or 5 V for logic 1 (the exact value depends on the logic family)
Building material	Each gate is itself built from transistors acting as voltage-controlled switches

The crucial abstraction is that, once a gate is built, we stop thinking about volts and transistors and reason purely in 0s and 1s. This is layered abstraction — the same principle that lets a programmer ignore machine code, applied one level lower.

Positive logic and noise margins

By convention this course uses positive logic: the higher voltage represents 1 and the lower voltage represents 0. (Negative-logic families exist, where the assignment is reversed, but you will not be examined on them.) Real gates do not require an exact voltage — they accept a band. Anything above a defined threshold counts as 1, anything below a lower threshold counts as 0, and the gap between them is the noise margin that lets digital signals survive electrical interference. This tolerance is precisely why digital electronics is so robust compared with analogue: small voltage wobbles are quietly rounded back to a clean 0 or 1 at every gate.

Combinational vs sequential

The six gates in this lesson are combinational: the output depends only on the present inputs, with no memory of the past. Stick a stable input pattern in and (after a tiny propagation delay) you always get the same output. Later in 1.4.3 you will meet sequential circuits — flip-flops and latches — whose output also depends on stored state. Everything here is the combinational foundation those sequential circuits are built upon.

---

The NOT Gate (Inverter)

The NOT gate has a single input and produces the complement (logical opposite) of that input.

The Boolean expression is written with an overbar:

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

It is also written as $A'$A′ or $\lnot A$¬A. The overbar is the OCR house notation and the one you should use.

Truth table:

A	$Q = \overline{A}$Q=A
0	1
1	0

The standard symbol is a triangle pointing right with a small circle — the inversion bubble — at its output:

flowchart LR
    A["A"] --> NOT["NOT (triangle + bubble)"]
    NOT --> Q["Q = NOT A"]

Key Term: The small circle on a gate symbol denotes inversion. It appears on NOT, NAND and NOR. Spotting bubbles is the fastest way to read an unfamiliar circuit: a bubble means "and then flip the output".

---

The AND Gate

The AND gate outputs 1 only when every input is 1.

$Q = A \cdot B$Q=A⋅B

(also written $A \land B$A∧B or simply $AB$AB). The dot is the OCR convention; when two variables sit side by side, AND is implied.

Truth table:

A	B	$Q = A \cdot B$Q=A⋅B
0	0	0
0	1	0
1	0	0
1	1	1

Think of AND as a series circuit: two switches in a line, where current reaches the lamp only if both are closed. The distinctive-shape symbol has a flat left edge and a semicircular right edge (a capital D shape). The rectangular IEC symbol is a box labelled &.

flowchart LR
    A1["A"] --> AND1["AND"]
    B1["B"] --> AND1
    AND1 --> QA["Q = A . B"]

A useful intuition: AND behaves like logical "all of" — $A \cdot B \cdot C \cdot D = 1$A⋅B⋅C⋅D=1 only if every input is 1. The moment a single 0 appears anywhere, the whole product collapses to 0. This is the null law ($A \cdot 0 = 0$A⋅0=0) in action and explains why one stuck-at-0 input disables an entire AND chain.

---

The OR Gate

The OR gate outputs 1 when at least one input is 1.

$Q = A + B$Q=A+B

(also written $A \lor B$A∨B). Note the deliberate clash with arithmetic: in Boolean algebra + means OR, not addition — $1 + 1 = 1$1+1=1 here, not 2.

Truth table:

A	B	$Q = A + B$Q=A+B
0	0	0
0	1	1
1	0	1
1	1	1

Think of OR as a parallel circuit: two switches side by side, where closing either one lets current through. The distinctive-shape symbol has a curved left edge and a pointed right tip (like a shield). The IEC symbol is a box labelled ≥1 (meaning "one or more inputs high").

flowchart LR
    A3["A"] --> OR1["OR"]
    B3["B"] --> OR1
    OR1 --> QO["Q = A + B"]

OR is the logical "any of": $A + B + C = 1$A+B+C=1 if at least one input is 1. The mirror image of the AND collapse applies here — a single stuck-at-1 input forces the whole sum to 1 ($A + 1 = 1$A+1=1, the OR null law), regardless of every other input. Series-and-parallel is the cleanest mental model for the AND/OR pair, and it is worth carrying into the circuits topic later in 1.4.3.

---

The NAND Gate

NAND means NOT AND — an AND gate immediately followed by an inverter. The output is 1 unless every input is 1.

$Q = \overline{A \cdot B}$Q=A⋅B

Truth table:

A	B	$A \cdot B$A⋅B	$Q = \overline{A \cdot B}$Q=A⋅B
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

NAND is the exact inverse of AND: read down the AND output column (0,0,0,1) and the NAND column (1,1,1,0) and you will see every value flipped. The symbol is the AND shape with an inversion bubble on its output.

Exam Tip: NAND is a universal (functionally complete) gate — every other gate can be built from NAND alone. This is a frequently examined fact; commit it to memory and be ready to demonstrate it (see the worked example below).

---

The NOR Gate

NOR means NOT OR — an OR gate followed by an inverter. The output is 1 only when every input is 0.

$Q = \overline{A + B}$Q=A+B​

Truth table:

A	B	$A + B$A+B	$Q = \overline{A + B}$Q=A+B​
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

NOR is the inverse of OR. Its symbol is the OR shape with an inversion bubble on the output. Like NAND, NOR is universal: any Boolean function can be built from NOR gates alone.

---

The XOR Gate (Exclusive OR)

The XOR gate outputs 1 when the inputs differ.

$Q = A \oplus B$Q=A⊕B

The $\oplus$⊕ symbol (a plus inside a circle) is the standard notation. XOR can also be written out in basic gates as $Q = \overline{A} \cdot B + A \cdot \overline{B}$Q=A⋅B+A⋅B — a fact you will use constantly in adder circuits.

Truth table:

A	B	$Q = A \oplus B$Q=A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

XOR differs from OR in exactly one row: when both inputs are 1, OR gives 1 but XOR gives 0. The symbol is the OR shape with an extra curved line drawn just before the curved input edge. The IEC label is =1 (exactly one input high). XOR is not universal.

Key Term: XOR is the difference detector — output 1 when the inputs disagree, 0 when they agree. The complementary gate, XNOR ($\overline{A \oplus B}$A⊕B​), is the equality detector.

---

Complete Gate Summary Table

Gate	Expression	Output = 1 when…	Universal?
NOT	$\overline{A}$A	input is 0	No
AND	$A \cdot B$A⋅B	all inputs are 1	No
OR	$A + B$A+B	at least one input is 1	No
NAND	$\overline{A \cdot B}$A⋅B	not all inputs are 1	Yes
NOR	$\overline{A + B}$A+B​	all inputs are 0	Yes
XOR	$A \oplus B$A⊕B	inputs differ	No

---

Functional Completeness: Building Any Gate from NAND

A set of gates is functionally complete if every possible Boolean function can be expressed using only that set. The standard complete set is {AND, OR, NOT}. The striking result is that NAND on its own is complete, because NAND can reproduce all three of {AND, OR, NOT}:

NOT from NAND — feed the same signal to both inputs:

$\overline{A \cdot A} = \overline{A}$A⋅A=A

(since $A \cdot A = A$A⋅A=A by the idempotent law). One NAND gives an inverter.

AND from NAND — a NAND followed by a NAND-inverter:

$\overline{\overline{A \cdot B}} = A \cdot B$A⋅B=A⋅B

OR from NAND — invert each input first, then NAND:

$\overline{\overline{A} \cdot \overline{B}} = A + B$A⋅B=A+B

The last line is De Morgan's law read backwards, and it needs three NAND gates (two as inverters, one to combine). Because {AND, OR, NOT} is complete and all three are reproducible from NAND, NAND is complete. The identical argument works for NOR.

flowchart LR
    subgraph OR_from_NAND["OR built from 3 NANDs"]
        A2["A"] --> N1["NAND (as NOT)"]
        B2["B"] --> N2["NAND (as NOT)"]
        N1 --> N3["NAND"]
        N2 --> N3
        N3 --> Q2["Q = A + B"]
    end

Why this matters in the real world: a chip foundry can mass-produce a single, highly optimised NAND cell and tile millions of copies, rather than fabricating six different gate layouts. Uniformity lowers cost and improves yield — abstraction paying a concrete dividend.

The same argument for NOR

NOR is likewise complete. Tying both NOR inputs together gives an inverter, $\overline{A + A} = \overline{A}$A+A​=A (using $A + A = A$A+A=A). OR comes from a NOR followed by a NOR-inverter, $\overline{\overline{A + B}} = A + B$A+B​​=A+B. And AND emerges via De Morgan, $\overline{\overline{A} + \overline{B}} = A \cdot B$A+B​=A⋅B. So {NAND} and {NOR} are each, on their own, a complete basis. A handy way to remember the pattern: a single universal gate behaves like a NOT when its inputs are tied together, and like its parent gate once a second copy un-inverts the output.

Why XOR is not universal

It is worth pinning down why XOR fails the test, because exam distractors exploit this. XOR (and XNOR) are linear functions over the field GF(2): an XOR network can only ever produce the parity of a subset of its inputs. Crucially, with XOR alone you cannot manufacture the constant 1 from independent variables, nor the AND function — both are non-linear. Because {AND, OR, NOT} cannot be rebuilt from XOR alone, XOR is not functionally complete. Useful, ubiquitous in arithmetic and error-checking, but not universal.

---

XNOR: The Equality Detector

The complement of XOR is XNOR (exclusive-NOR):

$Q = \overline{A \oplus B} = A \cdot B + \overline{A} \cdot \overline{B}$Q=A⊕B​=A⋅B+A⋅B

A	B	$A \oplus B$A⊕B	$Q = \overline{A \oplus B}$Q=A⊕B​
0	0	0	1
0	1	1	0
1	0	1	0
1	1	0	1

XNOR outputs 1 exactly when the two inputs are equal, which makes it the building block of comparator circuits — wire one XNOR per bit-pair and AND the results to test two multi-bit numbers for equality. OCR does not require XNOR as a named gate to the same degree as the core six, but recognising it as "the equality gate / NOT-XOR" is expected and frequently rewarded in circuit-reading questions.

---

Gates with More Than Two Inputs

AND, OR, NAND, NOR and XOR all generalise to more than two inputs. A 3-input AND outputs 1 only when all three inputs are 1:

A	B	C	$Q = A \cdot B \cdot C$Q=A⋅B⋅C
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

A 3-input OR outputs 1 whenever any input is 1. Multi-input XOR is subtler: $A \oplus B \oplus C$A⊕B⊕C outputs 1 when an odd number of inputs are 1 — which is exactly why XOR trees are used to compute parity bits for error detection (a synoptic link to 1.3 data transmission).

A practical note: a hardware "3-input AND" may physically be two 2-input ANDs in series, because real logic families limit fan-in (the number of inputs a single gate can sensibly accept). The associative law $A \cdot B \cdot C = (A \cdot B) \cdot C$A⋅B⋅C=(A⋅B)⋅C guarantees this rewiring leaves the logic unchanged — your first hint of how the algebraic laws license real engineering decisions.

---

A First Look at Gate Delay

Although a gate is drawn as an instantaneous black box, a real gate takes a small but non-zero time — its propagation delay — to settle after its inputs change (typically a few nanoseconds in modern silicon, though the exact figure is family-dependent and not something to memorise). Delays add up along a path: a signal threading through three gates in sequence experiences roughly three gate-delays before the output is valid. This is why the depth of a circuit (its longest gate path) caps the maximum clock speed of a processor, and it is a second reason simplification matters — fewer gates in the critical path means a faster circuit, not merely a cheaper one. You will meet timing again in the sequential-logic and architecture topics; for now, simply hold the idea that "logic takes time" alongside "logic costs gates".

---

Worked Example: Tracing a Mixed Expression

Question: Construct the truth table for $Q = (A \cdot B) + \overline{C}$Q=(A⋅B)+C.

• Step 1 — count variables. Three inputs (A, B, C), so $2^3 = 8$23=8 rows.
• Step 2 — add intermediate columns for $A \cdot B$A⋅B and $\overline{C}$C.
• Step 3 — OR the two intermediates for the final column.

A	B	C	$A \cdot B$A⋅B	$\overline{C}$C	$Q = (A \cdot B) + \overline{C}$Q=(A⋅B)+C
0	0	0	0	1	1
0	0	1	0	0	0
0	1	0	0	1	1
0	1	1	0	0	0
1	0	0	0	1	1
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	1	0	1

Exam Tip: Always include the intermediate columns. They earn method marks even if a slip creeps into the final column, and they make your reasoning auditable.

---

Worked Example: Reading a Gate Network

Symbols become useful only when you can read a network of them. Consider the following two-level circuit:

flowchart LR
    A["A"] --> G1["AND"]
    B["B"] --> G1
    B2["B"] --> G2["NOT"]
    G2 --> G3["AND"]
    C["C"] --> G3
    G1 --> G4["OR"]
    G3 --> G4
    G4 --> Q["Q"]

Tracing from the inputs:

• The top AND computes $A \cdot B$A⋅B.
• The NOT computes $\overline{B}$B, which feeds the lower AND alongside C, giving $\overline{B} \cdot C$B⋅C.
• The final OR combines the two AND outputs:

$Q = (A \cdot B) + (\overline{B} \cdot C)$Q=(A⋅B)+(B⋅C)

Building the truth table confirms the behaviour:

A	B	C	$A \cdot B$A⋅B	$\overline{B} \cdot C$B⋅C	$Q$Q
0	0	0	0	0	0
0	0	1	0	1	1
0	1	0	0	0	0
0	1	1	0	0	0
1	0	0	0	0	0
1	0	1	0	1	1
1	1	0	1	0	1
1	1	1	1	0	1

This circuit is in fact a 2-to-1 multiplexer: B is the select line, choosing A when $B = 1$B=1 and C when $B = 0$B=0. The same expression turns up again in the adders and circuit-design lessons — proof that a handful of gates, well combined, builds genuinely useful components.

---

Worked Example: Counting the Gate Cost

A second skill the examiner rewards is reasoning about how many gates an expression needs — the bridge to circuit cost and to simplification. Take:

$Q = A \cdot B + A \cdot \overline{B}$Q=A⋅B+A⋅B

A literal, term-by-term implementation needs: one NOT (for $\overline{B}$B), two ANDs (one per product term), and one OR — four gates. But applying the distributive and inverse laws,

$A \cdot B + A \cdot \overline{B} = A \cdot (B + \overline{B}) = A \cdot 1 = A,$A⋅B+A⋅B=A⋅(B+B)=A⋅1=A,

so the entire circuit reduces to a plain wire — zero gates. The point for this lesson is not the algebra (that comes later) but the mindset: every gate you can remove saves silicon area, power and propagation delay. Gate-counting is how you turn a correct circuit into an efficient one.

Exam Tip: When a question says "implement using the fewest gates", do the algebra first, then draw. Drawing the raw expression and counting gates from that almost always overshoots the mark scheme's expected minimum.

---

Exam Tips

• Learn the symbols both ways round. You must be able to draw a named gate and name a drawn one. The inversion bubble is the single most important detail to get right.
• Quote the overbar notation. Write NOT as $\overline{A}$A, AND as $A \cdot B$A⋅B, OR as $A + B$A+B, XOR as $A \oplus B$A⊕B. Consistency reads as fluency.
• Memorise the universal-gate fact. "NAND and NOR are functionally complete; XOR is not" is almost guaranteed to appear in some form.
• Show intermediate truth-table columns to bank method marks.
• Watch the 1-1 row whenever OR and XOR are both in play — it is the only place they differ and the most common source of dropped marks.
• Read + as OR, never as arithmetic inside Boolean working.

---

Synoptic Links

• The ALU and adders (1.4.3 / 1.1): the half adder is one XOR (sum) plus one AND (carry); the full adder chains two of these. Every arithmetic operation a CPU performs ultimately reduces to gate networks like these.
• The control unit and FDE cycle (1.1): decoders that translate an opcode into control signals are AND/OR gate trees. The logic you meet here is what makes "decode" a physical, not magical, step.
• Data transmission and parity (1.3): multi-input XOR computes the parity bit used to detect single-bit transmission errors.
• K-maps and circuit cost (1.4.3): the gate count of an expression is a direct cost and speed metric; simplification (later lessons) literally removes gates from the silicon.
• Programming operators (2.x): the bitwise AND, OR, NOT and XOR operators in high-level languages map one-to-one onto these gates applied across every bit of a word.

---

Common Errors & A-Level Misconceptions

• Confusing OR with XOR. The 1-1 row is the whole difference: OR gives 1, XOR gives 0. Candidates routinely use OR where the situation (e.g. an adder sum bit) needs XOR.
• Reading + as arithmetic. In Boolean algebra $1 + 1 = 1$1+1=1. Treating it as 2 (or as a carry) is a classic slip.
• Forgetting the inversion bubble. Drawing a NAND as a plain AND, or a NOR as a plain OR, changes the function entirely. Always draw — and always look for — the bubble.
• Claiming XOR is universal. Only NAND and NOR are universal. XOR cannot even produce a constant 0 or 1 without help, so it fails completeness.
• Mixing up "universal" with "most common". AND/OR/NOT are the most intuitive set, but NAND/NOR are the universal ones. Examiners test the distinction.
• Inconsistent notation. Mixing $\overline{A}$A, $A'$A′ and $\lnot A$¬A within one answer looks careless. Pick the overbar and stay with it.

---

Specimen Question

A logic circuit is to be built using only NAND gates. (a) Draw a truth table for a NAND gate. [1] (b) Show, using Boolean expressions, how a NAND gate can be configured to behave as a NOT gate and as an AND gate. [3] (c) Explain what is meant by describing NAND as a functionally complete (universal) gate, and state one practical manufacturing advantage that follows from this property. [3] [Total: 7 marks]

AO breakdown: AO1 (knowledge of gate behaviour and terminology) 3 marks; AO2 (application — configuring NAND to emulate other gates) 3 marks; AO3 (linking the property to a real manufacturing benefit) 1 mark.

Mid-band response

(a) Truth table: inputs 00→1, 01→1, 10→1, 11→0.

(b) For NOT, connect A to both inputs: $\overline{A \cdot A} = \overline{A}$A⋅A=A. For AND, take a NAND and then put its output through another NAND used as a NOT: $\overline{\overline{A \cdot B}} = A \cdot B$A⋅B=A⋅B.

(c) Functionally complete means you can build any logic function out of just NAND gates. The advantage is that the factory only has to make one type of gate, which is cheaper.

Examiner-style commentary: M1 correct NAND truth table; M1 NOT-from-NAND expression; M1 AND-from-NAND expression; M1 definition of functional completeness; M1 manufacturing advantage. The candidate secures most marks. The completeness definition is correct but bald — it states that any function can be built without making clear that this rests on NAND reproducing the complete set {AND, OR, NOT}. The cost point is valid but undeveloped.

Top-band response

(a) NAND truth table: 00→1, 01→1, 10→1, 11→0 (it is the inverse of AND).

(b) NOT from NAND — tie both inputs together. Because $A \cdot A = A$A⋅A=A (idempotent law), $\overline{A \cdot A} = \overline{A}$A⋅A=A, so one NAND inverts. AND from NAND — a NAND already computes $\overline{A \cdot B}$A⋅B; feeding that into a second NAND wired as an inverter gives $\overline{\overline{A \cdot B}} = A \cdot B$A⋅B=A⋅B by double negation. (For completeness, OR from NAND uses De Morgan: $\overline{\overline{A} \cdot \overline{B}} = A + B$A⋅B=A+B, needing three NANDs.)

(c) A gate (or set of gates) is functionally complete if every Boolean function can be realised using only that gate. NAND qualifies because it can reproduce the known complete set {AND, OR, NOT}, as shown in part (b); anything expressible in those operators is therefore expressible in NAND alone. The chief manufacturing benefit is uniformity: a foundry can perfect a single optimised NAND cell and replicate it millions of times across a die rather than laying out six distinct gate types. This simplifies the design rules, improves fabrication yield, and lowers unit cost — a direct economic consequence of the completeness property.

Examiner-style commentary: All seven marks. The response not only states each NAND configuration but justifies it by naming the law involved (idempotent, double negation, De Morgan). The completeness explanation is rigorous — it grounds the claim in reproducing {AND, OR, NOT} rather than merely asserting it — and the AO3 manufacturing point is explained causally (uniform cell → yield and cost), not just named.

---

Going Further

• Build it virtually. A free logic simulator (or a circuit-drawing tool) lets you wire up the NAND-only OR gate and watch the truth table emerge — far more convincing than reading it.
• Transistor view. Investigate how a CMOS NAND is built from just four transistors (two PMOS in parallel, two NMOS in series). This is why NAND is the "natural" universal gate in CMOS: it is cheaper in transistors than the basic AND.
• Beyond two values. Read about ternary and reversible logic gates (e.g. the Toffoli gate), which matter for low-power and quantum computing — a glimpse of where the gate abstraction is heading.
• Parity in practice. Trace how a chain of XORs generates the parity bit in a serial transmission protocol, then connect it back to the 1.3 error-detection content.