You are viewing a free preview of this lesson.
Subscribe to unlock all 7 lessons in this course and every other course on LearningBro.
Every digital computer ever built, from the 1940s ENIAC to a modern Apple M-series silicon chip, is constructed from a small repertoire of logic gates wired together in dense combinational and sequential networks. The remarkable fact is that just a handful of primitive Boolean operations — AND, OR, NOT, and a few derived gates such as NAND, NOR, XOR and XNOR — is sufficient to perform every arithmetic operation, every comparison, every memory access, and ultimately every computation that any finite digital system can carry out. The mathematics underlying this is Boolean algebra, formalised by George Boole in 1854. The engineering realisation — packaging Boolean operations as physical transistor circuits etched on silicon — emerged in the 1960s with TTL and later CMOS logic families. This lesson develops the seven standard logic gates with truth tables and circuit symbols, covers the laws of Boolean algebra including De Morgan's theorems, and applies the machinery to design problems — half-adders, full-adders, multiplexers, decoders, and simplification by Karnaugh map.
Spec mapping (AQA 7408 §3.13.4 — Digital signal processing, option E): This lesson covers the standard logic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR) with their truth tables and circuit symbols (BS 3939 or ANSI); the laws of Boolean algebra including commutativity, associativity, distributivity, complement and De Morgan's theorems; combinational logic design including half-adders, full-adders, multiplexers, demultiplexers, encoders and decoders; and simplification techniques including Boolean algebra manipulation and the Karnaugh map. (Refer to the official AQA specification document for exact wording.)
Synoptic links: Logic gates are physically realised using the junction transistors of Lesson 0 in their saturation (= "1") and cut-off (= "0") regions; every NAND gate inside a microprocessor is a small array of MOSFETs operating digitally. The same gates feed forward into sequential logic (Lesson 5) where they are wired into latches and flip-flops by connecting outputs back to inputs to create memory. Combinational logic also connects to the digital-signal picture from Lesson 1 — a digital adder is the heart of the CPU's arithmetic unit, and the resistor-ladder DAC's binary-weighted summation is a hardware addition that combines logic-gate outputs through analogue summing.
A logic gate takes one or more binary inputs (each 0 or 1) and produces a single binary output. The behaviour is captured by its truth table — an exhaustive listing of the output for every possible combination of inputs.
Single input A; output is the logical complement of A:
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Symbolically written as Ā or ¬A. The gate symbol is a triangle with a small circle ("bubble") on the output — the bubble universally denotes inversion in BS 3939 and ANSI conventions.
Two inputs A, B; output is 1 only if both inputs are 1:
| A | B | A·B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Symbol: a flat-back, curved-front shape resembling a "D".
Two inputs; output is 1 if either or both inputs are 1:
| A | B | A+B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Symbol: a curved-back, pointed-front shape.
The combination of AND followed by NOT:
| A | B | A·B | NAND |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Symbol: AND shape with an output bubble. NAND is a universal gate — any other logic function can be constructed from NAND gates alone. This is the basis of much commercial CMOS logic, where NAND is the smallest and fastest two-input gate.
OR followed by NOT:
| A | B | A+B | NOR |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
NOR is also a universal gate (every other function can be built from NOR alone), though it is slightly less efficient than NAND in CMOS.
Two inputs; output is 1 if the inputs differ, 0 if they are the same:
| A | B | A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Symbol: OR shape with an extra curved line at the input. XOR is the binary "sum-without-carry" — the basis of every adder circuit.
XOR followed by NOT — the "equivalence" function. Output is 1 if A = B, 0 if A ≠ B:
| A | B | XNOR |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Boolean variables take values in {0, 1}. The operations follow algebraic laws structurally similar to ordinary arithmetic — but with crucial differences. The standard notation: A·B for AND (often written as juxtaposition AB), A+B for OR (the "+" is OR, not addition), Ā for NOT A.
| Law | AND form | OR form |
|---|---|---|
| Identity | A·1 = A | A+0 = A |
| Null | A·0 = 0 | A+1 = 1 |
| Idempotency | A·A = A | A+A = A |
| Complement | A·Ā = 0 | A+Ā = 1 |
| Double negation | — | Ā̄ = A |
| Commutativity | A·B = B·A | A+B = B+A |
| Associativity | (A·B)·C = A·(B·C) | (A+B)+C = A+(B+C) |
| Distributivity | A·(B+C) = A·B + A·C | A+(B·C) = (A+B)·(A+C) |
| Absorption | A·(A+B) = A | A+(A·B) = A |
The two distributive laws are particularly important: the second one (OR distributes over AND) does not have an arithmetic analogue and often surprises students new to Boolean algebra.
The two most useful Boolean identities in practice are due to Augustus De Morgan (paraphrased):
De Morgan's First Theorem: The complement of a sum equals the product of the complements. (A + B)' = Ā · B̄
De Morgan's Second Theorem: The complement of a product equals the sum of the complements. (A · B)' = Ā + B̄
In words: "invert the whole expression, swap AND and OR, and invert each variable." The theorems let you convert any Boolean expression between sum-of-products form and product-of-sums form, and they explain why NAND and NOR are universal gates.
Question: Simplify the expression F = (A + B̄)(Ā + B).
Solution: Expand the product:
F = A·Ā + A·B + B̄·Ā + B̄·B
By complement A·Ā = 0 and B̄·B = 0. So:
F = A·B + Ā·B̄
This is the XNOR function — the expression equals 1 exactly when A = B.
Question: Simplify F = A·B + A·B·C + A·C̄.
Solution: Factor A from each term:
F = A·(B + B·C + C̄)
By absorption B + B·C = B:
F = A·(B + C̄)
The expression has been reduced from 3 terms (with 7 literal instances) to a single product of two terms (with 3 literal instances). Implementing this in hardware now requires 1 AND gate (with one input inverted from C) plus 1 OR gate plus 1 NOT gate, instead of 3 ANDs, 1 NOT and 1 OR.
A Karnaugh map (or K-map) is a visual grid layout that makes Boolean simplification straightforward for expressions of up to four variables. The grid has one cell per minterm; adjacent cells differ by exactly one variable. Groups of adjacent 1s in the grid correspond to simplified product terms.
For F(A, B):
| B=0 | B=1 | |
|---|---|---|
| A=0 | ||
| A=1 |
Each cell holds a 0 or 1 according to the truth table. Adjacent cells (horizontally or vertically) differ by one variable.
Suppose F has the truth table:
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
The K-map (with BC across the top in Gray code order 00, 01, 11, 10 — note that 11 comes before 10 so adjacent cells differ by one bit):
| BC=00 | BC=01 | BC=11 | BC=10 | |
|---|---|---|---|---|
| A=0 | 0 | 1 | 1 | 0 |
| A=1 | 1 | 1 | 1 | 1 |
Group the 1s:
Therefore F = A + C.
Verifying by truth table: F = A + C gives 1 whenever A=1 or C=1, which matches all 6 1-rows above (rows 1, 3, 4, 5, 7 have either A=1 or C=1; only rows 0 and 2 have both A=0 and C=0). ✓
The K-map produced a one-line simplification of an 8-row truth table.
A combinational circuit has outputs that depend only on the current inputs — no memory of past inputs. The opposite — sequential logic with internal state — is the subject of Lesson 5.
The simplest arithmetic circuit: take two single-bit inputs A and B and produce two outputs, sum S and carry C:
| A | B | S | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
By inspection: S = A ⊕ B (XOR), C = A · B (AND).
A half-adder uses one XOR gate plus one AND gate. The "half" qualifier indicates it does not accept a carry-in from a previous stage.
A full-adder accepts three inputs: A, B, and the carry-in C_in from the previous stage. It produces two outputs: sum S and carry-out C_out.
| A | B | C_in | S | C_out |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Sum: S is 1 when an odd number of inputs is 1 — that is, S = A ⊕ B ⊕ C_in.
Carry: C_out is 1 when at least two of the three inputs are 1 — that is, C_out = A·B + B·C_in + A·C_in. Alternatively, C_out = A·B + C_in·(A⊕B), which uses the XOR sub-result and is the standard textbook implementation.
A full-adder uses 2 XOR gates, 2 AND gates and 1 OR gate.
To add two 4-bit numbers A₃A₂A₁A₀ and B₃B₂B₁B₀, cascade four full-adders:
graph LR
A["FA0<br/>A0,B0,Cin=0"] -->|C1| B["FA1<br/>A1,B1"]
B -->|C2| C["FA2<br/>A2,B2"]
C -->|C3| D["FA3<br/>A3,B3"]
D -->|C4 = Cout| E["5-bit result<br/>C4 S3 S2 S1 S0"]
style A fill:#3498db,color:#fff
style D fill:#3498db,color:#fff
style E fill:#27ae60,color:#fff
The carry "ripples" from the least-significant stage to the most-significant — hence "ripple-carry". The total propagation delay is roughly 4 × t_carry, where t_carry is the carry-delay of one full-adder. For 32- and 64-bit adders, more elaborate carry-look-ahead designs precompute the carries in parallel to reduce delay.
A multiplexer (mux) selects one of N data inputs according to a binary select signal, and routes it to a single output. A 4-to-1 mux has 4 data inputs (D₀, D₁, D₂, D₃), 2 select bits (S₁S₀), and 1 output Y:
Y = D₀·S̄₁·S̄₀ + D₁·S̄₁·S₀ + D₂·S₁·S̄₀ + D₃·S₁·S₀
When (S₁,S₀) = (0,0), Y = D₀; when (0,1), Y = D₁; and so on. Multiplexers are the digital equivalent of an analogue selector switch and are heavily used in time-division-multiplexed communication channels.
A decoder is the inverse of a multiplexer: it takes a binary input of n bits and activates exactly one of 2^n outputs. A 2-to-4 decoder has 2 inputs (A,B) and 4 outputs (Y₀, Y₁, Y₂, Y₃). Exactly one output is 1 according to the input combination:
Subscribe to continue reading
Get full access to this lesson and all 7 lessons in this course.