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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

É 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[editar | editar código-fonte]

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[editar | editar código-fonte]

É 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 [editar | editar código-fonte]

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[editar | editar código-fonte]

Rodapé[editar | editar código-fonte]

↑ 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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]