Determine se é uma função de um conjunto de todas as cadeias de bits para o cojunjunto dos números inteiros se:
é o número de bit 1 em

Passo 1

Vamos começar resumindo o que o exercício pede: precisamos descobrir se a função que associa cada cadeia de bits ao número de bits iguais a 1 em é realmente uma função que vai de todas as cadeias de bits para os números inteiros. Para resolver isso, vamos precisar entender o que é uma função e como ela se aplica nesse contexto.

Passo 2

Primeiro, vamos lembrar o que é uma função. Em matemática, uma função é uma regra que associa cada elemento de um conjunto (chamado de domínio) a exatamente um elemento de outro conjunto (chamado de contradomínio). Então, para sermos uma função válida, para cada cadeia de bits que pegamos, devemos ter um único número inteiro como resultado.

Passo 3

Agora, vamos identificar os conjuntos envolvidos:
  • Domínio: Todas as cadeias de bits possíveis. Isso inclui qualquer sequência finita de 0s e 1s, como “0”, “1”, “01”, “110”, etc.
  • Contradomínio: Os números inteiros. No nosso caso, estamos contando o número de bits iguais a 1, então os resultados serão números inteiros não negativos (0, 1, 2, …).

Passo 4

A função está definindo que, para cada cadeia de bits , será o número de bits que são 1 na cadeia. Por exemplo:
  • Se , então .
  • Se , então .
Cada cadeia de bits leva a exatamente um número inteiro que representa a contagem dos bits 1.

Passo 5

Como para cada cadeia de bits existe apenas um número inteiro correspondente , a regra que estamos aplicando atende à definição de função. Não há ambiguidade ou múltiplos resultados para uma única entrada.

Resposta

Sim, é uma função que leva todas as cadeias de bits para os números inteiros, associando cada cadeia ao número de bits iguais a 1 que ela contém.

Exercícios relacionados

Dê um exemplo de uma relação em um conjunto que seja:
$(b) nem simétrica nem anti-simétrica
Quais destas relações em são relações de equivalência?
Determine se cada uma das funções abaixo são bijetoras de para :
Para cada uma das relações abaixo no conjunto , decida se ela é reflexiva, simétrica, transitiva e/ou anti-simétrica: