Como vimos anteriormente, a Álgebra Booleana usa um conjunto de leis e regras para definir o funcionamento de um circuito lógico digital com “0’s” e “1’s” a serem usados para representar uma condição de entrada ou saída digital. A Álgebra Booleana usa estes zeros e uns para criar tabelas de verdade e expressões matemáticas para definir a operação digital de uma lógica AND, OR e NOT (ou inversão), bem como formas de expressar outras operações lógicas como a função XOR (Exclusive-OR).
Enquanto o conjunto de leis e regras de George Boole nos permite analisar e simplificar um circuito digital, há duas leis dentro do seu conjunto que são atribuídas a Augustus DeMorgan (um matemático inglês do século XIX) que vê as operações lógicas NAND e NOR como funções separadas NOT E, OR e NOT OR, respectivamente.
Mas antes de analisarmos a Teoria de DeMorgan com mais detalhe, lembremo-nos das operações lógicas básicas onde A e B são variáveis binárias de entrada lógica (ou Booleana), e cujos valores só podem ser “0” ou “1” produzindo quatro combinações de entrada possíveis, 00, 01, 10, e 11.
Tabela da verdade para cada operação lógica
| Input Variable | Output Conditions | ||||||
| A | B | AND | NAND | OR | NOR | ||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | |
| 1 | 1 | 1 | 0 | 1 | 0 | ||
A tabela seguinte dá uma lista das funções lógicas comuns e a sua notação booleana equivalente onde a “.” (um ponto) significa uma operação AND (produto), um “+” (sinal de adição) significa uma operação OR (soma), e o complemento ou inverso de uma variável é indicado por uma barra sobre a variável.
| Função Lógica | Notação Booleana |
| AND>/td> | A.B |
| OR | A+B |
| NOT>/td> | A |
| NAND | A .B |
| NOR | A+B |
TeoriaDeMorgan
TeoriasDeMorgan são basicamente dois conjuntos de regras ou leis desenvolvidas a partir das expressões booleanas para AND, OU e NÃO utilizando duas variáveis de entrada, A e B. Estas duas regras ou teoremas permitem que as variáveis de entrada sejam negadas e convertidas de uma forma de uma função booleana para uma forma oposta.
O primeiro teorema de DeMorgan afirma que duas (ou mais) variáveis NOR’ed juntas é o mesmo que as duas variáveis invertidas (Complemento) e AND’ed, enquanto o segundo teorema afirma que duas (ou mais) variáveis NAND’ed juntas é o mesmo que os dois termos invertidos (Complemento) e OR’ed. Isto é, substituir todos os operadores OR por operadores AND, ou todos os operadores AND por um operador OR.
Primeiro TeoremaDeMorgan
Primeiro TeoremaDeMorgan prova que quando duas (ou mais) variáveis de entrada são AND’ed e negadas, elas são equivalentes ao OR dos complementos das variáveis individuais. Assim, o equivalente da função NAND será uma função NAND negativa-OR, provando que A.B = A+B. Podemos mostrar esta operação utilizando a seguinte tabela.
Verificando o Primeiro Teorema de DeMorgan usando a Tabela da Verdade
| Inputs | Saídas da tabela de verdade para cada termo | ||||||
| B | A | A.B | A.B | A | B | A + B | |
| 1 | 1 | 1 | 1 | ||||
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | |
Podemos também mostrar que A.B = A+B usando portas lógicas como mostrado.
DeMorgan’s First Law Implementation using Logic Gates
O arranjo da primeira porta lógica do DeMorgan: A.B pode ser implementado utilizando uma porta NAND padrão com entradas A e B. A disposição da porta lógica inferior inverte primeiro as duas entradas que produzem A e B. Estas passam então a ser as entradas para a porta OR. Portanto, a saída do portão OR torna-se: A+B
Então podemos ver aqui que uma função padrão da porta OU com inversores (NÃO portas) em cada uma das suas entradas é equivalente a uma função da porta NAND. Assim, uma porta NAND individual pode ser representada desta forma como a equivalência de uma porta NAND é um teorema negativo-OR.
Segundo TeoremaDeMorgan
Segundo TeoremaDeMorgan prova que quando duas (ou mais) variáveis de entrada são OR’ed e negadas, elas são equivalentes ao AND dos complementos das variáveis individuais. Assim, o equivalente da função NOR é uma função NOR negativa-AND provando que A+B = A.B, e mais uma vez podemos mostrar a operação usando a seguinte tabela de verdade.
Verificando o Segundo Teorema de DeMorgan usando a Tabela de Verdade
| Inputs | Saídas da Tabela de Verdade Para Cada Termo | ||||||
| B | A | A+B | A+B | A | B | A . B | |
| 0 | 0 | 1 | 1 | 1 | 1 | ||
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | ||
Podemos também mostrar que A+B = A.B usando o seguinte exemplo de portas lógicas.
A Segunda Implementação da LeiDeMorgan usando as Portas Lógicas
O arranjo da porta lógica superior de: A+B pode ser implementada usando uma função de porta NOR padrão usando entradas A e B. A disposição da porta lógica inferior inverte primeiro as duas entradas, produzindo assim A e B. Assim, tornam-se então as entradas para a porta AND. Assim, a saída do portão AND torna-se: A.B
Então podemos ver que uma função padrão AND com inversores (NÃO portas) em cada uma das suas entradas produz uma condição de saída equivalente a uma função padrão da porta NOR, e uma porta NOR individual pode ser representada desta forma, uma vez que a equivalência de uma porta NOR é uma porta NOR negativa-AND.
P>Embora tenhamos utilizado os teoremas de DeMorgan com apenas duas variáveis de entrada A e B, são igualmente válidos para utilização com três, quatro ou mais expressões de variáveis de entrada, por exemplo:
Para uma entrada com 3 variáveis
A.B.C = A+B+C
e também
A+B+C = A.B.C
Para uma entrada de 4 variáveis
A.B.C.D = A+B+C+D
e também
A+B+C+D = A.A.C.D.D
e assim por diante.
Portas Equivalentes de DeMorgan
Vimos aqui que usando os Teoremas de DeMorgan podemos substituir todos os operadores AND (.) por um OR (+) e vice-versa, e depois complementar cada um dos termos ou variáveis na expressão invertendo-a, ou seja, 0’s para 1’s e 1’s para 0’s antes de inverter toda a função.
Assim, para obter o equivalente DeMorgan para uma porta AND, NAND, OR ou NOR, simplesmente adicionamos inversores (NOT-gates) a todas as entradas e saídas e alteramos um símbolo AND para um símbolo OR ou alteramos um símbolo OR para um símbolo AND, como se mostra na tabela seguinte.
DeMorgan’s Equivalent Gates
| Standard Logic Gate | DeMorgan’s Equivalent Gate |
 |
|
 |
|
 |
|
> demorgans negativo-e gate |
e símbolo da porta
Então vimos neste tutorial sobre a Thereom do DeMorgan que o complemento de duas (ou mais) variáveis de entrada AND’ed é equivalente ao OR dos complementos destas variáveis, e que o complemento de duas (ou mais) variáveis OR’ed é equivalente ao AND dos complementos das variáveis tal como definidas por DeMorgan.
