WHAT. Before three inputs, master two. We list all four ways two lamps can be on/off and count the on-lamps each time.
WHY. Listing every case is the only way to be sure we never meet a scenario the circuit hasn't been told about (Contract rule: cover all cases). Four rows = four possible inputs, no gaps.
PICTURE. Four rows of two lamps; the count is written as a 2-bit box (CS).
Now stare at the two output columns:
S is on in exactly the two rows where the lamps disagree (one on, one off). "On when inputs differ" is the XOR, written ⊕.
C is on in exactly the one row where both lamps are on. "On when both" is the AND, written ⋅.
\qquad
C = \underbrace{A}_{\text{first bit}}\ \overbrace{\cdot}^{\text{“both?”}}\ \underbrace{B}_{\text{second bit}}$$
> [!mistake] The tempting wrong carry
> "Adding sounds like OR, so $C = A + B$?" No. OR fires on the $(0,1)$ row too, but $0+1$ carries **nothing**. Carry is ==AND==: on only when *both* are 1.
---
## Step 3 — The problem: real columns get a carry from the right
**WHAT.** When you add two multi-bit numbers, each column receives a **carry-in** $C_{in}$ from the column to its right. The half adder has no wire for it.
**WHY.** So the half adder is *incomplete for chaining*. We must upgrade it to accept **three** inputs: $A$, $B$, and $C_{in}$. That upgraded machine is the **full adder**.
**PICTURE.** Two columns side by side; the right column's spill arrow becomes the left column's $C_{in}$ arrow.
![[deepdives/dd-hardware-3.3.01-d2-s03.png]]
Nothing new is assumed — $C_{in}$ is just another lamp, a third one, feeding the same column.
---
## Step 4 — Full adder truth table: count three lamps
**WHAT.** Same game, now with **three** lamps. Eight rows (all combinations of three bits). For each, count the on-lamps and write the count as a 2-bit box $(C_{out}\,S)$.
**WHY.** Three bits → $2^3 = 8$ cases. Listing all eight guarantees no missing scenario, including the degenerate all-off row and the maxed-out all-on row.
**PICTURE.** Eight rows of three lamps; the running count (0,1,2,3) written beside each as binary.
![[deepdives/dd-hardware-3.3.01-d2-s04.png]]
| $A$ | $B$ | $C_{in}$ | on-count | $C_{out}$ | $S$ |
|--|--|--|--|--|--|
| 0 | 0 | 0 | 0 | 0 | 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 | 1 | 1 |
---
## Step 5 — Reading the Sum: why it is XOR of all three
**WHAT.** Look only at the $S$ column. It is 1 exactly when the on-count is **odd** (count 1 or 3), and 0 when the count is **even** (0 or 2).
**WHY.** [[XOR gate|XOR]] answers precisely the question "is the number of 1s odd?". Feed bits in one at a time: XOR flips its output every time a 1 arrives. Start at 0; an **odd** number of flips lands on 1, an **even** number lands back on 0. That is the parity of the inputs — exactly the $S$ column.
**PICTURE.** A flip-track: start at 0, each incoming 1 flips the pointer; the final position is $S$.
![[deepdives/dd-hardware-3.3.01-d2-s05.png]]
$$S = \underbrace{A}_{\text{flip?}}\ \oplus\ \underbrace{B}_{\text{flip?}}\ \oplus\ \underbrace{C_{in}}_{\text{flip?}}
\quad\Longleftrightarrow\quad \text{“odd number of 1s?”}$$
> [!mistake] Sum is not $A+B+C_{in}$
> In Boolean algebra $+$ means **OR**, not arithmetic add. OR of $(1,1,0)$ is 1, but the true Sum bit there is 0 (count 2 = even). Sum must be ==parity== → XOR.
---
## Step 6 — Reading the Carry-out: why it is a majority vote
**WHAT.** Look only at the $C_{out}$ column. It is 1 exactly in the four rows where the on-count is **at least two** (count 2 or 3).
**WHY.** "At least two of three are on" is precisely a **majority vote**: whatever value the majority of the three inputs holds, that is $C_{out}$. We can spell out the "≥ 2 on" rule as an OR of the three ways to pick a *pair*:
$$C_{out} = \underbrace{AB}_{A\&B\text{ on}} \;+\; \underbrace{AC_{in}}_{A\&C_{in}\text{ on}} \;+\; \underbrace{BC_{in}}_{B\&C_{in}\text{ on}}$$
Here $\cdot$ (AND) means "both on", and $+$ ([[OR gate|OR]]) means "any of these pairs is enough". If *any* pair is both-on, the count is already ≥ 2, so $C_{out}=1$.
**PICTURE.** Three voters; a raised hand for each "on". Two or three hands up ⇒ the carry lamp lights.
![[deepdives/dd-hardware-3.3.01-d2-s06.png]]
---
## Step 7 — Building the full adder from two half adders
**WHAT.** Instead of new gates, reuse the Step-2 machine twice.
- **HA1** adds $A,B$ → gives $S_1 = A\oplus B$ and $C_1 = AB$.
- **HA2** adds $S_1$ and $C_{in}$ → gives final $S = S_1\oplus C_{in}$ and $C_2 = S_1\,C_{in}$.
- One [[OR gate|OR]] merges the two carries: $C_{out} = C_1 + C_2$.
**WHY.** $S = (A\oplus B)\oplus C_{in}$ is XOR-of-three (Step 5 ✓). And $C_{out} = AB + (A\oplus B)C_{in}$ reproduces the majority rule: if $A,B$ both on, $AB$ fires; if exactly one of them is on, then $A\oplus B=1$, so the carry needs $C_{in}$ on — which is the "≥2 on" rule again.
**PICTURE.** Two half-adder blocks wired in series, their carries OR-ed together.
![[deepdives/dd-hardware-3.3.01-d2-s07.png]]
> [!formula] The two carry forms are the same circuit
> $$C_{out} = AB + AC_{in} + BC_{in} \;\equiv\; AB + (A\oplus B)\,C_{in}$$
> Left = pick any pair. Right = "both $A,B$" **or** "exactly one of $A,B$, plus the carry". Same eight rows.
---
## Step 8 — Edge and degenerate cases (never leave a gap)
**WHAT.** Check the two extreme rows and the "half-adder-inside" case.
**WHY.** Contract rule 4: the reader must never meet a scenario we didn't show.
**PICTURE.** Three spotlight rows: all-off, all-on, and $C_{in}=0$ collapsing to a half adder.
![[deepdives/dd-hardware-3.3.01-d2-s08.png]]
- **All off** $(0,0,0)$: count 0 → $S=0$, $C_{out}=0$. XOR of zeros = 0; no pair on → majority 0. ✓
- **All on** $(1,1,1)$: count 3 → $S=1$, $C_{out}=1$, i.e. $11_2 = 3$. XOR of three 1s = 1 (odd); every pair on → majority 1. ✓
- **Carry-in zero** $(C_{in}=0)$: the majority term drops to $AB$ and the parity term drops to $A\oplus B$ — the full adder **becomes** the half adder exactly. This is the sanity bridge between Step 2 and Step 6.
---
## The one-picture summary
![[deepdives/dd-hardware-3.3.01-d2-s09.png]]
Three inputs enter; **parity** (odd-count) produces $S$; **majority** (≥2-on) produces $C_{out}$. That is the entire full adder.
> [!formula] Everything on one line
> $$S = A\oplus B\oplus C_{in} \quad(\text{parity}),\qquad C_{out} = AB + AC_{in} + BC_{in}\quad(\text{majority})$$
> [!recall]- Feynman retelling in plain words
> You've got three little lamps that are each on or off. You want to know two things. First: **is an odd number of them on?** If yes, the "Sum" lamp lights — that's the XOR, a flip-switch that toggles once per on-lamp and only ends lit if it toggled an odd number of times. Second: **are at least two of them on?** If yes, the "Carry" lamp lights — that's the majority vote, because two lamps make a count of "2" which is too big for one box and spills to the next column. That's it. Set the carry-in to off and this exact machine shrinks back to the simpler two-lamp half adder. Chain a row of these, feeding each spill into its neighbour, and you can add numbers of any size — which is how a computer adds. See it here (Sum), cart it next door (Carry).
> [!mnemonic] Two questions, two gates
> **Sum asks "odd?" → XOR. Carry asks "at least two?" → Majority.**
## Connections
- [[XOR gate]] — the parity engine behind $S$ (Steps 2, 5)
- [[AND gate]] — the "both on" test inside every carry pair (Steps 2, 6)
- [[OR gate]] — merges the pair-terms and the two half-adder carries (Steps 6, 7)
- [[Truth tables and minterms]] — the read-off method used in Steps 2 and 4
- [[Ripple-carry adder]] — full adders chained, each spill feeding the next
- [[Carry-lookahead adder]] — computes carries in parallel to beat ripple delay
- [[Two's complement subtraction]] — the same adder, reused for subtraction
- [[Combinational circuits]] — the parent family (output depends only on current inputs)
