Reference no: EM132384583

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:

S_x,y = {mx + ny : m, n ∈ Z}.

(a) Give five elements of S_2,-3.

(b) Give five elements of S_12,16.

For the following questions, let d = gcd(x, y) and z be the smallest positive number in S_x,y.

(c) Show that S_x,y ⊆ {n : n ∈ Z and d|n}.

(d) Show that {n : n ∈ Z and z|n} ⊆ S_x,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 := 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)?

(b) Express A^c 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 ⊆ Σ∗ × Σ∗ 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.)