Your phone adds two numbers in a few billionths of a second, using nothing but switches that are either on or off. A barcode scanner knows you mistyped one digit of a book's number before it looks anything up. A map app finds the quickest route among millions of roads without trying them all. And a password check takes the same instant whether the password is long or short.
None of these runs on the smooth, continuous maths of calculus. They run on things you can count: bits, steps, roads, remainders. A graduate of a discrete mathematics course carries a small set of habits for reasoning about countable things, and they are the habits that separate "it seems to work" from "it must work".
This piece gives you those habits through six ideas and eight things to try: build an adder from logic, count what you cannot list, watch an induction proof grow, search a graph, wrap numbers around a clock, and see why some programs take longer than the age of the universe.
Who takes it: every computer science student in the first year, and many engineers; it is the entry ticket to the theory side of computing.
What it's for: reasoning exactly about finite and countable things: logic, collections, steps, networks.
Comes after: nothing but school mathematics. (Programming Fundamentals, 34/09, helps but isn't required.)
Leads to: Algorithms (34/24), Computer Architecture (34/25), Databases (34/28) and Theory of Computation (34/29) all list it as a prerequisite.
Honest line: you won't be able to prove a hard theorem after this. You will be able to see why a loop must stop, why a network has a shortest path, and why one algorithm will never finish. For easier first reads, see the library's Graph Theory (12/18) and Cryptography (12/09); this piece goes further into logic, proof, counting and growth.
Logic: truth tables become circuits
A proposition is a statement that is either true or false. Three operations build all the rest: AND (true only when both are true), OR (true when at least one is) and NOT (flips it). A truth table lists every case, and for two inputs there are only four rows. Another useful operation is XOR ("one or the other, but not both").
| A | B | A AND B | A OR B | A XOR B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Boole's 1854 book treated logic as algebra; the AND/OR/NOT algebra we use today was tidied up by his successors. The leap to hardware came in 1937, when Claude Shannon's MIT thesis showed that networks of switches could carry out exactly this algebra. Every gate in a processor since is a physical truth table.
Look at the XOR column: it is adding. 1 + 1 = 10 in binary, so the digit is 0 (XOR) and there is a carry of 1 (AND). Chain that into a full adder (it also takes the carry from the column on its right) and line four of them up, and you have a circuit that adds numbers up to 15. Choose two numbers and watch the carries ripple.
Without JavaScript: 7 + 9 is 0111 + 1001 in binary. The carry ripples through all four columns and the result is 10000, which is 16.
That is a complete circuit for one column: five gates. Everything a processor does (comparing, jumping, multiplying) is built the same way, so Computer Architecture (34/25) is largely this idea scaled up. Engineers also use the same logic on whole systems: a fault tree in reliability analysis is AND and OR gates over "this valve fails" and "this pump fails" (Systems Engineering, 34/22).
Sets, functions and counting: sorting the world and counting it
A set is a collection with no repeats; a function assigns each member of one set exactly one member of another. A function is one-to-one if no two inputs share an output, and onto if every possible output is hit. Remember these words: "the hash has collisions" means "the function is not one-to-one", and a compression scheme that shrinks every file would have to be one-to-one into a smaller set, which is impossible.
The first counting rule is about overlap. If you add the sizes of two sets, anything in both gets counted twice, so subtract it once. This is inclusion–exclusion:
In a class of 40, 25 take computing, 18 take maths and 9 take both: 25 + 18 − 9 = 34 take at least one, so 6 take neither.
Without JavaScript: in a class of 40 with 25 in computing, 18 in maths and 9 in both, 34 take at least one subject and 6 take neither.
Next, counting arrangements. If order matters, choose the first item in n ways, the next in n−1, and so on: choosing and ordering k of n items gives n!/(n−k)! possibilities. If order doesn't matter, divide by the k! ways to shuffle the chosen ones: that is a combination, written C(n,k).
Worked example: a five-card poker hand from 52 cards is C(52,5) = 2,598,960 hands, while the number of orderings of a whole deck is 52! ≈ 8.07×1067. A shuffled deck has almost certainly never been in that order before in history.
Without JavaScript: choosing 3 of 10 gives 720 ordered ways and 120 unordered ways; choosing 5 of 52 gives 2,598,960 hands.
The sneakiest counting idea has no formula. The pigeonhole principle says that if you put more than m items into m boxes, some box holds two. It sounds trivial, and it proves strong things: among any 13 people, two share a birth month; no compression method can shrink every file; any hash function that maps many inputs to few outputs must collide. Dirichlet used it in number theory in 1834. Drop random people into the seven days of the week: you are guaranteed a repeat by the eighth, and you will usually get one sooner (most often between the 3rd and 5th drop).
Without JavaScript: with 7 boxes, the 8th pigeon is guaranteed to share a box. With random drops the first double typically comes earlier, most often between the 3rd and the 5th pigeon.
Proof: induction and contradiction
You can't test infinitely many cases, so mathematicians prove. Two tools do most of the work. Induction is the domino proof: show the first domino falls (the base case), and show that if any domino falls, the next one does (the step). Then they all fall. Take the claim that the first n odd numbers add up to n². Base case: 1 = 1². Step: if the first n odd numbers make an n×n square, the next odd number, 2n+1, is exactly an L-shaped border that turns it into an (n+1)×(n+1) square. Slide n and watch the border go on.
Without JavaScript: 1 + 3 + 5 + 7 + 9 = 25 = 5². Adding the next odd number, 11, makes 36 = 6²: a border of 2×5+1 = 11 squares.
Induction is how you prove a loop does what it should: the loop invariant is the claim, the first pass is the base case, and each pass is the step. It is also the heart of recursion, which is a program that calls a smaller copy of itself.
Contradiction works the other way: assume the claim is false and show that this leads to nonsense. Euclid's proof that there are infinitely many primes is usually told this way: suppose the list of primes were finite, multiply them all together and add one. That number leaves remainder 1 when divided by every prime on your list, so either it is itself a new prime or it has a prime factor you didn't list. Either way the list was incomplete. (Some historians point out Euclid's own argument can be read as a direct one; the contradiction telling is the modern standard.) A programmer uses the same move when they say "suppose the algorithm returned a wrong answer; follow that and it breaks the invariant".
Graphs and trees: things and their connections
A graph is dots (nodes) and links (edges); the library's Graph Theory piece (12/18) introduced it. Here is a deeper habit. Count the edge ends: each edge has two, so the degrees (links at each node) always add up to exactly twice the number of edges. This handshake lemma is why the number of guests who shook an odd number of hands is always even.
The workhorse algorithm is breadth-first search: visit the start, then everything one step away, then everything two steps away, using a queue. It finds the fewest-hops route to every node. The edges it used to reach each new node form a tree: a connected graph with no loops, which always has exactly one fewer edge than nodes. Pick a start and press Step.
Without JavaScript: in the 8-node, 11-edge graph, the degrees add to 22, twice the edge count. Breadth-first search from A reaches every node in at most 3 hops, using exactly 7 edges, one fewer than the number of nodes.
Graphs appear everywhere in the two majors. A truss is a graph whose nodes are joints and edges are members (Statics, 34/10). A circuit is a graph (the loop equations you meet in Linear Algebra, 34/04, come straight from it). A road map, a network of routers, a dependency chart for building a product and a social network are all graphs, and a file system is a tree (Operating Systems, 34/26). Routers and links are a graph too (Computer Networks, 34/27).
Modular arithmetic: clocks, hashes and check digits
On a clock, 10 o'clock plus 5 hours is 3 o'clock, not 15. Modular arithmetic wraps numbers around: a mod m is the remainder when you divide a by m. It is used wherever a quantity cycles or has to be squeezed into a fixed number of slots. Try the clock, and below it a tiny hash table: each word is turned into a number, and that number mod the table size picks its slot.
Without JavaScript: 47 mod 8 = 7, because 47 = 5×8 + 7. With 8 slots, adding up each word's letter codes and taking the remainder sends "bolt" and "cam" to the same slot, and "shaft" and "valve" to the same slot: two collisions.
Slide the clock size up and the collisions mostly disappear, but by the pigeonhole principle you can't remove them while there are more words than slots. Databases (Databases, 34/28) and compilers use hash tables everywhere.
Remainders also catch mistakes. The last digit of a 13-digit book number (ISBN-13) is chosen so that the digits, weighted 1, 3, 1, 3 and so on, add to a multiple of 10. Take 978-0-306-40615-7: the first twelve digits give 93, and 10 − (93 mod 10) = 7. Change any one digit and the total is no longer a multiple of 10, so a scanner rejects it. Most swaps of neighbouring digits are caught too (those that differ by 5 slip through). Cryptography (12/09) is the same arithmetic taken to huge numbers, and it underlies Computer Security (34/33).
Engineers meet it in machines. A shaft encoder reports its angle modulo one turn. And gear designers sometimes choose tooth counts with no common factor, such as 20 and 21, so that each tooth meets every tooth on the other gear before any pair repeats: the pattern repeats only after lcm(20, 21) = 420 meshes, against 60 for 20 and 30 teeth, which spreads wear evenly (Machine Design, 34/19).
Big-O: growth as a counting idea
How long does a program take? Count its steps, as a function of the input size n, and keep only the part that grows fastest: big-O notation. Searching an unsorted list takes about n steps, O(n). Searching a sorted list by repeatedly halving takes about log2n, which is 20 steps for a million items. Comparing every pair is about n². And trying every subset of n things is 2n, which is where counting becomes a wall.
Pick a size and a machine speed. The shape of the growth matters more than the speed of the machine.
Without JavaScript: at n = 1,000,000 an O(n) job takes 0.001 seconds, an n log n job 0.02 seconds, an n² job 1,000 seconds (about 17 minutes), and a 2n job would take far longer than the age of the universe. Even at n = 60, a 2n job needs about 36.5 years at a billion steps per second.
That wall is the difference between an algorithm and a method that works in principle. Algorithms (34/24) is a whole course on getting from the right side of this table to the left; Theory of Computation (34/29) asks which problems can never be moved over.
What a graduate just sees
- Any decision, however tangled, is AND, OR and NOT; a processor is a pile of truth tables.
- When you count two overlapping groups, subtract the overlap once.
- Order matters means n!/(n−k)!; order doesn't matter means divide by k!.
- More items than boxes means some box holds two: collisions are guaranteed, not unlucky.
- Induction is dominoes: base case plus step proves infinitely many cases; a loop invariant is the same.
- To prove something is impossible, assume it and chase the contradiction.
- Graphs are dots and links; edge ends add to twice the edges; a tree has one fewer edge than nodes.
- A remainder is a clock: mod wraps numbers into slots, and a check digit is a remainder that catches typos.
- Growth shapes (log, linear, n log n, squared, exponential) decide what is feasible far more than hardware does.
Where it shows up next
- Algorithms (34/24) and Data Structures (34/23): induction proves them correct, big-O ranks them, graphs and trees are their raw material.
- Computer Architecture (34/25): gates, adders and the whole processor are applied logic.
- Databases (34/28): sets, functions and relations are the model; hashing makes lookups fast.
- Theory of Computation (34/29): proofs by contradiction show some problems are unsolvable.
- Statics (34/10), Systems Engineering (34/22) and Machine Design (34/19): trusses as graphs, fault trees as logic, tooth counts as remainders.
If you want to go deeper
- 📘 Kenneth Rosen, Discrete Mathematics and Its Applications (McGraw Hill; 8th edition). The most-assigned university text, with huge problem sets.
- 📘 Susanna Epp, Discrete Mathematics with Applications (Cengage; 5th edition). Slower and gentler on logic and proof.
- 📖 Richard Hammack, Book of Proof (free from the author, who is at Virginia Commonwealth University): the gentle route for learning alone, focused on how to write proofs. For a free full text aimed at computer scientists, see the open textbook for MIT's 6.042J below.
- 🌐 MIT OpenCourseWare 6.042J, Mathematics for Computer Science (Spring 2015): lectures, problem sets and a free textbook by Lehman, Leighton and Meyer.
Discrete mathematics is exact reasoning about things you can count. Logic turns decisions into circuits, counting tells you what is possible, proof tells you what must be true for every case, graphs model connection, remainders give clocks and check digits, and growth rates tell you what will ever finish.
Try this: check an ISBN on the back of a book yourself, weighting its digits 1, 3, 1, 3 and adding them. The total should end in 0. Then in the growth widget above, set n to 40 and then to 60, and watch the 2n job go from minutes to years while the n² job barely moves.
Sources. Logic, counting, induction, graphs and modular arithmetic are standard textbook content (Rosen; Lehman, Leighton and Meyer); every number shown was recomputed in code. Boole, An Investigation of the Laws of Thought (1854), and the later history of Boolean algebra: Wikipedia, "The Laws of Thought". Shannon, "A Symbolic Analysis of Relay and Switching Circuits" (MIT master's thesis, 1937). Euclid, Elements IX.20 (D. Joyce's commentary). Dirichlet and the pigeonhole principle (1834): Wikipedia, "Pigeonhole principle". ISBN-13 check digit: Wikipedia, "Check digit" and the ISBN agency rules. Age of the universe, about 13.8 billion years: NASA, from the Planck 2018 results.
Go deeper. The books and course above.