Determine se f é uma função de um conjunto de todas as cadeias de bits para o conjunto dos números inteiros, se
f(S) é a posição de um bit 0 em S.

Passo 1

O enunciado pede para ver se a regra “para cada cadeia de bits S, f(S) = posição de um bit 0 em S” define uma função do conjunto de todas as cadeias de bits em ℤ.

Passo 2

Uma vez que uma função de X em Y deve atribuir exatamente um elemento de Y a cada elemento de X, precisamos checar dois pontos: (1) que f(S) esteja sempre definida e (2) que essa definição seja única para cada S.

Passo 3

Considere uma cadeia S que não contém nenhum 0, por exemplo S = “1111”. Nesse caso não existe posição de bit 0, então f(S) não está definida. Ou seja, a regra falha no requisito (1).
Mesmo que S tenha zeros, por exemplo S = “10101”, existem várias posições com bit 0 (posições 2 e 4, supondo indexação começando em 1). A regra não diz qual dessas posições escolher, violando o requisito (2) de unicidade.

Passo 4

Conclusão: f não associa um único inteiro a cada cadeia de bits, nem está definida para todas as cadeias. Portanto, não é uma função entre esses conjuntos.

Resposta

Não, essa regra não define uma função do conjunto de todas as cadeias de bits para os inteiros, pois falta unicidade e definição em todas as entradas.

Exercícios relacionados