Discrete Mathematics: practice problems and exam questions

The mathematics of computer science and of every proof: propositional logic and quantifiers, sets, relations and functions, graphs with shortest paths and spanning trees, and number theory up to RSA. Exam questions ask for exact answers, so a careful table or diagram matters more than a calculator.

Practise this course for freePractise this courseTake a mock exam5 free problems every day. No card needed.

Cram pack (PDF)Formula sheets, method steps and practice problems with full solutions, ready to print.

Topics in this course

  1. Propositional logic & proofstruth tables · equivalences and proof methods · quantifiers and argumentscalculations
  2. Sets, relations & functionsVenn diagrams and subsets · inclusion–exclusion and relations · functions and countingcalculations
  3. Graph theorydegrees and edges · Euler paths and trees · shortest paths and spanning treescalculations
  4. Number theory & modular arithmeticgcd and remainders · inverses and congruences · modular powers and RSAcalculations

Exam tips for Discrete Mathematics

  • Write out the truth table or the Venn diagram: most mistakes come from skipping a row or a region.
  • To disprove a claim, one counterexample is enough; to prove it, check every case or give a general argument.
  • In modular arithmetic, reduce after every step and keep remainders between 0 and n − 1.

Worked examples

Propositional logic & proofsEasy
pq¬(p ∨ q) → q11100100

Exactly one row of the truth table makes ¬(p ∨ q) → q false. Click that row.

¬(p ∨ q) → q
  1. 1p = 1, q = 1
  2. 2p = 1, q = 0
  3. 3p = 0, q = 1
  4. 4p = 0, q = 0
Show hints
  1. a → b is 0 only when a = 1 and b = 0. ¬a flips the value. a ∨ b is 0 only when both are 0.
  2. Work out the main connective first: what must its two sides be for the whole formula to be 0?
  3. Give each part its own column: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Show the answer and explanation

Truth tables: a formula with n different variables has 2ⁿ rows, one for every combination of truth values (1 = true, 0 = false). Work from the inside out and give every subformula its own column. ¬a flips the value; a ∧ b is 1 only when both are 1; a ∨ b is 0 only when both are 0; a → b is 0 only when a = 1 and b = 0; a ↔ b is 1 when both sides are equal.

Truth table row by row

p = 1, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 1, q = 0: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 0: p ∨ q = 0, ¬(p ∨ q) = 1, ¬(p ∨ q) → q = 0

The row

p = 0, q = 0 → ¬(p ∨ q) → q = 0

Answer

p = 0, q = 0
Sets, relations & functionsMedium
UMPC

Of 53 first-year students, 35 passed Mathematics (M), 28 passed Physics (P) and 29 passed Chemistry (C). 20 passed M and P, 18 passed M and C, 10 passed P and C, and 6 passed all three. How many are in none of the three sets?

|U| = 53

Find |(M ∪ P ∪ C)′|

Show hints
  1. Fill in the Venn diagram from the centre outwards: first all three, then the pairs, then the single sets.
  2. Only M and P (not C): 20 − 6 = 14. Only M: 35 − 14 − 12 − 6 = 3.
  3. At least one set: 35 + 28 + 29 − 20 − 18 − 10 + 6 = 50.
Show the answer and the step-by-step solution

Sets and Venn diagrams: A ∪ B holds the elements in A or B (or both), A ∩ B the elements in both, A − B the elements of A that are not in B, and the complement A′ everything in U that is not in A. In a Venn diagram every set expression is a union of regions, so count it region by region. Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|, and |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Centre and pairs

M ∩ P ∩ C: 6
M ∩ P only: 20 − 6 = 14
M ∩ C only: 18 − 6 = 12
P ∩ C only: 10 − 6 = 4

Single sets

M only: 35 − 14 − 12 − 6 = 3
P only: 28 − 14 − 4 − 6 = 4
C only: 29 − 12 − 4 − 6 = 7

Answer

|M ∪ P ∪ C| = 50
|(M ∪ P ∪ C)′| = 53 − 50 = 3

Answer

|(M ∪ P ∪ C)′| = 3

How practising works

  • “Practise this course” mixes problems from all its topics, like a real exam.
  • Every problem has new values, so you learn the method instead of an answer.
  • Stuck? Open a small hint first, and the full explanation only when you need it.
  • Mock exams are timed and have no hints, and you get your score and a full review at the end.

Related courses

Computer Science FundamentalsData Structures and AlgorithmsCalculus 1Introductory StatisticsEngineering MathematicsStatistics 2: Statistical InferenceDifferential EquationsEngineering Mathematics 2
Practise this course for freePractise this courseTake a mock exam5 free problems every day. No card needed.