Building Software
Sections

Contents Section 4, Math and Algorithms

Logic and Discrete Math

Boolean logic, proof, sets, relations and graphs: the structures underneath conditions, databases, permissions and dependency systems.

Section 4 of 9, subsection 1 of 4. Depth: explain. A 9-minute read.

Mistakes to catch in review

  1. An inverted or incomplete condition, such as a less-than where less-than-or-equal was needed, or a compound check negated incorrectly.

  2. A relationship modeled as one-to-one when it is really many-to-many, so a join silently duplicates or drops rows.

  3. A circular dependency between modules or services that leaves build order or startup order undefined.

Reading Code as Logic

An agent adds a shipping rule to your checkout. The ticket said: "Orders of $50 or more ship free, as long as the address is in the country." The agent wrote this:

TypeScript
if (order.total > 50 && !order.address.isDomestic) {
  order.shipping = 0;
}

That one line has two mistakes. An order of exactly $50 still pays for shipping, because > leaves 50 out. And the ! is in the wrong place, so free shipping goes only to foreign addresses, the opposite of the rule. The test suite passed. Its only case was a $30 order, which pays shipping under the right rule and under this one too.

Mistakes like these are logic mistakes, and logic is a small, exact subject. A condition in code is a formula in propositional logic. A database relationship is a relation in set theory. A tangle of imports or startup dependencies is a directed graph. Agents write all three fluently, and they get each one slightly wrong in ways a few hand-picked test cases will not reveal.

A condition is a formula you can check row by row

A condition combines true-or-false values with three operators: and, or, not. Given the inputs, the answer is fully determined, so you can list every possible input and the result. That list is a truth table. With two inputs there are four rows.

Here is the table for what the ticket asked, with the two inputs "total is at least 50" and "address is domestic":

total ≥ 50 domestic free shipping
false false false
false true false
true false false
true true true

The agent's code is true in one situation only: a foreign address with a total above 50. That sits in the third row, where the rule says false. In the fourth row, where the rule says true, the code says false. Write the code's column next to the rule's and the disagreement is plain to see.

The number of rows doubles with every input: three booleans give 8 rows, ten give 1,024, twenty give about a million. This is the counting argument for why tests alone cannot confirm a condition over many flags. At some size you have to stop enumerating and reason about the shape of the condition.

Boundaries: which side does the edge fall on

A comparison on a number splits the number line in two. The only question is which side the boundary value lands on, and English is sloppy about it. "At least 50" and "50 or more" mean >= 50. "More than 50" and "over 50" mean > 50. "Up to 50" and "before the deadline" are ambiguous, and the right move is to ask what happens at exactly 50 or at exactly the deadline.

To check a boundary, test three values: the boundary itself, one step below, and one step above. The $30 test in the opening example checked none of them.

Three circles headed The three to test sit side by side: one step below 50, 50 itself, and one step above. Apart from them on the left is the $30 test, which tests none of the three. Below each point a box gives the result: the $30 test and one step below are false for both > and >=, one step above is true for both, and only 50 splits, false for > 50 and true for >= 50.
The $30 order and anything one step from 50 get the same answer under > 50 and >= 50. Only an order of exactly 50 tells the two apart.

Loops have boundaries too. for (let i = 0; i <= items.length; i++) runs one step too far and reads past the end of the array. The way to check a loop is to name its invariant, a statement that is true each time the loop tests its condition. For a loop over an array it is 0 <= i <= items.length: i starts at 0, each step adds 1, and the test stops the loop once i reaches the length. The guard i < items.length then makes i a valid index inside the body. If the invariant holds before the first test, and each iteration keeps it true, then it holds at every test. That is proof by induction, and it is the same argument you use informally when you convince yourself a loop is right. With the guard i <= items.length, the body runs once with i == items.length, which is not a valid index, so the loop is wrong. An empty array shows the same thing: the invariant holds with i == 0, and only the correct guard keeps the body from running.

Two rows. Top: guard i < items.length, then i = 0 and i = 1 with the body running, then the loop stops at i == items.length. Bottom: guard i <= items.length, the same i = 0 and i = 1, then one step too far, where the body runs with i == items.length, which is not a valid index.
Both loops run the body for i = 0, 1 and onward. At i == items.length the < guard stops the loop, and the <= guard runs the body one step too far.

A proof is only as good as its assumptions. Joshua Bloch's essay on broken binary searches describes a search whose correctness argument was sound on paper. The code computed the midpoint as (low + high) / 2, and when the array got large enough, low + high overflowed a 32-bit integer. The proof had assumed integers never overflow, and that assumption was false for the Java int the code actually used.

Negation and De Morgan's laws

Negating a compound statement is an easy place to go wrong. Two rules, called De Morgan's laws, tell you how to do it:

  • !(A && B) is the same as !A || !B
  • !(A || B) is the same as !A && !B

In words: "not both" means "at least one is missing", and "neither" means "each one is missing". When you move a ! inside parentheses, every && becomes || and every || becomes &&.

This comes up whenever a rule is stated as who is allowed but the code is written as who is denied. Suppose the rule is "a user may post if they are verified and not banned". The allow condition is verified && !banned. The deny condition is its negation:

TypeScript
// allow: verified && !banned
// deny:  !(verified && !banned)  ===  !verified || banned
if (!user.verified || user.banned) {
  return deny();
}

A common wrong version is if (!user.verified && user.banned) deny(). It denies only users who are both unverified and banned. An unverified user who has never been banned gets through. The question that exposes it: write the allow rule, negate the whole thing, push the ! inward with De Morgan, and compare the result with the code.

Precedence: where the parentheses really are

In C, Java, JavaScript, Go and most other languages, && binds tighter than ||, the way multiplication binds tighter than addition. Python's and and or follow the same order. So a || b && c means a || (b && c), whatever the spacing or the comment above it suggests.

Consider an event system where the intent is "staff or members may enter, but only while the event is open":

TypeScript
if (user.isStaff || user.isMember && event.isOpen) {
  allowEntry();
}

This parses as isStaff || (isMember && isOpen), so staff can enter a closed event. When a condition mixes && and ||, rewrite it with explicit parentheses before you judge it. Then compare it with the intended rule on every combination of inputs. With three booleans you can do that in a few lines:

TypeScriptRuns in your browser
const intended = (staff: boolean, member: boolean, open: boolean) => (staff || member) && open;
const written = (staff: boolean, member: boolean, open: boolean) => staff || (member && open);

for (const staff of [false, true])
  for (const member of [false, true])
    for (const open of [false, true])
      if (intended(staff, member, open) !== written(staff, member, open))
        console.log("staff:", staff, "member:", member, "open:", open);

It prints two rows, both with staff: true and open: false. Those two rows are exactly the users the code admits and the rule excludes. The same loop works for any condition you are unsure about: encode the comment as one function, the code as another, and print the disagreements.

Saying "every" and "some" precisely

Rules about permissions and data usually contain a hidden quantifier. "Every admin can see every document" is a for-all statement. "Some reviewer has approved this change" is a there-exists statement. They behave differently. One example confirms a there-exists claim and can only refute a for-all claim. To negate "every document is visible to admins" you need a single document that some admin cannot see.

This matters when you read an agent's test. A test that logs in as one admin and opens one document shows that some admin can see some document. The comment above the code claims something much stronger. When the rule says "every", ask how the cases the test skipped are covered. The usual answers are a property-based test that generates many users and documents, or an argument from the structure of the code.

Relationships: ask the question in both directions

A relation is a set of pairs: (user, team), (order, tag), (student, course). The kind of relation is set by two questions. For one X, how many Y can there be? For one Y, how many X? If both answers are "one", it is one-to-one. If one side is "many", it is one-to-many. If both are "many", it is many-to-many, and a relational database needs a separate table of pairs to store it.

Agents often ask only one of the two questions. A schema with a team_id column on users says each user belongs to one team. If a user can in fact join two teams, the column can hold only one of them, and the second membership either overwrites the first or leads someone to create a duplicate user row. The correct shape is a team_memberships table with one row per (user, team) pair.

The opposite mistake shows up in queries. Suppose orders can carry several tags, stored in order_tags, and an agent computes revenue like this:

SQL
SELECT SUM(o.total)
FROM orders o
JOIN order_tags t ON t.order_id = o.id;

Take two orders. Order 1 is $100 with the tags gift and rush. Order 2 is $40 with no tags. True revenue is $140. The join produces one row per (order, tag) pair, so order 1 appears twice and order 2, which has no pairs, disappears. The query returns $200. It is wrong in both directions at once, and the answer looks believable.

Order 1, $100 with tags gift and rush, and order 2, $40 with no tags, flow into JOIN order_tags, which makes one row per order and tag pair. Out come two rows for order 1 at $100 each, while order 2 has no pairs and is gone. The two rows feed SUM = $200, while true revenue is $140.
Order 1 becomes two rows, one per tag, and order 2, with no tags, disappears. The sum comes to $200 when true revenue is $140.

The question that catches this: after the join, is there still exactly one row per order? Compare the count of rows per order ID before and after the join, because equal totals can hide damage. The join above returns two rows for two orders, one order twice and the other not at all. If the join fans out, aggregate before joining or use EXISTS to test for a tag without multiplying rows.

Here are the same two orders in a database you can run. The first query is the agent's, the second is the row-count check, and the last two are the repairs.

SQLRuns on SQLite in your browser
CREATE TABLE orders (id INTEGER PRIMARY KEY, total INTEGER NOT NULL);
CREATE TABLE order_tags (order_id INTEGER NOT NULL REFERENCES orders(id), tag TEXT NOT NULL);
INSERT INTO orders VALUES (1, 100), (2, 40);
INSERT INTO order_tags VALUES (1, 'gift'), (1, 'rush');

-- The agent's query: one row per (order, tag) pair.
SELECT SUM(o.total) AS revenue
FROM orders o
JOIN order_tags t ON t.order_id = o.id;

-- The check: how many rows each order becomes in that join.
SELECT o.id, COUNT(t.order_id) AS rows_after_join
FROM orders o
LEFT JOIN order_tags t ON t.order_id = o.id
GROUP BY o.id;

-- Revenue is a fact about orders, so sum the orders table alone.
SELECT SUM(total) AS revenue FROM orders;

-- Revenue from tagged orders: EXISTS tests for a tag without multiplying rows.
SELECT SUM(o.total) AS tagged_revenue
FROM orders o
WHERE EXISTS (SELECT 1 FROM order_tags t WHERE t.order_id = o.id);

The second result shows the damage directly: order 1 became two rows and order 2 became none. Order 1 is the only tagged order, so the tagged revenue is $100.

Dependencies are graphs

Modules import modules. Services wait for other services at startup. Packages depend on packages. Roles inherit permissions from other roles. Each of these is a directed graph: a set of nodes and arrows between them, where an arrow from B to A means A needs B, so arrows point from what is needed to what needs it.

Three modules. db at the top has arrows to users and to billing. users imports billing and billing imports users, drawn as two arrows between them in opposite directions, forming a cycle with no valid order.
Arrows point from what is needed to what needs it. Users and billing each need the other, so no order puts both after their dependencies.

A build order or startup order is a topological order, a list in which every arrow points forward, so every node comes after everything it depends on. Such an order exists exactly when the graph has no cycle. When an agent splits a codebase so that billing imports users to look up a customer and users imports billing to show a plan on the profile page, it has created a cycle. What happens next depends on the runtime. Go refuses to compile an import cycle. Node.js with CommonJS modules hands one of the two a partly filled exports object, so a value is undefined at startup only when a certain file happens to load first. Two services that each wait for the other to report healthy never start.

The standard way to find an order, or prove there is none, is Kahn's algorithm. Count how many dependencies each node is still waiting on. Repeatedly take a node that is waiting on nothing, emit it, and reduce the count of everything that depends on it. If nodes remain when you run out of ready ones, they are in a cycle or depend on one.

TypeScriptRuns in your browser
// deps[x] lists what x depends on; every node must appear as a key.
function buildOrder(deps: Map<string, string[]>): string[] {
  const waiting = new Map<string, number>();
  const dependents = new Map<string, string[]>(); // the arrows leaving each node
  for (const [node, needs] of deps) {
    waiting.set(node, needs.length);
    for (const d of needs) dependents.set(d, [...(dependents.get(d) ?? []), node]);
  }
  const ready = [...deps.keys()].filter((n) => waiting.get(n) === 0);
  const order: string[] = [];
  while (ready.length > 0) {
    const n = ready.pop()!;
    order.push(n);
    for (const m of dependents.get(n) ?? []) {
      waiting.set(m, waiting.get(m)! - 1);
      if (waiting.get(m) === 0) ready.push(m);
    }
  }
  const blocked = [...deps.keys()].filter((n) => waiting.get(n)! > 0);
  if (blocked.length > 0) throw new Error(`blocked by a cycle: ${blocked.join(", ")}`);
  return order;
}

console.log(buildOrder(new Map([["db", []], ["users", ["db"]], ["billing", ["db", "users"]]])));
// [ "db", "users", "billing" ]

try {
  buildOrder(new Map([["db", []], ["users", ["db", "billing"]], ["billing", ["db", "users"]]]));
} catch (e) {
  console.log((e as Error).message);
}
// blocked by a cycle: users, billing

It visits each node and each arrow once, so its cost grows linearly with the size of the graph.

Permission inheritance is a different graph question. "Can this user delete invoices?" means "is there a path from the user's role to a role that grants delete?" That is reachability, answered by breadth-first or depth-first search. The bug to look for is a recursive function that walks up a role's parents without recording which roles it has already visited. It works on every tree, then loops forever the first time someone configures two roles that inherit from each other.

When an agent hands you anything with the words order, depends, inherits, or before, draw an arrow from each thing to whatever needs it, and check whether any path leads back to where it started. If one does, no valid order exists.

Check your understanding

6 questions on this lesson. Pick an answer to see whether it holds and why.

  1. 1The rule: a coupon applies when the cart has at least 3 items and the customer is not a first-time buyer. An agent wrote the rejection check below. Which condition should replace it?
    TypeScript
    if (cart.items.length < 3 && customer.isFirstOrder) {
      return reject("coupon not valid");
    }
    Show the answer

    Answer C. The allow rule is length >= 3 && !isFirstOrder. Negating it with De Morgan flips the && to || and each part: length < 3 || isFirstOrder. The agent kept &&, so a first-time buyer with 5 items gets the coupon. The <= 3 version has the right operator but rejects a cart of exactly 3, which the rule allows.

  2. 2An agent wrote this helper to return the last n log lines. What does tail(["a", "b", "c", "d"], 2) return?
    TypeScript
    function tail(lines: string[], n: number): string[] {
      const out: string[] = [];
      for (let i = lines.length - n; i <= lines.length; i++) out.push(lines[i]);
      return out;
    }
    Show the answer

    Answer B. The loop runs for i equal to 2, 3 and 4. With the guard i <= lines.length, the body runs once with i equal to the length, which is not a valid index. JavaScript returns undefined for a missing array index instead of throwing, so the bug shows up as an extra undefined at the end.

  3. 3A clinic app stores doctors and patients. A doctor sees many patients, a patient may see several doctors over the years, and each appointment has exactly one doctor and one patient. What is the relationship between doctors and patients?
    Show the answer

    Answer D. Ask both directions. One doctor has many patients, and one patient has many doctors, so it is many-to-many. Each appointment has one of each, which makes appointments the table of (doctor, patient) pairs. A doctor_id on patients would keep only one doctor per patient and overwrite the rest.

  4. 4An agent wrote this report. Customer 1 has 3 orders and 2 support tickets. What does the query report as customer 1's order count?
    SQL
    SELECT c.id, COUNT(*) AS orders
    FROM customers c
    JOIN orders o ON o.customer_id = c.id
    JOIN support_tickets t ON t.customer_id = c.id
    GROUP BY c.id;
    Show the answer

    Answer A. Each join is one-to-many from the customer, so the result has one row per (order, ticket) pair: 3 times 2 is 6. Adding the counts to get 5 assumes joins append rows; they multiply them. A customer with orders but no tickets also vanishes from this report, because the inner join finds no pairs for them.

  5. 5Roles inherit permissions from parent roles. Someone configures editor and reviewer as parents of each other, and neither grants delete. What happens when the code calls canDelete("editor")?
    TypeScript
    function canDelete(role: string): boolean {
      if (grants[role]?.includes("delete")) return true;
      return (parents[role] ?? []).some((p) => canDelete(p));
    }
    Show the answer

    Answer C. This is a reachability search on a graph, and it keeps no record of roles it has visited. editor asks reviewer, which asks editor again, forever. On a tree that never happens, which is why the tests passed. Carrying a set of visited roles and skipping any role already in it makes it return false.

  6. 6The rule says every invoice in a closed accounting period is read-only. The agent's test creates one closed invoice, tries to edit it, and checks that the edit is rejected. The test passes. What has it shown?
    Show the answer

    Answer B. One example confirms a there-exists statement and can only refute a for-all one. The test shows one closed invoice is protected. Invoices with other currencies, owners or edit paths are untested. A property-based test over many generated invoices, or reading the code to see that every edit path checks the period, covers the rest.

You understand it when you can

Drill

An agent wrote the access check if (!user.isAdmin || !user.isOwner && !doc.isPublic) deny() under a comment saying admins, owners and anyone viewing a public document are allowed. Work out which users the code wrongly denies, given that and binds tighter than or, and write the condition the comment describes.

Topics

Boolean Logic
Truth tables, De Morgan's laws and simplifying conditions so each branch is easy to verify.
Quantifiers and Precise Statements
For-all and there-exists statements, and writing rules precisely enough to be tested or proved.
Induction and Loop Invariants
Proving that loops and recursive functions do what they claim for every input.
Sets and Relations
Union, intersection, difference and relations, which are the mathematics behind relational databases.
Graphs
Nodes and edges for dependencies, networks and permissions, with traversal, cycles and topological order.
Counting and Combinatorics
Counting possible cases, which shows why exhaustive testing is impossible and where combinatorial bugs hide.

Further reading

Start here

Short reads

Watch

  • Lecture 1: Predicates, Sets, and Proofs. Erik Demaine, Zachary Abel and Brynmor Chapman (MIT 6.1200J), 2024. 79-minute lecture.

    Opens MIT's current discrete math course with predicates, quantifiers, set operations and what makes a proof valid, which is the vocabulary for writing precise rules.

  • Lec 6 | MIT 6.042J Mathematics for Computer Science, Fall 2010. MIT 6.042J Fall 2010 (Tom Leighton, Marten van Dijk), 2010. 83-minute lecture.

    Introduces graphs, vertices, edges and degree through worked problems, so you can recognize a dependency or permission question as a graph problem.

Books

  • Mathematics for Computer Science. Eric Lehman, F. Thomson Leighton and Albert R. Meyer, 2018, revised June 2018. Free to read online.

    Its chapters on propositional logic, induction and invariants, sets and relations, digraphs and counting line up almost one to one with this subsection's topics, all in a free CC-licensed text.

  • Discrete Mathematics: An Open Introduction. Oscar Levin, 2025, 4th edition. Free to read online.

    Moves from logic and proofs to graph theory and counting, with new sections on relations and probability and more than 750 exercises, at a gentler pace than the MIT text.

  • How to Prove It: A Structured Approach. Daniel J. Velleman, 2019, 3rd edition.

    Teaches how to translate English statements into logic with quantifiers and connectives and how to structure a proof, which is the skill behind reading an agent's condition against its comment.

Primary sources