Expresse cada uma das diferentes expressões booleanas em três variáveis na forma normal disjuntiva apenas com o operador
, usando tão poucos operadores
quanto possivel. Qual é o maior número de operadores
necessário?
Passo 1
O problema é: “Dado qualquer função booleana de três variáveis
escrita em forma normal disjuntiva (soma de mintermos), queremos reescrevê-la usando apenas o operador NAND (denotado aqui por
) e o mínimo possível de portas NAND. Qual é, entre todas as
funções de três variáveis, o maior número de portas NAND necessário numa implementação ótima?”
Conteúdo usado: completude funcional do NAND, construções de NOT, AND, OR via NAND e noções de simplificação (agrupamento de mintermos e fatoração superficial).
Passo 2
Mostramos como implementar as operações básicas com o mínimo de NANDs:
- Negação:
Usa 1 NAND.
2. Conjunção:
2. Conjunção:
Usa 2 NANDs.
3. Disjunção:
3. Disjunção:
Usa 3 NANDs (2 para
e 1 para o NAND final).
Passo 3
Se fizermos tradução direta de uma DNF canônica com
mintermos de 3 literais cada, cada mintermo (AND de 3 literais) daria
literais (algumas já podem ser
ou
): para cada literal invertido que não exista, 1 NAND;
• depois 2 NANDs para juntar par a par e inverter.
Mas, em média, implementa-se um AND de 3 sinais em 4 NANDs.
Para OR de sinais fazemos árvore binária de NANDs acrescentando inversões de entrada: no pior caso direto, são 7 NANDs para OR de 4 sinais. Assim, uma DNF com 4 mintermos isolados daria até cerca de
portas NAND.
• depois 2 NANDs para juntar par a par e inverter.
Mas, em média, implementa-se um AND de 3 sinais em 4 NANDs.
Para OR de
Porém, muita “DFN” de 4 mintermos isolados na verdade é a função de paridade ou funções equivalentes, que têm implementações muito mais econômicas via fatoração.
Passo 4
O caso que fica de fato mais caro, após simplificar ao máximo, é a paridade de três variáveis (ou seu complemento),
porque não se agrupa em mintermos maiores e não há fator comum que reduza abaixo do esquema XOR.
Uma implementação ótima em NANDs é:
-
-
-
-
// aqui -
-
-
-
// aqui Total: 8 portas NAND.
Passo 5
Pode-se verificar (por enumeração ou por argumentos de simetria e independência de agrupamento na K-mapa) que nenhuma outra função booleana de três variáveis exige mais de 8 portas NAND quando implementada de forma ótima.
Resposta
O maior número de operadores
(NAND) necessário, em uma implementação ótima de qualquer função booleana de três variáveis, é 8.