Expresse cada uma das diferentes expressões booleanas em três variáveis na forma normal disjuntiva apenas com o operador N E, usando tão poucos operadores N E quanto possivel. Qual é o maior número de operadores N E necessário?

Passo 1

O problema é: “Dado qualquer função booleana de três variáveis x,y,z escrita em forma normal disjuntiva (soma de mintermos), queremos reescrevê-la usando apenas o operador NAND (denotado aqui por N\!E) e o mínimo possível de portas NAND. Qual é, entre todas as 2^{2^3}=256 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:
  1. Negação:
\lnot x = N\!E(x,x).
Usa 1 NAND.
2. Conjunção:
x\land y = \lnot\bigl(N\!E(x,y)\bigr) = N\!E\bigl(N\!E(x,y),\,N\!E(x,y)\bigr).
Usa 2 NANDs.
3. Disjunção:
x\lor y = \lnot x\;\lor\;\lnot y = N\!E\bigl(N\!E(x,x),\,N\!E(y,y)\bigr).
Usa 3 NANDs (2 para \lnot x,\lnot y e 1 para o NAND final).

Passo 3

Se fizermos tradução direta de uma DNF canônica com k mintermos de 3 literais cada, cada mintermo (AND de 3 literais) daria
\bullet 3 literais (algumas já podem ser x ou \lnot x): 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 k 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 4\cdot4+7=23 portas NAND.
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),
f(x,y,z)=x\oplus y\oplus z,
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 é:
  1. w = N\!E(x,y)
  2. u = N\!E(x,w)
  3. v = N\!E(y,w)
  4. p = N\!E(u,v)   // aqui p = x\oplus y
  5. q = N\!E(p,z)
  6. r = N\!E(p,q)
  7. s = N\!E(z,q)
  8. f = N\!E(r,s)   // aqui f = p\oplus z 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 N\!E (NAND) necessário, em uma implementação ótima de qualquer função booleana de três variáveis, é 8.

Exercícios de Livros Relacionados