Leis de De Morgan

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, 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.

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-(B\cup C)=(A-B)\cap (A-C),$

$A-(B\cap C)=(A-B)\cup (A-C).$

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:

$\begin{array}{cc}\mathrm{\neg }(P\wedge Q)& ⊢(\mathrm{\neg }P\vee \mathrm{\neg }Q).\\ (\mathrm{\neg }P\vee \mathrm{\neg }Q)& ⊢\mathrm{\neg }(P\wedge Q).\end{array}$

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

$\begin{array}{cc}\mathrm{\neg }(P\vee Q)& ⊢(\mathrm{\neg }P\wedge \mathrm{\neg }Q).\\ (\mathrm{\neg }P\wedge \mathrm{\neg }Q)& ⊢\mathrm{\neg }(P\vee Q).\end{array}$

En forma de regra: negación da conxunción

$\frac{\mathrm{\neg }(P\wedge Q)}{\therefore \mathrm{\neg }P\vee \mathrm{\neg }Q}\frac{\mathrm{\neg }P\vee \mathrm{\neg }Q}{\therefore \mathrm{\neg }(P\wedge Q)}$

e negación da disxunción

$\frac{\mathrm{\neg }(P\vee Q)}{\therefore \mathrm{\neg }P\wedge \mathrm{\neg }Q}\frac{\mathrm{\neg }P\wedge \mathrm{\neg }Q}{\therefore \mathrm{\neg }(P\vee Q)}$

e exprésase como tautoloxías ou teoremas de lóxica proposicional de funcións de verdade:

$\begin{array}{cc}\mathrm{\neg }(P\wedge Q)& \leftrightarrow (\mathrm{\neg }P\vee \mathrm{\neg }Q),\\ \mathrm{\neg }(P\vee Q)& \leftrightarrow (\mathrm{\neg }P\wedge \mathrm{\neg }Q).\\ \end{array}$

onde $P$ e $Q$ 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 $P_1,P_2,\dots ,P_n$, as leis de De Morgan xeneralizadas son as seguintes:

$\begin{array}{c}\mathrm{\neg }(P_1\wedge P_2\wedge \dots \wedge P_n)\leftrightarrow \mathrm{\neg }{P}_1\vee \mathrm{\neg }{P}_2\vee \dots \vee \mathrm{\neg }{P}_n\\ \mathrm{\neg }(P_1\vee P_2\vee \dots \vee P_n)\leftrightarrow \mathrm{\neg }{P}_1\wedge \mathrm{\neg }{P}_2\wedge \dots \wedge \mathrm{\neg }{P}_n\end{array}$

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:

$\begin{array}{cc}(P\wedge Q)& ⟺\mathrm{\neg }(\mathrm{\neg }P\vee \mathrm{\neg }Q),\\ (P\vee Q)& ⟺\mathrm{\neg }(\mathrm{\neg }P\wedge \mathrm{\neg }Q).\end{array}$

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", que se pode expresar formalmente como:

$\begin{array}{cc}\overline{A\cup B}& =\bar{A}\cap \bar{B},\\ \overline{A\cap B}& =\bar{A}\cup \bar{B},\end{array}$

onde:

• $\bar{A}$ é a negación de $A$, escribindo a liña superior enriba dos termos que se van negar,
• $\cap$ é o operador de intersección (AND),
• $\cup$ é o operador únión (OR).

Álxebra de Boole

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

$\begin{array}{cc}\overline{A\wedge B}& =\bar{A}\vee \bar{B},\\ \overline{A\vee B}& =\bar{A}\wedge \bar{B},\end{array}$

onde:

• $\bar{A}$ é a negación de $A$, escribindo a liña superior enriba dos termos que se van negar,
• $\wedge$ é o operador de conxunción lóxica (AND),
• $\vee$ é 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:

$\overline{(A\cdot B)}\equiv (\bar{A}+\bar{B})$

$\overline{(A+B)}\equiv (\bar{A}\cdot \bar{B}),$

onde:

• $\cdot$ é o AND lóxico,
• $+$ é o OR lóxico,
• a Modelo:Overline é 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).

Véxase tamén

Outros artigos

• Táboa de verdade.

Ligazóns externas

• Modelo:Springer
• Modelo:MathWorld
• Modelo:PlanetMath
• Duality in Logic and Language, Internet Encyclopedia of Philosophy.