Essay Help Services

COMP9020 | Assignment 1 Foundation of Computer Science | IT

Home Recent Questions COMP9020 | Assignment 1 Foundation of Computer Science | IT

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)

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.)

Similar Posts

Order Now

Latest Reviews

Facebook

Payments And Security