𝖂𝖎ƙ𝖎𝖊

Teoremas 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

As leis

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 proposicional

Lógica booleana

Lógica booleana na eletrônica digital

  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:

Textual

  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

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

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. 1,0 1,1 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

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

talvez você goste