Abrir menu principal

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.

Sendo e as operações em sendo e assim definidas:

Operação lógica Símbolo Exemplos
OU +


E


Não

As leisEditar

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:

Lógica proposicionalEditar

  1.  

Lógica booleanaEditar

  1.  
  2.  

Lógica booleana na eletrônica digitalEditar

  1.  
  2.  
  3. O complemento, ou negação de um produto (AND) de variáveis é igual a soma(OR) dos complementos das variáveis.[1]
  4. 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.

 
1.1 Teorema
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.

 
1.2 Teorema
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:

 

 

TextualEditar

  1. Não (X E Y) = Não (X) Ou Não (Y)
  2. Não (X Ou Y) = Não (X) E Não (Y)

GeneralizaçãoEditar

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]:

 

 


ProvaEditar

Se de fato   então:

  1.  
  2.  

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  

Os teoremas de De Morgan são usados para provar que toda lógica booleana pode ser criada somente com portas lógicas NAND ou NOR.

Referências

  1. a b FLOYD, Thomas L.; Sistemas digitais: Fundamentos e aplicação, 9ª ed, página 250, Bookman, 2007, Porto Alegre
  2. 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.
  3. MUJICA, Jorge; Notas de Topologia Geral

Ligações externasEditar

  Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.