Discrete Math
Discrete math is the mathematics of separate, countable things: true or false, in a set or out of it, this path or that one. It is the maths computers run on, and it starts with logic you can switch on and off.
Last updated
Discrete math is the mathematics of separate, countable things. A statement is true or false, an element is in a set or not, a network has a link between two points or it does not. There is nothing in between, which is what "discrete" means, and it is exactly how a computer sees the world.
A first course covers six topics: logic, sets, counting, graphs, number theory and proof. Logic comes first, because every other topic is written in it. Pick a connective below and switch p and q.
Truth table for p ∧ q
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Switch p and q, or click a row. The highlighted row is the one they pick.
Read p as "x is in A" and q as "x is in B". Shaded regions are where the statement is true; the dot is the current row.
p ∧ q
Read it as p and q
With these values, p ∧ q is true.
True only when both p and q are true.
As sets AND is intersection: x is in A ∩ B exactly when x is in A and x is in B.
Logic: statements and connectives
A statement is a sentence that is either true or false, such as "7 is prime" or "it is raining". Logic builds bigger statements out of smaller ones with a few connectives, and a truth table lists what the result is for every combination of inputs.
| symbol | name | say it as | true when |
|---|---|---|---|
| ∧ | AND, conjunction | "p and q" | both are true |
| ∨ | OR, disjunction | "p or q" | at least one is true |
| ¬ | NOT, negation | "not p" | p is false |
| ⊕ | XOR, exclusive or | "p or q, but not both" | exactly one is true |
| → | IMPLIES, conditional | "if p, then q" | every case except p true and q false |
| ↔ | IFF, biconditional | "p if and only if q" | p and q have the same value |
Two of these surprise people. The logical OR is inclusive: "p or q" is true when both are true, unlike the everyday "tea or coffee?". The exclusive version has its own name, XOR.
The other is IMPLIES. p → q is false in only one row, when p is true and q is false. Think of it as a promise: "if it rains, I will bring an umbrella". The promise is broken only if it rains and there is no umbrella. On a dry day the promise has not been broken, whatever you carry, so the statement counts as true.
Equivalent statements
Two statements are equivalent when their truth tables match on every row. In the widget, choose OR and negate p: the column for ¬p ∨ q is identical to the column for p → q, so the two say the same thing.
The most useful equivalences are De Morgan's laws, which say how NOT passes through AND and OR:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
In words: "not both" is the same as "one or the other is false", and "neither" is the same as "both are false". Programmers use these every day to rewrite a condition such as "not (logged in and verified)".
Logic and sets are one idea
Read p as "x is in A" and q as "x is in B". Then AND is the intersection, OR is the union and NOT is the complement, and every truth table is a shaded Venn diagram, which is why the widget draws one beside the table. De Morgan's laws become rules about sets:
(A ∩ B)′ = A′ ∪ B′
The set notation page shades each of these on a diagram you can click.
Counting
Counting in discrete math means counting without listing. Two rules do most of the work.
The multiplication rule. If one choice can be made in m ways and a second in n ways, the pair can be made in m × n ways. A 4-digit PIN has 10 choices for each digit, so there are 10^4 = 10000 possible PINs.
Combinations. The number of ways to choose k things from n, when order does not matter, is written C(n, k). Choosing 3 toppings from 8:
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
The top counts ordered choices, and dividing by 3 × 2 × 1 removes the 6 orders in which the same three toppings could have been picked.
The answer is 6 × 5 divided by 2, which is 15. If you got 30, you counted each pair twice, once in each order.
Graphs
A graph is a set of points, called vertices, joined by lines, called edges. It models anything made of connections: roads between towns, friends in a social network, links between web pages.
A first result: if 5 people all shake hands with each other once, there are C(5, 2) = 10 handshakes. Each person shakes 4 hands, which gives 5 × 4 = 20 hand-ends, and every handshake has two ends, so 20 / 2 = 10. That argument is the handshake lemma: the degrees of all the vertices add up to twice the number of edges.
Number theory and proof
Modular arithmetic is arithmetic on a clock. 17 mod 5 is 2, the remainder when 17 is divided by 5. Nine hours after 8 o'clock it is 5 o'clock, because 17 mod 12 is 5. The same idea, with very large numbers, is how the RSA encryption behind secure websites works.
Proof by induction shows a statement holds for every whole number n in two steps: check it for n = 1, then show that if it holds for some n it also holds for n + 1. It is how you prove, for example, that
1 + 2 + ... + n = n(n + 1) / 2
for every n, not only the values you tried.
What discrete math is used for
- Programming: every if statement is logic, and De Morgan's laws rewrite conditions.
- Databases: a query that joins or filters tables is set operations.
- Algorithms: counting tells you how many steps a program takes as the input grows.
- Networks and maps: shortest routes and social networks are graph problems.
- Security: encryption rests on number theory and modular arithmetic.
- Hardware: a processor is built from logic gates, which are truth tables in silicon.
Is discrete math hard?
It is hard in a different way from algebra and calculus. There are few formulas to memorise and the arithmetic is small, but many questions ask you to prove something rather than compute it, and writing a convincing argument is a new skill for most students.
What helps most is working small cases by hand before looking for the pattern: draw the Venn diagram, write out the truth table, list every case. The notation reads as heavy at first, but most of it is the symbols on this page and the set notation page.
Common questions
- What is discrete math?
- The branch of mathematics that studies separate, countable objects rather than smoothly varying quantities. Its main topics are logic, sets, counting, graphs, number theory and proof. Calculus asks how things change continuously; discrete math asks how many, which ones, and whether a statement is true.
- Is discrete math hard?
- It is hard in a different way from calculus. There are fewer formulas to apply and more arguments to build, and for many students it is their first course built around writing proofs. The algebra is usually light. Students who find it difficult are mostly adjusting to proof, and that improves quickly with practice on small examples.
- What is discrete math used for?
- Almost everything in computer science. Logic is how circuits and if statements work, sets underlie database queries, counting tells you how long an algorithm takes, graphs model networks and maps, and number theory is the basis of the encryption that protects online payments.
- What topics are covered in discrete math?
- A typical first course covers propositional logic and truth tables, sets and Venn diagrams, functions and relations, proof techniques including induction, counting with permutations and combinations, basic probability, graphs and trees, and modular arithmetic. Some courses add recurrence relations and Boolean algebra.
- Do I need discrete math for computer science?
- Yes. Almost every computer science degree requires it, usually in the first or second year, because algorithms, data structures and theory of computation all assume it. For programming on its own you can start without it, but logic, sets and counting come up in everyday code sooner than most people expect.
- What is the difference between discrete and continuous math?
- Discrete math deals with values you can list one by one, such as whole numbers, true and false, or the nodes of a network. Continuous math, such as calculus, deals with quantities that can take any value in a range, such as time, distance or temperature.
- What is a truth table?
- A table that lists every combination of true and false for the inputs of a logical statement, and the value of the statement for each one. With two inputs p and q there are four rows. A truth table is how you prove that two statements are equivalent: if their columns match on every row, they always agree.
