miniatura| Leis de De Morgan representadas con diagramas de Venn. En cada caso, o conxunto resultante é o conxunto de todos os puntos en calquera ton de azul. 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