Notes · ElectronicsUK · A-Levels

Logic systems

Digital electronics is built from a handful of logic gates whose behaviour is captured entirely by their truth tables. This chapter defines the gates, develops Boolean algebra and De Morgan's theorems, and shows how to design a combinational circuit from a truth table and then minimise it with Boolean algebra or a Karnaugh map, finishing with adders and the universal NAND gate.

5 sections~18 min reading time3 competenciesLevel Foundation 1 · Standard 2 · Advanced 2

T·0444 / 16

Exam profile

AO1 · Recall the function and truth table of the AND, OR, NOT, NAND, NOR, XOR and XNOR gates and the laws of Boolean algebra.AO2 · Derive a Boolean expression from a truth table and build the corresponding gate circuit.AO3 · Simplify a Boolean expression by algebra or a Karnaugh map and evaluate the minimised design against gate count.

Operators:statederivesimplifydesignanalysecompleteevaluate

basic level

At AS the focus is the gates and their truth tables, Boolean algebra including De Morgan, and building a circuit from a truth table.

higher level

The full A-Level develops Karnaugh-map minimisation, adders and the use of universal NAND/NOR gates in economical designs.

Depth

Text

Contents · 5 sections

Logic systems

Logic gates and truth tables#

FoundationWJEC/Eduqas A Level Electronics — Unit 2 Digital Electronics (logic gates)

Truth tables of the two-input gates

Fig. 1The four input rows and the outputs of the six two-input gates. Each column is the complete definition of that gate.

A logic gate is a circuit whose output is a definite logic level — high (1) or low (0) — determined only by its present inputs. The behaviour of a gate is defined completely by its truth table, which lists the output for every possible combination of inputs. There are seven gates to know. The AND gate outputs 1 only when all inputs are 1; the OR gate outputs 1 when at least one input is 1; the NOT gate (inverter) reverses a single input.

The remaining four are compounds. NAND is AND followed by NOT, so it outputs 0 only when all inputs are 1; NOR is OR followed by NOT, outputting 1 only when all inputs are 0. The exclusive-OR (XOR) gate outputs 1 when its two inputs differ, and the exclusive-NOR (XNOR) outputs 1 when they are the same. XOR and XNOR are the difference and equality detectors, and they appear throughout arithmetic and comparison circuits.

For

n

inputs there are

2^n

input combinations, so a two-input gate has four rows in its truth table and a three-input gate has eight. Writing the input combinations in binary counting order (00, 01, 10, 11 for two inputs) guarantees that no combination is missed — a discipline that pays off when you later build a circuit from a full truth table. The truth table, not the symbol, is the definitive statement of what a gate does.

Logic levels are represented by voltages: in a typical system a logic 1 is a voltage near the positive supply and a logic 0 is near

0\,\text{V}

, with a forbidden band in between to give noise immunity. This is why digital signals are robust — a small amount of noise cannot turn a clean 1 into a 0. The comparator you met in the op-amp chapter is the usual bridge from an analogue level to these clean digital levels.

Everything in digital electronics is assembled from these gates, so fluency with their truth tables is the foundation of the whole digital unit. Combinational logic — where the output depends only on the present inputs — is built directly from them; sequential logic, where the output also depends on past inputs, adds memory but is still made of the same gates. Being able to fill in any gate's truth table instantly, and to read a small network by tracing levels through it, is the essential first skill.

N = 2^n

Number of input combinations

A gate or circuit with n inputs has 2^n rows in its truth table.

Worked example

Reading a two-gate network

A network computes $Q = \overline{A \cdot B} + C$ (a NAND of A and B, ORed with C). Find $Q$ for the inputs $A=1, B=1, C=0$ and for $A=1, B=0, C=0$ .

First inputs
$A \cdot B = 1 \cdot 1 = 1$ , so the NAND output is $\overline{1} = 0$ . Then $Q = 0 + C = 0 + 0 = 0$ .
Second inputs
$A \cdot B = 1 \cdot 0 = 0$ , so the NAND output is $\overline{0} = 1$ . Then $Q = 1 + 0 = 1$ .

Result: $Q = 0$ for $(1,1,0)$ and $Q = 1$ for $(1,0,0)$ — the NAND detects the 'not both A and B' condition, which C can then override.

Typical mistakes

Confusing NAND with AND, or NOR with OR — the bubble (NOT) inverts the basic gate's output.
Muddling XOR (output 1 when inputs differ) with OR (output 1 when at least one input is 1).

Active revision

Write the complete truth table for a two-input NAND gate and for a two-input XOR gate, and state one situation in which each gives a different output from a plain AND gate.

Active recall

Recall the key points — then reveal.

Sources: WJEC/Eduqas GCE Electronics specification (WJEC / Eduqas)

Boolean algebra and De Morgan's theorems#

StandardWJEC/Eduqas A Level Electronics — Unit 2 Digital Electronics (Boolean algebra)

Verifying De Morgan's first theorem

Fig. 2Column

\overline{A\cdot B}

matches column

\overline{A}+\overline{B}

in every row, proving De Morgan's first theorem by truth table.

Boolean algebra is the mathematics of logic. It uses three operations — AND (written as a product,

A \cdot B

), OR (written as a sum,

A + B

) and NOT (written as a bar,

\overline{A}

) — and a set of identities that let an expression be manipulated and simplified. The basic identities include

A + 0 = A

A \cdot 1 = A

A + 1 = 1

A \cdot 0 = 0

A + A = A

A \cdot A = A

, and the complements

A + \overline{A} = 1

and

A \cdot \overline{A} = 0

The algebra also has the familiar commutative, associative and distributive laws, plus two that surprise newcomers: the absorption laws

A + A\cdot B = A

and

A\cdot(A+B) = A

. These let a redundant term be removed entirely. Simplifying a Boolean expression means applying these identities to reach an equivalent expression that uses fewer operations — and therefore fewer, cheaper gates — while giving exactly the same truth table.

The most powerful tools are De Morgan's theorems, which relate AND to OR through inversion:

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

and

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

. In words, breaking a long inversion bar changes an AND to an OR (and vice versa) and inverts each term. De Morgan's theorems are what make it possible to convert any expression into a form using only NAND gates or only NOR gates, and they are indispensable for both simplification and universal-gate design.

A Boolean identity is proved by showing that both sides have the same truth table — the same output for every input combination. This is the honest test of any simplification: if two expressions share a truth table they are equivalent, whatever they look like. When you simplify, you must never change the truth table; you are only rewriting the same function more economically. Checking a simplified expression against the original truth table is a good habit and a common exam requirement.

Boolean simplification matters because it directly reduces the cost, size and power of a circuit. A logic function that naively needs a dozen gates might, after applying the identities and De Morgan, need only three or four — with the same behaviour. The examiner rewards not just reaching a simpler expression but justifying each step by naming the identity used, so that the simplification is transparent and verifiable rather than a lucky guess.

\overline{A \cdot B} = \overline{A} + \overline{B}, \quad \overline{A + B} = \overline{A} \cdot \overline{B}

De Morgan's theorems

Breaking an inversion bar swaps AND and OR and inverts each term.

A + A\cdot B = A, \quad A + \overline{A}\cdot B = A + B

Absorption laws

Redundant terms are removed, reducing gate count.

Worked example

Simplifying with named identities

Simplify $Q = A\cdot B + A\cdot \overline{B} + \overline{A}\cdot B$ using Boolean algebra, naming each identity.

Factor the first two terms
$A\cdot B + A\cdot \overline{B} = A\cdot(B + \overline{B})$ by the distributive law.
Apply the complement law
$B + \overline{B} = 1$ , so $A\cdot(B+\overline{B}) = A\cdot 1 = A$ . The expression is now $Q = A + \overline{A}\cdot B$ .
Apply the absorption law
$A + \overline{A}\cdot B = A + B$ by the second absorption law.
$Q = A + \overline{A}\cdot B = A + B$

Result: $Q = A + B$ — a three-term, four-gate expression reduced to a single OR gate with the identical truth table.

Typical mistakes

Applying De Morgan to only part of the expression, or failing to invert every term under a broken bar.
Changing the truth table during 'simplification' — an invalid step that produces a different function.

Active revision

Use Boolean algebra to simplify $Q = A\cdot B + A\cdot \overline{B}$ , naming the identities used, and verify your result with a truth table.

Active recall

Recall the key points — then reveal.

Sources: WJEC/Eduqas GCE Electronics specification (WJEC / Eduqas)

From truth table to circuit#

StandardWJEC/Eduqas A Level Electronics — Unit 2 Digital Electronics (combinational design)

Exclusive-OR built from AND, OR and NOT

Fig. 3The XOR function

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

as a sum of products: two AND gates (with inverters) feeding an OR gate.

Designing combinational logic from a specification is a systematic, four-step process. First, write the truth table that captures the required behaviour for every input combination. Second, identify every row whose output is 1. Third, write a product (AND) term for each such row, using each input directly if it is 1 in that row and inverted if it is 0. Fourth, OR all these product terms together. The result is the sum-of-products (SOP) expression, which is guaranteed to reproduce the truth table exactly.

Each product term is called a minterm and corresponds to exactly one row of the table. For example, the row

A=1, B=0, C=1

contributes the minterm

A\cdot \overline{B}\cdot C

, which is 1 for that one combination and 0 for every other. ORing the minterms gives an expression that is 1 precisely on the wanted rows and 0 elsewhere — a direct, mechanical translation from behaviour to Boolean algebra that never fails, though it is rarely the simplest form.

The SOP expression maps straight onto a gate circuit: each minterm becomes an AND gate (with inverters on the inputs that appear complemented), and a single OR gate combines the AND outputs. This 'AND-OR' structure is the canonical form of any combinational function. It may use more gates than necessary, which is exactly why the next step is simplification — but it always works, so it is the reliable starting point when a problem gives you a truth table or a word description.

The reverse skill — analysing a given circuit to find its truth table — uses the same ideas in reverse: label the output of each gate, write its Boolean expression in terms of the inputs, and build up the table combination by combination. Being able to move confidently in both directions, from specification to circuit and from circuit back to truth table, is the core competence of the combinational-logic questions and underpins everything from adders to decoders.

A worked design also brings in the systems view: a combinational block is a pure process stage that transforms present inputs into present outputs with no memory. A burglar alarm that sounds when a door OR a window is open AND the system is armed, or a voting circuit that outputs the majority decision, are combinational problems solved by exactly this procedure. Recognising a real-world specification as a truth table, and turning it into gates, is the practical pay-off of the method.

Q = \sum m_i \ (\text{minterms where } Q=1)

Sum of products

OR together one product term per input row that gives an output of 1.

Worked example

Majority voter from a truth table

Design a circuit whose output $Q$ is 1 when at least two of the three inputs $A, B, C$ are 1. Derive the sum-of-products expression and simplify it.

Truth table rows with Q = 1
$Q=1$ for $(0,1,1), (1,0,1), (1,1,0)$ and $(1,1,1)$ .
Sum of products
$Q = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC$ , one minterm per winning row.
Simplify
Pairing terms with $ABC$ (using $X + X = X$ so $ABC$ can be reused) gives $Q = AB + BC + AC$ — each pair of inputs contributes one AND term.
$Q = AB + BC + AC$

Result: $Q = AB + BC + AC$ : three two-input AND gates feeding a three-input OR gate — the majority (two-of-three) voter.

Typical mistakes

Writing a minterm with the wrong polarity — an input that is 0 in the row must appear inverted.
Missing a row whose output is 1, giving an expression that is wrong for that combination.

Active revision

A circuit outputs 1 only when exactly two of its three inputs A, B, C are 1. Write the truth table, derive the sum-of-products expression and describe the gate circuit.

Active recall

Recall the key points — then reveal.

Sources: WJEC/Eduqas GCE Electronics specification (WJEC / Eduqas)

Karnaugh map simplification#

AdvancedWJEC/Eduqas A Level Electronics — Unit 2 Digital Electronics (Karnaugh maps)

Three-variable Karnaugh map

Fig. 4The map for

Q = \sum m(3,5,6,7)

. The three overlapping pairs give

Q = BC + AC + AB

— the majority function.

A Karnaugh map (K-map) is a graphical tool that makes Boolean simplification systematic and reliable, avoiding the trial and error of pure algebra. It is a grid with one cell for every minterm, arranged so that cells which are physically adjacent differ in exactly one variable. This is the crucial feature: because adjacent cells differ in one input, a group of adjacent 1s corresponds to a term in which that changing variable cancels out.

The map's rows and columns are labelled in Gray-code order (00, 01, 11, 10) rather than binary counting order, precisely so that neighbouring cells differ by a single bit. A three-variable map is a

2 \times 4

grid; a four-variable map is

4 \times 4

. The map is filled directly from the truth table: a 1 in every cell whose minterm gives an output of 1. The pattern of 1s then reveals the simplifications visually.

Simplification proceeds by grouping the 1s into the largest possible rectangular blocks whose size is a power of two — ones, twos, fours or eights — with groups allowed to overlap and to wrap around the edges of the map. Each group of

2^k

cells eliminates

k

variables, leaving a single product term made only of the variables that stay constant across the group. Bigger groups give simpler terms, so you always make each group as large as possible.

Once every 1 is covered by at least one group, the simplified expression is the OR of the product term from each group. Because the grouping rules guarantee that each group corresponds to a valid Boolean term and that every 1 (and no 0) is included, the result is guaranteed correct and is usually the minimal sum-of-products form. The examiner expects the groups to be shown on the map and the resulting term for each group written down.

The K-map is faster and less error-prone than algebra for functions of up to four variables, which covers the great majority of exam problems. It also exposes 'don't care' conditions — input combinations that cannot occur — which can be treated as either 0 or 1 to enlarge a group and simplify further. Mastery of the K-map is one of the most useful practical skills in the digital unit, turning a messy sum of minterms into an economical circuit almost by inspection.

\text{group of } 2^k \text{ cells} \Rightarrow k \text{ variables eliminated}

Grouping rule

The larger the group, the simpler the resulting product term.

Worked example

Minimising a three-variable function

Simplify $Q = \sum m(3,5,6,7)$ (three variables $A, B, C$ ) using a Karnaugh map.

Plot the map
Place 1s at minterms 3 ( $011$ ), 5 ( $101$ ), 6 ( $110$ ) and 7 ( $111$ ). On the $A$ versus $BC$ map these are the $BC=11$ column and the $A=1$ cells for $BC=01,11,10$ .
Group the 1s
Three overlapping pairs cover all four 1s: the $BC=11$ column (minterms 3 and 7) gives $BC$ ; the $A=1, C=1$ pair (5 and 7) gives $AC$ ; the $A=1, B=1$ pair (6 and 7) gives $AB$ .
Combine
OR the three group terms: $Q = BC + AC + AB$ .
$Q = BC + AC + AB$

Result: $Q = AB + BC + AC$ — the same majority function reached by algebra, but read straight off the map.

Typical mistakes

Labelling the map in binary counting order instead of Gray code, so adjacent cells differ by more than one bit.
Making groups that are not a power of two in size, or failing to wrap groups around the map edges.

Active revision

Plot the function $Q = \sum m(3,5,6,7)$ of three variables on a Karnaugh map, group the 1s and write the minimal sum-of-products expression.

Active recall

Recall the key points — then reveal.

Sources: WJEC/Eduqas GCE Electronics specification (WJEC / Eduqas)

Adders and universal gates#

AdvancedWJEC/Eduqas A Level Electronics — Unit 2 Digital Electronics (adders, universal gates)

Full adder from two half adders

Fig. 5A full adder built from two half adders and an OR gate: the sum is

A\oplus B\oplus C_{in}

and the carry-out combines the two half-adder carries.

Binary addition is a combinational problem, and its building block is the half adder. A half adder adds two single bits

A

and

B

to produce a sum bit and a carry bit. The sum is 1 when the inputs differ, which is exactly the exclusive-OR function,

S = A \oplus B

; the carry is 1 only when both inputs are 1, which is the AND function,

C = A\cdot B

. So a half adder is simply an XOR gate and an AND gate sharing the same two inputs.

The half adder cannot accept a carry coming in from a lower stage, so it is not enough to add multi-bit numbers. The full adder fixes this by adding three bits:

A

B

and a carry-in

C_{in}

. Its sum is

S = A \oplus B \oplus C_{in}

and its carry-out is

C_{out} = A\cdot B + C_{in}\cdot(A \oplus B)

— a carry is generated when both inputs are 1, or when exactly one input is 1 and a carry comes in. A full adder is neatly built from two half adders and an OR gate.

Chaining full adders, with each stage's carry-out feeding the next stage's carry-in, produces a ripple-carry adder that adds two multi-bit binary numbers. This is a direct, physical realisation of the paper-and-pencil addition algorithm and shows how a genuinely useful arithmetic unit is assembled entirely from the gates of this chapter. The same XOR-and-carry structure underlies subtractors and the arithmetic unit of a processor.

A remarkable and examinable fact is that the NAND gate is universal: any logic function whatever can be built using NAND gates alone. A NOT is a NAND with its inputs joined; an AND is a NAND followed by a NAND-inverter; an OR is made by inverting both inputs of a NAND (via De Morgan). The NOR gate is universal in the same way. This matters commercially because a manufacturer can build an entire system from one cheap, mass-produced gate type.

Universal-gate design is a practical application of De Morgan's theorems: to convert an AND-OR circuit into all-NAND form, you insert pairs of inversions (which cancel) and apply De Morgan to rewrite each gate. The reward is a circuit that uses a single component type, which is cheaper to stock and often faster. Recognising that any of the seven gates can be synthesised from NAND (or NOR) alone, and being able to show the NOT, AND and OR constructions, rounds off the combinational-logic unit.

S = A \oplus B \oplus C_{in}, \quad C_{out} = A\cdot B + C_{in}\cdot(A \oplus B)

Full adder

Sum is the three-way exclusive-OR; carry-out is generated or propagated.

\overline{A} = \overline{A \cdot A} \ (\text{NAND with joined inputs})

NOT from NAND

The NAND gate is universal; a NOT is a NAND with its inputs joined.

Full adder truth table

Fig. 6The full adder truth table: the sum is 1 for an odd number of input 1s; the carry-out is 1 when two or more inputs are 1.

Worked example

Adding two bits with a carry

Using the full-adder expressions, add $A=1$ , $B=1$ with a carry-in $C_{in}=1$ , and confirm the result against binary arithmetic.

Sum bit
$S = A \oplus B \oplus C_{in} = 1 \oplus 1 \oplus 1 = 0 \oplus 1 = 1$ .
Carry-out
$C_{out} = A\cdot B + C_{in}\cdot(A\oplus B) = (1\cdot 1) + 1\cdot(1\oplus 1) = 1 + 0 = 1$ .
Check
In binary $1 + 1 + 1 = 11_2$ , which is a sum bit of 1 and a carry of 1 — exactly the outputs found.

Result: $S = 1$ , $C_{out} = 1$ , i.e. binary $11$ (decimal 3), confirming the full adder correctly adds three bits.

Typical mistakes

Using a half adder where a full adder is needed, so the incoming carry is ignored.
Forgetting that a single NAND with joined inputs makes an inverter when building universal-gate circuits.

Active revision

Write the truth table of a full adder for inputs $A, B, C_{in}$ , give the Boolean expressions for the sum and carry-out, and show how a NOT gate is made from a NAND gate.

Active recall

Recall the key points — then reveal.

Sources: WJEC/Eduqas GCE Electronics specification (WJEC / Eduqas)

References & sources

Sources

WJEC / Eduqas

WJEC/Eduqas GCE Electronics specification

Logic systems

5 sections~18 min reading time3 competenciesLevel Foundation 1 · Standard 2 · Advanced 2

Logic systems

Key points

Reading a two-gate network

Key points

Simplifying with named identities

Key points

Majority voter from a truth table

Key points

Minimising a three-variable function

Key points

Adding two bits with a carry

Sources

Logic systems

Key points

Reading a two-gate network

Key points

Simplifying with named identities

Key points

Majority voter from a truth table

Key points

Minimising a three-variable function

Key points

Adding two bits with a carry

Sources