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?
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
Cada variável pode ser 0 ou 1, então para k variáveis temos
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
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:
Resposta
Funções de 3 variáveis:
.
Funções de n variáveis: .
Funções de n variáveis: