Building Software

Engineering Fundamentals for the Agent Era

Contents Section 4, Math and Algorithms

Logic and Discrete Math

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.

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

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.

You understand it when you can

  • Spot the wrong boundary or wrong negation in a compound condition, and correct it using De Morgan's laws.
  • Identify from a plain description whether a relationship is one-to-one, one-to-many or many-to-many.
  • Recognize when a problem is a graph problem, such as build order or permission inheritance, and name the kind of algorithm that solves it.

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.

Start here

Watch

3 Ways to Show a Logical Equivalence | Ex: DeMorgan's Laws

Trefor Bazett, 2019. 5-minute explainer.

In five minutes it proves De Morgan's laws with truth tables and algebraic rewriting, which is exactly what you need to fix a wrongly negated compound condition like the one in the drill.

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.

Read

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