Discrete Mathematics Fundamentals' own Chapter 2 already covered truth tables, AND/OR/NOT, and De Morgan's Laws — as propositional logic: statements that are true or false, connected by logical words. This course reintroduces the exact same truth tables, on purpose, as a genuinely different thing: an algebra — a system of values and operations you can manipulate with algebraic laws, the way ordinary arithmetic lets you manipulate numbers. That shift in framing is what turns "true/false sentences" into "the actual mathematics every logic gate, CPU, and bitwise operator in a running computer is built from."

Same Truth Table, Two Different Framings

Propositional logic asks: is this sentence true? Boolean algebra asks: what does this expression evaluate to? The underlying table never changes — only what the two columns are understood to mean.

The · and + notation isn't decorative — writing Boolean operations as "multiplication" and "addition" is exactly what makes Chapter 3's algebraic laws (distributive, absorption, and the rest) feel like genuine algebra rather than a list of logic rules to memorize separately.

A Real Demonstration: Your Own Code Already Runs on These Laws

A permissions system — READ, WRITE, EXECUTE as individual bits, combined with | (OR) and tested with & (AND) — is Boolean algebra running directly in production code, not an analogy for it.

Five Concrete Connections to Real Code

What This Course Won't Cover

Digital logic, taken to its full depth, becomes computer architecture and then chip engineering. This course deliberately stops well before that point:

• Computer architecture / CPU design — instruction sets, pipelining, cache hierarchies, and how gates assemble into an actual processor stay out of scope; that's its own substantial future topic
• VLSI / physical circuit engineering — transistor-level design, timing analysis, and fabrication are a genuinely different (and much deeper) discipline than the logical structure this course covers
• Formal digital design tools — HDLs like Verilog/VHDL, and real synthesis/simulation tooling, aren't covered; this course builds the mathematical foundation those tools are built on top of

Where This Course Is Headed

Hands-On Exercises

A Boolean value is one of exactly two elements — 0 or 1 (equivalently False/True). A Boolean operator takes one or two Boolean values and produces another. This chapter defines the full working set — including two operators, XOR and NAND/NOR, that Discrete Mathematics Fundamentals' own propositional-logic chapter never needed but digital logic can't do without.

The Core Three: AND, OR, NOT

AND is 1 only when both inputs are 1. OR is 1 when at least one input is 1. NOT (x') simply flips: 0' = 1, 1' = 0.

XOR — Exclusive Or

XOR (⊕) is 1 exactly when its two inputs differ — true when exactly one input is 1, unlike plain OR which also accepts both.

NAND & NOR — Derived, and Surprisingly Powerful

NAND (NOT AND) and NOR (NOT OR) are simply AND/OR immediately followed by NOT:

A Remarkable Verified Fact: NAND Alone Builds Everything

NAND is functionally complete — every other operator in this chapter, including NOT, AND, and OR themselves, can be built using only NAND, wired to itself and to its own inputs.

Real Relevance: Logical vs. Bitwise Operators — a Genuine Trap

Most languages give you two separate operator families for what looks like the same idea: logical operators (and/or/not in Python) working on whole truthy/falsy expressions with short-circuit evaluation, and bitwise operators (&/|/^/~) working on individual bits — this chapter's own AND/OR/NOT/XOR, applied per-bit to an entire number at once.

Operators in Code

Hands-On Exercises

Chapter 1's own finding-box already showed three of these laws holding on a real permissions bitmask, without naming them formally. This chapter names every law properly, proves each one, and introduces the one proof method that's unique to Boolean algebra: since every variable only has two possible values, an identity in n variables can be proved completely just by checking all 2ⁿ input combinations — no infinite case to worry about, unlike ordinary algebra over the real numbers.

The Standard Laws

A Genuinely Surprising Law: The Second Distributive Law

Ordinary arithmetic distributes multiplication over addition (x(y+z)=xy+xz) — but never the reverse; addition does not distribute over multiplication for real numbers. Boolean algebra is different: OR genuinely does distribute over AND, a law with no counterpart in ordinary arithmetic at all.

De Morgan's Laws, Proved Algebraically

Discrete Mathematics Fundamentals introduced these as a logical equivalence between statements. Here they're the same two identities, proved the same exhaustive way as every other law in this chapter:

The Duality Principle

Notice the laws above come in matched pairs. That's not a coincidence: swap every + with ·, and every 0 with 1, and any true Boolean law becomes another true Boolean law — its dual. The two distributive laws are duals of each other; so are the two De Morgan's laws, the two identity laws, and the two domination laws. Once one half of a pair is proved, the other is guaranteed true for free.

Real Relevance: Negating Compound Conditions Correctly

De Morgan's Laws are the exact tool for correctly inverting a compound condition in real code — not (a and b) is not the same as (not a) and (not b), a mistake that's easy to make under pressure. The correct inversion, straight from this chapter's own proof, is (not a) or (not b). Chapter 5 builds on every law in this chapter directly to simplify tangled real conditions down to their shortest equivalent form.

Hands-On Exercises

Chapters 2-3 gave the vocabulary and the laws. This chapter gives the actual, mechanical procedure: given any truth table at all, how do you write down a Boolean expression that produces it? The answer works for every possible function, every time, with no cleverness required.

How Many Boolean Functions Even Exist?

A Boolean function of n variables has 2ⁿ rows in its truth table, and each row's output can independently be 0 or 1 — so there are exactly 2^(2ⁿ) possible functions of n variables.

Minterms: A Building Block for Exactly One Row

A minterm is an AND of every variable (each either plain or complemented) that evaluates to 1 for exactly one input combination and 0 everywhere else. For two variables x,y, the minterm for the row x=1,y=0 is xy' — it's only 1 when x=1 and y=0.

Sum-of-Products: Reconstructing Any Truth Table

Maxterms & Product-of-Sums: The Dual Construction

A maxterm is the dual idea — an OR of every variable that evaluates to 0 for exactly one input combination. Taking the maxterm for every row where the output is 0, and AND-ing them together, gives the product-of-sums (POS) form — the same truth table, built from the opposite direction.

A Real Worked Example: The Majority Function

majority(x,y,z) outputs 1 exactly when at least two of its three inputs are 1 — a genuinely useful function, not a toy: it's the core of triple modular redundancy (TMR), the real fault-tolerance technique used in spacecraft and other safety-critical computers, where three independent copies of a circuit vote and the majority result is trusted even if one copy has been corrupted (by a cosmic ray flipping a bit, for instance).

Real Relevance: Specifying Business Logic From Test Cases

Anywhere requirements arrive as a table of "given these flags, the system should do X" — SOP construction turns that table directly into a correct, complete Boolean condition, mechanically, without needing to guess a clever simplified form first. Chapter 5 picks up immediately from here: an SOP expression built this way is always correct, but rarely the shortest way to say it — simplification is the next problem.

Canonical Forms in Code

Hands-On Exercises

Chapter 4 closed with an honest admission: the SOP form it built is always correct, but almost never the shortest way to say the same thing. This chapter delivers two genuinely different tools for shrinking an expression down — algebraic simplification using Chapter 3's own laws, and Karnaugh maps, a visual method that finds the same simplification by spotting patterns instead of manipulating symbols.

Algebraic Simplification: Shrinking Chapter 4's Own Majority Function

Chapter 4's SOP form for the majority function was x'yz + xy'z + xyz' + xyz — 4 terms, 12 literals total. Simplifying it directly:

Karnaugh Maps: The Same Simplification, Found Visually

A Karnaugh map (K-map) arranges a truth table in a grid where adjacent cells always differ in exactly one variable — achieved by ordering the column headers in Gray code (00, 01, 11, 10, not the "obvious" 00, 01, 10, 11) so a single-bit change always corresponds to a single step across the grid.

A Second, Simpler Example

A 2-variable function: f(x,y) = xy + xy'.

Real Relevance

Chapter 4's requirements-table-to-SOP procedure is guaranteed correct but routinely produces expressions far longer than necessary — exactly what happened with the majority function's own 12-literal starting point. Whether reached algebraically or visually, a simplified expression means fewer conditions to read in code, and — critically for Chapter 6 onward — fewer physical logic gates to build the same circuit from.

Hands-On Exercises

Everything so far has been symbols on a page. This chapter makes it physical: a logic gate is a real electronic component that takes voltage levels standing in for 0 and 1, and produces an output voltage exactly matching one of Chapter 2's own truth tables. Wire gates together, and Chapter 5's simplified expressions become an actual working circuit.

Combinational Circuits: Output Depends Only on Right-Now Inputs

A combinational circuit is built purely from gates with no memory anywhere in it — its output at any instant depends only on its current inputs, never on what happened before. Every circuit in this chapter is combinational. Chapter 8 introduces the genuinely different case — circuits that do remember something — which is a different kind of building block entirely, not just "combinational logic with extra wires."

Building Chapter 5's Own Simplified Circuit

Chapter 5 simplified the majority function down to xy + xz + yz. Wired directly into gates, using only 2-input AND and OR gates:

Why Chapter 5's Simplification Mattered Physically

Chapter 4's own unsimplified SOP form (x'yz + xy'z + xyz' + xyz) needs real gates too — and Chapter 5's simplification isn't just a shorter formula, it's a genuinely smaller, cheaper, faster circuit.

Real Relevance

This is literally what happens inside an FPGA or ASIC design flow: a Boolean expression gets simplified, then mapped onto real gates, then measured by exactly the gate-count and propagation-delay metrics above. Chapter 2's own NAND-completeness proof is why many real fabrication processes build every gate type shown here — AND, OR, NOT included — out of nothing but wired-together NAND gates, for manufacturing consistency.

Gate Simulation in Code

Hands-On Exercises

Chapter 6 built one specific circuit. This chapter builds three genuinely reusable ones — standard components wired into essentially every real digital system, including the exact logic a CPU uses to add numbers.

The Half Adder: Chapter 2's XOR Promise, Delivered

Chapter 2 called XOR "the basis of binary addition without carry." A half adder adds two single bits and produces exactly that: a SUM bit and a CARRY bit.

The Full Adder — and a Genuine Reuse of Chapters 4-6

A half adder can't be chained — real multi-bit addition needs each column to also accept a carry in from the column before it. A full adder takes three inputs (x, y, cin) and produces SUM and COUT: SUM = x ⊕ y ⊕ cin, COUT = xy + cin(x⊕y).

Chaining Full Adders: A Real Multi-Bit Adder

Wire the COUT of one full adder into the cin of the next, and multi-bit numbers add correctly, column by column, exactly like doing long addition by hand — this is a real ripple-carry adder, and it's genuinely how simple ALU addition works.

Multiplexers: A Selectable Wire

A multiplexer (MUX) routes exactly one of several data inputs through to a single output, chosen by a separate select input. A 2-to-1 MUX: output = sel'·in0 + sel·in1.

Decoders: Physically Wired Minterms

A decoder takes n select inputs and activates exactly one of 2ⁿ output lines. A 2-to-4 decoder's four outputs are literally Chapter 4's own four possible 2-variable minterms — a'b', a'b, ab', ab — each wired to its own physical output line.

Real Relevance

Ripple-carry addition is the literal mechanism behind a CPU's own integer addition (real ALUs use faster carry-lookahead variants at scale, but the correctness principle is identical). Multiplexers select which data path is active on every clock cycle inside a real processor. Decoders turn a binary address into "activate exactly this one memory location" — the basic mechanism behind RAM addressing itself.

Building Blocks in Code

Hands-On Exercises

Chapter 6 defined a combinational circuit as one whose output depends only on its current inputs, and named this chapter as the exception. The mechanism behind that exception is simple to state and genuinely powerful: wire a gate's output back into its own input, and the circuit's behavior starts depending on its own history — which is exactly what memory is.

The SR Latch: Two Gates, Wired to Remember

The simplest memory element is two NOR gates, cross-coupled — each gate's output feeds into the other gate's input. It has two inputs, S (set) and R (reset), and two outputs, Q and its complement Q'.

The Forbidden State

The D Latch: A Structural Fix

A D latch adds a data input D and an enable line, deriving S and R automatically: S = D · enable, R = D' · enable.

Level-Triggered vs. Edge-Triggered: Why Flip-Flops Exist

A D latch is level-triggered — while enable stays high, Q tracks D continuously, which can cause real problems when latches are chained (a change can "race" through several stages within a single enable pulse). A D flip-flop is edge-triggered — it only updates at the exact instant a clock signal transitions (e.g. low-to-high), holding steady the rest of the time. This is the real building block used in registers, counters, and pipeline stages, specifically because it makes multi-stage timing predictable.

Real Relevance: This Is What a Variable Actually Is

A CPU register, one bit of RAM, or the value behind an ordinary variable in running code — all the way down at the hardware level — genuinely is one of these feedback circuits. There's no separate "memory technology" beyond this trick, repeated billions of times: writing a variable sets a flip-flop; reading it later returns whatever that flip-flop has been holding since.

Sequential Logic in Code

Hands-On Exercises

Every chapter so far has quietly assumed numbers arrive as bits. This chapter asks the question directly — and answers a mystery Chapter 2 left open along the way: why ~True really does equal -2, not by accident, but by design.

Binary and Hexadecimal: The Same Number, Two Notations

Binary is positional notation base 2. Hexadecimal (base 16) exists because it aligns perfectly with binary in a way decimal never can: each hex digit represents exactly 4 bits, with no remainder.

Two's Complement: How Negative Numbers Actually Work

A naive "sign bit" scheme (flip the top bit to mean negative) has two real problems: it creates two representations of zero (+0 and -0), and ordinary addition breaks unless the hardware special-cases signs. Two's complement avoids both: to negate a number, invert every bit, then add 1.

The Real Payoff: Chapter 7's Own Adder Needs No Changes at All

This is the entire reason two's complement is universal: a ripple-carry adder built with zero awareness of signs correctly computes negative results, purely because of how the bit patterns are chosen.

Closing the Loop: Why ~True Really Is -2

Chapter 2 flagged ~True == -2 as a real, verified gotcha without explaining why. In two's complement, bitwise complement and negation are related by a clean identity:

Arithmetic vs. Logical Right Shift

Right-shifting a negative number needs to decide what to fill the vacated high bits with. Python's >> is an arithmetic shift — it fills with the sign bit, preserving negativity and behaving like floor division by 2.

Real Relevance

Bitwise operators (&, |, ^, ~, <<, >>) operate directly on these representations — Chapter 2's own flags/bitmasks are binary representation in action, and every value stored anywhere in a running program is, physically, one of the encodings this chapter just formalized.

Number Representation in Code

Hands-On Exercises

One continuous project: a real 3-bit adder/subtractor with overflow detection — the exact same technique a genuine ALU uses to compute both A+B and A-B from a single piece of hardware, touching every chapter of this course in the order a real designer would actually reach for each idea.

Step 1 — The Core Trick

Step 2 — Wiring the Mode-Select Logic

Step 3 — The Full 3-Bit Circuit

Step 4 — Four Real Cases, Fully Traced

Step 5 — Deriving Overflow Detection From First Principles

Step 6 — Full Gate-Count Accounting

What This Course Doesn't Cover

As stated honestly back in Chapter 1: full computer architecture/CPU design, VLSI/physical circuit engineering, and formal HDL tooling were named as deliberately out of scope, and stayed out of scope through all ten chapters. This capstone's own adder/subtractor is a genuine, real ALU building block — but a real ALU is many such blocks, plus instruction decoding, registers, and control logic this course never claimed to cover.

Where This Course Connects

Algorithms & Complexity's own "fewer operations, less time" reasoning reappeared directly in Chapter 6's gate-count argument, now paying off again in this capstone's own 19-gate, three-function circuit. Discrete Mathematics Fundamentals' own propositional logic was this course's own starting point (Chapter 1), and its proof-technique toolkit underwrote Chapter 3's own exhaustive law proofs. Number Theory & Cryptographic Math's own binary/modular reasoning and this course's Chapter 9 cover genuinely adjacent ground — worth revisiting side by side.

Hands-On Exercises