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 $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 teoremas

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. $\lnot (X\land Y)\leftrightarrow (\lnot X)\lor (\lnot Y)$

Lógica booleana

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

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.
4. O complemento, ou negação de uma soma (OR) de variáveis é igual ao produto (AND) dos complementos das variáveis.

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:

${\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

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:

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

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

No caso geral, dado X um conjunto qualquer, temos :

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

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

Prova

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\cdot 1\cdot 1=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.

Ligações externas

• O Teorema de De Morgan