Teoremas de De Morgan

(Redirecionado de Leis De Morgan)

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.