Leis de De Morgan

En lóxica proposicional e álxebra de Boole, as leis de De Morgan, tamén coñecidas como teorema de De Morgan,DeMorgan's [sic] Theorem son un par de regras de transformación que son regras de inferencia válidas. Levan o nome de Augustus De Morgan, un matemático británico do século XIX. As regras permiten a expresión de conxuncións e disxuncións unicamente en termos entre si mediante a negación.

As regras pódense expresar en texto como:

 A negación de "A e B" é o mesmo que "non A ou non B".
 A negación de "A ou B" é o mesmo que "non A e non B".

ou

 O complementario da unión de dous conxuntos é o mesmo que a intersección dos seus complementos
 O complementario da intersección de dous conxuntos é o mesmo que a unión dos seus complementarios

ou

 non (A ou B) = (non A) e (non B)
 non (A e B) = (non A) ou (non B)

onde "A ou B" é "ou inclusivo" que significa polo menos un de A ou B en lugar de "ou exclusivo" que significa exactamente un de A ou B.
miniatura| Lei de De Morgan con operación de resta de conxuntos
Outra forma da lei de De Morgan é a seguinte como se ve a continuación.




A aplicación destas regras inclúen a simplificación de expresións lóxicas en programas informáticos e deseños de circuítos dixitais. As leis de De Morgan son un exemplo dun concepto máis xeral de dualidade matemática.

 Notación formal 
A regra de negación da conxunción pódese escribir en notación de consecuentes:



A regra de negación da disxunción pódese escribir como:



En forma de regra: negación da conxuncióne negación da disxuncióne exprésase como tautoloxías ou teoremas de lóxica proposicional de funcións de verdade:



onde  e  son proposicións expresadas nalgún sistema formal.

As leis xeneralizadas de De Morgan proporcionan unha equivalencia para negar unha conxunción ou disxunción que implica varios termos.Para un conxunto de proposicións , as leis de De Morgan xeneralizadas son as seguintes:



 Forma de substitución 
As leis de De Morgan móstranse normalmente na forma compacta anterior, coa negación da saída á esquerda e a negación das entradas á dereita. Unha forma máis clara para a substitución pódese indicar como:



Isto fai fincapé na necesidade de inverter tanto as entradas como a saída, así como mudar o operador ao facer unha substitución.

 Teoría de conxuntos 
Na teoría de conxuntos, adoita dicirse como "troco de unión e intersección baixo complementación",Boolean Algebra by R. L. Goodstein.  que se pode expresar formalmente como:



onde:

  é a negación de , escribindo a liña superior enriba dos termos que se van negar,
  é o operador de intersección (AND),
  é o operador únión (OR).

 Álxebra de Boole 
Na álxebra de Boole, do mesmo xeito, esta lei  pode expresarse formalmente como:



onde:

  é a negación de , escribindo a liña superior enriba dos termos que se van negar,
  é o operador de conxunción lóxica (AND),
  é o operador de disxunción lóxica (OR).

 Enxeñaría 
En enxeñaría eléctrica e informática, as leis de De Morgan escríbense habitualmente como:





onde:

  é o AND lóxico,
  é o OR lóxico,
 a  é o NOT lóxico do que hai debaixo da barra superior.

 Busca de texto (informática) 
As leis de De Morgan adoitan aplicarse á busca de texto mediante operadores booleanos AND, OR e NOT. Considere un conxunto de documentos que conteñan as palabras "gatos" e "cans". As leis de De Morgan sosteñen que estas dúas procuras devolverán o mesmo conxunto de documentos:

 Busca A: NON (gatos OU cans)
 Busca B: (NON gatos) E (NON cans)

Pódese aplicar unha avaliación similar para mostrar que as dúas buscas seguintes:

 Busca C: NOT (gatos E cans),
 Busca D: (NON gatos) OU (NON cans).
 Notas 


 Véxase tamén 

 Bibliografía 

 Outros artigos 
 Táboa de verdade.
 Ligazóns externas 



  Duality in Logic and Language, Internet Encyclopedia of Philosophy.

Categoría:Lóxica
Categoría:Lóxica matemática
Categoría:Teoremas