Description
1. (a) Compute gcd(288, 120).
(b) Compute lcm(−91, 52).
(c) What can be said about gcd(n, n + 1) for n ∈ N?
2. (a) What is card(Pow(Pow(∅)))?
(b) Show that A ∩ (B ⊕ C) = (A ∩ B) ⊕ (A ∩ C) for any sets A, B, C.
(c) Find sets A, B, C to show that A ⊕ (B ∩ C) 6= (A ⊕ B) ∩ (A ⊕ C).
3. Let Σ = {a, b}. List the elements of Σ≤3
in:
(a) Lexicographic order
(b) Lenlex order
4. (a) List all possible functions f : {a, b, c} → {0, 1}
(b) 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?
(c) Describe a connection between your answer for (a) and Pow({a, b, c}).
5. Let Σ = {a, b} and L = {w ∈ Σ
∗
: 3|length(w)}. Define R ⊆ Σ
∗ × Σ
∗ as
follows: (w, w0
) ∈ R if for all v ∈ Σ
∗
the following holds: either wv ∈ L
and w
0v ∈ L, or wv /∈ L and w
0v /∈ L.
For example (a, bbb) ∈/ R because
for v = λ, av = a /∈ L but bbbv = bbb ∈ L. On the other hand, (a, b) ∈ R
because for any v ∈ Σ
∗
, length(av) = length(bv) so av ∈ L if, and only if,
bv ∈ L.
(a) Which of the following are elements of R:
(i) (abab, baba)?
(ii) (ab, abab)?
(iii) (λ, b)?
(iv) (λ, bb)?
(v) (λ, bbb)?
(b) Show that R is an equivalence relation.
(c) How many equivalence classes does R have?
