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.
Mintermos Para uma função booleana de variáveis , um produto de termos em que cada uma das 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, , e são 3 exemplos dos 8 mintermos para uma função Booleana de três variáveis , e . A leitura costumeira deste último é: a E b E NÃO-c.
Há 2n 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 () e 0 para as formas complementares (); o mintermo é . Por exemplo, o mintermo é associado a 1102 = 610 e denotado .
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: cixyu(ci,x,y)00000011010101101001101011001111 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 e . Se quisermos verificar isso: 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 variáveis , uma soma de termos em que cada uma das 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á 2n 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 e 1 para formas complementares . Por exemplo, podemos atribuir o índice de 6 o maxtermo (110) e denotamo-lo como M6. Da mesma forma M0 de três variáveis é (000) e M7 é (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: cixyco(ci,x,y)00000010010001111000101111011111 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 e . Se quisermos verificar isso: co(ci, x, y) = = (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:
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: abcf(a,b,c)00000010010001111000101011001111 tem a representação do mintermo canônico: , mas este tem um equivalente em forma simplificada:. Neste exemplo trivial, é óbvio que , 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, [], 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 Vcc, 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 Vcc 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 Vcc.
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 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 é,
= AND() = NOR(). Tabelas de verdade: cixyM0M3M5M6ANDu(ci,x,y)000011100001111111010111111011101100100111111101110100110111000111111111 cixym0m3m5m6NORu(ci,x,y)000100000001000011010000011011010000100000011101001000110000100111000011 No maxtermo exemplificado acima, escrevemos mas para realizar isso com porta NOR de 4 entradas nós precisamos observar a igualdade para o NOR dos mesmos mintermos. Que é,
= AND() = NOR(). Tabelas verdade: cixyM0M1M2M4ANDco(ci,x,y)000011100001101100010110100011111111100111000101111111110111111111111111 cixym0m1m2m4NORco(ci,x,y)000100000001010000010001000011000011100000100101000011110000011111000011
Projetos de trade-offs considerados em complemento às formas canônicas