Skip to content

Combinational Logic

Overview

This lecture introduces combinational logic: digital circuits whose outputs depend only on their current inputs, with no memory of the past. We start from the three primitive logic gates (AND, OR, NOT), see how any function can be expressed as a circuit, and learn the sum-of-products (SoP) recipe for systematically turning a specification into a truth table, then a Boolean equation, then a circuit. We apply this to a parity (even/odd) detector and to the Lab 8 max2 problem, then build the arithmetic circuits that are the heart of every processor: a 1-bit half adder, a 1-bit full adder, and finally an 8-bit ripple-carry adder.

Learning Objectives

  • Distinguish combinational logic (acyclic, stateless) from sequential logic (cyclic, stateful)
  • Read and draw the symbols and truth tables for the AND, OR, and NOT gates
  • Translate a word-problem specification into a complete truth table
  • Apply the sum-of-products method to derive a Boolean equation from a truth table
  • Convert a sum-of-products equation into a gate-level circuit (product terms → AND gates, sum → OR gate)
  • Design a 1-bit full adder with carry-in and carry-out from grade-school binary addition
  • Compose eight full adders into an 8-bit ripple-carry adder using splitters and mergers
  • Explain why a brute-force truth table for a 17-input adder is infeasible (2^17 rows) and why composition is the right answer

Prerequisites

  • Binary number representation and base conversion (Lecture: C base conversion)
  • Bitwise operators in C: &, |, ~, ^ (Lecture: bit manipulation)
  • Familiarity with two's complement (for the subtraction preview)
  • The Digital application installed and the Lab 8 autograder set up

1. Two Kinds of Digital Circuits

Everything a processor does is built out of wires carrying one of two voltage levels. We abstract those voltages into the binary values 0 and 1:

Logic value Voltage (idealized) Name
1 ~high (e.g. 3.3 V) high / true / asserted
0 ~low (e.g. 0 V) low / false / deasserted

From wires and transistors we build gates, from gates we build components, and from components we build a processor. This hierarchical abstraction is what makes designing a CPU tractable.

Digital circuits come in two fundamental flavors:

flowchart TD
    A[Digital Circuits] --> B[Combinational Logic]
    A --> C[Sequential Logic]
    B --> B1["Acyclic (no feedback loops)"]
    B --> B2["Output depends ONLY on current inputs"]
    B --> B3["No memory / no state"]
    C --> C1["Has cycles / feedback"]
    C --> C2["Output depends on inputs AND stored state"]
    C --> C3["Remembers the past (registers, counters)"]

    style B fill:#cfe,stroke:#333,stroke-width:2px
    style C fill:#fcc,stroke:#333,stroke-width:1px
  • Combinational logic is an acyclic network of gates — a directed acyclic graph (DAG). Apply inputs, wait for the signals to propagate, and the outputs settle to a value determined purely by those inputs. Adders, multiplexers, decoders, and ALUs are combinational.
  • Sequential logic contains cycles (feedback). That feedback lets a circuit store a value, so its output depends on both the current inputs and the bits it is remembering. Latches, flip-flops, registers, and counters are sequential. (We cover these in a later lecture.)

Today is entirely about combinational logic. The defining rule: no feedback loops, no memory — the output is a pure function of the input.

2. The Three Primitive Gates

Every combinational function can be built from just three gates: AND, OR, and NOT. Their schematic symbols (as drawn in lecture) and truth tables follow.

AND

Output is 1 only when all inputs are 1.

 a ──┐
     ├──╲
     │    ╲────  r = a · b
     ├──  ╱
 b ──┘
   (flat back, round front: AND)
a b r = a · b
0 0 0
0 1 0
1 0 0
1 1 1

OR

Output is 1 when any input is 1.

 a ──╲
      ╲╲
       ╲╲───  r = a + b
      ╱╱
 b ──╱
   (curved back, pointed front: OR)
a b r = a + b
0 0 0
0 1 1
1 0 1
1 1 1

NOT (inverter)

Output is the opposite of the input. The small circle (the bubble) on the tip of the triangle means "invert."

 a ──▷o──  r = ā
   (triangle + bubble: NOT)
a r = ā
0 1
1 0

Three notations for the same operations

We will move freely between three ways of writing the same logic:

Operation C code Boolean algebra Logic notation
AND a & b a · b (or ab) a ∧ b
OR a \| b a + b a ∨ b
NOT ~a ā ¬a

A bubble on any gate input or output simply means "invert that signal." Putting a bubble on an AND output gives NAND; on an OR output gives NOR; XOR (^) and XNOR are common enough that the Digital application provides them directly.

3. Circuits: Composing Gates

A circuit is just gates wired together. Because combinational circuits are acyclic, you can always read them left-to-right: inputs on the left, gates in the middle, outputs on the right.

The lecture's first example combines two AND gates feeding an OR gate:

flowchart LR
    a((a)) --> AND1[AND]
    b((b)) --> AND1
    c((c)) --> AND2[AND]
    d((d)) --> AND2
    AND1 --> OR1[OR]
    AND2 --> OR1
    OR1 --> r((r))

This computes:

r = (a · b) + (c · d)

We can then hide an entire circuit behind a box (a subcircuit) and treat it as a new building block. The lecture drew a + box with inputs a, b and output r — an adder used as a black box. This abstraction is the whole game: once a block works, we reuse it without re-thinking its internals.

Reading wiring diagrams: dots matter

A crucial convention when wires cross in a schematic:

   │                  │
───┼───   (no dot)  ──●───   (dot present)
   │                  │
 NOT connected     CONNECTED (junction)
  • Lines that cross without a dot are NOT connected — one passes over the other.
  • A solid dot at a crossing means the wires are joined.

Getting this wrong is the single most common source of bugs when drawing circuits in Digital.

4. The Goal: An 8-bit Adder

The destination for this lecture (and Lab 8) is an 8-bit adder:

                 cin
                  │
          ┌───────┴───────┐
   a ──8──┤               │
          │   8-bit adder ├──8──▶ r   (the sum)
   b ──8──┤               │
          └───────┬───────┘
                  │
                cout

It takes two 8-bit operands a and b, a 1-bit carry-in cin, and produces an 8-bit result r plus a 1-bit carry-out cout. The slash with an 8 on a wire denotes an 8-bit-wide bus rather than a single wire.

But before we can build it, we need a systematic way to turn any specification into a circuit. That method is sum-of-products.

5. The Sum-of-Products Method

Sum-of-products (SoP) is a three-step recipe that converts a function specification into a working circuit:

flowchart LR
    A["1. Build truth table"] --> B["2. Identify rows<br/>with output = 1"]
    B --> C["3. Build equation:<br/>AND each row (product),<br/>OR the rows (sum)"]
    C --> D["Draw circuit"]
  1. Truth table — enumerate every combination of inputs and record the desired output.
  2. Identify the 1-rows — find each row where the output should be 1.
  3. Build the equation — for each 1-row write a product term (an AND of every input, complemented where that input is 0), then sum (OR) all the product terms together.

The name says it all: it is a sum (OR) of products (ANDs). Each product term is a single AND gate that is true for exactly one input combination; the final OR gate fires if any of those combinations occurs.

Why each product term picks out exactly one row

In a product term, an input that is 1 in the target row appears uncomplemented (n), and an input that is 0 appears complemented (n̄). The product is 1 only when every literal is 1, which happens for precisely that one input combination. ORing the product terms therefore reproduces exactly the set of 1-rows — no more, no less.

6. Worked Example: Even/Odd Parity Detector

Function. - Input: a 3-bit number n₂ n₁ n₀. - Output: two 1-bit outputs, even and odd. - Goal: determine whether the number of 1 bits is even or odd.

Examples:

010  →  one 1-bit   → odd
110  →  two 1-bits  → even

(Note: zero 1-bits counts as even.)

Step 1 — Truth table

Three inputs means 2³ = 8 rows. We count the 1-bits in each row and set even/odd accordingly. The rows where even = 1 are checked (✓):

✓ n₂ n₁ n₀ # of 1s even odd
✓ 0 0 0 0 1 0
0 0 1 1 0 1
0 1 0 1 0 1
✓ 0 1 1 2 1 0
1 0 0 1 0 1
✓ 1 0 1 2 1 0
✓ 1 1 0 2 1 0
1 1 1 3 0 1

Step 2 — Identify the 1-rows for even

even is 1 in four rows: 000, 011, 101, 110.

Step 3 — Build the equation

Write one product term per 1-row (complement the inputs that are 0 in that row), then OR them:

even = (n̄₂ · n̄₁ · n̄₀)    ← row 000
     + (n̄₂ · n₁ · n₀)     ← row 011
     + (n₂ · n̄₁ · n₀)     ← row 101
     + (n₂ · n₁ · n̄₀)     ← row 110

Each parenthesized group is a product (one AND gate); the + signs form the sum (one OR gate).

Deriving odd the easy way

odd is the complement of even — a number's 1-count is either even or odd, never both:

odd = even̄

So instead of a second four-term SoP, we just feed even through a single NOT gate (an inverter, drawn as the triangle-with-bubble). This is a nice example of reusing a result rather than re-deriving it.

Step 4 — The circuit

The equation maps directly to gates. Each product term becomes a 3-input AND gate (with input bubbles where the literal is complemented); the four AND outputs feed one 4-input OR gate, whose output is even (here labeled r):

flowchart LR
    n2((n2)) --> A1
    n1((n1)) --> A1
    n0((n0)) --> A1
    A1["AND: n̄₂·n̄₁·n̄₀"]

    n2 --> A2
    n1 --> A2
    n0 --> A2
    A2["AND: n̄₂·n₁·n₀"]

    n2 --> A3
    n1 --> A3
    n0 --> A3
    A3["AND: n₂·n̄₁·n₀"]

    n2 --> A4
    n1 --> A4
    n0 --> A4
    A4["AND: n₂·n₁·n̄₀"]

    A1 --> OR1[OR]
    A2 --> OR1
    A3 --> OR1
    A4 --> OR1
    OR1 --> r((r = even))

In the Digital application you implement the complemented literals by placing input bubbles on the AND gate's pins rather than wiring separate NOT gates — fewer gates, same logic. A separate sanity-check helper drawn in the notes simply ANDs n₂, n₁, n₀ (each first inverted) — a reminder that a bubble on an input is exactly an inline NOT.

7. Lab 8 Part 2: max2 — Maximum of Two 2-bit Numbers

Lab 8 asks you to implement this C fragment in hardware, where a, b, and r are 2-bit values (so each is 0, 1, 2, or 3):

if (a > b) {
    r = a;
} else {
    r = b;
}

This is just r = max(a, b). The inputs are a₁ a₀ and b₁ b₀; the outputs are r₁ r₀. For example:

a = 01  (1)
b = 10  (2)
max2(01, 10) = 10   (2)   ← b wins

With 4 inputs the truth table has 2⁴ = 16 rows. For each row, compute max(a, b) and write the 2-bit result. The full table:

a₁ a₀ b₁ b₀ a b max r₁ r₀
0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 1 0 1
0 0 1 0 0 2 2 1 0
0 0 1 1 0 3 3 1 1
0 1 0 0 1 0 1 0 1
0 1 0 1 1 1 1 0 1
0 1 1 0 1 2 2 1 0
0 1 1 1 1 3 3 1 1
1 0 0 0 2 0 2 1 0
1 0 0 1 2 1 2 1 0
1 0 1 0 2 2 2 1 0
1 0 1 1 2 3 3 1 1
1 1 0 0 3 0 3 1 1
1 1 0 1 3 1 3 1 1
1 1 1 0 3 2 3 1 1
1 1 1 1 3 3 3 1 1

The lecture stressed the key insight: you write one SoP equation per output bit. There are two outputs, so there are two equations — one for r₁ and one for r₀. Underline the result bits in each row, then collect the 1-rows for each output column separately.

Reading the 1-rows for each output gives (before any simplification):

r₁ = sum of the eight product terms from rows where r₁ = 1
r₀ = sum of the eight product terms from rows where r₀ = 1

For instance, r₀ is 1 in the rows 0001, 0100, 0101, 0011, 0111, 1011, 1100, 1101, 1110, 1111 — collect those product terms and OR them. (You may simplify with Boolean algebra, but the autograder only checks behavior, so a literal SoP circuit is acceptable.)

Naming matters for auto-grading: the inputs must be named exactly a1, a0, b1, b0, and the file must be max2.dig. The autograder checks names and the file name, not your truth table or equation, so submit a working .dig circuit.

8. Building an Adder: Grade-School Arithmetic in Gates

Addition is the most fundamental operation a processor performs, so we build it carefully. The plan: start from a 1-bit adder and scale up.

Binary addition is grade-school addition

Adding binary numbers works exactly like decimal addition, column by column, carrying into the next column:

    carries: 1 1
                0 1 1   (a = 3)
              + 0 0 1   (b = 1)
              -------
              1 0 0     (= 4)

Each column adds three bits — the two operand bits and the carry coming in — and produces a sum bit for that column plus a carry-out into the next column. A circuit that does one column is exactly what we need to replicate.

Half adder vs. full adder

       1-bit HALF adder              1-bit FULL adder
                                          cin
   a ─1─┐                          a ─1─┐  │
        ├─ + ─1─ sum                    ├─ + ─1─ sum
   b ─1─┘                          b ─1─┘  │
        (no carry-in)                    cout
  • A half adder has two inputs (a, b) and two outputs (sum, cout). It cannot accept a carry from a previous column, so it is only useful for the very first (least-significant) column — or as a building block.
  • A full adder adds a third input, the carry-in (cin). With three inputs (a, b, cin) and two outputs (sum, cout), it can be chained, making it the universal building block for multi-bit addition.

Full-adder truth table

Three inputs → 2³ = 8 rows. sum is 1 when an odd number of the three inputs are 1; cout is 1 when two or more inputs are 1 (majority). The 1-rows for sum are highlighted:

✓ sum a b cin sum cout
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-of-products equations for the full adder

Applying the SoP recipe to each output column:

sum  = (ā · b̄ · cin)
     + (ā · b · c̄in)
     + (a · b̄ · c̄in)
     + (a · b · cin)

cout = (ā · b · cin)
     + (a · b̄ · cin)
     + (a · b · c̄in)
     + (a · b · cin)

These are the equations Lab 8 Part 3 gives you for building the full adder in Digital. (sum is the 3-input XOR a ^ b ^ cin, and cout is the majority function (a·b) + (a·cin) + (b·cin) — equivalent simplified forms, but the SoP versions above are perfectly correct and graded only on behavior.)

flowchart LR
    a((a)) --> SUM
    b((b)) --> SUM
    cin((cin)) --> SUM
    SUM["SoP for sum<br/>(4 AND terms → OR)"] --> s((sum))

    a --> COUT
    b --> COUT
    cin --> COUT
    COUT["SoP for cout<br/>(4 AND terms → OR)"] --> co((cout))

In Digital you save this as a subcircuit named 1-bit-full-adder.dig with inputs a, b, cin and outputs sum, cout, so you can drop it into the 8-bit design as a single component.

9. Why Not Just Build One Giant Truth Table?

A tempting but disastrous idea: build the 8-bit adder as a single SoP circuit. Its inputs are cin, a₇…a₀ (8 bits), and b₇…b₀ (8 bits) — that is 1 + 8 + 8 = 17 inputs:

cin  a7 a6 a5 a4 a3 a2 a1 a0  b7 b6 b5 b4 b3 b2 b1 b0 │ sum7 ... sum0  cout
─────────────────────────────────────────────────────┼────────────────────
                      2^17 rows  ✗  (= 131,072 rows)

2¹⁷ = 131,072 rows. That is hopeless to enumerate by hand, and the resulting circuit would be enormous. The notes literally cross this approach out.

The right answer is composition. We already built a 1-bit full adder that handles one column correctly. So:

Combine eight 1-bit full adders to build an 8-bit ripple-carry adder.

This is the core lesson of hierarchical design: solve the small problem once, then chain copies of it.

10. The 8-bit Ripple-Carry Adder

Chain eight full adders so that each adder's cout feeds the next adder's cin. The carry "ripples" from the least-significant bit up to the most-significant bit — hence ripple-carry.

        cin = 0
          │
    ┌─────┴─────┐
a0 ─┤  1-bit FA ├─▶ sum0
b0 ─┤    (+)    │
    └─────┬─────┘
          │ carry
    ┌─────┴─────┐
a1 ─┤  1-bit FA ├─▶ sum1
b1 ─┤    (+)    │
    └─────┬─────┘
          │ carry
          ⋮   (FA for bits 2..6)
          │
    ┌─────┴─────┐
a7 ─┤  1-bit FA ├─▶ sum7
b7 ─┤    (+)    │
    └─────┬─────┘
          │
        cout

flowchart LR
    cin((cin=0)) --> FA0
    a0((a0)) --> FA0
    b0((b0)) --> FA0
    FA0[FA 0] --> s0((sum0))
    FA0 -- carry --> FA1

    a1((a1)) --> FA1
    b1((b1)) --> FA1
    FA1[FA 1] --> s1((sum1))
    FA1 -- carry --> dots(("...")) 

    dots -- carry --> FA7
    a7((a7)) --> FA7
    b7((b7)) --> FA7
    FA7[FA 7] --> s7((sum7))
    FA7 -- carry --> cout((cout))
  • The first adder's cin is set to 0 (or to the external cin for a chainable adder).
  • Each subsequent adder receives the previous adder's cout as its cin.
  • The eight sum bits form the 8-bit result; the final adder's cout is the overall carry-out.

Splitters and mergers

The external interface is two 8-bit buses a and b, but each full adder wants single bits. Digital provides splitter/merger components:

  • A splitter breaks an 8-bit bus into its 8 individual wires (a → a₇…a₀).
  • A merger (the same component used in reverse) combines the 8 individual sum bits back into one 8-bit sum bus.
       splitter                         merger
   a ─8─▶ ║ ─▶ a0                  sum0 ─▶ ║
          ║ ─▶ a1                  sum1 ─▶ ║ ─8─▶ sum
          ⋮                          ⋮     ║
          ║ ─▶ a7                  sum7 ─▶ ║

So the full 8-bit adder: split a and b into bits, route bit i of each into full adder i, chain the carries, and merge the eight sum outputs into the 8-bit sum bus. Save it as 8-bit-ripple-carry-adder.dig with inputs a, b, cin and outputs sum, cout.

Propagation delay

Because the carry must ripple through all eight adders, the most-significant sum bit cannot be correct until the carry has traveled the entire chain. The time for outputs to stabilize after inputs change is the propagation delay. In a ripple-carry adder this delay grows linearly with the number of bits — an 8-bit adder is roughly twice as slow as a 4-bit one. (Faster designs like carry-lookahead reduce this, but ripple-carry is the simplest and is exactly what we build here.)

Abstraction pays off

Once the 8-bit adder works, it too becomes a black box. You can wire two 8-bit adders (carrying between them) into a 16-bit adder, four into a 32-bit adder, and so on. The same composition trick scales all the way up to the 32-bit and 64-bit adders inside a real CPU's ALU.

11. Preview: Subtraction from an Adder

You do not need a separate subtractor. In two's complement, subtraction is addition of a negated operand:

a - b  =  a + (-b)  =  a + (~b + 1)

To compute -b you invert every bit of b (~b) and add 1. The "+1" is free in a ripple-carry adder: set the very first cin to 1 instead of 0. So:

to subtract:  invert b  AND  set cin = 1

This is why an ALU can share one adder for both add and subtract — a topic for the next lecture, along with comparators, multiplexers, decoders, and encoders that round out the combinational toolkit for building a processor.

Key Concepts

Concept Definition Example
Combinational logic Acyclic circuit; output depends only on current inputs (no memory) Adder, MUX, decoder
Sequential logic Circuit with feedback that stores state Register, counter
AND gate Output 1 only when all inputs are 1 (a · b) 1·1 = 1, 1·0 = 0
OR gate Output 1 when any input is 1 (a + b) 1+0 = 1, 0+0 = 0
NOT gate Inverts the input (ā); drawn as triangle + bubble 1̄ = 0
Truth table Lists output for every input combination (2ⁿ rows) 3 inputs → 8 rows
Sum-of-products OR (sum) of AND terms (products), one per 1-row even = (n̄₂·n̄₁·n̄₀) + ...
Product term A single AND of all inputs, complemented where the row has 0 (ā · b · c̄)
Half adder Adds two bits → sum, cout; no carry-in inputs a, b
Full adder Adds three bits (a, b, cin) → sum, cout chainable building block
Ripple-carry adder N full adders chained, each cout → next cin 8-bit adder = 8 FAs
Propagation delay Time for outputs to settle after inputs change grows linearly in ripple-carry
Splitter / merger Splits a bus into bits or merges bits into a bus 8-bit a → a₇…a₀

Practice Problems

Problem 1: Combinational or Sequential?

Classify each circuit and explain why: (a) a full adder, (b) a counter that increments each clock tick, (c) a 4-input multiplexer.

Click to reveal solution - **(a) Full adder — combinational.** Its output (`sum`, `cout`) is a pure function of the current inputs `a`, `b`, `cin`. No feedback, no stored state. - **(b) Counter — sequential.** It must *remember* the current count and add 1 each clock edge; the output depends on stored state, which requires feedback. - **(c) Multiplexer — combinational.** It selects one of its data inputs based on the select lines right now; no memory involved. The test: does the output depend only on the present inputs (combinational) or also on past values / stored state (sequential)?

Problem 2: SoP from a Truth Table

Use sum-of-products to derive an equation for the function f(a, b, c) that is 1 exactly when the input has the bit pattern 001, 100, or 111.

Click to reveal solution Write one product term per specified 1-row, complementing inputs that are `0`: 
f = (ā · b̄ · c)     ← 001
  + (a · b̄ · c̄)     ← 100
  + (a · b · c)      ← 111
That is three 3-input AND gates feeding one 3-input OR gate. Each product term is `1` for exactly one input pattern; the OR makes `f` true if any of the three occurs.

Problem 3: Verify a Full-Adder Row

For the full adder, what are sum and cout when a = 1, b = 1, cin = 1? Check it against the SoP equations.

Click to reveal solution Adding `1 + 1 + 1 = 3 = binary 11`, so `sum = 1` and `cout = 1`. Check against the table row `a=1, b=1, cin=1`: `sum = 1`, `cout = 1`. ✓ From the equations: the `sum` term `(a · b · cin) = 1·1·1 = 1`, so `sum = 1`. The `cout` term `(a · b · cin) = 1`, so `cout = 1`. Both confirmed.

Problem 4: Counting Rows

You want to build a single SoP circuit that directly adds two 4-bit numbers with a carry-in (no composition). How many rows would the truth table have, and why is this a bad idea?

Click to reveal solution Inputs: `cin` (1) + `a` (4 bits) + `b` (4 bits) = **9 inputs**, so `2⁹ = 512` rows. It is a bad idea because the table size grows *exponentially* with the number of inputs, and the resulting flat circuit is huge and unstructured. For an 8-bit adder it would be `2¹⁷ = 131,072` rows — utterly impractical. The right approach is **composition**: build one 1-bit full adder, then chain copies of it (ripple-carry). Effort grows *linearly*, not exponentially.

Problem 5: Carry Ripple

In an 8-bit ripple-carry adder, you add a = 11111111 and b = 00000001 with cin = 0. Describe what the carry does and give sum and cout.

Click to reveal solution `255 + 1 = 256`, which does not fit in 8 bits. In binary the carry generated at bit 0 ripples all the way up: 
  carry: 1 1 1 1 1 1 1 1
         1 1 1 1 1 1 1 1   (a = 255)
       + 0 0 0 0 0 0 0 1   (b = 1)
       -----------------
       1 0 0 0 0 0 0 0 0
So `sum = 00000000` and `cout = 1`. The carry from bit 0 propagates through all eight full adders — a worst-case path for propagation delay, since the final `sum` bit and `cout` are not valid until the carry has rippled through the entire chain.

Problem 6: Subtraction via the Adder

Using only an 8-bit ripple-carry adder (plus inverters), how do you compute a - b? Demonstrate with a = 5, b = 3.

Click to reveal solution Compute `a + (~b) + 1`: invert every bit of `b` and set the adder's `cin = 1`. For `a = 5 = 00000101`, `b = 3 = 00000011`: 
~b = 11111100
a  = 00000101
cin = 1

  00000101   (a)
+ 11111100   (~b)
+        1   (cin)
----------
1 00000010
Discard the carry-out: `sum = 00000010 = 2`, and indeed `5 - 3 = 2`. ✓ This is exactly why an ALU can share a single adder for both addition and subtraction — invert `b` and set `cin = 1`.

Further Reading

Summary

  1. Combinational logic is stateless and acyclic — outputs depend only on current inputs — in contrast to sequential logic, which has feedback and stores state.

  2. Three primitive gates (AND a·b, OR a+b, NOT ā) plus the wiring convention that crossings need a dot to connect are enough to build any combinational function.

  3. Sum-of-products is a three-step recipe: build a truth table, identify the 1-rows, then OR together one AND product term per 1-row.

  4. One SoP equation per output bit — the max2 problem needs separate equations for r₁ and r₀; the parity detector derives odd simply as even̄.

  5. A 1-bit full adder (inputs a, b, cin; outputs sum, cout) is the universal building block for addition, derived directly from grade-school binary carrying.

  6. Brute force fails: a flat 8-bit adder truth table has 2¹⁷ rows. Composition wins: chain eight full adders into an 8-bit ripple-carry adder, each cout feeding the next cin.

  7. Splitters and mergers bridge 8-bit buses and single-bit adder pins, and the carry's journey through the chain defines the adder's propagation delay.

  8. Subtraction reuses the adder: a - b = a + (~b) + 1, implemented by inverting b and setting cin = 1 — the foundation for the next lecture's ALU components.