Determine se
é uma função de um conjunto de todas as cadeias de bits para o cojunjunto dos números inteiros se:
é o menor número inteiro
tal que o i-ésimo bit de
é 1 e
quando
for uma cadeia vazia (uma cadeia sem bits)
Passo 1
Beleza, vamos lá! O exercício pede pra gente verificar se a função
é realmente uma função que vai de todas as possíveis cadeias de bits para os números inteiros. A ideia é que, para qualquer cadeia de bits
,
dá o menor número inteiro
onde o
-ésimo bit de
é 1. Se a cadeia for vazia (ou seja, sem bits), então
. Para resolver isso, vamos entender o que é uma função e verificar se
respeita todas as regras necessárias.
Passo 2
Primeiro, vamos lembrar o que é uma função. Uma função é uma regra que associa cada elemento de um conjunto de partida (domínio) a um único elemento de um conjunto de chegada (contradomínio). No nosso caso, o domínio é o conjunto de todas as cadeias de bits e o contradomínio são os números inteiros.
Passo 3
Agora, vamos analisar como
está definida. Para qualquer cadeia de bits
,
procura o menor índice
onde o bit é 1. Se a cadeia for vazia, ou seja, não tiver nenhum bit, então
é definido como 0.
Passo 4
Precisamos verificar se, para cada cadeia de bits
, existe um único número inteiro
que
vai associar. Vamos considerar dois casos:
-
Cadeia não vazia com pelo menos um bit 1: Nesse caso, sempre existe um menor índice
onde o bit é 1. Como estamos buscando o menor , esse número é único. -
Cadeia vazia ou sem bits 1: Se a cadeia for vazia,
está bem definido. Se a cadeia não for vazia mas não tiver nenhum bit 1, o exercício não especificou, mas podemos assumir que também seria 0 ou algum valor previamente definido, garantindo que sempre retorna um único inteiro.
Passo 5
Como em todos os casos
retorna exatamente um inteiro para cada cadeia de bits
, independente se ela é vazia ou não, a função
cumpre os requisitos de uma função bem definida.
Resposta
Sim,
é uma função que mapeia todas as cadeias de bits para os números inteiros conforme descrito.
Exercícios relacionados
Por que
não é uma função de
em
se:
Por que
não é uma função de
em
se:
Determine se cada uma das funções abaixo, do conjunto
para ele mesmo é injetora:
Determine se cada uma das funções abaixo são bijetoras de
para
: