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?
1
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 pdf
• 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 answers.
• If you use further resources (books, scientific papers, the internet,…) to
formulate your answers, then add references to your sources.
2