Teoremas de De Morgan

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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  X, Y \in \{0, 1\} e as operações em \{0, 1\} sendo  +, \cdot e \overline{\ } , assim definidas:

Operação lógica Símbolo Exemplos
OU + 0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
E \cdot  0 \cdot 0 = 0
0 \cdot 1 = 0
1 \cdot 0 = 0
1 \cdot 1 = 1
Não  \overline{\ }  \overline{0} = 1
\overline{1} = 0

As leis[editar | editar código-fonte]

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[editar | editar código-fonte]

  1. \lnot(X \land Y) \leftrightarrow (\lnot X)\lor (\lnot Y)

Lógica booleana[editar | editar código-fonte]

  1. \overline{X \cup Y}\leftrightarrow\overline{X} \cap \overline{Y}.
  2. \overline{X \cap Y}\leftrightarrow\overline{X} \cup \overline{Y}

Lógica booleana na eletrônica digital[editar | editar código-fonte]

  1. \overline{X \cdot Y}=\overline{X}+\overline{Y}
  2. \overline{X+Y}=\overline{X}\cdot\overline{Y}
  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 \overline{X \cdot Y} \overline{X} + \overline{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 \overline{X+Y} \overline{X} \cdot \overline{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]

\overline{A+B+\overline{C}}=X

Aplicando os teoremas de De Morgan:

\overline{A} \cdot \overline{B} \cdot \overline{ \overline{C} } = X

\overline{A} \cdot \overline{B} \cdot C  = X

Textual[editar | editar código-fonte]

  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:

\overline{X+Y+Z}=\overline{X}\cdot\overline{Y}\cdot\overline{Z}

\overline{X \cdot Y \cdot Z}=\overline{X}+\overline{Y}+\overline{Z}

Prova[editar | editar código-fonte]

Se de fato  \overline{X+Y+Z}=\overline{X}\cdot\overline{Y}\cdot\overline{Z}, então:

  1. (X+Y+Z)+(\overline{X}\cdot\overline{Y}\cdot\overline{Z}) = 1
  2. (X+Y+Z)\cdot(\overline{X}\cdot\overline{Y}\cdot\overline{Z}) = 0

a)  (X + Y + Z) + (\overline{X}\cdot\overline{Y}\cdot\overline{Z})=(X + Y + Z + \overline{X})\cdot(X + Y + Z + \overline{Y})\cdot(X + Y + Z + \overline{Z}) =  = (Y + Z + 1)\cdot(X + Z + 1)\cdot(X + Y + 1)= 1\cdot1\cdot1 = 1

primeiro usamos a propriedade distributiva do operador +, depois a propriedade comutativo (passo não mostrado), então vemos a soma de elementos complementares X + \overline{X} = 1.

b)  (X+Y+Z)\cdot(\overline{X}\cdot\overline{Y}\cdot\overline{Z}) = X\cdot\overline{X}\cdot\overline{Y}\cdot\overline{Z} + Y\cdot\overline{X}\cdot\overline{Y}\cdot\overline{Z} + Z\cdot\overline{X}\cdot\overline{Y}\cdot\overline{Z} = 0 + 0 + 0 = 0

Primeiro usamos a propriedade distributiva do operador \cdot, depois usamos a propriedade de comutatividade (esse passo não foi mostrado), então usamos a propriedade de elementos complementares X\cdot\overline{X} = 0

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.

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.