Um famoso matemático De Morgan inventou os dois teoremas mais importantes da álgebra booleana. Os teoremas de DeMorgan são usados para verificação matemática da equivalência das portas NOR e AND negativo e das portas OR negativo e NAND. Esses teoremas desempenham um papel importante na resolução de várias expressões de álgebra booleana. Na tabela abaixo, é definida a operação lógica para cada combinação da variável de entrada.
Variáveis de entrada | Condição de saída | ||||
---|---|---|---|---|---|
A | B | E | NAND | OU | NEM |
0 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 1 | 0 |
As regras do teorema de De-Morgan são produzidas a partir das expressões booleanas para OR , AND e NOT usando duas variáveis de entrada x e y. O primeiro teorema de Demorgan diz que se realizarmos a operação AND de duas variáveis de entrada e depois realizarmos a operação NOT do resultado, o resultado será igual à operação OR do complemento daquela variável. O segundo teorema de DeMorgan diz que se realizarmos a operação OR de duas variáveis de entrada e depois realizarmos a operação NÃO operação do resultado, o resultado será igual à operação AND do complemento dessa variável.
Primeiro Teorema de De-Morgan
De acordo com o primeiro teorema, o resultado complementar da operação AND é igual à operação OR do complemento daquela variável. Assim, é equivalente à função NAND e é uma função OR negativa provando que (A.B)' = A'+B' e podemos mostrar isso usando a tabela a seguir.
Entradas | Saída para cada termo | |||||
---|---|---|---|---|---|---|
A | B | AB | (AB)' | A' | B' | A'A+B' |
0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 0 | 0 |
Segundo Teorema de De-Morgan
De acordo com o segundo teorema, o resultado complementar da operação OR é igual à operação AND do complemento daquela variável. Assim, é equivalente à função NOR e é uma função AND negativa provando que (A+B)' = A'.B' e podemos mostrar isso usando a seguinte tabela verdade.
Entradas | Saída para cada termo | |||||
---|---|---|---|---|---|---|
A | B | A+B | (A+B)' | A' | B' | A'.B' |
0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 0 | 0 | 0 |
Tomemos alguns exemplos nos quais pegamos algumas expressões e aplicamos os teoremas de DeMorgan.
Exemplo 1: (A.B.C)'
(A.B.C)'=A'+B'+C'
Exemplo 2: (A+B+C)'
(A+B+C)'=A'.B'.C
Exemplo 3: ((A+BC')'+D(E+F')')'
Para aplicar o teorema de DeMorgan nesta expressão, temos que seguir as seguintes expressões:
1) Na expressão completa, primeiro encontramos os termos aos quais podemos aplicar o teorema de DeMorgan e tratar cada termo como uma única variável.
Então,
2) A seguir aplicamos o primeiro teorema de DeMorgan. Então,
3) A seguir, usamos a regra número 9, ou seja, (A=(A')') para cancelar as barras duplas.
4) A seguir aplicamos o segundo teorema de DeMorgan. Então,
5) Aplique novamente a regra número 9 para cancelar a barra dupla
Ora, esta expressão não tem termo ao qual possamos aplicar qualquer regra ou teorema. Então, esta é a expressão final.
Exemplo 3: (AB'.(A + C))'+ A'B.(A + B + C')'
como inventou a escola