Saltar para o conteúdo

Teoremas de De Morgan

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Leis de 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

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:

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

  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ção

[editar | editar código-fonte]

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


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

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 externas

[editar | editar código-fonte]
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.