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
