Sample Exam Solutions Spring 2026

Discrete Mathematics — Lecture Exam Sample (Spring 2026) — Worked Solutions

All notation matches the lecture slides. Answers chosen to be the simplest correct ones for the exam.

---

Part 1 — Short questions (18 marks)

1. Two properties of inclusive or (∨) — (1 mark)

Any two of the following (definition excluded):

• Commutativity: $p\vee q\iff q\vee p$
• Associativity: $p\vee (q\vee r)\iff (p\vee q)\vee r$
• Idempotence: $p\vee p\iff p$
• De Morgan: $\neg (p\vee q)\iff \neg p\wedge \neg q$
• Distributivity: $p\vee (q\wedge r)\iff (p\vee q)\wedge (p\vee r)$

---

2. Cartesian product — (2 marks)

(a) The Cartesian product of two sets $A$ and $B$ is the set of all ordered pairs whose first component is from $A$ and whose second component is from $B$: $A\times B=\{(a,b)\mid a\in A\wedge b\in B\}.$

(b) For $A=\{1,2,3\}$, $B=\{a,b,c\}$: $A\times B=\{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)\}.$

---

3. Composition of two binary relations — (1 mark)

Let $R$ and $S$ be binary relations. Their composition $S\circ R$ is the relation defined by $(x,z)\in S\circ R⟺\exists y:(x,y)\in R\wedge (y,z)\in S.$ (That is, $R$ is applied first, then $S$.)

---

4. Transitivity — (2 marks)

(a) A binary relation $R\subseteq X\times X$ is transitive if for all $x,y,z\in X$: $((x,y)\in R\wedge (y,z)\in R)\Rightarrow (x,z)\in R.$

(b) Example on $A=\{a,b,c,d,e\}$: the empty relation $R=\varnothing$ is transitive; or, for a non-trivial one, $R=\{(a,b),(b,c),(a,c)\}.$ Check: the only “chained” pair is $(a,b),(b,c)$, and indeed $(a,c)\in R$. (The identity relation $\{(a,a),(b,b),(c,c),(d,d),(e,e)\}$ also works.)

---

5. Equivalence relation — (2 marks)

(a) A binary relation $\sim$ on a set is an equivalence relation if it is reflexive, symmetric and transitive.

(b) Example: $X=\mathbb{Z}$ and $a\sim b⟺a-b$ is even (i.e. congruence mod 2). This is reflexive, symmetric and transitive. (Simpler finite example: $X=\{1,2,3\}$ with $\sim$ = equality, $\sim =\{(1,1),(2,2),(3,3)\}$.)

---

6. Surjective function — (2 marks)

(a) A function $f:X\to Y$ is surjective (onto) if every element of $Y$ is the image of at least one element of $X$: $\forall y\in Y\exists x\in X:f(x)=y.$

(b) Example $f:\{a,b,c,d\}\to \{1,2,3\}$ hitting all of $\{1,2,3\}$: $f(a)=1,f(b)=2,f(c)=3,f(d)=3.$

---

7. Complex numbers — (2 marks)

(a) Any four (definitions excluded), e.g.:

• $\overline{\overline{z}}=z$
• $\overline{z+w}=\overline{z}+\overline{w}$
• $\overline{z\cdot w}=\overline{z}\cdot \overline{w}$
• $z\cdot \overline{z}=|z{|}^2$
• $|\overline{z}|=|z|$
• $|z\cdot w|=|z|\cdot |w|$
• $z+\overline{z}=2\mathrm{Re}(z)$

(b) For $z=-3-2i$: $|z|=\sqrt{(-3{)}^2+(-2{)}^2}=\sqrt{9+4}=\sqrt{13},\overline{z}=-3+2i.$

---

8. Permutations with repetition (statement) — (1 mark)

The number of permutations with repetition of $m$ different kinds of objects, with repetition numbers $k_1,k_2,\dots ,k_m$ (i.e. $k_i$ copies of the $i$-th kind), is $\frac{n!}{k_1!k_2!\cdots k_m!},\text{where }n=k_1+k_2+\cdots +k_m\text{ is the total number of objects.}$

---

9. Binomial theorem — (2 marks)

(a) For any real numbers $x,y$ and any $n\in \mathbb{N}$: $(x+y{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k},$ where $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is the binomial coefficient ”$n$ choose $k$”.

(b) $(x+y{)}^6=(\genfrac{}{}{0ex}{}{6}{0})y^6+(\genfrac{}{}{0ex}{}{6}{1})x{y}^5+(\genfrac{}{}{0ex}{}{6}{2})x^2{y}^4+(\genfrac{}{}{0ex}{}{6}{3})x^3{y}^3+(\genfrac{}{}{0ex}{}{6}{4})x^4{y}^2+(\genfrac{}{}{0ex}{}{6}{5})x^{5}y+(\genfrac{}{}{0ex}{}{6}{6})x^6$ $=y^6+6x{y}^5+15x^2{y}^4+20x^3{y}^3+15x^4{y}^2+6x^{5}y+x^6.$

---

10. Two properties of binomial coefficients — (1 mark)

Any two of:

• Symmetry: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$
• Pascal’s identity: $\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)+\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)$
• $\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$

---

11. Pigeonhole principle — (1 mark)

If $n+1$ items are put into $n$ containers, then there is at least one container that contains at least two items.

---

12. Definition of an undirected graph — (1 mark)

A triple $G=(\phi ,E,V)$ is an (undirected) graph if $E$ and $V$ are sets with $V\ne \varnothing$, $V\cap E=\varnothing$, and $\phi :E\to \{\{v,v^{\prime }\}\mid v,v^{\prime }\in V\}.$ Here $V$ is the set of vertices, $E$ the set of edges, and $\phi$ the incidence function, which assigns to each edge an unordered pair of vertices.

---

Part 2 — Proof questions (16 marks)

Scoring: statement 1 mark, proof 3 marks. For two/three statements the marks split evenly.

P1. Three properties of set union, with proofs — (4 marks)

I prove idempotence, associativity and the empty-set property. Each set proof reduces the statement to the corresponding logical law via the definition of $\cup$.

(i) Idempotence: $A\cup A=A$. $x\in A\cup A\stackrel{(1)}{\iff }(x\in A\vee x\in A)\stackrel{(2)}{\iff }x\in A.$ (1) definition of $\cup$; (2) idempotence of $\vee$.

(ii) Associativity: $A\cup (B\cup C)=(A\cup B)\cup C$.

$$\begin{array}{rl}x\in A\cup (B\cup C)& \stackrel{(1)}{\iff }x\in A\vee x\in (B\cup C)\stackrel{(1)}{\iff }x\in A\vee (x\in B\vee x\in C)\\ & \stackrel{(2)}{\iff }(x\in A\vee x\in B)\vee x\in C\stackrel{(1)}{\iff }x\in (A\cup B)\vee x\in C\\ & \stackrel{(1)}{\iff }x\in (A\cup B)\cup C.\end{array}$$

(1) definition of $\cup$; (2) associativity of $\vee$.

(iii) Empty set: $A\cup \varnothing =A$. $x\in A\cup \varnothing \stackrel{(1)}{\iff }(x\in A\vee x\in \varnothing )\stackrel{(2)}{\iff }(x\in A\vee F)\stackrel{(3)}{\iff }x\in A.$ (1) definition of $\cup$; (2) definition of $\varnothing$ (no element lies in $\varnothing$, so $x\in \varnothing$ is false $F$); (3) property of $\vee$ ($p\vee F\iff p$).

(Commutativity $A\cup B=B\cup A$ via commutativity of $\vee$ is an equally valid third choice.)

---

P2. Associativity of the composition of binary relations — (4 marks)

Statement. Let $R,S,T$ be binary relations. Then composition is associative: $T\circ (S\circ R)=(T\circ S)\circ R,$ where for relations $P,Q$ the composition is $(x,z)\in Q\circ P⟺\exists y:(x,y)\in P\wedge (y,z)\in Q$.

Proof. We show that an ordered pair belongs to the left-hand side exactly when it belongs to the right-hand side.

$$\begin{array}{rl}(x,w)\in T\circ (S\circ R)& \stackrel{(1)}{\iff }\exists v:(x,v)\in S\circ R\wedge (v,w)\in T\\ & \stackrel{(1)}{\iff }\exists v:(\exists u:(x,u)\in R\wedge (u,v)\in S)\wedge (v,w)\in T\\ & \stackrel{(2)}{\iff }\exists u\exists v:(x,u)\in R\wedge (u,v)\in S\wedge (v,w)\in T\\ & \stackrel{(2)}{\iff }\exists u:(x,u)\in R\wedge (\exists v:(u,v)\in S\wedge (v,w)\in T)\\ & \stackrel{(1)}{\iff }\exists u:(x,u)\in R\wedge (u,w)\in T\circ S\\ & \stackrel{(1)}{\iff }(x,w)\in (T\circ S)\circ R.\end{array}$$

(1) definition of composition; (2) reordering and regrouping the existential quantifiers and conjunctions (the order of the independent “intermediate” elements $u,v$ does not matter, and $\wedge$ is associative/commutative). Since the two relations contain exactly the same pairs, $T\circ (S\circ R)=(T\circ S)\circ R$. $■$

---

P3. Formula for the $n^{\text{th}}$ roots of a complex number — (4 marks)

Statement. Let $z=|z|(\cos \phi +i\sin \phi )$ be a complex number given in polar form and $n\in {\mathbb{N}}^{+}$. The $n^{\text{th}}$ roots of $z$ (the numbers $w$ with $w^n=z$) are exactly $w_k=\sqrt[n]{|z|}\left(\cos (\frac{\phi }{n}+\frac{2k\pi }{n})+i\sin (\frac{\phi }{n}+\frac{2k\pi }{n})\right),k=0,1,\dots ,n-1.$

Proof. Write a candidate root in polar form as $w=|w|(\cos \psi +i\sin \psi )$. By De Moivre’s formula, $w^n=|w{|}^n(\cos n\psi +i\sin n\psi ).$ Hence $w^n=z$ is equivalent to $|w{|}^n(\cos n\psi +i\sin n\psi )=|z|(\cos \phi +i\sin \phi ).$ Two complex numbers in polar form are equal iff their absolute values are equal and their arguments differ by an integer multiple of $2\pi$. Therefore this holds iff $|w{|}^n=|z|\iff |w|=\sqrt[n]{|z|},\text{and}n\psi =\phi +2k\pi \text{ for some }k\in \mathbb{Z}\iff \psi =\frac{\phi }{n}+\frac{2k\pi }{n}.$ The values $k=0,1,\dots ,n-1$ give $n$ distinct arguments (they differ by less than $2\pi$), and any other integer $k$ reproduces one of these (since the arguments repeat with period $2\pi$ in $\psi$). Thus there are exactly the $n$ roots $w_0,\dots ,w_{n-1}$ given above. $■$

---

P4. Number of combinations with repetition — (4 marks)

Statement. Let $n\in {\mathbb{N}}^{+}$ and $k\in \mathbb{N}$. The number of $k$-combinations with repetition of an $n$-element set (selections of $k$ elements, repetition allowed, order irrelevant) is $\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right).$

Proof. Let $A=\{a_1,a_2,\dots ,a_n\}$. Any $k$-combination with repetition is determined solely by how many times each element is chosen, so we may encode it as a $0$–$1$ sequence: $\underset{\text{number of }{a}_1\text{’s}}{\underbrace{1,1,\dots ,1}},0,\underset{\text{number of }{a}_2\text{’s}}{\underbrace{1,\dots ,1}},0,\dots ,0,\underset{\text{number of }{a}_n\text{’s}}{\underbrace{1,\dots ,1}}.$ The block of $1$‘s before the first $0$ tells how many $a_1$‘s were chosen, the next block how many $a_2$‘s, and so on. This sequence contains exactly $k$ ones (one per chosen element) and $n-1$ zeros (the separators between the $n$ groups), so it has length $n-1+k$. Conversely, every such sequence corresponds to exactly one combination with repetition.

The number of such sequences equals the number of ways to choose the $k$ positions for the $1$‘s among the $n+k-1$ positions, which is $\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)$. Hence the number of $k$-combinations with repetition of $A$ is $\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)$. $■$

---

Mark check

• Part 1: 18 marks available — all answered (need ≥ 9 to pass).
• Part 2: 16 marks available — all four proofs answered (need ≥ 7 to pass).
• Reaching ≥ 29 total qualifies for grade 5.