Leyes de De Morgan - De Morgan's laws

Leyes de De Morgan representadas con diagramas de Venn . En cada caso, el conjunto resultante es el conjunto de todos los puntos en cualquier tono de azul.

En lógica proposicional y álgebra booleana , las leyes de De Morgan son un par de reglas de transformación que son ambas reglas válidas de inferencia . Llevan el nombre de Augustus De Morgan , un matemático británico del siglo XIX. Las reglas permiten la expresión de conjunciones y disyunciones puramente en términos entre sí a través de la negación .

Las reglas se pueden expresar en inglés como:

la negación de una disyunción es la conjunción de las negaciones
la negación de una conjunción es la disyunción de las negaciones

o

el complemento de la unión de dos conjuntos es el mismo que la intersección de sus complementos
el complemento de la intersección de dos conjuntos es el mismo que la unión de sus complementos

o

no (A o B) = (no A) y (no B)
no (A y B) = (no A) o (no B),

donde "A o B" es un " inclusivo o " que significa al menos uno de A o B en lugar de un " exclusivo o " que significa exactamente uno de A o B.

En teoría de conjuntos y álgebra booleana , estos se escriben formalmente como

{\ Displaystyle {\ begin {alineado} {\ overline {A \ cup B}} & = {\ overline {A}} \ cap {\ overline {B}}, \\ {\ overline {A \ cap B}} & = {\ overline {A}} \ cup {\ overline {B}}, \ end {alineado}}}

dónde

${\ Displaystyle A}$ y son conjuntos, ${\ Displaystyle B}$
${\ Displaystyle {\ overline {A}}}$ es el complemento de , ${\ Displaystyle A}$
${\ Displaystyle \ cap}$ es la intersección , y
${\ Displaystyle \ cup}$ es la unión .

En lenguaje formal , las reglas están escritas como

{\ Displaystyle \ neg (P \ lor Q) \ iff (\ neg P) \ land (\ neg Q),}

y

{\ Displaystyle \ neg (P \ land Q) \ iff (\ neg P) \ lor (\ neg Q)}

dónde

P y Q son proposiciones,
${\ Displaystyle \ neg}$ es el operador lógico de negación (NO),
${\ Displaystyle \ land}$ es el operador lógico de conjunción (Y),
${\ Displaystyle \ lor}$ es el operador lógico de disyunción (OR),
${\ Displaystyle \ iff}$ es un símbolo metalogico que significa "puede ser reemplazado en una prueba lógica con".

Las aplicaciones de las reglas incluyen la simplificación de expresiones lógicas en programas de computadora y diseños de circuitos digitales. Las leyes de De Morgan son un ejemplo de un concepto más general de dualidad matemática .

Notación formal

La regla de negación de conjunción se puede escribir en notación secuencial :

{\ Displaystyle \ neg (P \ land Q) \ vdash (\ neg P \ lor \ neg Q)}

,

y

{\ Displaystyle (\ neg P \ lor \ neg Q) \ vdash \ neg (P \ land Q)}

.

La regla de negación de disyunción se puede escribir como:

{\ Displaystyle \ neg (P \ lor Q) \ vdash (\ neg P \ land \ neg Q)}

,

y

{\ Displaystyle (\ neg P \ land \ neg Q) \ vdash \ neg (P \ lor Q)}

.

En forma de regla : negación de la conjunción

{\ Displaystyle {\ frac {\ neg (P \ land Q)} {\ por lo tanto \ neg P \ lor \ neg Q}}}

{\ Displaystyle {\ frac {\ neg P \ lor \ neg Q} {\ por lo tanto \ neg (P \ land Q)}}}

y negación de la disyunción

{\ Displaystyle {\ frac {\ neg (P \ lor Q)} {\ por lo tanto \ neg P \ land \ neg Q}}}

{\ Displaystyle {\ frac {\ neg P \ land \ neg Q} {\ por lo tanto \ neg (P \ lor Q)}}}

y expresado como una tautología funcional de verdad o teorema de lógica proposicional:

{\ Displaystyle {\ begin {alineado} \ neg (P \ land Q) & \ to (\ neg P \ lor \ neg Q), \\ (\ neg P \ lor \ neg Q) & \ to \ neg (P \ tierra Q), \\\ neg (P \ lor Q) & \ to (\ neg P \ land \ neg Q), \\ (\ neg P \ land \ neg Q) & \ to \ neg (P \ lor Q), \ end {alineado}}}

donde y son proposiciones expresadas en algún sistema formal. ${\ Displaystyle P}$ ${\ displaystyle Q}$

Formulario de sustitución

Las leyes de De Morgan normalmente se muestran en la forma compacta anterior, con la negación de la salida a la izquierda y la negación de las entradas a la derecha. Una forma más clara de sustitución se puede establecer como:

{\ Displaystyle {\ begin {alineado} (P \ land Q) & \ Longleftrightarrow \ neg (\ neg P \ lor \ neg Q), \\ (P \ lor Q) & \ Longleftrightarrow \ neg (\ neg P \ land \ neg Q). \ end {alineado}}}

Esto enfatiza la necesidad de invertir tanto las entradas como la salida, así como cambiar el operador, al hacer una sustitución.

Las leyes tienen una brecha importante con la ( ) ley de la doble negación. , para convertirse en un sistema lógico formal: la secuencia informa de símbolos que se definen bien formados en el primer orden. El mismo sistema tiene esas conjunciones: . Obviamente, es conocimiento válido, entonces hay al menos una conjunción, que - número - en la tabla de verdad, proposición básica de - es igual al contexto de existencia atómica de , por supuesto de acuerdo con el conocimiento. Consideramos la teoría de la equivalencia, la lógica lo hace. En este punto, las leyes de De Morgan muestran un efecto que es hacia arriba o hacia abajo, el contexto atómico de . ${\ Displaystyle \ neg (\ neg p) \ iff p}$ ${\ Displaystyle \ mathbb {L}}$ ${\ Displaystyle \ p, q, r, ...., \ emptyset \ in \ mathbb {L} \}$ ${\ Displaystyle C_ {| j}: x \ | \ x \ en conjunto :: \ {\ land, \ lor, \ iff, \ vdash \}}$ ${\ Displaystyle C_ {| j} = conjunto, \ x \ en C_ {| j}}$ ${\ Displaystyle x}$ ${\ Displaystyle T}$ ${\ Displaystyle x}$ ${\ Displaystyle x}$ ${\ Displaystyle \ forall x: (\ mathbb {L} \ vDash \ forall c \ subsetneq C_ {| j}, \ x \ in c)}$ ${\ Displaystyle x}$

Teoría de conjuntos y álgebra booleana

En la teoría de conjuntos y el álgebra de Boole , a menudo se indica como "intercambio de unión e intersección bajo complementación", que se puede expresar formalmente como:

{\ Displaystyle {\ begin {alineado} {\ overline {A \ cup B}} & = {\ overline {A}} \ cap {\ overline {B}}, \\ {\ overline {A \ cap B}} & = {\ overline {A}} \ cup {\ overline {B}}, \ end {alineado}}}

dónde:

${\ Displaystyle {\ overline {A}}}$ es la negación de la overline ser escrita por encima de los términos a ser negado, ${\ Displaystyle A}$
${\ Displaystyle \ cap}$ es el operador de intersección (Y),
${\ Displaystyle \ cup}$ es el operador de la unión (OR).

Uniones e intersecciones infinitas

La forma generalizada es

{\ Displaystyle {\ begin {alineado} {\ overline {\ bigcap _ {i \ in I} A_ {i}}} & \ equiv \ bigcup _ {i \ in I} {\ overline {A_ {i}}} , \\ {\ overline {\ bigcup _ {i \ in I} A_ {i}}} & \ equiv \ bigcap _ {i \ in I} {\ overline {A_ {i}}}, \ end {alineado} }}

donde $I$ es un conjunto de indexación, posiblemente incontable.

En notación de conjuntos, las leyes de De Morgan se pueden recordar usando el mnemónico "romper la línea, cambiar el signo".

Ingenieria

En ingeniería eléctrica e informática , las leyes de De Morgan se escriben comúnmente como:

{\ Displaystyle {\ overline {A \ cdot B}} \ equiv {\ overline {A}} + {\ overline {B}}}

y

{\ Displaystyle {\ overline {A + B}} \ equiv {\ overline {A}} \ cdot {\ overline {B}},}

dónde:

${\ Displaystyle \ cdot}$ es el Y lógico,
${\ displaystyle +}$ es el OR lógico,
la barra superior es el NO lógico de lo que está debajo de la barra superior.

Búsqueda de texto

Las leyes de De Morgan se aplican comúnmente a la búsqueda de texto utilizando operadores booleanos AND, OR y NOT. Considere un conjunto de documentos que contengan las palabras "automóviles" y "camiones". Las leyes de De Morgan sostienen que estas dos búsquedas devolverán el mismo conjunto de documentos:

Buscar A: NO (automóviles O camiones)

Buscar B: (NO automóviles) Y (NO camiones)

El corpus de documentos que contienen "automóviles" o "camiones" puede estar representado por cuatro documentos:

Documento 1: contiene solo la palabra "coches".

Documento 2: Contiene solo "camiones".

Documento 3: contiene tanto "automóviles" como "camiones".

Documento 4: No contiene ni "automóviles" ni "camiones".

Para evaluar la Búsqueda A, claramente la búsqueda "(automóviles O camiones)" dará en los Documentos 1, 2 y 3. Por lo tanto, la negación de esa búsqueda (que es la Búsqueda A) afectará a todo lo demás, que es el Documento 4.

Al evaluar la Búsqueda B, la búsqueda "(NO automóviles)" dará en los documentos que no contienen "automóviles", que son los Documentos 2 y 4. De manera similar, la búsqueda "(NO camiones)" dará en los Documentos 1 y 4. Aplicando el Y el operador de estas dos búsquedas (que es la Búsqueda B) dará en los documentos que son comunes a estas dos búsquedas, que es el Documento 4.

Se puede aplicar una evaluación similar para mostrar que las dos búsquedas siguientes devolverán el mismo conjunto de documentos (Documentos 1, 2, 4):

Buscar C: NO (automóviles Y camiones),

Buscar D: (NO automóviles) O (NO camiones).

Historia

Las leyes llevan el nombre de Augustus De Morgan (1806-1871), quien introdujo una versión formal de las leyes a la lógica proposicional clásica . La formulación de De Morgan fue influenciada por la algebraización de la lógica realizada por George Boole , que luego cimentó la afirmación de De Morgan sobre el hallazgo. Sin embargo, Aristóteles hizo una observación similar , que era conocida por los lógicos griegos y medievales. Por ejemplo, en el siglo XIV, Guillermo de Ockham escribió las palabras que resultarían de la lectura de las leyes. Jean Buridan , en su Summulae de Dialectica , también describe reglas de conversión que siguen las líneas de las leyes de De Morgan. Sin embargo, a De Morgan se le atribuye el mérito de enunciar las leyes en los términos de la lógica formal moderna e incorporarlas al lenguaje de la lógica. Las leyes de De Morgan pueden probarse fácilmente e incluso pueden parecer triviales. No obstante, estas leyes son útiles para hacer inferencias válidas en pruebas y argumentos deductivos.

Prueba informal

El teorema de De Morgan se puede aplicar a la negación de una disyunción o la negación de una conjunción en todo o parte de una fórmula.

Negación de una disyunción

En el caso de su aplicación a una disyunción, considere la siguiente afirmación: "es falso que A o B sea verdadero", que se escribe como:

{\ Displaystyle \ neg (A \ lor B).}

Dado que se ha establecido que ni A ni B son verdaderos, entonces debe seguirse que tanto A no es cierto como B no lo es, lo que puede escribirse directamente como:

{\ Displaystyle (\ neg A) \ wedge (\ neg B).}

Si A o B fueran verdaderas, entonces la disyunción de A y B sería verdadera, haciendo que su negación fuera falsa. Presentado en inglés, sigue la lógica de que "dado que dos cosas son ambas falsas, también es falso que cualquiera de ellas sea verdadera".

Trabajando en la dirección opuesta, la segunda expresión afirma que A es falso y B es falso (o equivalentemente que "no A" y "no B" son verdaderos). Sabiendo esto, una disyunción de A y B también debe ser falsa. Por tanto, la negación de dicha disyunción debe ser verdadera y el resultado es idéntico al de la primera afirmación.

Negación de una conjunción

La aplicación del teorema de De Morgan a una conjunción es muy similar a su aplicación a una disyunción tanto en forma como en lógica. Considere la siguiente afirmación: "es falso que A y B sean ambos verdaderos", que se escribe como:

{\ Displaystyle \ neg (A \ land B).}

Para que esta afirmación sea verdadera, tanto A como B, o ambos, deben ser falsos, porque si ambos fueran verdaderos, entonces la conjunción de A y B sería verdadera, haciendo que su negación fuera falsa. Por lo tanto, uno (al menos) o más de A y B deben ser falsos (o de manera equivalente, uno o más de "no A" y "no B" deben ser verdaderos). Esto puede escribirse directamente como,

{\ Displaystyle (\ neg A) \ lor (\ neg B).}

Presentado en inglés, sigue la lógica de que "dado que es falso que dos cosas sean ambas verdaderas, al menos una de ellas debe ser falsa".

Trabajando en la dirección opuesta nuevamente, la segunda expresión afirma que al menos uno de "no A" y "no B" debe ser verdadero, o de manera equivalente que al menos uno de A y B debe ser falso. Dado que al menos uno de ellos debe ser falso, su conjunción también sería falsa. Negar dicha conjunción da como resultado una expresión verdadera, y esta expresión es idéntica a la primera afirmación.

Prueba formal

Aquí usamos para denotar el complemento de A. La demostración que se completa en 2 pasos probando ambos y . ${\ Displaystyle A ^ {\ complemento}}$ ${\ Displaystyle (A \ cap B) ^ {\ complemento} = A ^ {\ complemento} \ taza B ^ {\ complemento}}$ ${\ Displaystyle (A \ cap B) ^ {\ complemento} \ subseteq A ^ {\ complemento} \ taza B ^ {\ complemento}}$ ${\ Displaystyle A ^ {\ complemento} \ taza B ^ {\ complemento} \ subseteq (A \ cap B) ^ {\ complemento}}$

Parte 1

Deja . A continuación, . ${\ Displaystyle x \ in (A \ cap B) ^ {\ complemento}}$ ${\ Displaystyle x \ not \ in A \ cap B}$

Porque , debe ser el caso que o . ${\ Displaystyle A \ cap B = \ {\, y \ | \ y \ in A \ wedge y \ in B \, \}}$ ${\ Displaystyle x \ not \ in A}$ ${\ Displaystyle x \ not \ in B}$

Si , entonces , entonces . ${\ Displaystyle x \ not \ in A}$ ${\ Displaystyle x \ in A ^ {\ complemento}}$ ${\ Displaystyle x \ in A ^ {\ complemento} \ taza B ^ {\ complemento}}$

Del mismo modo, si , entonces , es así . ${\ Displaystyle x \ not \ in B}$ ${\ Displaystyle x \ in B ^ {\ complemento}}$ ${\ Displaystyle x \ in A ^ {\ complemento} \ taza B ^ {\ complemento}}$

Por lo tanto, ; ${\ Displaystyle \ forall x (x \ in (A \ cap B) ^ {\ complemento} \ rightarrow x \ in A ^ {\ complemento} \ cup B ^ {\ complemento})}$

es decir, . ${\ Displaystyle (A \ cap B) ^ {\ complemento} \ subseteq A ^ {\ complemento} \ taza B ^ {\ complemento}}$

Parte 2

Para probar la dirección inversa, supongamos , y por contradicción . ${\ Displaystyle x \ in A ^ {\ complemento} \ taza B ^ {\ complemento}}$ ${\ Displaystyle x \ not \ in (A \ cap B) ^ {\ complemento}}$

Bajo ese supuesto, debe darse el caso de que , ${\ Displaystyle x \ in A \ cap B}$

entonces sigue eso y , y así y . ${\ Displaystyle x \ in A}$ ${\ Displaystyle x \ in B}$ ${\ Displaystyle x \ not \ in A ^ {\ complemento}}$ ${\ Displaystyle x \ not \ in B ^ {\ complemento}}$

Sin embargo, eso significa , en contradicción con la hipótesis de que , ${\ Displaystyle x \ not \ in A ^ {\ complemento} \ taza B ^ {\ complemento}}$ ${\ Displaystyle x \ in A ^ {\ complemento} \ taza B ^ {\ complemento}}$

por lo tanto, la suposición no debe ser el caso, lo que significa que . ${\ Displaystyle x \ not \ in (A \ cap B) ^ {\ complemento}}$ ${\ Displaystyle x \ in (A \ cap B) ^ {\ complemento}}$

Por lo tanto , ${\ Displaystyle \ forall x (x \ in A ^ {\ complemento} \ cup B ^ {\ complemento} \ rightarrow x \ in (A \ cap B) ^ {\ complemento})}$

es decir, . ${\ Displaystyle A ^ {\ complemento} \ taza B ^ {\ complemento} \ subseteq (A \ cap B) ^ {\ complemento}}$

Conclusión

Si y , entonces ; esto concluye la prueba de la ley de De Morgan. ${\ Displaystyle A ^ {\ complemento} \ taza B ^ {\ complemento} \ subseteq (A \ cap B) ^ {\ complemento}}$ ${\ Displaystyle (A \ cap B) ^ {\ complemento} \ subseteq A ^ {\ complemento} \ taza B ^ {\ complemento}}$ ${\ Displaystyle (A \ cap B) ^ {\ complemento} = A ^ {\ complemento} \ taza B ^ {\ complemento}}$

La otra ley de De Morgan , se prueba de manera similar. ${\ Displaystyle (A \ taza B) ^ {\ complemento} = A ^ {\ complemento} \ cap B ^ {\ complemento}}$

Generalizando la dualidad de De Morgan

Las leyes de De Morgan representadas como un circuito con puertas lógicas

En las extensiones de la lógica proposicional clásica, la dualidad todavía se mantiene (es decir, para cualquier operador lógico siempre se puede encontrar su dual), ya que en presencia de las identidades que gobiernan la negación, siempre se puede introducir un operador que sea el dual de De Morgan de otro. Esto conduce a una propiedad importante de las lógicas basadas en la lógica clásica , a saber, la existencia de formas normales de negación : cualquier fórmula es equivalente a otra fórmula donde las negaciones solo ocurren aplicadas a los átomos no lógicos de la fórmula. La existencia de formas normales de negación impulsa muchas aplicaciones, por ejemplo en el diseño de circuitos digitales , donde se utiliza para manipular los tipos de puertas lógicas , y en la lógica formal, donde se necesita encontrar la forma normal conjuntiva y la forma normal disyuntiva de un fórmula. Los programadores de computadoras los usan para simplificar o negar adecuadamente condiciones lógicas complicadas . También suelen ser útiles en los cálculos de la teoría de probabilidad elemental .

Dejemos que uno defina el dual de cualquier operador proposicional P ( p , q , ...) dependiendo de las proposiciones elementales p , q , ... para ser el operador definido por ${\ Displaystyle {\ mbox {P}} ^ {d}}$

{\ Displaystyle {\ mbox {P}} ^ {d} (p, q, ...) = \ neg P (\ neg p, \ neg q, \ dots).}

Extensión a la lógica modal y de predicados

Esta dualidad se puede generalizar a los cuantificadores, por ejemplo, el cuantificador universal y el cuantificador existencial son duales:

{\ Displaystyle \ forall x \, P (x) \ equiv \ neg [\ existe x \, \ neg P (x)]}

{\ Displaystyle \ existe x \, P (x) \ equiv \ neg [\ forall x \, \ neg P (x)]}

Para relacionar estas dualidades cuantificadoras con las leyes de De Morgan, establezca un modelo con un pequeño número de elementos en su dominio D , como

D = { a , b , c }.

Luego

{\ Displaystyle \ forall x \, P (x) \ equiv P (a) \ land P (b) \ land P (c)}

y

{\ Displaystyle \ existe x \, P (x) \ equiv P (a) \ lor P (b) \ lor P (c).}

Pero, usando las leyes de De Morgan,

{\ Displaystyle P (a) \ land P (b) \ land P (c) \ equiv \ neg (\ neg P (a) \ lor \ neg P (b) \ lor \ neg P (c))}

y

{\ Displaystyle P (a) \ lor P (b) \ lor P (c) \ equiv \ neg (\ neg P (a) \ land \ neg P (b) \ land \ neg P (c)),}

verificar las dualidades cuantificadoras en el modelo.

Luego, las dualidades del cuantificador se pueden extender más a la lógica modal , relacionando los operadores de caja ("necesariamente") y de diamante ("posiblemente"):

{\ Displaystyle \ Box p \ equiv \ neg \ Diamond \ neg p,}

{\ Displaystyle \ Diamond p \ equiv \ neg \ Box \ neg p.}

En su aplicación a las modalidades aléticas de posibilidad y necesidad, Aristóteles observó este caso, y en el caso de la lógica modal normal , la relación de estos operadores modales con la cuantificación puede entenderse estableciendo modelos utilizando la semántica de Kripke .

En lógica intuicionista

Tres de las cuatro implicaciones de las leyes de De Morgan se mantienen en la lógica intuicionista . Específicamente, tenemos

{\ Displaystyle \ neg (P \ lor Q) \ iff (\ neg P) \ land (\ neg Q),}

y

{\ Displaystyle (P \ lor Q) \ rightarrow \ neg ((\ neg P) \ land (\ neg Q)),}

{\ Displaystyle (P \ land Q) \ rightarrow \ neg ((\ neg P) \ lor (\ neg Q)),}

{\ Displaystyle (\ neg P) \ lor (\ neg Q) \ rightarrow \ neg (P \ land Q)}

mientras que la inversa de la última implicación no se sostiene en la lógica intuicionista pura y sería equivalente a la ley del débil medio excluido

{\ Displaystyle \ neg P \ lor \ neg \ neg P}

que se puede utilizar como base para una lógica intermedia .

Ver también

Isomorfismo : operador NO como isomorfismo entre lógica positiva y lógica negativa
Lista de temas de álgebra de Boole
Lista de identidades y relaciones de conjuntos
Lógica positiva

Referencias

enlaces externos

"Principio de dualidad" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
Weisstein, Eric W. "Leyes de Morgan" . MathWorld .
las leyes de Morgan en PlanetMath .
Dualidad en lógica y lenguaje , Enciclopedia de Filosofía de Internet .

Languages

In other projects