Determine whether f is a function from the set of all bit strings to the set of integers if (a) f (S) is the position of a 0 bit in S. (b) f (S) is the number of 1 bits in S.

(a) Not a function, because a string can be assigned to more than one value.

(b) Function

(c) Not a function, because the function does not assign an integer to every string.

Step-by-step explanation:

Definition:

A function f from A to B has the property that has each element of A has been assigned to exactly one element of B.

Solution

A = Set of all bits strings

B = Z

(a) Given: f (S) = {position of a 0 bit in S}

f is not a function, because a string can be assigned to more than one value.

for example if S = 001, then f (S) = 1 and f (S) = 2, because S = 001

contain a 0 in the first and second position.

Moreover there are also strings that do not get assign to an integer. For example, the string S = 111111 does not get assign by f, because S does not contain any 0's.

b) Given:f (S) = {number of 1 bits in S}

f is defined for all strings and the action f maps every element of A to exactly one element in Z, thus f is a function.

c) Given:

f (S) = i if the ith bit of S is the first 1 in the string

f (S) = 0 if S is the empty string

f is not a function because the string does not assign an integer to every string. More precisely, no integer are assigned to all string not containing a 1.

For example:

if S=00111, then f (S) = 3.

if S=000000, then f (S) is not defined.