Number Systems, Logic Gates & Boolean Algebra

Decimal and Binary: One Idea, Two Bases

You already know the only concept required: place value. In decimal, 347 means 3×100 + 4×10 + 7×1 — each column weighs ten times its neighbor. Binary works identically with columns weighing two times their neighbor:

Binary → Decimal: Add the Weights

Write the weights over the bits and sum wherever a 1 appears. That's the entire method — and exactly what the Digital Lab's Binary Explorer animates as you click bits.

Decimal → Binary: Two Methods

• Repeated division by 2: divide, keep the remainder, repeat; read remainders bottom-up. 25 → 12 r1 → 6 r0 → 3 r0 → 1 r1 → 0 r1 gives 11001₂.
• Greatest-weight subtraction: subtract the largest power of 2 that fits, mark that bit 1, repeat. 25 − 16 = 9, − 8 = 1, − 1 = 0 → 11001₂. Faster mentally once the weights are memorized.

Octal and Hexadecimal: Binary Shorthand

Nobody enjoys reading 1010111101101001. Octal and hex exist to compress binary for humans, and both work by the same beautiful accident of powers: 8 = 2³ and 16 = 2⁴, so one octal digit is exactly 3 bits and one hex digit is exactly 4 bits (a nibble).

The Grouping Shortcut (no arithmetic required)

Grouping starts from the right (LSB). Convert hex→binary by expanding each digit back to its 4 bits. Between octal and hex? Go through binary — it's the common language.

Arithmetic in Base-N

Binary Addition: Four Facts Total

Worked example:

The rhythm is identical to decimal addition — you just carry at 2 instead of at 10. The same is true in any base: hex carries at 16 (9 + 8 = 11₁₆, i.e., "one-one": 1 carry, 1 down).

Binary Subtraction

Borrowing works (0 − 1 borrows a 2 from the next column), but real hardware doesn't bother: it adds the 2's complement instead — one adder circuit, both operations. That trick is the whole next tab.

Hex Arithmetic

Signed Binary: 2's Complement

Bits have no minus sign, so we spend one bit to encode it. The naive approach (sign-magnitude) creates two zeros and breaks the adder. The universal solution is 2's complement, where the MSB carries negative weight:

Negating a Number: Invert and Add One

Why Hardware Loves It

• Subtraction = addition: A − B is computed as A + (−B). One adder does everything; the carry out of the top bit is simply discarded.
• One zero, instant sign test: MSB = 1 means negative, full stop.
• Overflow is detectable: add two positives and get a negative (0111 1111 + 1 = 1000 0000, i.e., 127+1 = −128) — the classic wraparound. Watch it live in the Lab with the SIGNED toggle on.

The Five Fundamental Gates

A logic gate is a transistor circuit that computes one Boolean operation. Its complete personality fits in a truth table — list every input combination (2ⁿ rows) and the output for each. Master these five tables and you can read any digital schematic:

Reading the Symbols

• Shape carries meaning: flat-backed D = AND family; curved shield = OR family; triangle = buffer/inverter.
• The bubble is a NOT: NAND is literally the AND symbol wearing a bubble. No bubble, no inversion.
• The dot and plus are operators, not arithmetic: A·B reads "A AND B"; A+B reads "A OR B". In Boolean land 1+1 = 1.

NAND and NOR: The Universal Gates

Here is one of digital design's most elegant facts: you don't need five gate types. NAND alone can build everything — and so can NOR. A gate with this property is called universal.

Building the Basics from NAND

• NOT: tie both NAND inputs together. (A·A)̅ = A̅ — the idempotent law in action.
• AND: NAND followed by that NAND-inverter. Two gates.
• OR: invert each input, then NAND them: A̅ NAND B̅ = (A̅·B̅)̅ = A + B — which is DeMorgan's theorem doing the heavy lifting. Three gates.

The NOR story is the perfect mirror (swap the roles of AND and OR throughout — Boolean algebra's duality principle).

Why This Matters Beyond Elegance

• Silicon economics: in CMOS, NAND is the cheapest, fastest gate to fabricate — so real chips are seas of NAND with everything else synthesized from it. ("NAND flash" memory earned its name honestly.)
• Inventory reality: a technician with a tube of 7400 quad-NAND ICs can prototype any logic function on the bench.
• Historical proof: the Apollo Guidance Computer was built entirely from one gate type — 3-input NOR — about 5,600 of them, navigating to the Moon.

The Laws of Boolean Algebra

Boolean algebra lets you simplify a circuit on paper before spending gates on it. Fewer gates means lower cost, less power, and fewer failure points. The laws come in memorable pairs — every AND rule has an OR twin (duality):

Worked Simplification

Three gates collapsed to a piece of wire — and the truth tables of the original and simplified expressions are identical, which is the only test that matters.

DeMorgan's Theorems and Truth Table Analysis

Augustus DeMorgan's two theorems are the master keys of gate-level reasoning — they convert freely between the AND world and the OR world:

The verbal rule: break the bar, change the operator (· ↔ +), and complement each term. The schematic rule: a bubble on a gate's output can be "pushed" to its inputs if you also swap the gate's shape — invaluable when a schematic is drawn in mixed logic.

Proof by Truth Table

Columns four and seven match on every row — the theorem is proven, no algebra required. This column-by-column construction is the general method for analyzing any combinational circuit: work from the inputs through each intermediate signal to the output, one column per node.

Analysis Procedure for Any Gate Network

1. Label every internal node on the schematic.
2. Build a truth table with a column for each node, filling left to right.
3. The final column is the circuit's function — compare it against the five standard tables (or a required spec).
4. Optionally, write the Boolean expression by composing gate expressions from output back to inputs, then simplify with Tab 8's laws and re-verify by table.