Ver o código fonte de «Leis de De Morgan»

[[Ficheiro:Demorganlaws.svg|miniatura| Leis de De Morgan representadas con [[Diagrama de Venn|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''',<ref>{{Cita libro |last1=Copi |first1=Irving M. |url=https://www.taylorfrancis.com/books/mono/10.4324/9781315510897/introduction-logic-irving-copi-carl-cohen-kenneth-mcmahon |title=Introduction to Logic |last2=Cohen |first2=Carl |last3=McMahon |first3=Kenneth |date=2016 |doi=10.4324/9781315510897|isbn=9781315510880 }}</ref><ref>{{cita libro|first=Patrick J.|last=Hurley|title=A Concise Introduction to Logic|edition=12th|publisher=Cengage Learning|year=2015|isbn=978-1-285-19654-1}}</ref><ref>{{Cita libro|last=Moore |first=Brooke Noel |url=https://www.worldcat.org/oclc/689858599 |title=Critical thinking |date=2012 |publisher=McGraw-Hill |others=Richard Parker |isbn=978-0-07-803828-0 |edition=10th |location=New York |oclc=689858599}}</ref> tamén coñecidas como '''teorema de De Morgan''',<ref>[http://hyperphysics.phy-astr.gsu.edu/hbase/Electronic/DeMorgan.html DeMorgan's &#91;sic&#93; Theorem]</ref> son un par de regras de transformación que son [[Regra de inferencia|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ón lóxica|conxuncións]] e [[Disxunción lóxica|disxuncións]] unicamente en termos entre si mediante a [[Negación (lóxica)|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 (conxuntos)|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" é "[[Disxunción lóxica|ou inclusivo]]" que significa ''polo menos'' un de A ou B en lugar de "[[OR exclusivo|ou exclusivo]]" que significa ''exactamente'' un de A ou B.
[[Ficheiro:De_Morgan's_law_with_set_subtraction_operation.png|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.

: <math>A -(B \cup C) = (A - B) \cap (A - C),</math>
: <math>A -(B \cap C) = (A - B) \cup (A - C).</math>

A aplicación destas regras inclúen a simplificación de [[Expresión (informática)|expresións]] lóxicas en [[Programa informático|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áticas)|dualidade matemática]].

== Notación formal ==
A regra ''de negación da conxunción'' pódese escribir en notación de [[Consecuencia lóxica|consecuentes]]:

: <math>\begin{align}
\neg(P \land Q) &\vdash (\neg P \lor \neg Q). \\
(\neg P \lor \neg Q) &\vdash \neg(P \land Q).
\end{align}</math>

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

: <math>\begin{align}
\neg(P \lor Q) &\vdash (\neg P \land \neg Q). \\
(\neg P \land \neg Q) &\vdash \neg(P \lor Q).
\end{align}</math>

En [[Regra de inferencia|forma de regra]]: ''negación da conxunción''<div style="margin-left: 2em">
<math>
\frac{\neg (P \land Q)}{\therefore \neg P \lor \neg Q}
\qquad
\frac{\neg P \lor \neg Q}{\therefore \neg (P \land Q)}
</math>
</div>e ''negación da disxunción''<div style="margin-left: 2em">
<math>
\frac{\neg (P \lor Q)}{\therefore \neg P \land \neg Q}
\qquad
\frac{\neg P \land \neg Q}{\therefore \neg (P \lor Q)}
</math>
</div>e exprésase como [[Tautoloxía (lóxica)|tautoloxías]] ou [[Teorema|teoremas]] de lóxica proposicional de funcións de verdade:

: <math>\begin{align}
 \neg (P \land Q) &\leftrightarrow (\neg P \lor \neg Q), \\
  \neg (P \lor Q) &\leftrightarrow (\neg P \land \neg Q). \\
\end{align}</math>

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

: <math>\begin{align}
\lnot(P_1 \land P_2 \land \dots \land P_n) \leftrightarrow \lnot P_1 \lor \lnot P_2 \lor \ldots \lor \lnot P_n \\
\lnot(P_1 \lor P_2 \lor \dots \lor P_n) \leftrightarrow \lnot P_1 \land \lnot P_2 \land \ldots \land \lnot P_n
\end{align}</math>

=== 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:

: <math>\begin{align}
(P \land Q) &\Longleftrightarrow \neg (\neg P \lor \neg Q), \\
(P \lor Q) &\Longleftrightarrow \neg (\neg P \land \neg Q).
\end{align}</math>

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",<ref name="r l goodstein">''Boolean Algebra'' by R. L. Goodstein. {{ISBN|0-486-45894-6}}</ref> que se pode expresar formalmente como:

: <math>\begin{align}
 \overline{A \cup B} &= \overline{A} \cap \overline{B}, \\
 \overline{A \cap B} &= \overline{A} \cup \overline{B},
\end{align}</math>

onde:

* <math>\overline{A}</math> é a negación de <math>A</math>, escribindo a liña superior enriba dos termos que se van negar,
* <math>\cap</math> é o operador [[Intersección (conxuntos)|de intersección]] (AND),
* <math>\cup</math> é o operador [[Unión (conxuntos)|únión]] (OR).

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

: <math>\begin{align}
 \overline{A \land B} &= \overline{A} \lor \overline{B}, \\
 \overline{A \lor B} &= \overline{A} \land \overline{B},
\end{align}</math>

onde:

* <math>\overline{A}</math> é a negación de <math>A</math>, escribindo a liña superior enriba dos termos que se van negar,
* <math>\land</math> é o operador [[Conxunción lóxica|de conxunción lóxica]] (AND),
* <math>\lor</math> é o operador [[Disxunción lóxica|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:

: <math>\overline{(A \cdot B)} \equiv (\overline {A} + \overline {B})</math>

: <math>\overline{(A + B)} \equiv (\overline {A} \cdot \overline {B}),</math>

onde:

* <math> \cdot </math> é o AND lóxico,
* <math>+</math> é o OR lóxico,
* a {{Overline|liña superior}} é 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 ==
{{reflist|30em}} 

== Véxase tamén ==

=== Bibliografía ===

=== Outros artigos ===
* [[Táboa de verdade]].
=== Ligazóns externas ===
* {{springer|title=Duality principle|id=p/d034130}}
* {{MathWorld | urlname=deMorgansLaws | title=de Morgan's Laws}}
* {{PlanetMath | urlname=DeMorgansLaws | title=de Morgan's laws | id=2308}}
* [http://www.iep.utm.edu/dual-log/  Duality in Logic and Language], ''Internet Encyclopedia of Philosophy''.

{{control de autoridades}}

[[Categoría:Lóxica]]
[[Categoría:Lóxica matemática]]
[[Categoría:Teorema]]