Os teoremas do matemático De Morgan são propostas de simplificação de expressões em álgebra booleana de grande contribuição. Definem regras usadas para converter operações lógicas OU em E e vice versa.
Considere X e Y como variáveis booleanas ou proposições cuja resposta seja {Sim, Não} ou {Verdadeiro, Falso} ou ainda {0,1}. Seguem as leis de De Morgan conforme algumas notações possíveis:
O complemento, ou negação de um produto (AND) de variáveis é igual a soma(OR) dos complementos das variáveis.[1]
O complemento, ou negação de uma soma (OR) de variáveis é igual ao produto (AND) dos complementos das variáveis.[1]
A figura 1.1 mostra o circuito que representa o 1. Teorema e a tabela abaixo representa sua respectiva tabela verdade.
X
Y
0
0
1
1
0
1
1
1
1
0
1
1
1
1
0
0
A figura 1.2 mostra o circuito que representa o 1. Teorema e a tabela abaixo representa sua respectiva tabela verdade.
X
Y
0
0
1
1
0
1
0
0
1
0
0
0
1
1
0
0
Observada a equivalência na saída das tabelas, isto prova o mesmo comportamento lógico.
Considere a seguinte expressão:[2]
Aplicando os teoremas de De Morgan:
Textual
Não (X E Y) = Não (X) OuNão (Y)
Não (X Ou Y) = Não (X) ENão (Y)
Generalização
A ideia é que ao "aplicar" a barra (operador Não) sobre uma outra operação, esta muda seu sinal, restando uma barra para cada membro da operação. Exemplos:
No caso geral, dado X um conjunto qualquer, temos [3]:
Prova
Se de fato então:
a)
primeiro usamos a propriedade distributiva do operador depois a propriedade comutativo (passo não mostrado), então vemos a soma de elementos complementares
b)
Primeiro usamos a propriedade distributiva do operador depois usamos a propriedade de comutatividade (esse passo não foi mostrado), então usamos a propriedade de elementos complementares
↑ abFLOYD, Thomas L.; Sistemas digitais: Fundamentos e aplicação, 9ª ed, página 250, Bookman, 2007, Porto Alegre
↑TOCCI, Ronald; Sistemas digitais: princípios e aplicações, Ronald J. Tocci, Neal S. Widmer, Gregory L. Moss, página 65, Pearson Education, São Paulo-SP, 2007.