Forma normal canônica

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.

Para uma função booleana de n {\displaystyle n} variáveis x 1 , … , x n {\textstyle {\displaystyle {x_{1},\dots ,x_{n}}}} , um produto de termos em que cada uma das n {\displaystyle 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, a b c {\displaystyle abc} , a b ′ c {\displaystyle ab'c} e a b c ′ {\displaystyle abc'} são 3 exemplos dos 8 mintermos para uma função Booleana de três variáveis a {\displaystyle a} , b {\displaystyle b} e c {\displaystyle c} . 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.

Para uma função booleana de n {\displaystyle n} variáveis x 1 , … , x n {\textstyle {\displaystyle {x_{1},\dots ,x_{n}}}} {\displaystyle } , uma soma de termos em que cada uma das n {\displaystyle 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: 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.

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 ′ = ( a b ′ c ) ′ = m 5 ′ {\displaystyle M_{5}=a'+b+c'=(ab'c)'=m_{5}'}

É 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: tem a representação do mintermo canônico: f = a ′ b c + a b c {\displaystyle {\displaystyle f=a'bc+abc}} , mas este tem um equivalente em forma simplificada: f = b c {\displaystyle {\displaystyle f=bc}} . Neste exemplo trivial, é óbvio que b c = a ′ b c + a b c {\displaystyle {\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.

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.