What is discrete math? The main topics, an example of each, and how hard it is

By Muaz Notiar, founder of Tangibool Published 7 November 2026 18 min read

Discrete math is the mathematics of things that come in separate, countable pieces: whole numbers, true and false, sets, networks and step-by-step processes. Its main topics are logic, sets, relations and functions, counting, graphs, number theory, proofs and recurrences.

This guide explains what “discrete” means, takes each topic in turn with one small worked example and the places it is used, and answers the question most students ask: is discrete math hard? Where an example is a statement of logic, it links to a free checker that tests it on every row of its truth table.

What “discrete” means in math

Discrete means made of separate values with gaps between them. The whole numbers are discrete: between 2 and 3 there is no other whole number. The real numbers are continuous: between any two of them there are infinitely many more. Calculus studies continuous change, such as speed and area, with limits and derivatives. Discrete math studies objects that can be listed and counted one at a time, and it reasons about them with logic and proof.

Computers are discrete machines. Everything they store is a finite string of bits, and everything they do is a finite sequence of steps. That is why discrete math is the mathematics of computer science, and why computer science degrees teach it in the first or second year, often under the name discrete structures. In British English it is discrete maths. And the word is discrete, meaning separate, not discreet, meaning tactful.

The main topics at a glance

Many courses add discrete probability, trees, or automata and formal languages. The eight topics above are the common core.

The topics one by one, with a worked example each

Logic

Logic studies propositions, statements that are either true or false, and the connectives that combine them: not (¬), and (∧), or (∨), if–then (→) and if and only if (↔). A truth table lists every combination of true and false for the parts, with the value of the whole statement on each row.

Example: is “not (p and q)” the same as “not p and not q”? A truth table answers it. Row 0 has p and q both false:

Computed by the Tangibool engine

The columns ¬(p ∧ q) and ¬p ∨ ¬q match on every row, so the two statements are logically equivalent. That is one of De Morgan's laws. The column ¬p ∧ ¬q differs from them on rows 1 and 2, so it is not equivalent, and the checker gives the counterexample p = F, q = T. In words, with p for “it is cold” and q for “it is raining”: on a warm, rainy day, “it is not both cold and raining” is true, but “it is not cold and not raining” is false.

Logic is the base of everything else in the course: every proof is a chain of logical steps, and every definition is a logical statement. Most courses go on to predicate logic, which adds the quantifiers “for all” (∀) and “there exists” (∃). Tangibool's tools cover propositional logic, the part without quantifiers.

Where it is used: digital circuits are built from logic gates, every if condition in a program is a logical statement, and database queries filter rows with AND, OR and NOT.

Sets

A set is a collection of distinct objects, called its elements. The main operations are union (A ∪ B, the elements in either set), intersection (A ∩ B, in both), difference (A − B, in A but not in B) and complement (everything not in A).

Each set operation is a connective of logic in disguise. An element is in A ∪ B when “it is in A” or “it is in B” is true, in A ∩ B when both are, and in A − B when “it is in A” and “it is not in B” are. So a question about sets can be answered with a membership table: a truth table with a column for each set, where T means the element is in it.

Example: is A − (B − C) the same set as (A − B) − C?

Computed by the Tangibool engine

The two columns differ on rows 5 and 7, the elements that are in A and in C, so the two sets are not always equal. The checker's counterexample, A = T, B = F, C = T, describes an element that is in A and in C but not in B. With numbers: take A = {1, 2}, B = {2} and C = {1}. Then A − (B − C) = {1, 2} − {2} = {1}, but (A − B) − C = {1} − {1}, which is empty. Set difference is not associative.

The same method confirms the identities that do hold, such as De Morgan's law for sets, the complement of A ∪ B is the complement of A intersected with the complement of B, and the distributive law, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Where it is used: a database table is a set of rows, and SQL's UNION, INTERSECT and EXCEPT are the set operations. Probability measures sets of outcomes.

Relations and functions

A relation between two sets is a set of ordered pairs. On the positive whole numbers, “a divides b” is a relation: (3, 12) is in it and (5, 12) is not. A relation on one set can be reflexive (everything is related to itself), symmetric (if a is related to b, then b is related to a) and transitive (if a is related to b and b to c, then a is related to c).

Example: “has the same remainder when divided by 3” is all three, which makes it an equivalence relation. It splits the integers into three classes: {…, −3, 0, 3, 6, …}, {…, −2, 1, 4, 7, …} and {…, −1, 2, 5, 8, …}. Every equivalence relation splits its set into classes like these, and every such split comes from an equivalence relation.

A function is a relation that pairs each input with exactly one output. It is one-to-one (injective) if different inputs give different outputs, and onto (surjective) if every possible output is reached. f(n) = 2n on the integers is one-to-one but not onto, because no integer doubles to an odd number. A function that is both is a bijection, and two finite sets have the same size exactly when there is a bijection between them, which is the idea behind much of counting.

Where it is used: relational databases take their name from relations, since a table is a relation between its columns. A hash function maps many keys to a few slots, so it cannot be one-to-one, and a hash table has to handle the collisions. Sorting needs an order relation.

Counting

Counting, or combinatorics, answers “how many?” without listing every case. Four rules do most of the work:

• Product rule. If one choice has m options and a second has n, the pair has m × n. A 4-digit PIN has 10 × 10 × 10 × 10 = 10,000 options. A truth table with n inputs has 2ⁿ rows for the same reason: each input is true or false.
• Permutations. n different things can be put in order in n! = n × (n − 1) × … × 1 ways. Three books on a shelf: 3! = 6 orders.
• Combinations. Choosing k of n things, with order ignored, can be done in C(n, k) = n! / (k! (n − k)!) ways. A team of 2 from 5 people: C(5, 2) = 10 teams.
• Inclusion and exclusion. |A ∪ B| = |A| + |B| − |A ∩ B|. If 20 students take French, 15 take Spanish and 5 take both, then 30 take at least one of them.

Example: the pigeonhole principle says that if more than n objects go into n boxes, some box gets at least two. With 13 people, two share a birth month. Logic can check a small case. Put 3 pigeons into 2 holes, and let p1h1 stand for “pigeon 1 is in hole 1”, p1h2 for “pigeon 1 is in hole 2”, and so on: six statements. “Every pigeon is in a hole” is three “or” parts, such as p1h1 ∨ p1h2, and “no two pigeons share a hole” is six “not both” parts, such as ¬(p1h1 ∧ p2h1). The truth table generator finds their conjunction false on all 64 rows: a contradiction, so 3 pigeons cannot fit into 2 holes one to a hole. With 2 pigeons and 2 holes, the same kind of statement is true on some rows.

Where it is used: a probability is a count of favourable cases divided by a count of all cases; the running time of an algorithm is a count of its steps; test design counts the cases a set of tests has to cover.

Graphs

A graph is a set of points, called vertices, joined by lines, called edges. A road map, a social network, the web and a computer network are all graphs. The degree of a vertex is the number of edges that meet it.

Example 1, handshakes: if 5 people each shake hands once with everyone else, the graph has an edge for every pair, so C(5, 2) = 10 edges. Each person has degree 4, and 5 × 4 = 20 is twice the number of edges, because every edge has two ends. That is the handshake lemma: in any graph the degrees add up to twice the number of edges. It follows that the number of people who shook an odd number of hands is always even.

Example 2, colouring: can the vertices be coloured red and blue so that every edge joins two different colours? Logic answers it for a small graph. Let r1 stand for “vertex 1 is red”, and so on. An edge between vertices 1 and 2 needs exactly one of them red, which is r1 ⊕ r2 (exclusive or). For a triangle, (r1 ⊕ r2) ∧ (r2 ⊕ r3) ∧ (r3 ⊕ r1) is a contradiction, so a triangle cannot be coloured with two colours. For a square, the statement for its four edges is true on some rows, such as red, blue, red, blue around the square. In general, a graph can be coloured with two colours exactly when it has no cycle of odd length.

Where it is used: route finding on a map is a shortest-path problem on a graph; scheduling exams so that no student has two at once is graph colouring; search engines rank pages using the links between them.

Number theory

Number theory studies the whole numbers: divisibility, primes and remainders. Modular arithmetic keeps only the remainder: 17 mod 5 = 2, because 17 = 3 × 5 + 2. A 12-hour clock is arithmetic mod 12: 9 hours after 8 o'clock is (8 + 9) mod 12 = 5 o'clock.

Example: what is the last digit of 7¹⁰⁰? The last digit is the remainder mod 10, and the last digits of the powers of 7 repeat in a cycle of four: 7, 9, 3, 1, 7, 9, 3, 1, …. Since 100 is a multiple of 4, 7¹⁰⁰ ends in 1, like 7⁴ = 2,401.

Parity is number theory at its smallest: a number is odd or even, its remainder mod 2. The sum of two numbers is odd exactly when one of them is odd and the other even, so the parity of a sum is the exclusive or of the parities. That is why the sum bit of a binary adder is an XOR gate, as the half adder example shows.

Where it is used: public-key cryptography such as RSA relies on arithmetic with remainders and large primes. ISBNs and bank card numbers end in a check digit computed from remainders, which catches most typing errors. Hash functions use remainders to spread keys over slots.

Proofs

A proof shows that a statement holds in every case, not only in the cases tried. Discrete math is where most students meet proofs for the first time, and four methods cover most of them:

• Direct proof. Assume the hypothesis and reason to the conclusion. The sum of two even numbers is even, because 2a + 2b = 2(a + b).
• Proof by contrapositive. Prove “if not Q, then not P” instead of “if P, then Q”; the two are equivalent. The guide to converse, inverse and contrapositive has three worked proofs.
• Proof by contradiction. Assume the statement is false and derive something impossible. It works because (¬p → (q ∧ ¬q)) → p is a tautology: if “not p” leads to a contradiction, p holds.
• Proof by induction. Prove the statement for n = 1, then prove that whenever it holds for n, it holds for n + 1. Like a row of dominoes, it then holds for every positive whole number.

Example, by induction: 1 + 2 + … + n = n(n + 1)/2 for every positive whole number n.

For n = 1, both sides are 1. Now suppose the formula holds for some n. Adding n + 1 to both sides gives 1 + 2 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2, which is the formula for n + 1. So it holds for 1, then for 2, then for 3, and so on for every n.

Underneath every method are a few valid forms of argument. Modus ponens, from “if p, then q” and “p” conclude “q”, is the step most proofs repeat. Chaining conditionals, from “if p, then q” and “if q, then r” conclude “if p, then r”, is how a proof strings its steps together, and the argument validity checker confirms that the chain is valid.

Where it is used: proofs are how mathematics establishes its results. In computing, an algorithm is shown correct with a loop invariant, which is induction in another form.

Recurrences

A recurrence defines each term of a sequence from the terms before it. Solving it means finding a formula that gives the nth term directly.

Example: the Tower of Hanoi. To move n discs, move the top n − 1 discs to the spare peg, move the largest disc, then move the n − 1 discs back on top of it. So the number of moves is T(1) = 1 and T(n) = 2T(n − 1) + 1, which gives 1, 3, 7, 15, 31, …. The pattern suggests T(n) = 2ⁿ − 1, and induction confirms it: if T(n − 1) = 2ⁿ⁻¹ − 1, then T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. With 64 discs, that is about 1.8 × 10¹⁹ moves.

The Fibonacci numbers are the most famous recurrence: F(n) = F(n − 1) + F(n − 2), starting 1, 1, 2, 3, 5, 8, 13, ….

Where it is used: the running time of a recursive algorithm is a recurrence. Binary search halves the list at each step, T(n) = T(n/2) + 1, which comes to about log₂ n steps. Merge sort sorts both halves and merges them, T(n) = 2T(n/2) + n, about n log₂ n steps.

Where discrete math is used

Is discrete math hard?

It is different more than it is hard. A calculus course is mostly computation: learn a technique, then apply it to many problems that look alike. A discrete math course asks you to read precise definitions, find the right idea and write an argument, and its problems do not all look alike. Many students who struggle are meeting proofs for the first time, and that, more than the material, is what makes the course feel hard.

The usual sticking points:

• Proofs. Knowing that a statement is true is not the same as showing it. Students often check a few cases and stop, or assume the thing they are meant to prove.
• Precise reading. “If p, then q” does not mean “if q, then p”, and “not all” does not mean “none”. One misread word changes the problem.
• Negation and quantifiers. The negation of “every student passed” is “some student did not pass”. Negating statements with “for all”, “there exists”, “and”, “or” and “if” is a skill of its own.
• Counting each case once. Deciding whether order matters, and whether cases overlap, is where most counting answers go wrong.

What to practise first:

1. Logic. Truth tables, translating English into symbols, negating statements and recognising valid arguments. The rest of the course is written in this language, so time spent here pays off in every later topic.
2. Small cases. Before proving a statement about every n, try n = 1, 2, 3 and 4. The pattern often suggests the proof, and a case that fails is a counterexample.
3. Proof templates. Learn the shape of a direct proof, a proof by contrapositive, a proof by contradiction and a proof by induction, and write out several of each in full sentences.
4. Counterexamples. One example is enough to show that a statement is false. Looking for one is also the quickest way to see why a true statement is true.

Start with logic

Logic is the part of discrete math where answers can be checked mechanically: a truth table settles any question about a statement with a few variables. That makes it a good place to start and to check your own work. The reference's lessons build it up in order:

1. Lesson 1: NOT, AND, OR
2. Lesson 4: truth tables
3. Lesson 5: if, only if, unless
4. Lesson 6: De Morgan's laws
5. Lesson 8: arguments and validity
6. Lesson 9: counterexamples
7. Lesson 10: normal forms

Then practise with answers: truth tables, English to logic, De Morgan's laws, argument validity and tautology, contradiction or contingency.

Discrete math problems with answers

1. Logic. Is (p → q) ∨ (q → p) always true? Yes. If q is true, p → q is true; if q is false, q → p is true. The truth table generator shows a tautology.
2. Logic. Negate “every student passed and nobody cheated”. Answer: “some student did not pass, or somebody cheated”. The “and” becomes “or”, and each part is negated.
3. Sets. Is A − (B ∪ C) equal to (A − B) ∩ (A − C)? Yes: an element is in either side exactly when it is in A, not in B and not in C. The equivalence checker confirms it.
4. Counting. How many strings of 8 bits contain exactly three 1s? Choose the positions of the 1s: C(8, 3) = 56.
5. Counting. How many subsets does a set with 5 elements have? 2⁵ = 32, because each element is either in or out, like a row of a truth table with 5 inputs.
6. Graphs. A graph has 6 vertices, each of degree 3. How many edges does it have? (6 × 3) / 2 = 9, by the handshake lemma.
7. Number theory. What is the remainder when 2¹⁰ is divided by 7? 2³ = 8 leaves remainder 1, so 2⁹ = (2³)³ also leaves 1, and 2¹⁰ leaves 2. Check: 1,024 = 146 × 7 + 2.
8. Proofs. Prove that n² + n is even for every integer n. n² + n = n(n + 1), the product of two consecutive integers, and one of any two consecutive integers is even.
9. Recurrences. If a(1) = 2 and a(n) = 3a(n − 1), what is a(n)? a(n) = 2 × 3ⁿ⁻¹, giving 2, 6, 18, 54, ….

Frequently asked questions

What is discrete math in simple terms?

The math of separate, countable things, such as whole numbers, true-or-false statements, sets and networks, as opposed to quantities that change smoothly. It is the math that computers run on.

What does discrete mean in math?

Made of separate values with gaps between them. The integers are discrete, and the real numbers are continuous.

Is discrete math hard?

It is hard in a different way from calculus: less computation and more reasoning. Most students find writing proofs the hardest part, and practising logic first makes it easier.

Is discrete math harder than calculus?

Neither is simply harder. Students who are at home with procedures often find calculus easier, and students who enjoy puzzles and arguments often find discrete math easier.

Do you need calculus for discrete math?

No technique from calculus is needed; the course uses algebra and careful reasoning. Some universities still list calculus as a prerequisite, as a sign of experience with mathematical thinking.

What is discrete math used for?

Computer science above all. Algorithms, data structures, databases, cryptography, networks, digital circuits and software testing all rest on it.

What topics are in discrete math?

Logic, sets, relations and functions, counting, graphs, number theory, proofs and recurrences, with probability, trees or automata in many courses.

Is discrete math the same as discrete structures?

Mostly. Discrete structures is the name many computer science departments give their discrete math course.

What is an example of discrete math?

Counting the possible passwords of a given length, finding the shortest route between two towns on a road map, and checking with a truth table whether two statements mean the same thing are all discrete math.

Why do computer science students take discrete math?

Because a computer is a discrete machine. Its data is bits, its programs are logic and steps, and reasoning about what a program does uses counting, induction and graphs.

Related pages

• Guides: rules of inference; valid vs sound arguments; how to make a truth table; converse, inverse and contrapositive, with proof by contrapositive
• Logic lessons and practice sets with answers
• Glossary: proposition, truth table, tautology, valid argument, counterexample
• Boolean algebra vs propositional logic
• Worked examples: modus ponens, hypothetical syllogism, De Morgan's law

Written by Muaz Notiar. The Tangibool engine (semantics tangibool-semantics/1, engine 1.0.0) computed the 2 truth tables marked “Computed by the Tangibool engine”, and the 15 tool results the guide links to were re-run through the tools' own code in the build of 2026-11-07 and match what the text says. © 2026 Foreranger LTD.