Fall 2000, CSE 468: Solution of Assignment 1
Exercise 1
- R is an equivalence relation.
In fact, x+y is an even number iff
x+y = 2n for some n.
Then the relation is reflexive, because x+x = 2x.
Simmetry follows from the commutativity of +. As for transitivity,
observe that x+y = 2n and y+z = 2m imply x+z = 2(m+n-y).
The corresponding partition is constituted by the odd and the even
numbers.
- R is not an equivalence relation, because transitivity is
not satisfied. As a counterexample, consider x = 1, y = 10 and z = 19.
- R is an equivalence relation. Let us denote by rep(x) the
decimal representation of x, and by all_but_last(rep(x)) the
representation of x without the last digit.
Then x R y iff all_but_last(rep(x)) = all_but_last(rep(y)).
Since = is an equivalence relation, we have that also R is.
As for the partition, note that all_but_last(rep(x)) represents
the quotient of the integer division of x by 10. Hence the generic
n-th element of the partition will be Pn = { x | x div 10 = n }
(where div represents the integer division).
Note: the first part of this question could also be
solved by observing that x and y are related iff
x div 10 = y div 10.
Exercise 2
- Proof that L is contained in L'.
This is equivalent to say that
for all x in L, x is in L'
We prove the statement by structural induction on L.
- Base: abcc is in L', infact it is of the form
anbc2n when we take n = 1.
- Inductive step: Take a generic x in L and assume (inductive hypothesis)
that x is in L'. Then x is of the form
akbc2k for some k > 0. Observe now that
the string axcc is of the form
aakbc2kcc, i.e.
ak+1bc2(k+1) with k+1 > 0. Hence axcc
is also in L'.
- Proof that L' is contained in L.
This is equivalent to say that
for all x in L', x is in L.
We prove the statement by induction on n.
(The proof just follows the reverse reasoning of the above one.)
- Base: for n = 1, the string
anbc2n is abcc, hence it is in L.
- Inductive step: For a generic k > 0,
assume that x = akbc2k
is in L. Then
the string ak+1bc2(k+1)
is also in L, because it is equal to
axcc.
Exercise 3
- One possible solution is:
((1+2+...+9)(0+1+...+9)*)*(0+2+4+6+8).
- One possible solution is: (a+c)*b(a+c)*.
- One possible solution is: ab(ab)*.
- One possible solution is: ((a+b)(a+b))*(a+b).
Exercise 4
The inductive step does not hold for n = 1. In fact, assume that in the room
there are two persons, John and Jack. We can't prove that John and Jack have the same
height, because we need at least another person to apply the transitivity reasoning implicit in
the "proof". In other words, when we send away John, the remaining group is composed only by Jack.
When we reintroduce John and send away Jack, the new group is composed only by John. There is
nothing which links the heights of the two groups.