La negación de "A y B" es lo mismo que "no A o no B".
La negación de "A o B" es lo mismo que "no A y no B".
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 " o inclusivo " que significa al menos uno de A o B en lugar de un " o exclusivo " que significa exactamente uno de A o B.
Otra forma de la ley de De Morgan es la siguiente, como se ve a continuación.
Las aplicaciones de las reglas incluyen la simplificación de expresiones lógicas en programas informáticos 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 la conjunción puede escribirse en notación secuencial :
La regla de negación de la disyunción puede escribirse como:
y expresados como tautologías veritativo-funcionales o teoremas de lógica proposicional:
donde y son proposiciones expresadas en algún sistema formal.
Las leyes de De Morgan generalizadas proporcionan una equivalencia para negar una conjunción o disyunción que involucra múltiples términos. Para un conjunto de proposiciones , las leyes de De Morgan generalizadas son las siguientes:
Estas leyes generalizan las leyes originales de De Morgan para negar conjunciones y disyunciones.
Formulario de sustitución
Las leyes de De Morgan se muestran normalmente en la forma compacta que se muestra arriba, 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 la sustitución se puede expresar de la siguiente manera:
Esto enfatiza la necesidad de invertir tanto las entradas como la salida, así como cambiar el operador cuando se realiza una sustitución.
Teoría de conjuntos
En la teoría de conjuntos, a menudo se expresa como "unión e intersección intercambiadas bajo complementación", [6] lo que se puede expresar formalmente como:
En ingeniería eléctrica e informática , las leyes de De Morgan se escriben comúnmente como:
y
dónde:
es el AND lógico,
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 mediante los operadores booleanos AND, OR y NOT. Considere un conjunto de documentos que contengan las palabras "gatos" y "perros". Las leyes de De Morgan sostienen que estas dos búsquedas devolverán el mismo conjunto de documentos:
Buscar A: NO (gatos O perros)
Búsqueda B: (NO gatos) Y (NO perros)
El corpus de documentos que contiene "gatos" o "perros" puede estar representado por cuatro documentos:
Documento 1: Contiene sólo la palabra "gatos".
Documento 2: Contiene únicamente "perros".
Documento 3: Contiene tanto "gatos" como "perros".
Documento 4: No contiene ni "gatos" ni "perros".
Para evaluar la Búsqueda A, claramente la búsqueda "(gatos O perros)" afectará a 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 gatos)" dará como resultado documentos que no contengan "gatos", es decir, los Documentos 2 y 4. De manera similar, la búsqueda "(NO perros)" dará como resultado los Documentos 1 y 4. Al aplicar el operador AND a estas dos búsquedas (que es la Búsqueda B), dará como resultado los documentos que son comunes a estas dos búsquedas, es decir, el Documento 4.
Se puede aplicar una evaluación similar para demostrar que las dos búsquedas siguientes devolverán los Documentos 1, 2 y 4:
Buscar C:NO (gatos Y perros),
Buscar D: (NO gatos) O (NO perros).
Historia
Las leyes reciben su nombre de Augustus De Morgan (1806-1871), [8] quien introdujo una versión formal de las leyes en la lógica proposicional clásica . La formulación de De Morgan estuvo influenciada por la algebrización de la lógica realizada por George Boole , que más tarde consolidó 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. [9] Por ejemplo, en el siglo XIV, Guillermo de Ockham escribió las palabras que resultarían de la lectura de las leyes. [10] 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. [11] Aún así, a De Morgan se le atribuye el mérito de enunciar las leyes en términos de la lógica formal moderna e incorporarlas al lenguaje de la lógica. Las leyes de De Morgan se pueden demostrar fácilmente, e incluso pueden parecer triviales. [12] No obstante, estas leyes son útiles para hacer inferencias válidas en pruebas y argumentos deductivos.
Prueba del álgebra de Boole
El teorema de De Morgan puede aplicarse a la negación de una disyunción o a 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, considérese la siguiente afirmación: "es falso que A o B sea verdadero", que se escribe así:
Como se ha establecido que ni A ni B son verdaderos, entonces debe seguirse que tanto A como B no son verdaderos, lo que puede escribirse directamente como:
Si A o B fueran verdaderas, entonces la disyunción de A y B sería verdadera, lo que haría falsa su negación. En inglés, esto sigue la lógica de que "dado que dos cosas son falsas, también es falso que cualquiera de ellas sea verdadera".
En sentido inverso, 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. La negación de dicha disyunción debe ser, por tanto, verdadera, y el resultado es idéntico a 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 su forma como en su fundamento. Consideremos la siguiente afirmación: "es falso que A y B sean ambas verdaderas", que se escribe así:
Para que esta afirmación sea verdadera, A o B, o ambas, deben ser falsas, porque si ambas fueran verdaderas, entonces la conjunción de A y B sería verdadera, haciendo falsa su negación. Por lo tanto, una (al menos) o más de A y B deben ser falsas (o equivalentemente, una o más de "no A" y "no B" deben ser verdaderas). Esto puede escribirse directamente como:
Presentado en inglés, esto sigue la lógica de que "dado que es falso que dos cosas sean verdaderas, al menos una de ellas debe ser falsa".
Trabajando nuevamente en la dirección opuesta, la segunda expresión afirma que al menos una de las afirmaciones "no A" y "no B" debe ser verdadera, o equivalentemente, que al menos una de las afirmaciones "no A" y "no B" debe ser falsa. Como al menos una de ellas debe ser falsa, entonces su conjunción también sería falsa. La negación de dicha conjunción da como resultado una expresión verdadera, y esta expresión es idéntica a la primera afirmación.
Prueba de la teoría de conjuntos
Aquí usamos para denotar el complemento de A, como en el § Teoría de conjuntos y álgebra de Boole. La prueba se completa en 2 pasos demostrando tanto y .
Parte 1
Sea . Entonces, .
Porque , debe ser el caso que o .
Si , entonces , entonces .
De manera similar, si , entonces , por lo tanto .
De este modo, ;
eso es, .
Parte 2
Para demostrar la dirección inversa, sea , y por contradicción supongamos .
Bajo ese supuesto, debe ser el caso que ,
por lo tanto se sigue que y , y por lo tanto y .
Sin embargo, eso significa , en contradicción con la hipótesis de que ,
Por lo tanto, la suposición no debe ser el caso, lo que significa que .
Por eso, ,
eso es, .
Conclusión
Si y , entonces ; esto concluye la prueba de la ley de De Morgan.
La otra ley de De Morgan, , se demuestra de manera similar.
Generalizando la dualidad de De Morgan
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 lógica formal, donde se necesita para encontrar la forma normal conjuntiva y la forma normal disyuntiva de una fórmula. Los programadores de computadoras las utilizan para simplificar o negar adecuadamente condiciones lógicas complicadas . También suelen ser útiles en cálculos en teoría de probabilidad elemental .
Definamos el dual de cualquier operador proposicional P( p , q , ...) en función de las proposiciones elementales p , q , ... como el operador definido por
Para relacionar estas dualidades cuantificadoras con las leyes de De Morgan, configure un modelo con un pequeño número de elementos en su dominio D , tal como
D = { a , b , c }.
Entonces
y
Pero, utilizando las leyes de De Morgan,
y
verificando las dualidades cuantificadoras en el modelo.
Luego, las dualidades cuantificadoras pueden extenderse aún más a la lógica modal , relacionando los operadores de caja ("necesariamente") y diamante ("posiblemente"):
Tres de las cuatro implicaciones de las leyes de De Morgan se cumplen en la lógica intuicionista . En concreto, tenemos
y
El recíproco de la última implicación no se cumple en la lógica intuicionista pura. Es decir, el fracaso de la proposición conjunta no puede resolverse necesariamente como el fracaso de cualquiera de los dos conjuntos . Por ejemplo, de saber que no es el caso de que tanto Alice como Bob se presentaron a su cita, no se sigue quién no se presentó. El último principio es equivalente al principio del tercio débil excluido .
Esta forma débil puede utilizarse como base para una lógica intermedia . Para una versión refinada de la ley fallida relativa a los enunciados existenciales, véase el principio de omnisciencia menos limitado , que sin embargo es diferente de .
La validez de las otras tres leyes de De Morgan sigue siendo cierta si la negación se reemplaza por la implicación para algún predicado constante arbitrario C, lo que significa que las leyes anteriores siguen siendo verdaderas en la lógica minimal .
De manera similar a lo anterior, las leyes cuantificadoras:
y
son tautologías incluso en la lógica mínima con la negación reemplazada por una implicación de un fijo , mientras que el recíproco de la última ley no tiene por qué ser cierto en general.
Las leyes de De Morgan se utilizan ampliamente en ingeniería informática y lógica digital con el propósito de simplificar diseños de circuitos. [13]
En los lenguajes de programación modernos, debido a la optimización de compiladores e intérpretes, las diferencias de rendimiento entre estas opciones son insignificantes o completamente inexistentes.
^ Copi, Irving M.; Cohen, Carl; McMahon, Kenneth (2016). Introducción a la lógica. doi :10.4324/9781315510897. ISBN 9781315510880.
^ Hurley, Patrick J. (2015), Una introducción concisa a la lógica (12.ª ed.), Cengage Learning, ISBN978-1-285-19654-1
^ Moore, Brooke Noel (2012). Pensamiento crítico. Richard Parker (10.ª ed.). Nueva York: McGraw-Hill. ISBN978-0-07-803828-0.OCLC 689858599 .
^ Teorema de DeMorgan
^ Kashef, Arman. (2023), En busca de la lógica universal: una breve descripción general de la evolución de la lógica formal, doi :10.13140/RG.2.2.24043.82724/1
^ Guillermo de Ockham, Summa Logicae , parte II, secciones 32 y 33.
^ Jean Buridan, Summula de Dialectica . Trad. Gyula Klima. New Haven: Yale University Press, 2001. Véase especialmente el Tratado 1, Capítulo 7, Sección 5. ISBN 0-300-08425-0
^ Wirth, Niklaus (1995), Diseño de circuitos digitales para estudiantes de informática: un libro de texto introductorio, Springer, pág. 16, ISBN9783540585770