Responda às seguintes perguntas sobre o nível lógico digital
Existem quatro funções booleanas de uma única variável e 16 funções de duas variáveis. Quantas funções de três variáveis existem? E de n variáveis?

Passo 1

Beleza, o enunciado diz que temos 4 funções booleanas de 1 variável e 16 de 2 variáveis. Agora querem saber:
  • Quantas funções de 3 variáveis existem?
  • E, de forma geral, quantas funções de n variáveis existem?
Conteúdo envolvido: funções booleanas e contagem de quantas delas existem, sabendo que uma função booleana de k variáveis é um mapeamento de {0,1}^k em {0,1}. Vamos usar a ideia de que, se você tem M entradas possíveis, cada uma pode gerar 0 ou 1, e o total de funções é 2^M.

Passo 2

Primeiro, vamos entender quantas entradas (combinações de bits) existem para k variáveis.
Cada variável pode ser 0 ou 1, então para k variáveis temos
# entradas = 2^k
Por exemplo:
  • Para k=1, 2^1 = 2 entradas (0 ou 1).
  • Para k=2, 2^2 = 4 entradas (00, 01, 10, 11).

Passo 3

Agora, cada uma dessas # de funções = 2^(# entradas) = 2^2^k entradas pode ser mapeada para 0 ou 1 pela função. Logo, para determinar uma função booleana, em cada uma das entradas você escolhe 0 ou 1. Isso dá
çõ

Passo 4

Aplicando para o caso k = 3:
# funções de 3 variáveis = 2^2^3 = 2^8 = 256 çõá

Resposta

Funções de 3 variáveis: .
Funções de n variáveis: .

Exercícios relacionados