Forma normal canônica

Na álgebra Booleana, qualquer função Booleana pode ser colocada na forma normal canônica disjuntiva (do inglês, CDNF) ou na forma canônica de mintermos e a sua dupla forma normal canônica conjuntiva (do inglês, CCNF) ou forma canônica de maxtermos. Outras formas canônicas incluem a soma completa dos implicantes primos ou Forma canônica de Blake (e seu dual), e a forma normal algébrica (também chamada de forma normal de Zhegalkin ou forma normal de Reed–Muller).

Mintermos são chamados de produtos, pois eles são a conjunção lógica de um conjunto de variáveis, e maxtermos são chamados de somas, porque eles são a disjunção lógica de um conjunto de variáveis. Estes conceitos estão conectados por causa de sua relação de simetria expressa pelas leis de De Morgan.

A forma canônica de qualquer função Booleana pode ser expressa de duas maneiras: como uma "soma de mintermos" ou um "produto de maxtermos". O termo "Soma de Produtos" ou "SdP" é amplamente utilizado para a forma canônica que é composta por uma disjunção (OU) de mintermos. Seu "dual" de De Morgan é o "Produto de Somas" ou "PdS" para a forma canônica que é uma conjunção (E) de maxtermos. Essas formas podem ser úteis para a simplificação dessas funções, que são de grande importância na otimização de fórmulas Booleanas em geral e, principalmente, circuitos digitais.

Resumo

Uma aplicação da álgebra Booleana é no desenho de circuitos digitais. O objetivo pode ser o de minimizar o número de portas, para minimizar o tempo de assentamento, etc.

Há dezesseis possíveis funções de duas variáveis, mas, na lógica digital de hardware, os mais simples circuitos de portas implementam apenas quatro delas: conjunção (E), disjunção (OU inclusivo), e os respectivos complementos (NAND e NOR).

A maioria dos circuitos lógicos aceitam mais de 2 variáveis de entrada; por exemplo, o computador de bordo espacial Apollo Guidance Computer, que foi pioneiro na aplicação de circuitos integrados na década de 60, foi construído com apenas um tipo de porta, a de 3 entradas NOR, cuja saída é verdadeira somente quando todas as 3 entradas são falsas.^[1]

Mintermos

Para uma função booleana de $n$ variáveis ${\textstyle {\displaystyle {x_{1},\dots ,x_{n}}}}$ , um produto de termos em que cada uma das $n$ variáveis aparece uma vez (em sua forma complementar ou não-complementar) é chamado de mintermo. Assim, um mintermo é uma expressão lógica de n variáveis que emprega apenas o operador de complemento e o de conjunção.

Por exemplo, $abc$ , $ab'c$ e $abc'$ são 3 exemplos dos 8 mintermos para uma função Booleana de três variáveis $a$ , $b$ e $c$ . A leitura costumeira deste último é: a E b E NÃO-c.

Há 2ⁿ mintermos de n variáveis, uma vez que uma variável num mintermo pode estar na sua forma direta ou em sua forma complementar—duas escolhas por variável.

Indexação de mintermos

Mintermos muitas vezes são contados por uma codificação binária padrão, onde as variáveis são escritas geralmente em ordem alfabética. Esta convenção atribui o valor 1 para a forma direta ( $x_{i}$ ) e 0 para as formas complementares ( $x'_{i}$ ); o mintermo é ${\displaystyle \sum \limits _{i=1}^{n}2^{i}\operatorname {value} (x_{i})}$ . Por exemplo, o mintermo $abc'$ é associado a 110₂ = 6₁₀ e denotado $m_{6}$ .

Equivalência funcional

Um dado mintermo n dá um valor verdadeiro (por exemplo, 1) por apenas uma combinação das variáveis de entrada. Por exemplo, mintermo 5, a b' c, é verdadeiro somente quando a e c são ambos verdadeiros e b é falso—a entrada do arranjo, onde a = 1, b = 0 e c = 1, resulta em 1.

Dada a tabela verdade de uma função lógica, é possível escrever a função como uma "soma de produtos". Esta é uma forma especial da forma normal disjuntiva. Por exemplo, se dada a tabela-verdade para a soma aritmética de bits u, que faz parte de um circuito somador, como função de x e y a partir da própria adição e do "carry in", ci:

ci	x	y	u(ci,x,y)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Observando que as linhas que têm uma saída em 1 são as 2º, 3º, 5º e 8º, podemos escrever u como uma soma de mintermos $m_{1},m_{2},m_{4},$ e $m_{7}$ . Se quisermos verificar isso: $u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)$ avaliado por todas as 8 combinações de três variáveis, que vai coincidir com a tabela.

Maxtermos

Para uma função booleana de $n$ variáveis ${\textstyle {\displaystyle {x_{1},\dots ,x_{n}}}}$ , uma soma de termos em que cada uma das $n$ variáveis aparece uma vez (em sua forma complementar ou não-complementar) é chamado um maxtermo. Assim, um maxtermo é uma expressão lógica de n variáveis que emprega apenas os operadores de complemento e o de disjunção. Maxtermos são um dual à ideia do mintermo (por exemplo, exibindo uma simetria complementar em todos os aspectos). Em vez de usar os operadores AND e complementos, usamos OR e complementos e procedemos da mesma forma.

Por exemplo, a seguir estão dois dos oito maxtermos de três variáveis:

a + b' + c

a' + b + c

Há 2ⁿ maxtermos de n variáveis, uma vez que uma variável na expressão de maxtermos pode ser em sua forma direta ou em sua forma complementar—duas escolhas por variável.

Indexação maxtermos

A cada maxtermo é atribuído um índice com base no oposto ao convencional utilizado para mintermos. A conversão para maxtermos atribui o valor 0 para a forma direta ${\displaystyle (x_{i})}$ e 1 para formas complementares ${\displaystyle (x'_{i})}$ . Por exemplo, podemos atribuir o índice de 6 o maxtermo ${\displaystyle a'+b'+c}$ (110) e denotamo-lo como M₆. Da mesma forma M₀ de três variáveis é ${\displaystyle a+b+c}$ (000) e M₇ é ${\displaystyle a'+b'+c'}$ (111).

Equivalência funcional

É evidente que o maxtermo n dá um valor falso (i.é., 0) para apenas uma combinação das variáveis de entrada. Por exemplo, o maxtermo 5, a' + b + c', é falsa somente quando a e c são ambos verdadeiros e b é falso—a entrada do arranjo, onde a = 1, b = 0 e c = 1, resulta em 0.

Se é dada uma tabela verdade de uma função lógica, é possível escrever a função como um "produto de somas". Esta é uma forma especial da forma normal conjuntiva. Por exemplo, se a tabela dada for a de um bit de "carry-out" co que faz parte de um circuito somador, como função de x e y da adição e do "carry in", ci:

ci	x	y	co(ci,x,y)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Observando-se que as linhas que têm uma saída de 0 são 1º, 2º, 3º e 5º, podemos escrever o co como um produto de maxtermos ${\displaystyle M_{0},M_{1},M_{2}}$ e ${\displaystyle M_{4}}$ . Se quisermos verificar isso: co(ci, x, y) = ${\displaystyle M_{0}M_{1}M_{2}M_{4}}$ = (ci + x + y) (ci + x + y') (ci + x' + y) (ci' + x + y) avaliado por todas as 8 combinações de três variáveis, que vai coincidir com a tabela.

Dualização

O complemento de um mintermo é o respectivo maxtermo. Isso pode ser facilmente verificado usando a lei de De Morgan. Por exemplo: $M_{5}=a'+b+c'=(ab'c)'=m_{5}'$

Formas não-canônicas de PdS e SdP

É frequente o caso em que a forma canônica do mintermo pode ser simplificado para uma equivalente em SdP. Esta forma simplificada consiste de uma soma de termos de produtos. No entanto, na forma simplificada, é possível que existam um menor número de termos de produto e/ou produtos de termos que contém menos variáveis. Por exemplo, a seguinte função de 3 variáveis:

a	b	c	f(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

tem a representação do mintermo canônico: ${\displaystyle f=a'bc+abc}$ , mas este tem um equivalente em forma simplificada: ${\displaystyle f=bc}$ . Neste exemplo trivial, é óbvio que ${\displaystyle bc=a'bc+abc}$ , mas a forma simplificada apresenta tanto uma quantidade menor de termos, quanto de variáveis no total. A representação mais simplificada em SdP de uma função é chamada de forma mínima de SdP.

De forma semelhante, uma forma canônica de maxtermos pode ter uma forma em PdS mais simplificada.

Embora esse exemplo tenha facilmente simplificado após a aplicação de métodos algébricos normais, [ ${\displaystyle f=(a'+a)bc}$ ], em casos menos óbvios, um método conveniente para encontrar a forma mínima em PdS/SdP de uma função com até quatro variáveis é usar um mapa de Karnaugh.

As formas mínimas de PdS e SdP são muito importantes para encontrar ideal implementações de funções booleanas e de minimização de circuitos lógicos.

Exemplo de aplicação

Os exemplos de tabelas-verdade para mintermos e maxtermos acima são suficientes para estabelecer a forma canônica para um único bit de posição na adição de números binários, mas não são suficientes para o projeto de uma lógica digital, a menos que seu inventário de portas incluir as AND e OR. Onde o desempenho é um problema (como na Apollo Guidance Computer), as peças são mais propensas a serem compostas por NAND e NOR devido à ação inerente de complementação na lógica de transistores. Os valores são definidos como estados de tensão, um perto do "terra" e outro perto da tensão de alimentação DC V_cc, i.e. +5 VDC. Se a maior tensão é definida como 1 para valor "true", uma porta NOR é o mais simples e útil elemento da lógica possível.

Especificamente, uma porta NOR de 3 entradas pode consistir de 3 transistores bipolares de junção com os seus emissores todos em "terra" e seus cobradores amarrados juntos e ligados a V_cc através de uma impedância de carga. Cada base é ligada a um sinal de entrada, e o ponto de coletor comum apresenta o sinal de saída. Qualquer entrada que tem um 1 (alta tensão) para a sua base comprime os transistores do emissor para o seu coletor, fazendo com que um fluxo de corrente passe através da impedância de carga, o que traz a tensão do coletor (saída) muito perto do "terra". O resultado disto independe das outras entradas. Somente quando todos os 3 sinais de entrada forem 0 (baixa tensão) o emissor-coletor de impedâncias de todos os 3 transistores permanecem elevados. Em seguida uma corrente muito pequena flui, e o divisor de tensão trabalhando com a impedância de carga impõe ao coletor um ponto de alta tensão (1), muito perto de V_cc.

A propriedade complementar destas portas pode parecer uma desvantagem quando tentamos implementar a uma função na forma canônica, mas há um bônus que compensa: a porta com apenas um sinal de entrada implementa a função complementar, o qual é com freqüência na lógica de circuitos.

Este exemplo assume que o estoque de peças da Apollo era constituído de portas NOR de 3 entradas apenas, mas a discussão é simplificada ao supormos que portas NOR com 4 entradas também estavam disponíveis (na Apollo, estes eram compostos de pares de portas NOR de 3 entradas).

Consequências canônicas e não-canônicas de portas NOR

Fato #1: um conjunto de 8 portas NOR, se as suas entradas são todas as combinações das formas diretas e complementares de 3 variáveis de entrada do ci, x, e y, sempre produzem mintermos, nunca maxtermos—isto é, das 8 portas necessárias para processar todas as combinações de 3 variáveis de entrada, apenas uma tem o valor de saída 1. Isso porque uma porta NOR, apesar do seu nome, poderia ser melhor visualizado (usando a lei de De Morgan) como um E dos complementos de seus sinais de entrada.

Fato #2: o motivo do Fato #1 não ser um problema é a dualidade de mintermos e maxtermos, i.e. cada maxtermo é o complemento do respectivo mintermo, e vice-versa.

No mintermo do exemplo acima, escrevemos $u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}$ mas, para realizar isso com porta NOR de 4 entradas, precisamos reafirmar-lo como um produto de somas (PdS), onde as somas são os maxtermos opostos. Que é,

$u(ci,x,y)$ = AND( $M_{0},M_{3},M_{5},M_{6}$ ) = NOR( $m_{0},m_{3},m_{5},m_{6}$ ). Tabelas de verdade:

ci	x	y	M₀	M₃	M₅	M₆	AND	u(ci,x,y)
0	0	0	0	1	1	1	0	0
0	0	1	1	1	1	1	1	1
0	1	0	1	1	1	1	1	1
0	1	1	1	0	1	1	0	0
1	0	0	1	1	1	1	1	1
1	0	1	1	1	0	1	0	0
1	1	0	1	1	1	0	0	0
1	1	1	1	1	1	1	1	1

ci	x	y	m₀	m₃	m₅	m₆	NOR	u(ci,x,y)
0	0	0	1	0	0	0	0	0
0	0	1	0	0	0	0	1	1
0	1	0	0	0	0	0	1	1
0	1	1	0	1	0	0	0	0
1	0	0	0	0	0	0	1	1
1	0	1	0	0	1	0	0	0
1	1	0	0	0	0	1	0	0
1	1	1	0	0	0	0	1	1

No maxtermo exemplificado acima, escrevemos ${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}$ mas para realizar isso com porta NOR de 4 entradas nós precisamos observar a igualdade para o NOR dos mesmos mintermos. Que é,

$co(ci,x,y)$ = AND( $M_{0},M_{1},M_{2},M_{4}$ ) = NOR( $m_{0},m_{1},m_{2},m_{4}$ ). Tabelas verdade:

ci	x	y	M₀	M₁	M₂	M₄	AND	co(ci,x,y)
0	0	0	0	1	1	1	0	0
0	0	1	1	0	1	1	0	0
0	1	0	1	1	0	1	0	0
0	1	1	1	1	1	1	1	1
1	0	0	1	1	1	0	0	0
1	0	1	1	1	1	1	1	1
1	1	0	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1

ci	x	y	m₀	m₁	m₂	m₄	NOR	co(ci,x,y)
0	0	0	1	0	0	0	0	0
0	0	1	0	1	0	0	0	0
0	1	0	0	0	1	0	0	0
0	1	1	0	0	0	0	1	1
1	0	0	0	0	0	1	0	0
1	0	1	0	0	0	0	1	1
1	1	0	0	0	0	0	1	1
1	1	1	0	0	0	0	1	1

Projetos de trade-offs considerados em complemento às formas canônicas

Pode-se supor que o trabalho de projetar um somador está concluída, mas ainda não abordamos o fato de que as 3 variáveis de entrada têm que aparecer em sua forma direta ou complementar. Não há nenhuma dificuldade sobre adicionar x e y até o momento, porque eles são estáticos durante a adição e, portanto, são normalmente utilizados em circuitos que têm casualmente saídas tanto em forma direta, quanto na complementar. (O mais simples circuito "Latch" feito de portas NOR é um par de portas cruzadas com um objetivo de fazer um flip-flop: a saída de cada um é ligada por fio como uma das entradas dos outros). Também não há necessidade de se criar a forma complementar da soma u. No entanto, o "carry out" de uma posição de bit deve ser passado como o carry para o bit da posição seguinte em ambas as formas (direta e complementar). A maneira mais simples para fazer isto é passar co através de uma porta NOR de 1 entrada e com nome de saída co', mas isto adicionaria uma porta de atraso no pior lugar possível, diminuindo a ondulação de todos os outros carry's da direita para a esquerda. Uma porta NOR adicional de 4 entradas formando a forma canônica de co' (o oposto mintermos como co) resolve este problema.

$co'(ci,x,y)$ = AND( $M_{3},M_{5},M_{6},M_{7}$ ) = NOR( $m_{3},m_{5},m_{6},m_{7}$ ).

Tabelas-verdade:

ci	x	y	M₃	M₅	M₆	M₇	And	co'(ci,x,y)
0	0	0	1	1	1	1	1	1
0	0	1	1	1	1	1	1	1
0	1	0	1	1	1	1	1	1
0	1	1	0	1	1	1	0	0
1	0	0	1	1	1	1	1	1
1	0	1	1	0	1	1	0	0
1	1	0	1	1	0	1	0	0
1	1	1	1	1	1	0	0	0

ci	x	y	m₃	m₅	m₆	m₇	NOR	co'(ci,x,y)
0	0	0	0	0	0	0	1	1
0	0	1	0	0	0	0	1	1
0	1	0	0	0	0	0	1	1
0	1	1	1	0	0	0	0	0
1	0	0	0	0	0	0	1	1
1	0	1	0	1	0	0	0	0
1	1	0	0	0	1	0	0	0
1	1	1	0	0	0	1	0	0

O trade-off para manter a velocidade máxima desta forma inclui um custo inesperado (além de ter que usar uma porta maior). Se tivéssemos usado apenas aquela porta de 1 entrada para complementar co, não teria havido nenhum uso para o mintermo e a porta que o gerou poderia ter sido eliminada. Mesmo assim, é ainda um bom negócio.

Contundo nós poderíamos ter implementado as funções exatamente de acordo com suas formas canônicas SdP e PdS , transformando portas NOR para as funções especificadas. Uma porta NOR é usada para fazer uma OR passando a sua saída através de uma porta de 1 entrada NOR; e é usada para fazer uma AND passando por cada uma de suas entradas através de uma NOR de 1 entrada. No entanto, esta abordagem não só aumenta o número de portas usadas, mas também dobra o número de atrasos de processamento de sinais, cortando a velocidade de processamento na metade. Consequentemente, sempre que o desempenho é vital, ir além das formas canônicas e se utilizar de porta NOR é um trabalho que vale a pena.

Planejamento top-down vs. bottom-up

Temos visto até agora como as ferramentas de mintermo/maxtermo podem ser usadas para criar um somador de estágio na forma canônica com a adição de um pouco de álgebra Booleana, custando apenas 2 porta atrasos para cada uma das saídas. Essa é a maneira "top-down"(de cima para baixo) de se construir um circuito digital para esta função, mas é o melhor caminho? A discussão centrou-se em identificar o "mais rápido" como "melhor", e a forma canônica aumentada atende a esse critério de maneira impecável, mas, às vezes, outros fatores predominam. O designer pode ter um objetivo principal de minimizar o número de portas, e/ou minimizar as divisões de sinais para as outras portas, já que grandes divisões reduzem a resiliência da degradação da fonte de alimentação, entre outros fatores ambientais. Em tal caso, o designer deve desenvolver a forma canônica de planejamento como base, e, em seguida, tentar um desenvolvimento "bottom-up"(de baixo para cima), e, finalmente, comparar os resultados.

O desenvolvimento bottom-up envolve perceber que u = ci XOR (x XOR y), onde XOR significa OU exclusivo [true quando uma entrada é verdade, mas não quando ambas são verdadeiras], e que co = ci x + x y + y ci. Um tal desenvolvimento leva doze portas NOR: seis de 2 entradas e duas de 1 entrada para produzir u em 5 atrasos de portas, além de três de 2 entradas e um de 3 entradas para produzir co' em 2 portas de atraso. A linha canônica de base levou oito portas NOR de 3 entradas, além de três de 4 entradas para produzir u, co e co' em 2 portas de atraso. Se o circuito de inventário, na verdade, inclui portas de 4 entradas NOR, o projeto top-down canônico parece um vencedor nos quesitos quantidade de portas e velocidade. Mas se (ao contrário de nossa suposição conveniente) os circuitos são, na verdade, de 3 entradas em portas NOR, das quais duas são necessárias para cada função NOR de 4 entradas, então, o projeto canônico tem 14 portas em comparação a 12 para a abordagem bottom-up, mas ainda produz a soma de dígitos u consideravelmente mais rápido. O fan-out de comparação é tabulado com:

Variáveis	De cima para baixo	De baixo para cima
x	4	1
x'	4	3
y	4	1
y'	4	3
ci	4	1
ci'	4	3
M ou m	4@1,4@2	N/A
x XOR y	N/A	2
Diversos	N/A	5@1
Max.	4	3

Qual a melhor opção a se fazer? Um atento terá notado que a descrição do desenvolvimento bottom-up menciona co' como uma saída, mas não co. Será que o projeto simplesmente nunca precisará da forma direta do "carry out"? Bem, sim e não. Em cada fase, o cálculo de co' só depende de ci', x' e y', o que significa que a propagação de ondas de "carry" ao longo das posições dos bits é tão rápido como no projeto canônico sem nunca produzir a saída co. O cálculo de u, o que requer ci a ser feita a partir de ci' por uma NOR de 1 entrada, é mais lento, mas, para qualquer comprimento de palavra, o projeto paga a penalidade apenas uma vez (quando o bit mais à esquerda da soma é desenvolvido). Isso porque os cálculos se sobrepõem, onde cada um se amontoa em seu próprio "encanamento" sem afetar sobre o momento quando a próxima posição do bit da soma de bits pode ser calculado. E, com certeza, o co' do bit mais à esquerda provavelmente terá de ser complementado como parte da lógica de determinar se a adição gerou um "overflow" ou não. Mas usando portas NOR de 3 entradas,o projeto bottom-up é quase tão rápido para fazer adição paralela em um comprimento de palavra não-trivial, reduz a contagem de portas, e usa menores fanouts ... então ele ganha se a contagem de portas e/ou fanout são fundamentais!

Vamos deixar o circuito exato do projeto bottom-up no qual todas estas afirmações são verdadeiras, como um exercício para o leitor interessado, assistido por mais uma fórmula algébrica u = ci(x XOR y) + ci'(x XOR y)']'. Dissociar a propagação do carry na formação da soma desta forma é o que eleva o desempenho de um carry "precoupado com o futuro", quando comparado ao carry ondulatório adder.

Para ver como as portas lógicas NOR foram utilizadas na Apollo Guidance Computer's ALU, visite: http://klabs.org/history/ech/agc_schematics/index.htm, selecione qualquer um dos MÓDULOS 4 BITS de entradas no Índice e expanda as imagens como desejar.

Veja também

Rodapé

↑ Hall, Eldon C. (1996). Journey to the Moon: The History of the Apollo Guidance Computer. [S.l.]: AIAA. ISBN 1-56347-185-X

Referências

Bender, Edward A.; Williamson, S. Gill (2005). A Short Course in Discrete Mathematics. Mineola, NY: Dover Publications, Inc: Dover Publication. ISBN 0-486-43946-1
McCluskey, E. J. (1965). Introduction to the Theory of Switching Circuits. NY: McGraw: Hill Book Company. 78 páginas. LCCN 65-17394
Hill, Fredrick J.; Peterson, Gerald R. (1974). Introduction to Switching Theory and Logical Design (2nd ed.). NY: John Wiley & Sons. 101 páginas. ISBN 0-471-39882-9

Ligações externas

Boole, George. «"The Calculus of Logic"». Cambridge and Dublin Mathematical Journal. III: 183—198

[1] Hall, Eldon C. (1996). Journey to the Moon: The History of the Apollo Guidance Computer. [S.l.]: AIAA. ISBN 1-56347-185-X

[1]