# Boolean Algebra & Logic Gates > The same AND/OR/NOT you already know, turned into an algebra you can compute with - and then etched into hardware as logic gates. This is the bridge from 'true and false' all the way down to how a CPU adds two numbers. --- # Boolean Algebra & Logic Gates Here is one of the most beautiful facts in all of computing: the entire machine in front of you - every calculation, every pixel, every saved file - is built out of the three little words you already know from [Propositional Logic](/guides/propositional-logic). **AND, OR, and NOT.** That's the whole alphabet. Everything else is spelling. This guide walks that bridge in two steps. First, **boolean algebra**: treating true/false as values you can calculate with, using laws that let you simplify a tangled condition the same way you'd simplify `2(x + 3)`. Then, **logic gates**: those same operations built as physical components - and how a handful of them, wired together, learn to *add*. By the end, "the computer is only logic" will stop being a slogan and become something you can actually trace, gate by gate. ## How to read this - **Here for the "how does a CPU work" payoff?** [Phase 3](03-from-gates-to-a-computer.md) builds an adder from gates. - **Want the full bridge?** Read in order - the algebra (Phase 1) and the gates (Phase 2) are what make Phase 3 click. ## The phases 1. **[Boolean Algebra: The Laws](01-boolean-algebra-the-laws.md)** - true/false as 1/0, the laws (incl. De Morgan), and simplifying expressions. 2. **[Logic Gates: Logic Made Physical](02-logic-gates-logic-made-physical.md)** - AND/OR/NOT/NAND/NOR/ XOR gates, their truth tables, and why NAND alone can build anything. 3. **[From Gates to a Computer](03-from-gates-to-a-computer.md)** - wiring gates into an adder, and the leap from "adds two bits" to "is a CPU." > This builds directly on [Propositional Logic](/guides/propositional-logic). It pairs well with the > hardware track for what happens once these gates become silicon. --- # Boolean Algebra: The Laws You already push true and false around with words - and, or, not. Boolean algebra swaps the words for symbols, so you can *calculate* with truth the way you calculate with numbers. The payoff is real: a condition that looks like a tangle of `&&`, `||`, and `!` often collapses into something short once you know a handful of rules. This phase builds on [propositional logic](/guides/propositional-logic), where AND, OR, and NOT were connectives between statements. Here they're operations in an algebra - and an algebra comes with laws you can lean on. ## Two values, three operations Boolean algebra is built from exactly two values: - `1` means **true** - `0` means **false** That's the whole number system. No 2, no 5, no -1. Only on and off. Three operations combine these values. Each has more than one common notation, and you'll meet all of them in the wild, so see them side by side: ```text AND written A · B or A ∧ B or AB OR written A + B or A ∨ B NOT written ¬A or Ā (an overbar) ``` The shorthand `AB` (two things side by side) means AND, the way `xy` means "x times y" in ordinary algebra. This guide uses `·` for AND, `+` for OR, and `¬` for NOT, with the overbar where it reads more cleanly. A reminder of what each does, in case the symbols are new: ```text A · B is 1 only when BOTH A and B are 1 A + B is 1 when EITHER A or B (or both) is 1 ¬A flips: ¬1 = 0, and ¬0 = 1 ``` ## The laws Here's what makes this an *algebra*. These identities hold for any values of A, B, and C. Read each as a sentence - that's how they stick. **Identity** - combining with the "do nothing" value leaves you unchanged. ```text A · 1 = A AND-ing with true changes nothing A + 0 = A OR-ing with false changes nothing ``` **Domination (null)** - one value swallows everything. ```text A · 0 = 0 AND-ing with false is always false A + 1 = 1 OR-ing with true is always true ``` **Idempotent** - repeating yourself adds nothing. ```text A · A = A "A and A" is only A A + A = A "A or A" is only A ``` **Complement** - a thing and its opposite. ```text A · ¬A = 0 something can't be true and false at once A + ¬A = 1 something is either true or false - always ``` **Double negation** - two flips cancel. ```text ¬¬A = A "not not A" is A ``` **Commutative** - order doesn't matter. ```text A · B = B · A A + B = B + A ``` **Associative** - grouping doesn't matter. ```text (A · B) · C = A · (B · C) (A + B) + C = A + (B + C) ``` **Distributive** - here boolean algebra goes beyond ordinary arithmetic. AND distributes over OR, *and* OR distributes over AND (that second one fails for regular numbers). ```text A · (B + C) = A·B + A·C A + (B · C) = (A + B) · (A + C) ``` **Absorption** - a shortcut that collapses a redundant term. ```text A + A·B = A if A alone is enough, the extra AND doesn't matter ``` **De Morgan** - the rule for pushing a NOT through a group. A negated AND becomes an OR of negations, and a negated OR becomes an AND of negations. ```text ¬(A · B) = ¬A + ¬B ¬(A + B) = ¬A · ¬B ``` De Morgan is the most useful law for cleaning up code conditions: it moves an outer `!` inward, rewriting "not (this and that)" as something more readable. You met the truth-table version in [propositional logic](/guides/propositional-logic); here it's a mechanical rewrite you apply on sight. ## A worked simplification Laws stay abstract until you watch them collapse a real expression. Let's simplify `A + ¬A·B` down to `A + B`. Each step names the law that justifies it. ```text Start: A + ¬A·B Distributive (A + ¬A) · (A + B) (OR over AND): we factor the A out across the + Complement: 1 · (A + B) A + ¬A = 1 the left group is always true Identity: A + B 1 · X = X AND-ing with true changes nothing Result: A + B ``` Three named steps, and a five-symbol expression became three. `¬A·B` folds in because whenever A is false, `¬A·B` is B - so the whole thing behaves like "A or B" anyway. Here's a shorter one using absorption, simplifying `A · (A + B)` to `A`: ```text Start: A · (A + B) Distributive: A·A + A·B Idempotent: A + A·B A · A = A Absorption: A A + A·B = A Result: A ``` If A is true the whole thing is true; if A is false the whole thing is false. The expression never depends on B - and the algebra proves it without you checking a single row of a truth table. ## For builders This is not a math-class party trick. Every time you write a condition like: ```text if (isAdmin && !(isAdmin && isSuspended)) { ... } ``` you've shipped something harder to read than it needs to be. Apply De Morgan to the inner group, then absorption, and it reduces to `isAdmin && !isSuspended`. Same behavior, half the surface area for a bug to hide in. Simplifying boolean conditions buys you three concrete things: - **Clearer guards.** A short condition is one a reviewer can hold in their head. - **Fewer bugs.** Redundant terms (`A + A·B`) are where a future edit changes one copy and forgets the other. - **Clear intent.** When the code says `isAdmin && !isSuspended`, the rule is obvious; the tangled version leaves everyone guessing what it tests. You don't have to do this by hand every time. But knowing the laws means you can *recognize* when a condition is more complicated than the logic requires. > ⚠️ **`+` is OR, not addition.** In boolean algebra `1 + 1 = 1`, not 2. The `+` means OR, so > "true or true" is true - there's no value above 1 to land on. If you carry arithmetic > instincts into these expressions, this is the trap that gets you. `A + A = A`, not `2A`. ## Recap - Boolean algebra has exactly two values: `1` (true) and `0` (false). - Three operations: AND (`·`), OR (`+`), NOT (`¬`) - each with several notations. - The laws (identity, domination, idempotent, complement, double negation, commutative, associative, distributive, absorption, De Morgan) let you rewrite expressions while preserving their meaning. - **De Morgan** pushes a NOT through a group; **absorption** drops redundant terms - together they clean up most real-world conditions. - `+` means OR, so `1 + 1 = 1`. It is not arithmetic. ## Open-ended exercise Here's a condition from a real access-control system: ```text if (isAdmin && !(isAdmin && isSuspended)) { allow(); } ``` Apply the boolean algebra laws you've learned to simplify this expression step by step. Name the law at each step. Then write the final simplified condition in plain English: what rule is it actually checking? A quick check before you move on: ```quiz [ { "q": "In boolean algebra, what do the symbols 1 and 0 stand for?", "choices": ["The numbers one and zero, used for counting", "True and false, respectively", "On and off, where 0 is true", "Maximum and minimum signal strength"], "answer": 1, "explain": "Boolean algebra has only two values: 1 means true and 0 means false. There are no other numbers in the system." }, { "q": "What does A + 1 simplify to?", "choices": ["A", "1", "0", "It depends on the value of A"], "answer": 1, "explain": "This is the domination (null) law: A + 1 = 1. OR-ing anything with true gives true, regardless of A. (And remember + is OR, not addition.)" }, { "q": "Simplify A · (A + B).", "choices": ["A · B", "A + B", "A", "B"], "answer": 2, "explain": "By absorption (via distribution and idempotence), A · (A + B) = A. The result never depends on B: if A is true it's true, if A is false it's false." } ] ``` --- # Logic Gates: Logic Made Physical In Phase 1, AND, OR, and NOT were ideas - rules for combining `true` and `false`. They lived on paper. This phase gives them a body. The logic you learned isn't a metaphor for how computers work. It *is* how computers work. The same three operations, soldered into silicon, are the entire foundation under everything your machine does. ## What a gate actually is A **logic gate** is a small physical component that takes one or two electrical signals as input and produces one signal as output. That's it. No magic. Inside a chip, a wire carries either a higher voltage or a lower one. We call the high voltage `1` and the low voltage `0` (some designs flip this, but the principle holds). A wire is never "kind of on" - it's exactly one of two states. That's the whole bridge: Phase 1's `true` and `false` became `1` and `0`, and now those become voltages. A gate is a boolean operation you can hold in your hand. When you think `A AND B`, a chip routes two voltages into an AND gate and reads what comes out - the logic didn't change, it got physical. ## The basic gates Three gates map directly onto the three operations you know. Each is fully described by its truth table: list every possible input, write down the output, and you've captured everything the gate does. **AND** - output is `1` only when *both* inputs are `1`. ```text A B | A AND B 0 0 | 0 0 1 | 0 1 0 | 0 1 1 | 1 ``` **OR** - output is `1` when *at least one* input is `1`. ```text A B | A OR B 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 1 ``` **NOT** - takes a single input and flips it. The one gate with only one input. ```text A | NOT A 0 | 1 1 | 0 ``` If these tables feel familiar, good - they're the same ones from [the laws of boolean algebra](01-boolean-algebra-the-laws.md), now read as hardware. ## Derived gates You build more useful gates by gluing the basics together. Three show up so often they get their own names and symbols. **NAND** - "not AND." Run AND, then flip the result. It outputs `0` only when both inputs are `1`, and `1` in every other case. ```text A B | A NAND B 0 0 | 1 0 1 | 1 1 0 | 1 1 1 | 0 ``` **NOR** - "not OR." Run OR, then flip it. Outputs `1` only when both inputs are `0`. ```text A B | A NOR B 0 0 | 1 0 1 | 0 1 0 | 0 1 1 | 0 ``` **XOR** - "exclusive OR." Outputs `1` only when the inputs *differ* - one is `1` and the other is `0`. If they match, the output is `0`. Think of it as asking "are these two things different?" ```text A B | A XOR B 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 0 ``` XOR is the workhorse behind addition and comparison. When a computer adds two bits, the "sum" digit before carrying is exactly XOR. You'll see that in Phase 3. > ⚠️ **XOR is not OR.** They agree on three of the four rows - the difference is the last one. > Plain OR says "one or both," so `1 OR 1` is `1`. XOR says "one *or the other, not both*," so > `1 XOR 1` is `0`. If you ever wonder which you want, ask: should "both true" count? OR says > yes, XOR says no. ## Gate diagrams: how they wire together The truth tables tell you what a gate does. A diagram shows how gates *talk* to each other. Here's a half-adder - the circuit that adds two single bits: ```mermaid flowchart LR A[A] --> AND[AND] A --> XOR[XOR] B[B] --> AND B --> XOR AND --> Cout[Cout] XOR --> Sum[Sum] ``` Two inputs, `A` and `B`, flow into both an AND gate and an XOR gate. AND produces the **carry-out** (`Cout`) - `1` only when both inputs are `1`. XOR produces the **sum** (`Sum`) - `1` when the inputs differ, exactly the "sum" digit before carrying in binary addition. This is the circuit that lives inside every adder in your CPU; chain more gates and you get multi-bit addition. ## Universality: why NAND is special Here's a result that sounds too good to be true: **the NAND gate, all by itself, can build every other gate.** Give an engineer nothing but NAND gates and enough wire, and they can construct AND, OR, NOT, XOR - the whole family (the same is true of NOR alone). This property is called **functional completeness**: one building block, enough to express any boolean function. The cleanest place to see it is NOT. Take a NAND gate and feed the *same* signal into both inputs. Look at the rows where `A` and `B` are equal: ```text A A | A NAND A 0 0 | 1 1 1 | 0 ``` The output is the flip of the input - that's NOT, made from one NAND. ```mermaid flowchart LR A[A] --> NAND[NAND] A --> NAND NAND --> NOT[NOT output] ``` Once you have NOT, the rest follows. NAND is already "AND then flip," so flipping a NAND's output (with another NAND wired as NOT) gives you back a plain **AND**. Getting **OR** takes more wiring, but it's the same idea - chain NANDs until the truth table matches. Why care? Building a chip from one repeated component is cheaper and easier to manufacture than juggling many gate types, and real silicon leans on this hard. The deep idea you saw in [what logic actually is](/guides/what-logic-actually-is) - that a few simple rules can express enormous complexity - is the literal blueprint for a processor. ## For builders You've met these gates already without knowing it. Most languages have **bitwise operators** that apply a logic gate to *every bit of an integer at once*, in parallel: - `&` is AND - `|` is OR - `^` is XOR - `~` is NOT When you write `5 & 3`, the computer writes both numbers in binary, lines up their bits, and runs an AND gate on each column: ```text 0101 (5) & 0011 (3) ------ 0001 (1) ``` So `5 & 3` is `1`. Swap in `|` and you'd get `7` (`0111`); swap in `^` and you'd get `6` (`0110`). The truth tables above are the *only* rules you need to predict the result - column by column, bit by bit. The gates aren't an abstraction sitting above your code; they run underneath it. ## Recap - A **logic gate** is a physical component that does one boolean operation on electrical signals, where high voltage means `1` and low means `0`. - **AND, OR, NOT** are the basic gates - the Phase 1 operations, now in hardware. - **NAND** and **NOR** are those gates with the output flipped; **XOR** outputs `1` only when its inputs *differ*. - **NAND alone can build every other gate** (functional completeness) - start with NOT from a NAND with tied inputs, and the rest follows. - The bitwise operators `&`, `|`, `^`, `~` are these gates run across all the bits of a number at once. ## Open-ended exercise Sketch (in text or on paper) a circuit that uses AND, OR, and NOT gates to implement this condition: `(A AND B) OR (NOT C)`. Then ask: if you only had NAND gates, could you build the same circuit? Why or why not? (Hint: you already know NAND can make NOT, AND, and OR.) Quick check before you move on: ```quiz [ { "q": "What is a logic gate?", "choices": [ "A physical component that performs one boolean operation on electrical signals read as 1s and 0s", "A line of software that simulates true/false values", "A storage cell that remembers a single bit between operations", "A connector that converts one voltage level into another" ], "answer": 0, "explain": "A gate is hardware: it takes signals (high = 1, low = 0) and outputs one signal according to a boolean operation like AND, OR, or NOT." }, { "q": "For which inputs does an XOR gate output 1?", "choices": [ "Only when both inputs are 1", "Only when the two inputs differ (one is 1, the other 0)", "When at least one input is 1, including both", "Only when both inputs are 0" ], "answer": 1, "explain": "XOR means 'exclusive OR': it outputs 1 only when the inputs are different. Unlike plain OR, 1 XOR 1 is 0." }, { "q": "Why is the NAND gate called 'universal' (functionally complete)?", "choices": [ "It is the fastest gate to manufacture", "It is the only gate that works on single inputs", "Every other gate - NOT, AND, OR, XOR - can be built using only NAND gates", "It never produces an output of 0" ], "answer": 2, "explain": "NAND alone can construct any boolean function. For example, a NAND with both inputs tied together acts as NOT, and from NOT the rest follow." } ] ``` Watch it animated: [logic gates](/explainers/LogicGates.dc.html) --- # From Gates to a Computer You've built a real toolkit: [true and false](/guides/what-logic-actually-is), then AND/OR/NOT as [an algebra you can combine them with](/guides/propositional-logic), then those operations made physical as gates in Phase 2. This phase is the payoff - wire a handful of gates together and watch them do something none of them can do alone: **arithmetic**. ## The question driving this phase AND, OR, and NOT are about truth - true/false in, true/false out. Addition is about *numbers*: `2 + 3 = 5`. Those feel like two different worlds. So how does a machine that only knows true and false add numbers? Nobody snuck a calculator inside - there's no "+" component hiding in the silicon, only gates. The answer is one of the most satisfying ideas in computing, and you already have every piece you need. ## Binary addition, recapped Computers count in binary - only `0` and `1`. Adding two single bits has exactly four cases: ```text 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10 ← two! doesn't fit in one bit ``` The first three are calm. `1 + 1` is two, and two in binary is `10` - it doesn't fit in a single bit, so it spills. That spill is the whole game: when a column overflows, the extra `1` moves to the next column over, the same move you make in decimal (`7 + 5 = 12`, write the `2`, carry the `1`). So adding two bits produces *two* answers: a **sum** bit (what you write down) and a **carry** bit (what spills into the next column). Hold onto those two words - we're about to build a circuit for each. ## The half-adder One table for both outputs. Inputs `A` and `B`; outputs `sum` and `carry`: ```text A B | sum carry ---------+----------- 0 0 | 0 0 0 1 | 1 0 1 0 | 1 0 1 1 | 0 1 ``` Look at each output column on its own. The **sum** column is `0, 1, 1, 0` - `1` when exactly one input is `1`, `0` when the inputs match. That's precisely XOR: ```text sum = A XOR B ``` The **carry** column is `0, 0, 0, 1` - `1` only when *both* inputs are `1`. That's AND: ```text carry = A AND B ``` That's the payoff of the whole guide: no new device, no arithmetic bolted onto the hardware. Two gates you already knew - one XOR, one AND - wired to the same two inputs, and the pair *adds*. This circuit is the **half-adder**: ```mermaid flowchart LR A[A] --> X[XOR] B[B] --> X A --> N[AND] B --> N X --> S[sum] N --> C[carry] ``` Two inputs fan out to two gates; two outputs come back. That's all it is. > Why "half"? It can produce a carry *out*, but has no way to accept a carry coming *in* from the > column to its right. To chain columns together, we need to fix that. ## The full adder Past a single bit, each column deals with three things: bit `A`, bit `B`, and the carry that arrived from the column to its right. A **full adder** handles all three - it takes `A`, `B`, and a **carry-in**, and produces a **sum** and a **carry-out**. You can build one from two half-adders and an OR gate: fold the carry-in into the mix and ask "did *either* stage produce a carry?" - that's the OR. Line up one full adder per bit. The carry-out of each feeds the carry-in of its left-hand neighbor - exactly how you carry the `1` by hand, column by column: ```text bit: 3 2 1 0 [FA] ← [FA] ← [FA] ← [FA] ← carry starts at 0 | | | | sum3 sum2 sum1 sum0 ``` That's a **ripple-carry adder** - the carry ripples leftward through the chain. Want to add 8-bit numbers? Chain eight full adders. 64-bit? Chain sixty-four. A machine that adds whole numbers is a row of the same tiny circuit, repeated. ## The leap, plainly put With small variations on the same gates you can also subtract (addition with a flipped sign), and run AND, OR, and NOT across whole numbers at once. Bundle those operations with logic that picks *which* one to run, and you've built an **ALU** - an Arithmetic Logic Unit, the part of a processor that does the math. An ALU is not a computer, though: it computes an answer the instant its inputs arrive and forgets it just as fast - no memory, no sense of time. Two more ingredients get you the rest of the way: - A **memory element** - a small loop of gates called a *latch* that holds a single bit after the input goes away. Stack enough of these and you get registers and RAM: somewhere to keep numbers between steps. - A **clock** - a steady tick that says "now," so operations happen in order instead of all at once, and a held bit updates only when you want it to. Add **control logic** - gates that read an instruction and decide what the ALU should do and which bits go where - and the skeleton of a computer is in front of you: do math (ALU), remember results (latches), take turns (clock), follow instructions (control). That paragraph is a sketch, not a build - a real CPU is millions to billions of gates, and each of those four pieces is a deep topic on its own. But the leap that might have looked like magic, from true/false to a working machine, is now a list of named, understandable parts. None is a miracle. All are gates. ## For builders When you write `a + b` in any language, that line ultimately becomes adder hardware doing the column-by-column carry you just traced. The bitwise operators (`&`, `|`, `^`, `~`) are even more direct - they *are* AND, OR, XOR, and NOT applied across every bit of a number in one shot. The same world you've been reasoning about on paper runs underneath your code. ## The whole journey 1. **True and false** - the two values everything is built from. 2. **Algebra over them** - AND, OR, NOT, and reliable rules for combining them. 3. **Gates** - those operations made physical, in voltage and silicon. 4. **Arithmetic** - gates wired together until they add, subtract, and beyond. Each layer was a short, fair step; stacked up, they reach from a single bit to the machine on your desk. From here it's down into the silicon - how a gate is carved from transistors, how memory and clocks are built for real. That's a hardware story, but it's the physics underneath the logic you now understand. You've finished the logic. The foundation is solid, and it's yours. ## Open-ended exercise A half-adder takes two single-bit inputs (A and B) and produces two outputs: Sum and Carry. The Sum is `A XOR B` and the Carry is `A AND B`. Now imagine chaining two half-adders (plus an OR gate) to make a **full-adder** that also takes a carry-in from a previous stage. Sketch the gate-level diagram for a full-adder, labeling each gate and showing how the carry propagates. The goal is to see how a multi-bit adder - and ultimately a CPU's arithmetic unit - is just gates all the way down. A quick check before you go: ```quiz [ { "q": "In a half-adder, which gate produces the sum bit?", "choices": ["AND", "OR", "XOR", "NOT"], "answer": 2, "explain": "The sum is 1 when exactly one input is 1 and 0 when they match - that's XOR. So sum = A XOR B." }, { "q": "In a half-adder, which gate produces the carry bit?", "choices": ["AND", "XOR", "OR", "NOT"], "answer": 0, "explain": "The carry is 1 only when both inputs are 1 (because 1 + 1 overflows a single bit). That's exactly AND, so carry = A AND B." }, { "q": "What's the big idea this phase demonstrates?", "choices": [ "Computers contain a hidden special 'plus' component separate from logic", "Plain logic gates wired together can perform arithmetic", "Arithmetic and logic are unrelated and need different hardware", "Only XOR gates can do any useful computation" ], "answer": 1, "explain": "No special adder part is hiding in the chip. Ordinary AND/OR/NOT/XOR gates, wired up the right way, produce arithmetic - that's how true/false becomes math." } ] ```