Description
Problem 1 (20 marks)
(a) List all possible functions f : {a, b, c} → {0, 1}. (4 marks)
(b) Describe a connection between your answer for (a) and Pow({a, b, c}). (4 marks)
(c) In general, if card(A) = m and card(B) = n, how many:
(i) functions are there from A to B? (4 marks)
(ii) relations are there between A and B? (4 marks)
(iii) symmetric relations are there on A? (4 marks)
Problem 2 (26 marks)
For x, y ∈ Z we define the set:
Sx,y = {mx + ny : m, n ∈ Z}.
(a) Give five elements of S2,−3. (5 marks)
(b) Give five elements of S12,16. (5 marks)
For the following questions, let d = gcd(x, y) and z be the smallest positive number in Sx,y.
(c) Show that Sx,y ⊆ {n : n ∈ Z and d|n}. (4 marks)
(d) Show that {n : n ∈ Z and z|n} ⊆ Sx,y. (4 marks)
(e) Show that d ≤ z. (Hint: use (c)) (4 marks)
(f) Show that z ≤ d. (Hint: use (d)) (4 marks)
1
Problem 3 (24 marks)
We define the operation ∗ on subsets of a universal set U as follows. For any two sets A and B:
A ∗ B := A
c ∪ B
c
.
Answer the following questions using the Laws of Set Operations (and any derived results given in lectures) to justify your answer:
(a) What is (A ∗ B) ∗ (A ∗ B)? (6 marks)
(b) Express A
c using only A, ∗ and parentheses (if necessary). (6 marks)
(c) Express ∅ using only A, ∗ and parentheses (if necessary). (6 marks)
(d) Express A \ B using only A, B, ∗ and parentheses (if necessary). (6 marks)
Problem 4 (20 marks)
Let Σ = {a, b}. Define R ⊆ Σ
∗ × Σ
∗ as follows:
(w, v) ∈ R if there exists z ∈ Σ
∗
such that v = wz.
(a) Give two words w, v ∈ Σ
∗
such that (w, v) ∈/ R and (v, w) ∈/ R. (4 marks)
(b) What is R←({aba})? (4 marks)
(c) Show that R is a partial order. (12 marks)
Problem 5 (10 marks)
Show that for all x, y, z ∈ Z:
If x|yz and gcd(x, y) = 1 then x|z.
(Hint: Use the connection between gcd(x, y) and Sx,y shown in Problem 2.)
2
Advice on how to do the assignment
All submitted work must be done individually without consulting someone else’s solutions in accordance
with the University’s “Academic Dishonesty and Plagiarism” policies.
• Assignments are to be submitted via WebCMS (or give) as a single pdf file.
• Be careful with giving multiple or alternative answers. If you give multiple answers, then we will
give you marks only for your worst answer, as this indicates how well you understood the question.
• Some of the questions are very easy (with the help of the lecture notes or book). You can use the
material presented in the lecture or book (without proving it). You do not need to write more than
necessary (see comment above).
• When giving answers to questions, we always would like you to prove/explain/motivate your answers.
• If you use further resources (books, scientific papers, the internet,…) to formulate your answers, then
add references to your sources.
3