To solve this type of exercise, first, we need to know what is a function.
“Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. We write f(a) = b if b is the unique element of B assigned by the function f to the element a of A. If f is a function from A to B, we write f: A → B.” Discrete Mathematics and its Applications by Rosen.
a) f(S) is the position of a 0 bit in S
This function goes from the set S to the set of integers. So, we can write it as f: S → Z.
Because there can be several 0s in a bit string (i.e. 0011010), f(S)=b, b won’t be a unique value of Z assigned to f(S).
Therefore, f is not a function because it doesn’t hold the definition of a function.
b) f(S) is the number of 1 bits in S
In this case, the definition of function holds. Notice that the number of 1s in a specific bit string is always the same. In other words, you cannot have n 1s and m 1s at the same time in the same bit string.
Example:
f(1011)=3
There is no way, that f(1011) can equal a number different than 3.
Therefore, f is a function.
c) f (S) is the smallest integer i such that the ith bit of S is 1 and f (S) = 0 when S is the empty string, the string with no bits.
Let’s try to find an example that shows that f is not a function.
f(000) is not defined.
So, f is not defined when the bit string does not have 1s.
Reviewing the definition “… A function f from A to B is an assignment of exactly one element of B to each element of A …”.
Therefore, it is not a function.
Related exercises:
