Teoremas de De Morgan

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

1. ${\displaystyle \lnot (X\land Y)\leftrightarrow (\lnot X)\lor (\lnot Y)}$

Lógica booleana

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

Lógica booleana na eletrônica digital

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

X	Y	${\displaystyle {\overline {X\cdot Y}}}$	${\displaystyle {\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.

X	Y	${\displaystyle {\overline {X+Y}}}$	${\displaystyle {\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]

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

Aplicando os teoremas de De Morgan:

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

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

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:

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

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

No caso geral, dado X um conjunto qualquer, temos ^[3]:

${\displaystyle X\backslash \bigcup \limits _{i\in I}A_{i}=\bigcap \limits _{i\in I}(X\backslash A_{i})}$

${\displaystyle X\backslash \bigcap \limits _{i\in I}A_{i}=\bigcup \limits _{i\in I}(X\backslash A_{i})}$

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

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

a) ${\displaystyle (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}})=}$ ${\displaystyle =(Y+Z+1)\cdot (X+Z+1)\cdot (X+Y+1)=1\cdot 1\cdot 1=1}$

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

b) ${\displaystyle (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 ${\displaystyle \cdot ,}$ depois usamos a propriedade de comutatividade (esse passo não foi mostrado), então usamos a propriedade de elementos complementares ${\displaystyle 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.

• O Teorema de De Morgan

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

• Portal da matemática