Part I: Logic and Proof

"Logic is the anatomy of thought." — commonly attributed to John Locke

Every program you have ever written rests on two things you have probably never been asked to justify. The first is logic: the if that fires only when a condition is exactly true, the && that must not short-circuit the wrong way, the negation that has to push through a compound condition without flipping a case by accident. The second is proof — not the kind with a turnstile and Greek letters, but the everyday claim that your code is correct, that it does the right thing on every input and not just the dozen you happened to test. Part I is about making both of those things precise. It is the grammar of the entire book, and the skill that will outlast any particular algorithm you learn from it.

We begin with logic because it is the language in which everything else is written. A set identity, a counting argument, a statement about graphs, a theorem about what computers cannot do — each is ultimately a logical claim, and you cannot prove a claim you cannot state without ambiguity. So the first half of this part teaches you to write statements that mean exactly one thing: propositional logic (the math of true/false and the Boolean operators you already use), predicate logic (the quantifiers $\forall$ and $\exists$ that turn "for every element" and "there exists an element" into symbols), and the rules of inference that say when one statement legitimately follows from others. By the end you will be able to translate a tangled English specification into symbols, simplify it the way you refactor a function, and tell a valid argument from a plausible-sounding fallacy.

The second half is where the book's central skill lives: writing and reading proofs. "It passed the tests" tells you a program works on the cases you tried; a proof tells you it works on all of them, including the infinitely many you will never run. That gap — between confidence and certainty — is exactly where production bugs hide, and the proof techniques in Chapters 4 through 7 are the tools that close it. You will not be asked to take anything on faith. Every technique is motivated by a programmer's problem first, then made rigorous, then handed back to you as something you can actually use in a code review.

What You Will Learn

Chapter 1 — Propositional Logic. You will translate English statements into the connectives $\neg, \land, \lor, \rightarrow, \leftrightarrow,$ and $\oplus$, build and read truth tables, and classify a compound proposition as a tautology, a contradiction, or a contingency. The payoff is concrete: you will use logical equivalences and De Morgan's laws to simplify a real if condition, and meet satisfiability (SAT) as the first hint that some problems are computationally hard.

Chapter 2 — Predicate Logic and Quantifiers. Propositions about specific things become predicates about any thing once you add the universal quantifier $\forall$ and the existential quantifier $\exists$. You will translate multiply-quantified statements, learn why the order of nested quantifiers changes the meaning, and master negation — pushing $\neg$ through a quantified statement, which is the formal version of writing the negative test case. The CS thread: quantifiers are loops, all() and any(), and the preconditions and postconditions that specify what a function promises.

Chapter 3 — Rules of Inference. Here logic becomes argument. You will apply valid inference rules such as modus ponens and modus tollens, construct step-by-step derivations, and — just as importantly — learn to spot the fallacies (like affirming the consequent) that feel convincing but prove nothing. This chapter draws directly on Chapters 1 and 2 and sets up everything that follows, because a proof is simply a derivation whose every step is justified. We connect it to where inference already lives in CS: type checking and logic programming.

Chapter 4 — Proof Strategies I: Direct Proof and Contraposition. This is where you write your first rigorous proofs. You will learn what a proof actually is (and is not), use definitions as the raw material they are, and master the two most common forms: the direct proof and its mirror image, proof by contraposition. We work with even and odd numbers and with divisibility — the latter quietly planting the seed for the number theory of Part IV. You will also learn to read a proof critically, which is half the skill.

Chapter 5 — Proof Strategies II: Contradiction and Cases. Some truths are easiest to reach by assuming the opposite and watching it collapse. You will prove by contradiction (the irrationality of $\sqrt{2}$, the infinitude of the primes), prove by exhaustive cases, and handle existence and uniqueness. You will also learn to disprove a universal claim with a single counterexample. A forward-looking note: contradiction is exactly the engine behind proving the halting problem unsolvable, which we will reach in Chapter 36.

Chapter 6 — Mathematical Induction. This is the part's threshold concept and the book's voice anchor. You already reason by induction every time you trust a recursive function because it works on size $n-1$; this chapter turns that instinct into a tool you can defend. You will identify the base case and the inductive step, prove facts about sums, inequalities, and divisibility, and — crucially for a programmer — use a loop invariant to prove iterative code correct. It is here that Fibonacci, one of the book's three running threads, is first defined recursively and proven about.

Chapter 7 — Strong Induction, Well-Ordering, and Recursive Definitions. The advanced finale of the part generalizes induction in two directions. Strong induction lets you assume the claim for all smaller cases at once (sometimes you need every previous domino, not just the last one); the well-ordering principle gives the same power a different shape. You will write recursive definitions of sequences, sets, and structures, then prove things about them by structural induction — the technique that makes reasoning about trees and lists tractable later in the book.

How This Part Fits

Part I has no prerequisites: it is the foundation the other five parts stand on, and Chapter 1 assumes nothing beyond having written a few if statements. Internally the part is a tight chain. Logic (Chapters 1–3) gives you the language; proof (Chapters 4–7) gives you the method; and the two halves meet in the fact that every proof is just a careful argument in the logic you learned first.

Looking outward, almost everything downstream leans on this part. The proof techniques are used in every chapter that states a theorem, so the habits you build here compound. Direct proof and divisibility (Chapter 4) set up the number theory and RSA cryptography of Part IV. Induction and recursive definitions (Chapters 6–7) are the foundation for recurrence relations (Chapters 18–19) and for trees (Chapter 31). Proof by contradiction (Chapter 5) is the technique behind the deepest results in the book — uncountability and undecidability in Part VI. In a real sense, you are not just learning logic and proof for their own sake; you are acquiring the toolkit the rest of the book assumes you own.

You will also start building the Discrete Math Toolkit here. The Project Checkpoint at the end of each chapter adds one piece to a Python package, dmtoolkit, that grows with you across all forty chapters. In this part you build logic.py: a truth-table generator, a tautology checker, and a predicate evaluator over finite domains — your first concrete demonstration of the book's fourth theme, that computation and proof are complementary tools, not rivals.

Time Investment

Chapter Title Difficulty Estimated hours
1 Propositional Logic beginner 5–6
2 Predicate Logic and Quantifiers beginner 5–6
3 Rules of Inference intermediate 6
4 Proof Strategies I: Direct Proof and Contraposition intermediate 6–7
5 Proof Strategies II: Contradiction and Cases intermediate 6–7
6 Mathematical Induction intermediate 7
7 Strong Induction, Well-Ordering, and Recursive Definitions advanced 7
Part I total 42–46

These are honest estimates of focused work, including the exercises and at least one case study per chapter. Reading the prose is the smaller half; the real learning happens when you work the proofs yourself before reading ours, which is why the higher end of each range assumes you do exactly that.

We begin where every program begins: with a decision that is either true or false. Chapter 1 takes the Boolean operators you already use without thinking and turns them into a precise, provable language — the first and most useful piece of the mathematics of computing. Turn the page and let's make the logic in your code something you can reason about, not just run.

Chapters in This Part