How digital systems are built from logic gates — AND, OR, NOT, NAND, NOR, XOR. The 6-step combinational design procedure. Half-adder, full-adder, half-subtractor, and full-subtractor circuits. NAND as a universal gate. Sequential circuits and flip-flops — the memory elements that store state.
⚡Combinational vs Sequential Circuits
All digital logic circuits fall into one of two fundamental categories:
COMBINATIONAL CIRCUIT
Output depends only on current inputs
No memory — no feedback paths
Output changes immediately when input changes (after propagation delay)
Described by Boolean functions
Examples: adders, subtractors, multiplexers, decoders, encoders, ALU
SEQUENTIAL CIRCUIT
Output depends on current inputs and past history (state)
Contains memory elements (flip-flops)
Has feedback paths — output feeds back to input
Described by state machines (state table + state diagram)
The fundamental distinction: A combinational circuit is a pure function — same inputs always produce the same outputs. A sequential circuit has state — it remembers past events. A CPU is a sequential circuit: the current instruction cycle output depends on the current instruction (input) and the contents of all registers and flags (state from previous cycles).
🔌Logic Gates — The Building Blocks
Every digital system is built from a small set of basic logic gates. Each gate implements one Boolean operation:
Figure 1 — The six fundamental logic gates: symbol, Boolean expression, and description
The six fundamental logic gates. AND, OR, NOT are the primary gates. NAND = NOT-AND (bubble on output of AND), NOR = NOT-OR (bubble on output of OR). XOR outputs 1 only when inputs differ — it is the basis of binary addition. NAND and NOR are universal: any circuit can be built using only one gate type.
📋Gate Truth Tables
A truth table enumerates every possible input combination and the resulting output. For n inputs there are 2ⁿ rows:
Figure 2 — Truth tables for all six gates (2-input where applicable)
Truth tables for all six gates. AND outputs 1 only when both inputs are 1. OR outputs 1 when either or both inputs are 1. XOR outputs 1 only when exactly one input is 1. NAND and NOR are the complement of AND and OR respectively.
📐Combinational Circuit Design Procedure
The systematic 6-step procedure for designing any combinational circuit from a verbal problem statement:
State the problem clearly. Understand exactly what transformation is needed.
Determine the number of input and output variables. Count how many input bits describe each possible input case and how many output bits are required.
Assign letter symbols to all input and output variables.
Derive the truth table. List all 2ⁿ possible input combinations. For each, determine the correct output value. Don’t-care inputs may be marked X for later optimisation.
Simplify the Boolean function for each output using algebraic manipulation, Karnaugh map (K-map), or tabulation.
Draw the logic diagram. Implement the simplified Boolean expressions with gates.
Design constraints to consider in step 5: (1) Minimum number of gates, (2) minimum number of gate inputs, (3) minimum signal propagation time, (4) minimum number of interconnections, (5) fan-out limitations. These constraints often conflict — a faster design may require more gates. The design context determines which constraints dominate.
½Half-Adder
A half-adder adds two single bits and produces a 2-bit result (sum + carry). Inputs: x (augend), y (addend). Outputs: S (sum bit), C (carry out).
x
y
C (carry)
S (sum)
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
S = x ⊕ yC = xy
S is the XOR of x and y. C is the AND of x and y. The most compact implementation uses one XOR gate and one AND gate.
Figure 3 — Half-adder (left) and full-adder built from two half-adders + OR gate (right)
Half-adder (left): XOR gate produces sum S = x⊕y; AND gate produces carry C = xy. Full-adder (right): built from two half-adders and an OR gate. The first half-adder computes S₁=x⊕y and C₁=xy. The second adds S₁ with carry-in z, producing final sum S and partial carry C₂. The final carry-out is C₁ OR C₂.
⊕Full-Adder — Truth Table & Equations
A full-adder adds three bits: x (augend), y (addend), z (carry-in). Two outputs: S (sum), C (carry-out). Chain n full-adders to add n-bit numbers.
x
y
z (Cᵢₙ)
C (carry-out)
S (sum)
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
S = x’y’z + x’yz’ + xy’z’ + xyz
C = xy + xz + yz
Critical observation: S in the full-adder is identical to the XOR of three inputs: S = x ⊕ y ⊕ z. The carry-out C = 1 whenever any two or more of the three inputs are 1 — each term in C = xy + xz + yz is a “majority” pair. This leads to the efficient two-half-adder implementation shown in Figure 3.
½Half-Subtractor
A half-subtractor computes x − y, producing a difference D and a borrow B:
x (minuend)
y (subtrahend)
B (borrow)
D (difference)
0
0
0
0
0
1
1
1
1
0
0
1
1
1
0
0
D = x ⊕ y (same logic as S in half-adder!)
B = x’y (borrow only when x=0 and y=1)
Note the symmetry: D = x ⊕ y is identical to S in the half-adder. The only difference is the borrow output: C = xy (AND) in the half-adder, but B = x’y (AND of inverted x with y) in the half-subtractor.
−Full-Subtractor
A full-subtractor computes x − y − z, where z is the borrow-in from a lower-significance stage:
x
y
z (Bᵢₙ)
B (borrow-out)
D (difference)
0
0
0
0
0
0
0
1
1
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
0
0
1
1
1
1
1
D = x ⊕ y ⊕ z (same as S in full-adder)
B = x’y + x’z + yz
Adder–subtractor duality: D in the full-subtractor is identical to S in the full-adder. Borrow B = x’y + x’z + yz resembles C = xy + xz + yz in the full-adder — except that x is complemented in each term. This is why the hardware adder-subtractor circuit works — it only needs to complement the B operand.
🌐NAND — The Universal Gate
NAND (and NOR) are called universal gates because any Boolean function can be implemented using only NAND gates. NAND gates are the most efficient gate to fabricate in CMOS technology — modern standard cell libraries are built primarily from NAND gates.
Figure 4 — NAND gate implementing NOT, AND, and OR (De Morgan)
NAND gate implementing the three primary operations. NOT: tie both inputs together → (A·A)’ = A’. AND: NAND followed by a NOT-NAND → ((AB)’)’ = AB. OR: invert both inputs with NOT-NANDs, then NAND → (A’·B’)’ = A+B by De Morgan’s theorem. Since NOT, AND, and OR can all be built from NAND gates, NAND alone can implement any Boolean function.
🔁Code Conversion Example — BCD to Excess-3
Code conversion is a classic combinational design problem. BCD represents decimal digits 0–9 using 4 bits. Excess-3 represents the same digits by adding 3 to each BCD value:
🔍 Worked Example — BCD to Excess-3 Code Converter Design
Inputs: A, B, C, D (4-bit BCD, 0–9) Outputs: w, x, y, z (4-bit Excess-3)
Decimal
BCD (ABCD)
Excess-3 (wxyz)
0
0000
0011
1
0001
0100
4
0100
0111
7
0111
1010
9
1001
1100
Don’t-care inputs: BCD combinations 1010–1111 never occur → treat as don’t-cares (X) in K-map for simplification.
Simplified Boolean expressions (after K-map with don’t-cares):
z = D’ y = CD + C’D’ x = B'(C+D) + B(C+D)’ w = A + B(C+D)
Key insight: The OR gate producing C+D is shared by expressions for x and w — this is multi-output optimisation. Don’t-care conditions reduced complexity by allowing the K-map to form larger groupings.
💾Sequential Circuits & Flip-Flops
Sequential circuits add memory to combinational logic. The fundamental memory element is a flip-flop — a bistable circuit that stores one bit indefinitely, changing state only in response to a clock edge and control inputs.
Figure 5 — Sequential circuit structure (left) and SR NAND latch (right)
Sequential circuit structure (left): outputs depend on both current inputs and stored state. The memory block feeds back current state to the combinational logic; the clock synchronises updates. SR NAND latch (right): two cross-coupled NAND gates. S’=0 sets Q=1; R’=0 resets Q=0; both at 1 holds state; both at 0 is forbidden.