Logic Circuits

A logic circuit is the physical realisation of a Boolean expression — the gates of lesson 1 wired together so that signals flow from inputs on the left to an output on the right. Everything earlier in this course was preparation for this moment: a truth table specifies a function, a Boolean expression describes it compactly, the laws and K-maps minimise it, and a logic circuit is it, in silicon. The OCR H446 specification expects you to move fluently in both directions — to derive a circuit from a Boolean expression and to derive an expression (and truth table) from a given circuit — and to reason about multi-stage circuits and the propagation delay their depth incurs.

The skill at the heart of this lesson is translation. A Boolean expression and a logic circuit are two notations for the same thing, related by a simple correspondence: every operator becomes a gate, every variable becomes an input wire, and the structure of the expression — which operation is applied last — fixes which gate sits at the output. Reading a circuit is the same correspondence run backwards: trace each wire forward, name the operation each gate performs, and assemble the sub-expressions until you reach the output. Because the mapping is exact and mechanical, neither direction should be guesswork. This lesson drills the procedure both ways with worked examples, and renders every circuit as a diagram (never as ASCII art), because in an exam a clearly drawn, fully labelled circuit is itself worth marks.

---

Spec Mapping

This lesson covers the combinational-logic-circuit strand of OCR H446 section 1.4.3 (Boolean algebra and its application):

• Constructing a logic circuit from a given Boolean expression, identifying the output gate from the last-evaluated operation and building inward.
• Deriving the Boolean expression, and hence the truth table, from a given logic circuit by tracing signals from inputs to output.
• Working with multi-level (multi-stage) combinational circuits and understanding propagation delay, circuit depth, fan-in and fan-out.
• Designing a circuit from a truth table by deriving a sum-of-products expression, minimising it, and drawing the result — and converting a design into a single gate family (NAND-only / NOR-only).

It depends on logic gates, Boolean algebra, De Morgan's laws and simplification, and it directly feeds the half-adder/full-adder and full circuit-design lessons.

---

From Boolean Expression to Circuit

The reliable procedure is to build from the output backwards:

1. Find the last operation to be evaluated — respecting brackets and the NOT-before-AND-before-OR precedence. That operation is the output gate.
2. Make each operand of that gate a sub-circuit, recursing into any compound operand.
3. Connect the input variables to the innermost gates, drawing a NOT (inverter) wherever a variable or sub-expression is complemented.
4. Label every wire — input names on the left, intermediate labels (P, R, …) on internal wires, the output name on the right.

Worked example. Draw the circuit for $Q = (A \cdot B) + \overline{C}$Q=(A⋅B)+C.

The last operation is the OR (the two bracketed-or-barred operands are combined by $+$+), so the output gate is an OR. Its two inputs are: $A \cdot B$A⋅B, which needs a 2-input AND fed by A and B; and $\overline{C}$C, which needs a NOT fed by C.

flowchart LR
    A((A)) --> AND{{"AND"}}
    B((B)) --> AND
    C((C)) --> NOT{{"NOT"}}
    AND -- "A·B" --> OR{{"OR"}}
    NOT -- "C̄" --> OR
    OR --> Q["Q"]

Three gates, two levels deep. Building from the output gate inward guarantees you never lose track of which operation combines which operands — the commonest cause of a tangled, wrong circuit.

A more involved example. Draw $Q = (A + \overline{B}) \cdot (B + C)$Q=(A+B)⋅(B+C).

The last operation is the AND joining the two brackets, so the output gate is an AND. Its left input, $A + \overline{B}$A+B, is an OR fed by A and by $\overline{B}$B (so B passes through a NOT first). Its right input, $B + C$B+C, is a second OR fed by B and C. Note that B is needed in two places — once inverted into the left OR and once direct into the right OR — which is fan-out: a single input wire driving more than one gate.

flowchart LR
    A((A)) --> OR1{{"OR"}}
    B((B)) --> NOT{{"NOT"}}
    NOT -- "B̄" --> OR1
    B --> OR2{{"OR"}}
    C((C)) --> OR2
    OR1 -- "A+B̄" --> AND{{"AND"}}
    OR2 -- "B+C" --> AND
    AND --> Q["Q"]

Four gates, two levels deep (the inverter shares level 1 with the two ORs). The discipline is identical to the simpler case — find the output gate, recurse into each operand — but this example shows two features exam circuits routinely include: an inverter buried inside a bracket, and a variable that fans out to several gates. Drawing the inverter as its own gate (rather than mentally "remembering" B is inverted) keeps the circuit honest and markable.

---

From Circuit to Boolean Expression

Run the correspondence in reverse, tracing from inputs to output:

1. Start at the input wires on the left.
2. Pass through each gate, writing the operation it performs on its inputs and giving the result an intermediate label.
3. Substitute and combine the intermediate labels until you reach the output wire.

Worked example. A circuit is wired as:

• Gate 1 — NOT, input A, output $P$P.
• Gate 2 — AND, inputs $P$P and B, output $R$R.
• Gate 3 — OR, inputs $R$R and C, output $Q$Q.

Trace it:

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

So the circuit computes $Q = \overline{A}\cdot B + C$Q=A⋅B+C. Working strictly left to right and substituting one intermediate label at a time keeps a complex schematic from overwhelming you — each gate is a single, small step.

---

From Circuit to Truth Table

Once you have the expression (or directly from the schematic), build the truth table by evaluating every input combination, showing the intermediate columns so the method is visible and checkable.

Worked example. Tabulate $Q = (A \oplus B) \cdot (B + C)$Q=(A⊕B)⋅(B+C):

A	B	C	$A \oplus B$A⊕B	$B + C$B+C	$Q$Q
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	1	0	0
1	0	1	1	1	1
1	1	0	0	1	0
1	1	1	0	1	0

The intermediate $A \oplus B$A⊕B and $B + C$B+C columns are the outputs of the two sub-circuits feeding the final AND; writing them out turns a fiddly multi-gate evaluation into eight straightforward two-column ANDs and earns method marks even if a single final value slips.

---

Worked Example: Circuit → Expression → Truth Table → Simplify

A common high-mark question hands you a schematic and asks for everything. Suppose a circuit is wired as follows:

flowchart LR
    A((A)) --> N1{{"NAND"}}
    B((B)) --> N1
    A --> OR{{"OR"}}
    C((C)) --> OR
    N1 -- "P" --> AND{{"AND"}}
    OR -- "R" --> AND
    AND --> Q["Q"]

Step 1 — derive the expression by tracing. The NAND gives $P = \overline{A \cdot B}$P=A⋅B. The OR gives $R = A + C$R=A+C. The final AND combines them:

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

Step 2 — tabulate, showing the intermediate gate outputs:

A	B	C	$P = \overline{A\cdot B}$P=A⋅B	$R = A + C$R=A+C	$Q = P\cdot R$Q=P⋅R
0	0	0	1	0	0
0	0	1	1	1	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	0	1	0
1	1	1	0	1	0

Step 3 — simplify. First expand the NAND with De Morgan's, then multiply out:

$Q = (\overline{A} + \overline{B})\cdot(A + C) \quad \text{[De Morgan 1st on } P\text{]}$Q=(A+B)⋅(A+C)[De Morgan 1st on P] $= \overline{A}\cdot A + \overline{A}\cdot C + \overline{B}\cdot A + \overline{B}\cdot C \quad \text{[distributive]}$=A⋅A+A⋅C+B⋅A+B⋅C[distributive] $= 0 + \overline{A}\cdot C + A\cdot\overline{B} + \overline{B}\cdot C \quad \text{[complement: } \overline{A}\cdot A = 0\text{]}$=0+A⋅C+A⋅B+B⋅C[complement: A⋅A=0]

The term $\overline{B}\cdot C$B⋅C is redundant (it is the consensus of $\overline{A}\cdot C$A⋅C and $A\cdot\overline{B}$A⋅B — wherever $\overline{B}\cdot C$B⋅C is 1, one of the other two is already 1), so it can be dropped:

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

Reading the truth-table output column $(0,1,0,1,1,1,0,0)$(0,1,0,1,1,1,0,0) confirms the simplified form, and the circuit drops from three gates on its critical path to two. This single worked example exercises every translation in the lesson — circuit to expression, expression to table, and algebraic minimisation — which is exactly why such questions carry high marks.

---

Multi-Level Circuits, Depth and Delay

A multi-level (or multi-stage) circuit has more than two layers of gates between input and output. Each layer a signal crosses adds one gate delay — the short but non-zero time a real gate takes to respond to a change at its inputs. The circuit depth (the number of gate levels on the longest input-to-output path, the critical path) therefore sets the circuit's overall propagation delay, and hence the maximum clock speed at which it can be used reliably.

Worked example. Consider $Q = \big((A \cdot B) \oplus (C + D)\big) \cdot \overline{D}$Q=((A⋅B)⊕(C+D))⋅D, organised in three levels:

flowchart LR
    A((A)) --> P{{"AND"}}
    B((B)) --> P
    C((C)) --> R{{"OR"}}
    D((D)) --> R
    D --> T{{"NOT"}}
    P -- "P=A·B" --> S{{"XOR"}}
    R -- "R=C+D" --> S
    S -- "S" --> Q2{{"AND"}}
    T -- "T=D̄" --> Q2
    Q2 --> Q["Q"]

• Level 1: $P = A \cdot B$P=A⋅B, $R = C + D$R=C+D, $T = \overline{D}$T=D all compute in parallel.
• Level 2: $S = P \oplus R$S=P⊕R.
• Level 3: $Q = S \cdot T$Q=S⋅T.

The critical path runs input → (AND or OR) → XOR → AND = three gates deep. If each gate has a 10 ns delay, the output is not guaranteed valid until $3 \times 10 = 30$3×10=30 ns after the inputs settle. The inverter T is not on the critical path (it is only one level deep), so it does not add to the worst-case delay — only the longest path matters.

Concept	Meaning
Fan-in	Number of inputs to a single gate
Fan-out	Number of gate inputs that one output drives
Propagation delay	Time for one gate to respond to an input change
Circuit depth	Number of gate levels on the longest (critical) path

Minimising an expression first (previous two lessons) usually reduces depth as well as gate count, shortening the critical path — which is why simplification and speed go hand in hand.

---

Designing a Circuit from a Truth Table

Given only a required behaviour, the standard route is truth table → SoP expression → minimise → draw:

1. Derive a sum-of-products expression: write one product (minterm) for each row where the output is 1, then OR them.
2. Minimise with Boolean algebra or a K-map.
3. Draw the circuit from the minimised expression.

Worked example. Design a circuit for:

A	B	Q
0	0	1
0	1	0
1	0	0
1	1	1

The output is 1 on rows 00 and 11, giving $Q = \overline{A}\cdot\overline{B} + A\cdot B$Q=A⋅B+A⋅B — the XNOR / equality function. It is already minimal in basic gates, so the circuit needs two inverters, two ANDs and an OR; equivalently, an XOR followed by a NOT, or a single XNOR gate. Recognising the standard function (as drilled in the simplification lesson) lets you pick the cheapest realisation immediately.

---

Circuit Equivalence

Two circuits are equivalent if they give the same output for every input combination. There are two standard proofs:

1. Algebraic: derive each circuit's expression and simplify both to the same form.
2. Tabular: build a truth table for each and confirm the output columns match row for row.

Equivalence is what licenses every optimisation in this course: a minimised circuit is equivalent to the original but cheaper. It is also the basis of gate-family conversion — a NAND-only circuit is accepted precisely because it is provably equivalent to the AND/OR/NOT design it replaces.

---

NAND-Only and NOR-Only Circuits

Because NAND and NOR are universal (lesson 1), any function can be built from one gate type alone — valuable in manufacture, where a uniform fabric of identical cells is cheaper and easier to fabricate than a mix of gate types. The conversion uses double negation and De Morgan's law (lesson 4).

Converting a sum-of-products to NAND-only. Take $Q = A \cdot B + C$Q=A⋅B+C. Double-negate (changes nothing), then apply De Morgan's to the inner bar:

$Q = \overline{\overline{A \cdot B + C}} \quad \text{[double negation]}$Q=A⋅B+C​​[double negation] $= \overline{\,\overline{A \cdot B} \cdot \overline{C}\,} \quad \text{[De Morgan 2nd on the inner bar]}$=A⋅B⋅C[De Morgan 2nd on the inner bar]

Read as gates: $\overline{A \cdot B}$A⋅B is a NAND; $\overline{C}$C is a NAND with both inputs tied to C (since $\overline{C \cdot C} = \overline{C}$C⋅C=C); and the outer bar over their product is a third NAND. So a two-level AND-OR circuit becomes a uniform NAND-NAND circuit:

flowchart LR
    A((A)) --> N1{{"NAND"}}
    B((B)) --> N1
    C((C)) --> N2{{"NAND (C,C)"}}
    N1 -- "A·B bar" --> N3{{"NAND"}}
    N2 -- "C bar" --> N3
    N3 --> Q["Q = A·B + C"]