--- title: "Boolean Logic & Gates" description: "AND/OR/NOT and digital circuits" source: https://vizlearn.app/cs/architecture/boolean-logic --- # Boolean Logic and Gates A logic gate is a lookup table with wires attached. It takes one or two bits, finds the matching row in a table of two or four entries, and puts what it finds there on its output. AND answers 1 only when both inputs are 1; OR answers 1 when at least one is; NOT inverts its single input. Once the wires have settled, nothing about a gate is deeper than that table. And yet two of them — an XOR and an AND, fed by the same pair of bits — answer `1 + 1 = 10`. Nobody put addition into those gates. It fell out of the wiring. That is the claim this lesson makes good on. Connecting gates does not invent a new rule; it forces a new table, one you do not get to choose. Drive one input pair through the pair of gates and you get one row of that table. Drive the rest and the whole of two-bit addition is sitting there, decided the moment somebody chose which wire went where. ## A Gate Is Its Table There is a temptation to think of AND as *doing* something — testing, deciding, evaluating. It is worth resisting early, because the moment a circuit gets large enough to matter, the "deciding" story stops helping. Take AND. There are exactly four things two bits can be: `(0,0)`, `(0,1)`, `(1,0)`, `(1,1)`. AND answers `0, 0, 0, 1`. Write that down and you have said everything true about AND. Flip every output and you get NAND: `1, 1, 1, 0`, a different gate with an equally complete description. Change only the `(1,1)` entry to 0 and you get the always-zero function instead. The on-stage lookup table is authoritative for exactly this reason: the lookup is not a stand-in for the real behaviour, it *is* the behaviour. Two consequences follow immediately. First, there are only 16 possible two-input gates, because there are only 16 ways to fill four rows with bits, and most of them are useless. Second, a gate has no memory. Its answer depends on nothing but what is on its wires right now, which is why a pile of gates cannot count or remember on its own — that takes feedback, and feedback is a different lesson. ## Boolean Logic Step by Step The default run wires a half adder — an XOR and an AND, both fed by the same two input wires — and drives `a = 1, b = 1` into it. 1. **Nothing is driven.** Both gates are drawn from the start, faint, with dead wires between them. The circuit's shape is the question, so it is never hidden; only the signals are revealed. 2. **The inputs go in.** `a` and `b` both become 1, and each wire carries its value to two places at once. One output feeding several inputs is ordinary and free here; on real silicon it is called fan-out and it is not free. 3. **XOR reads its table.** The gate lights up and its own four-row table docks below the circuit with the row `(1, 1)` picked out. That row says 0. The gate does not add, compare, or check anything — it locates a row. 4. **XOR drives its wire.** The 0 lands on the `sum` wire and travels to the output. The pulse is the only thing moving; the wire already shows its final value, so pausing anywhere still reads correctly. 5. **AND reads its table.** Same two inputs, different table: `(1, 1)` answers 1. 6. **AND drives its wire.** `carry` goes to 1. 7. **Read the outputs.** `sum = 0, carry = 1`. Read the two bits together as one binary number and you get `10` — which is 2, which is 1 + 1. The carry is the twos column. 8. **The other three rows.** The remaining input combinations get a beat each: every wire re-solves, and the row lands beside the reference column for `a + b`. Nothing about the circuit changes between them — only the inputs do — which is what makes the sweep a proof rather than three more lessons. 9. **The verdict.** All four rows sit beside the reference column for `a + b`, and they match. Two gates, chosen and connected by a person, produced arithmetic that nobody wrote down anywhere. Beats 3 and 4 split one gate operation into two visible moments: first the selected truth-table row, then the value arriving on the output wire. The split belongs to the hardware story; it does not imply two separate computations. ## Wiring Decides the Table A half adder cannot be chained. It has no way to accept a carry from the column to its right, so it can add the two lowest bits of a number and nothing else. The `Full adder: 1+1+1` scenario fixes that with five gates: two XORs, two ANDs, and an OR that merges the two possible carries. Its table has eight rows, and `1 + 1 + 1` correctly answers `sum = 1, carry = 1` — binary `11`, which is 3. That circuit is the unit of arithmetic. Chain eight of them, each one's carry out feeding the next one's carry in, and you have the byte adder from Two's Complement — the one that adds signed numbers without ever testing a sign. The whole of integer addition, in a machine, is gates arranged this way. Two scenarios show how small the starting set can be. `XOR from AND/OR/NOT` builds XOR out of the three primitives: `(a OR b) AND NOT(a AND b)` — either one of them, but not both. XOR is a convenience, not a fourth ingredient. `AND from NAND` goes further: feed a single wire into *both* inputs of a NAND and only the rows `(0,0)` and `(1,1)` can ever fire, which makes it an inverter. NAND plus that trick reaches NOT, then AND, then OR, then everything. This is not a curiosity — a CMOS NAND costs four transistors while a CMOS AND costs six, so real chips are built out of the gate that is cheapest to make, not the one that is easiest to name. ## Edge Cases - **A one-input gate has a two-row table.** NOT is the whole of it: `0 → 1`, `1 → 0`. Chain two and you get a wire back, which is the cheapest demonstration that composition can cancel a gate as easily as build one. - **The same wire can reach both pins of a gate.** Then only the rows where the two inputs agree are reachable, and the gate collapses into a one-input function. That is a feature when you want a NAND to act as an inverter, and a bug when you did it by accident. - **A wrong circuit is usually right most of the time.** The `Broken: OR instead of XOR` scenario swaps one gate. OR and XOR disagree on exactly one input pair out of four, so three rows still match binary addition perfectly. Testing `0 + 1` and `1 + 0` would have passed it. - **Tables grow as 2ⁿ.** Two inputs give four rows, three give eight, and a 32-bit adder's inputs give more rows than you could enumerate in a lifetime. A useful rule of thumb: enumerate up to about four inputs, and past that stop. Real designs switch to Boolean algebra to simplify by hand, simulation over chosen input vectors to smoke out bugs, and formal equivalence checking to prove two versions of a circuit agree on all 2ⁿ rows without visiting them. Truth tables are how you *define* a gate and how you check a small circuit; they are not how anyone verifies a real one. - **Gate count is not the only cost.** A ripple-carry adder is small and slow, because in the worst case a carry must propagate from bit 0 through to bit 31. Carry-lookahead circuits spend far more gates to shorten that chain. Same table, different silicon. ## Common Mistakes - **Treating XOR as a basic gate.** It is drawn as one symbol and it is manufactured as one component, but it is a composite. AND, OR, and NOT already reach every possible table; XOR is a name for a common arrangement of them. - **Reading a circuit as a sequence of steps.** This lesson walks gates one at a time because that is how a person follows a diagram. Real gates respond continuously and concurrently, with propagation delay along paths. The ordering shown here is a reading order, not a sequence of software calls. - **Confusing bitwise and logical operators.** In C-family languages `&` applies the AND table to every bit position in parallel, while `&&` collapses each side to true/false and short-circuits. In `if (flags & MASK && x)`, `&` binds before `&&`: the expression means `if ((flags & MASK) && x)`. Parentheses make the intended grouping explicit. - **Reading OR as "one or the other".** English "or" usually excludes both — coffee *or* tea. Boolean OR includes it: `1 OR 1` is 1. The gate that matches the everyday sense is XOR, and this mismatch is behind a large share of first-week confusion. - **Assuming a matching table means matching hardware.** Two circuits with identical truth tables can behave differently in a real machine, because signals arrive at different times and outputs can flicker through wrong values on the way to the right one. Tables say what a circuit settles on, not what it does en route. ## A Note on Simplification This lesson is an explainer, not a substitute for a digital design course. Gates here switch instantly, one output drives any number of inputs, and every wire is ideal. None of that is true of hardware: real gates have propagation delay measured in picoseconds, a driver can only feed so many loads before it slows down or fails, and transient glitches during switching are the reason synchronous designs put a clock between one block of logic and the next. Power, area, and timing analysis — most of what a chip designer actually spends time on — are all outside what an animation of four wires can show. The logic itself, though, is exactly right. AND, OR, and NOT compose into everything a computer computes, and the half adder on screen is the same circuit, gate for gate, as the one in the corner of a real ALU.