COMP9020 Assignment 1 2019 Term 3
Due: Sunday, 13th October, 23:59
Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should
be typed, not handwritten. Use of LATEX is encouraged, but not required.
Discussion of assignment material with others is permitted, but the work submitted must be your own in
line with the University’s plagiarism policy.
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 := Ac ∪ Bc.
Answer the following questions using the Laws of Set Operations (and any derived results given in lec-
tures) to justify your answer:
(a) What is (A ∗ B) ∗ (A ∗ B)? (6 marks)
(b) Express Ac 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 an-
swers.
• If you use further resources (books, scientific papers, the internet,...) to formulate your answers, then
add references to your sources.
3