Preface

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." — Ted Nelson

Why this book exists

Discrete mathematics is the one math course nearly every computer science student is required to take — and the one most of them dread. That dread is not the students' fault. It is a failure of presentation.

The standard textbooks are encyclopedic, expensive, and — for a CS student — strangely silent about computer science. They prove that $\sqrt{2}$ is irrational without ever mentioning that the same technique, proof by contradiction, is how you prove a problem is unsolvable. They define a function as a set of ordered pairs without mentioning that this is exactly what a hash table approximates. They develop graph theory in the abstract while the student wonders what any of it has to do with the social network on their phone or the routing of the packet that delivered this sentence.

The result is a course that feels like a toll booth: pay it, get the credit, move on. That is a tragedy, because discrete mathematics is not a toll booth. It is the foundation of the entire field. Logic underlies every conditional and every circuit. Set theory and functions underlie every data structure. Counting and probability underlie algorithm analysis, hashing, cryptography, and machine learning. Graph theory is, with little exaggeration, the most useful branch of mathematics a programmer can know. And proof — the skill students fear most — is simply the discipline of being sure your code is correct, for every input, not just the ones you happened to test.

This book is an attempt to teach that foundation the way it should be taught: CS first.

What makes this book different

• Every concept starts with a computing problem. The abstraction is the reward for understanding the problem, never the starting point. You will meet modular arithmetic because you want to understand RSA, not the other way around.
• Python lives alongside the mathematics. You will not just prove things about graphs — you will build them, traverse them, and find shortest paths in them. Code lets you test a conjecture on a million cases; a proof tells you it holds for all cases. This book insists you learn both, because both are part of the job.
• Proof is taught gently and progressively. Proof techniques are introduced exactly when you need them, with heavy scaffolding, "find the error" exercises, and — always — the strategy explained in plain English before the formal argument. By Chapter 6 you will be proving your own recursive functions correct.
• It is readable. Conversational where the competition is dense, visual where it is symbolic, motivated where it is abstract. It respects that the material is genuinely hard and refuses to make it harder than it has to be.

How this book is organized

The book is six parts, forty chapters:

• Part I — Logic and Proof builds the grammar of mathematics and the proof skills used everywhere after.
• Part II — Structures develops sets, functions, relations, and complexity — the data types of mathematics.
• Part III — Counting and Probability teaches you to count without listing and to reason about uncertainty.
• Part IV — Number Theory and Cryptography goes from divisibility to a working RSA implementation.
• Part V — Graph Theory develops the single most useful structure in computer science.
• Part VI — Advanced Topics and Synthesis reaches the theory of computation — what computers can recognize, what they cannot compute, and what they cannot compute efficiently — and ties it all together in a capstone.

Three examples thread through the whole book: the RSA cryptosystem (built piece by piece across Parts I–IV and implemented in Chapter 25), the graph theory of social networks (the lens for all of Part V), and the Fibonacci sequence (analyzed with nearly every tool in the book). And one project grows with you: the Discrete Math Toolkit, a Python library you build a piece at a time until, at the capstone, you can apply the whole thing to a real problem.

What you will need

• High-school algebra and a little precalculus (functions, exponents, logarithms). No calculus.
• The ability to read simple code in any language. Python is used throughout, but it is taught as it appears; you do not need to know Python in advance.
• A willingness to struggle productively. Some ideas here — induction, uncountability, undecidability, NP-completeness — genuinely change how you think. They reward patience.

You do not need any prior experience with proofs, logic, set theory, or graph theory. The book starts from scratch on every mathematical topic. If you would like to check your readiness, the next sections (How to Use This Book, and Prerequisites) will help.

A note on honesty

Two promises. First, this book never fakes a citation: sources are tagged by how confident we are in them, and constructed examples are labeled as such. Second, the code is meant to be understood, not worshipped — every example shows its expected output so you can check your understanding even without a computer, and every algorithm is explained before it is optimized.

Welcome. The mathematics ahead is the language your field is written in. Let's learn to read and write it — and to know, with a proof, that what we have written is correct.