Discrete Mathematics: free practice, theory and problems

1. Logic and sets

What is it about?

Computers are built on logic: true and false, and and or. Sets are how mathematics collects things. Both show up everywhere in programming, databases and digital circuits.

Concepts and formulas

• Propositional logic: $\neg p$ (not), $p \wedge q$ (and), $p \vee q$ (or), $p \rightarrow q$ (if … then).
• $p \rightarrow q$ is only false when $p$ is true and $q$ is false.
• De Morgan's laws:

• Contrapositive: $p \rightarrow q$ is equivalent to $\neg q \rightarrow \neg p$.
• A truth table with $n$ variables has $2^n$ rows.
• Sets: union $A \cup B$ (in A or B), intersection $A \cap B$ (in both), complement.
• Inclusion–exclusion:

• A set with $n$ elements has $2^n$ subsets (the power set).

How to solve the problems

1. Logic: make a truth table, or use De Morgan and the contrapositive.
2. Counting with overlap: add and subtract what was counted twice.
3. "Neither": total minus the union.

Example

40 students: 25 take maths, 18 take physics and 10 take both. How many take neither?

1. $|M \cup P| = 25 + 18 - 10 = 33$.
2. Neither: $40 - 33 = 7$.

Common mistakes

• Thinking $p \rightarrow q$ is false when $p$ is false. A promise is not broken if the condition doesn't happen.
• Forgetting to subtract the intersection and so counting some twice.
• Confusing the converse ($q \rightarrow p$) with the contrapositive.

Concepts in this part

Practise logic and sets in the app →

2. Combinatorics

What is it about?

How many passwords exist? In how many ways can a team be chosen? Combinatorics is systematic counting. It is used in probability, security (how long does it take to guess a password?) and algorithms (how many cases must be checked?).

Concepts and formulas

• Multiplication principle: $a$ choices followed by $b$ choices give $a\cdot b$ possibilities.
• Ordered selections with repetition: $n^k$ (for example a PIN code).
• Permutations: $n$ things in order: $n! = n\cdot(n-1)\cdots 1$.
• Ordered selection without repetition (order matters):

• Combinations (order doesn't matter):

• Handshakes between $n$ people: $\binom{n}{2} = \dfrac{n(n-1)}{2}$.

How to solve the problems

1. Ask: does order matter? Can the same thing be chosen more than once?
2. Order and repetition: $n^k$. Order without repetition: $P(n,k)$. No order: $\binom nk$.

Example

8 runners compete for gold, silver and bronze. How many possible podiums are there?

1. The order matters, and nobody can get two medals.
2. $P(8,3) = 8\cdot 7\cdot 6 = 336$.

Common mistakes

• Using combinations when the order matters (or the other way round).
• Forgetting that $0! = 1$.
• Adding when the choices should be multiplied.

Concepts in this part

Practise combinatorics in the app →

3. Graphs and modular arithmetic

What is it about?

A graph is nodes (points) connected by edges (lines). Road networks, computer networks, friends on social media and dependencies between program modules are all graphs. Modular arithmetic is "clock arithmetic" with remainders, used in hashing, encryption and check digits.

Concepts and formulas

• The degree of a node: the number of edges leaving it. Handshake lemma:

• The complete graph $K_n$ (everyone connected to everyone) has $\dfrac{n(n-1)}{2}$ edges.
• A tree is a connected graph without cycles. A tree with $n$ nodes has exactly $n - 1$ edges.
• Euler circuit (use every edge exactly once and return): exists when the graph is connected and every node has even degree.
• Shortest path in a weighted graph: Dijkstra's algorithm. Always expand from the nearest node you haven't finished.
• Modular arithmetic: $a \bmod m$ is the remainder when $a$ is divided by $m$. For example $17 \bmod 5 = 2$.

How to solve the problems

1. Count edges via the degrees: add up and divide by 2.
2. For trees and complete graphs: use the formulas.
3. Shortest path: try all reasonable routes in small graphs, or follow Dijkstra.

Example

Edges: A–B (4), A–C (1), C–B (2), B–D (5), C–D (8). Shortest path from A to D?

1. A–C–B costs $1 + 2 = 3$, which is cheaper than A–B directly (4).
2. Then B–D: $3 + 5 = 8$. The alternative A–C–D costs $1 + 8 = 9$.
3. The shortest path is A–C–B–D with length 8.

Common mistakes

• Forgetting to divide the degree sum by 2.
• Thinking the direct edge is always shortest.
• Using negative remainders: in mathematics $a \bmod m$ is always between 0 and $m - 1$.

Concepts in this part

Practise graphs and modular arithmetic in the app →