Discrete mathematics

(the mathematics of countable, separate structures: sets, logic, and graphs)

What is discrete mathematics?

Discrete mathematics studies things that come in separate, countable pieces — like whole numbers, yes/no logic, or networks of connections — rather than things that flow smoothly, like a curve in calculus. It's the branch of math that underlies computers, since a computer only ever works with distinct, separate pieces of information.

Sets: collections of distinct things

A set is just a collection of distinct objects. If A = {1, 2, 3} and B = {2, 3, 4}, the union (A ∪ B) combines everything in either set: {1, 2, 3, 4}. The intersection (A ∩ B) keeps only what's in both: {2, 3}.

Basic logic: combining true and false statements

Logic works with statements that are either true or false, combined using AND, OR, and NOT. "It is raining AND it is cold" is only true when both parts are true. "It is raining OR it is cold" is true if at least one part is true (or both). "NOT raining" is true exactly when "raining" is false. These rules can be laid out completely in a truth table — a table listing every possible combination of true/false inputs, alongside the result for each one.

Graphs: dots and connections

A graph, in this sense, isn't a chart — it's a set of points (called vertices) connected by lines (called edges). Graphs naturally represent networks: people as vertices and friendships as edges, cities as vertices and roads as edges, web pages as vertices and links as edges.

A real proof: the handshake lemma

Here's a fact worth proving properly: in any graph, if you add up the number of edges touching each vertex (called that vertex's "degree"), the total is always exactly twice the number of edges — no matter what the graph looks like.

The reason: every single edge connects exactly two vertices. When you count each vertex's degree, that one edge gets counted once for each of the two vertices it touches — so it contributes exactly 2 to the running total, no more and no less. Since this is true for every edge individually, and the sum of all degrees is just adding up each edge's contribution, the grand total must be exactly 2 times the number of edges. This works for any graph at all, since the reasoning never depended on the graph's specific shape or size — only on the fact that every edge has exactly two ends.

Why discrete mathematics matters

Computers store and process information as distinct, separate pieces — bits, characters, records — which is exactly what discrete mathematics is built to describe. Every algorithm, database, network, and piece of software design relies on the tools of sets, logic, and graphs covered here.