Reference no: EM132388524
COMP9020 Foundations of Computer Science Assignment - University of New South Wales, Australia
Problem 1 -
(a) List all possible functions f : {a, b, c{ → {0, 1}.
(b) Describe a connection between your answer for (a) and Pow({a, b, c}).
(c) In general, if card(A) = m and card(B) = n, how many:
(i) functions are there from A to B?
(ii) relations are there between A and B?
(iii) symmetric relations are there on A?
Problem 2 -
For x, y ∈ Z we define the set:
Sx,y = {mx + ny : m, n ∈ Z}.
(a) Give five elements of S2,-3.
(b) Give five elements of S12,16.
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}.
(d) Show that {n : n ∈ Z and z|n} ⊆ Sx,y.
(e) Show that d ≤ z. (Hint: use (c)).
(f) Show that z ≤ d. (Hint: use (d)).
Problem 3 -
We define the operation * on subsets of a universal set U as follows. For any two sets A and B:
A * B := Ac U Bc.
Answer the following questions using the Laws of Set Operations to justify your answer:
(a) What is (A * B) * (A * B)?
(b) Express Ac using only A, * and parentheses (if necessary).
(c) Express ? using only A, * and parentheses (if necessary).
(d) Express A \ B using only A, B, * and parentheses (if necessary).
Problem 4 -
Let Σ = {a, b}. Define R ⊆ Σ* x Σ* 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.
(b) What is R←({aba})?
(c) Show that R is a partial order.
Problem 5 -
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.).
Attachment:- Foundations of Computer Science Assignment File.rar