There is a natural relationship between sets and bit strings which is called the characteristic vector...
There is a natural relationship between sets and bit strings which is called the characteristic vector for a set. We'll look only at subsets of the universe U = {0, … , n-1} for some n, but the concept can be generalised to arbitrary sets. For a set S C U, the characteristic vector is denoted by xs and is an n-bit string where bit j is 1 if and only if j E S. For example, with n 4 and S1,3) we have xs 1010. a) What are xo and x? (1 mark) b) Given xs and xT, what is the characteristic vector of SnT? (1 mark) c) Suppose you are given xs and xT. In terms of S and T, what set is xs Ixr the characteristic vector for? (1 mark)