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 ∈ { 0 , 1 } {\displaystyle X,Y\in \{0,1\}} e as operações em { 0 , 1 } {\displaystyle \{0,1\}} sendo + , ⋅ {\displaystyle +,\cdot } e ¯ , {\displaystyle {\overline {\ }},} assim definidas:
Operação lógica Símbolo Exemplos OU + 0 + 0 = 0 {\displaystyle 0+0=0} 0 + 1 = 1 {\displaystyle 0+1=1} 1 + 0 = 1 {\displaystyle 1+0=1} 1 + 1 = 1 {\displaystyle 1+1=1} E ⋅ {\displaystyle \cdot } 0 ⋅ 0 = 0 {\displaystyle 0\cdot 0=0} 0 ⋅ 1 = 0 {\displaystyle 0\cdot 1=0} 1 ⋅ 0 = 0 {\displaystyle 1\cdot 0=0} 1 ⋅ 1 = 1 {\displaystyle 1\cdot 1=1} Não ¯ {\displaystyle {\overline {\ }}} 0 ¯ = 1 {\displaystyle {\overline {0}}=1} 1 ¯ = 0 {\displaystyle {\overline {1}}=0}
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:
¬ ( X ∧ Y ) ↔ ( ¬ X ) ∨ ( ¬ Y ) {\displaystyle \lnot (X\land Y)\leftrightarrow (\lnot X)\lor (\lnot Y)} X ∪ Y ¯ ↔ X ¯ ∩ Y ¯ . {\displaystyle {\overline {X\cup Y}}\leftrightarrow {\overline {X}}\cap {\overline {Y}}.} X ∩ Y ¯ ↔ X ¯ ∪ Y ¯ {\displaystyle {\overline {X\cap Y}}\leftrightarrow {\overline {X}}\cup {\overline {Y}}} X ⋅ Y ¯ = X ¯ + Y ¯ {\displaystyle {\overline {X\cdot Y}}={\overline {X}}+{\overline {Y}}} X + Y ¯ = X ¯ ⋅ Y ¯ {\displaystyle {\overline {X+Y}}={\overline {X}}\cdot {\overline {Y}}} O complemento, ou negação de um produto (AND ) de variáveis é igual a soma(OR ) dos complementos das variáveis.[ 1] 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 X ⋅ Y ¯ {\displaystyle {\overline {X\cdot Y}}} X ¯ + 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.
1.2 Teorema X Y X + Y ¯ {\displaystyle {\overline {X+Y}}} 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]
A + B + C ¯ ¯ = X {\displaystyle {\overline {A+B+{\overline {C}}}}=X}
Aplicando os teoremas de De Morgan :
A ¯ ⋅ B ¯ ⋅ C ¯ ¯ = X {\displaystyle {\overline {A}}\cdot {\overline {B}}\cdot {\overline {\overline {C}}}=X}
A ¯ ⋅ B ¯ ⋅ C = X {\displaystyle {\overline {A}}\cdot {\overline {B}}\cdot C=X}
Não (X E Y) = Não (X) Ou Não (Y) Não (X Ou Y) = Não (X) E Não (Y) 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:
X + Y + Z ¯ = X ¯ ⋅ Y ¯ ⋅ Z ¯ {\displaystyle {\overline {X+Y+Z}}={\overline {X}}\cdot {\overline {Y}}\cdot {\overline {Z}}}
X ⋅ Y ⋅ Z ¯ = X ¯ + Y ¯ + Z ¯ {\displaystyle {\overline {X\cdot Y\cdot Z}}={\overline {X}}+{\overline {Y}}+{\overline {Z}}}
No caso geral, dado X um conjunto qualquer, temos [ 3] :
X ∖ ⋃ i ∈ I A i = ⋂ i ∈ I ( X ∖ A i ) {\displaystyle X\backslash \bigcup \limits _{i\in I}A_{i}=\bigcap \limits _{i\in I}(X\backslash A_{i})}
X ∖ ⋂ i ∈ I A i = ⋃ i ∈ I ( X ∖ A i ) {\displaystyle X\backslash \bigcap \limits _{i\in I}A_{i}=\bigcup \limits _{i\in I}(X\backslash A_{i})}
Se de fato X + Y + Z ¯ = X ¯ ⋅ Y ¯ ⋅ Z ¯ , {\displaystyle {\overline {X+Y+Z}}={\overline {X}}\cdot {\overline {Y}}\cdot {\overline {Z}},} então:
( X + Y + Z ) + ( X ¯ ⋅ Y ¯ ⋅ Z ¯ ) = 1 {\displaystyle (X+Y+Z)+({\overline {X}}\cdot {\overline {Y}}\cdot {\overline {Z}})=1} ( X + Y + Z ) ⋅ ( X ¯ ⋅ Y ¯ ⋅ Z ¯ ) = 0 {\displaystyle (X+Y+Z)\cdot ({\overline {X}}\cdot {\overline {Y}}\cdot {\overline {Z}})=0} a) ( X + Y + Z ) + ( X ¯ ⋅ Y ¯ ⋅ Z ¯ ) = ( X + Y + Z + X ¯ ) ⋅ ( X + Y + Z + Y ¯ ) ⋅ ( X + Y + Z + Z ¯ ) = {\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}})=} = ( Y + Z + 1 ) ⋅ ( X + Z + 1 ) ⋅ ( X + Y + 1 ) = 1 ⋅ 1 ⋅ 1 = 1 {\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 X + X ¯ = 1. {\displaystyle X+{\overline {X}}=1.}
b) ( X + Y + Z ) ⋅ ( X ¯ ⋅ Y ¯ ⋅ Z ¯ ) = X ⋅ X ¯ ⋅ Y ¯ ⋅ Z ¯ + Y ⋅ X ¯ ⋅ Y ¯ ⋅ Z ¯ + Z ⋅ X ¯ ⋅ Y ¯ ⋅ Z ¯ = 0 + 0 + 0 = 0 {\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 X ⋅ X ¯ = 0 {\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 .
Referências ↑ a b FLOYD, Thomas L.; Sistemas digitais: Fundamentos e aplicação, 9ª ed, página 250, Bookman, 2007, Porto Alegre ↑ 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. ↑ MUJICA, Jorge; Notas de Topologia Geral