Week 2 — Boolean Algebra, Logic Gates, and Combinational Circuits

Overview

This week builds the mental bridge from Boolean expressions to the physical circuits that compute them. Everything a CPU does is ultimately combinational and sequential logic over the bits of Week 1, and to understand the CPU (Week 3) you first need to understand how a handful of gates compose into adders, multiplexers, and decoders. You will work the algebra (Boolean identities, De Morgan, canonical forms), minimize expressions (Karnaugh maps), and build combinational circuits — most importantly the half-adder and full-adder that implement the two’s-complement arithmetic of Week 1.

Course 6’s semiconductor-devices week covers how a transistor acts as the physical switch beneath every gate; here we take the gate as a primitive and reason at the logic level. By the end you can take a truth table, derive a minimal circuit, and explain how a ripple-carry adder adds two numbers.

Readings

ARM (Plantz) Ch. 4–6: Boolean algebra, logic gates, and combinational logic circuits. Extract: gate-level building blocks and the adder construction.
CA (Fox) Ch. 4–5: switches and digital logic. Extract: how switches compose into gates and gates into functional units.
(The transistor as the physical switch implementing a gate: see Course 6’s semiconductor-devices week.)

Key Concepts

Boolean algebra and canonical forms

Variables in {0,1}; operators AND (·), OR (+), NOT (¬). Identities (distributive, absorption) and De Morgan’s laws (\(\overline{A\cdot B}=\bar A+\bar B\)) let you transform expressions. Any function has canonical forms: sum-of-products (OR of AND-terms, one per true row of the truth table) and product-of-sums. NAND and NOR are functionally complete — any circuit can be built from one gate type, which is why real hardware favors them.

Minimization with Karnaugh maps

A truth table often yields a bloated SoP expression; a K-map groups adjacent 1-cells (which differ in one variable) to cancel that variable, producing a minimal expression with fewer gates. Minimization matters: fewer gates means less area, power, and delay. You will reduce expressions both algebraically and via K-maps and compare.

Combinational building blocks

From gates: the half-adder (XOR for sum, AND for carry) adds two bits; the full-adder chains carries to add three bits (a, b, carry-in). A ripple-carry adder chains \(n\) full-adders to add \(n\)-bit numbers — directly implementing Week 1’s two’s-complement addition (subtraction = add the negation). Multiplexers select among inputs; decoders turn an n-bit code into one-hot outputs. These are the parts the CPU (Week 3) is assembled from.

Propagation delay

Gates take time; signals ripple through combinational logic, and the longest path (critical path) sets the maximum clock speed. A ripple-carry adder’s carry chain is its critical path — motivating carry-lookahead and the broader performance concerns of Week 10.

Theory Exercises

Prove De Morgan’s laws from truth tables and use them to convert an expression to NAND-only form.
Derive the sum-of-products expression for a 3-input majority function and minimize it with a K-map.
Build a full-adder from gates; write its sum and carry equations and verify the truth table.
Show how \(n\) full-adders form an \(n\)-bit ripple-carry adder and how subtraction reuses it via two’s complement (Week 1).
Identify the critical path of a 4-bit ripple-carry adder and explain how it bounds clock frequency.

Implementation

Build a small gate-level logic simulator (gates as functions/objects with wires) and compose it up to a 4-bit (or 8-bit) ripple-carry adder/subtractor and a multiplexer/decoder. Drive it from truth tables and verify every output. Optionally express the same circuits in a hardware description style for comparison.

Measurement / Inspection

Verify each circuit against its truth table exhaustively. Count gates before and after K-map minimization for a few functions. Trace the carry propagation through the adder and identify the critical path; estimate relative delay by path length.

Expected baselines: circuits match their truth tables exactly; K-map minimization measurably reduces gate count; the adder’s critical path is the carry chain, growing with bit width — the motivation for faster adder designs and a concrete instance of the performance thinking in Week 10.

Connections

These combinational blocks are the ALU and datapath pieces the CPU emulator assembles in Week 3; the adder implements Week 1’s arithmetic. The transistor-level realization is Course 6’s; the critical-path idea seeds Week 10’s performance work. Boolean minimization is the same logic that underlies compiler/strength-reduction optimizations later.