Midterm Spring 2024

Discrete Mathematics - Midterm - Spring 2024

NAME:
NEPTUN code:
Group number/Class teacher:

• Duration: 90 minutes.
• Total score: The maximal total score achievable in the midterm test is 40 points.
• Success criterion: In order to successfully pass this test, you need to achieve at least 16 points.
• Equipment: Only blank papers and pen allowed, no calculators.

Instructions

• Each task must be solved on paper using pen. Please:
  • write your name, Neptun code and the name of your practice class teacher on the top of this exam paper;
  • write your name and Neptun code on the top of each paper you submit;
  • note that in most questions justification is required. Just an answer to these questions without any proof is worth very few marks only. Please do not forget to justify your answers. (Applying and showing the steps of a method learnt in the class — where relevant — is regarded as sufficient justification.)
  • note that a ‘yes’ or ‘no’ answer on its own without any justification is worth 0 marks only;
  • after finishing the test, place all the papers with your solutions behind this exam paper and in order for the papers to stay together please fold them into half (parallel to the longer side);
  • note that the actual test paper will be shared on Canvas, hence you will be able to obtain it.

In Question 6 you have a choice between two questions: You do not need to solve both of them, please choose just one of them.

Thank you and all the best for the test!

---

Values of some trigonometric functions that may be needed for some questions

$x$	$0$	$\pi /6$	$\pi /4$	$\pi /3$	$\pi /2$	$2\pi /3$	$3\pi /4$	$5\pi /6$	$\pi$
$\cos x$	$1$	$\sqrt{3}/2$	$\sqrt{2}/2=1/\sqrt{2}$	$1/2$	$0$	$-1/2$	$-\sqrt{2}/2=-1/\sqrt{2}$	$-\sqrt{3}/2$	$-1$
$\sin x$	$0$	$1/2$	$\sqrt{2}/2=1/\sqrt{2}$	$\sqrt{3}/2$	$1$	$\sqrt{3}/2$	$\sqrt{2}/2=1/\sqrt{2}$	$1/2$	$0$

---

Questions

1.

For each of the equalities below decide if it is true for every set $A$, $B$ and $C$. Prove your answers.

$(A\setminus B)\cap (A\setminus C)=A\setminus (B\setminus C)$

$A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)$

---

2.

a)

Consider the binary relation
$T=\{(1,1),(1,2),(1,4),(2,1),(2,2),(2,4),(3,1),(3,3),(4,4)\}$
on set $X=\{1,2,3,4\}$. Decide whether $T$ is reflexive, symmetric, transitive and/or antisymmetric. Justify your answers.

b)

Let $R=\{(a,d),(a,e),(b,a),(c,b),(c,d),(d,d)\}$. Find:

i.

$\mathrm{rng}(R)△\mathrm{dmn}(R)$

ii.

$R(\{a,b,c\})$

iii.

$R^{-1}{|}_{\{a,c\}}$

c)

On set $A=\{1,2,3,4\}$ construct a relation $R$ which satisfies all of the following properties: it is anti-symmetric, reflexive, but not transitive.

(10 marks)

---

3.

a)

Let
$R=\{(x,y)\in \mathbb{R}\times \mathbb{R}\mid 2x^3-5=\frac{3y+2}{4}\}$
and
$S=\{(x,y)\in \mathbb{R}\times \mathbb{R}\mid 2x+3=6y-2\}$
Find the composition $S\circ R$.

b)

Let
$R=\{(1,1),(1,2),(2,1),(2,3),(4,4),(4,1)\}$
and
$S=\{(1,2),(1,3),(2,2),(3,4),(4,3),(4,1)\}$
Find $R^{-1}\circ S$.

(6 marks)

---

4.

a)

For each of the following examples, decide if the relation is an equivalence relation, justifying your answer.

i.

$R_1=\{(1,1),(1,5),(2,2),(2,4),(3,3),(4,2),(4,4),(5,1),(5,5)\}\subseteq X\times X,$
where $X=\{1,2,\dots ,5\}$.

ii.

$R_2=\{(x,y):xy>-1\}\subseteq \mathbb{R}\times \mathbb{R}.$

iii.

$R_3=\{(x,y):x^{10}-y^{10}\text{ is even}\}\subseteq \mathbb{Z}\times \mathbb{Z}.$

b)

For each equivalence relation in part (a) find the partition determined by the equivalence relation.

(7 marks)

---

5.

For each of the relations below decide if it is a partial order. Justify your answers.

$T_1=\{(x,y)\in \mathbb{R}\times \mathbb{R}:4x^2-4y^2\le 0\}\subseteq \mathbb{R}\times \mathbb{R}.$

$T_2=\{(x,y)\in \mathbb{R}\times \mathbb{R}:x-y<100\}\subseteq \mathbb{R}\times \mathbb{R}.$

$T_3=\{(x,y)\in \mathbb{Z}\times \mathbb{Z}:x-y\text{ is a natural number}\}\subseteq \mathbb{Z}\times \mathbb{Z}.$

---

There are two versions of Question 6, which you can choose from.

Please choose one of the two versions:

Version 1

6.

a)

Decide about each of the relations below if it is a function, justifying your answer.

i.

$f_1=\{(a,c),(b,b),(b,d),(d,c),(e,a)\}\subseteq Y\times Y,$
where $Y=\{a,b,c,d,e,f\}$.

ii.

$f_2=\{(x,y)\in \mathbb{R}\times \mathbb{R}\mid x^3-1=y^2+2\}\subseteq \mathbb{R}\times \mathbb{R}.$

iii.

$f_3=\{(x,y)\in \mathbb{R}\times \mathbb{R}\mid \frac{2x+6}{4}=\frac{y+2}{3}\}\subseteq \mathbb{R}\times \mathbb{R}.$

b)

For each of the above relations that is a function, decide if it is injective, surjective and/or bijective. Justify your answers.

(8 marks)

---

Version 2

6.

a)

Using the polar form of complex numbers, calculate

$z=\frac{(1+i{)}^{32}}{(-1-\sqrt{3}i{)}^{12}},$

giving your answer in polar form. Then find all complex numbers $w$ such that $w^4=z$.

(8 marks)