En lógica proposicional y álgebra booleana , las leyes de De Morgan [1] [2] [3] 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.
En teoría de conjuntos y álgebra booleana , estos se escriben formalmente como
dónde
- y son conjuntos,
- es el complemento de ,
- es la intersección , y
- es la unión .
En lenguaje formal , las reglas están escritas como
y
dónde
- P y Q son proposiciones,
- es el operador lógico de negación (NO),
- es el operador lógico de conjunción (Y),
- es el operador lógico de disyunción (OR),
- 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 :
- ,
y
- .
La regla de negación de disyunción se puede escribir como:
- ,
y
- .
En forma de regla : negación de la conjunción
y negación de la disyunción
y expresado como una tautología funcional de verdad o teorema de lógica proposicional:
dónde y son proposiciones expresadas en algún sistema formal.
Formulario de sustitución
Las leyes de De Morgan se muestran normalmente 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:
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 el () Ley de la doble negación. , para convertirse en un sistema lógico formal: La secuencia informa de los símbolos que están bien definidos 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. [4]
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", [5] que se puede expresar formalmente como:
dónde:
- es la negación de , El overline ser escrita por encima de los términos a ser negado,
- es el operador de intersección (Y),
- es el operador de la unión (OR).
Uniones e intersecciones infinitas
La forma generalizada es
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". [6]
Ingenieria
En ingeniería eléctrica e informática , las leyes de De Morgan se escriben comúnmente como:
y
dónde:
- es el Y 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 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), [7] quien introdujo una versión formal de las leyes a la lógica proposicional clásica . La formulación de De Morgan estuvo 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. [8] Por ejemplo, en el siglo XIV, Guillermo de Ockham escribió las palabras que resultarían al leer las leyes. [9] Jean Buridan , en su Summulae de Dialectica , también describe las reglas de conversión que siguen las líneas de las leyes de De Morgan. [10] Aún así, se le da crédito a De Morgan por 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. [11] 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:
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:
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:
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,
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 prueba de que se completa en 2 pasos probando tanto y .
Parte 1
Dejar . Luego,.
Porque , debe ser el caso que o .
Si , luego , entonces .
Del mismo modo, si , luego , entonces .
Por lo tanto, ;
es decir, .
Parte 2
Para probar la dirección inversa, dejemos , y por contradicción asumir .
Bajo ese supuesto, debe darse el caso de que ,
entonces 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, ,
es decir, .
Conclusión
Si y , luego ; esto concluye la prueba de la ley de De Morgan.
La otra ley de De Morgan, , se prueba 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 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
Extensión a la lógica modal y de predicados
Esta dualidad se puede generalizar a cuantificadores, por lo que, por ejemplo, el cuantificador universal y el cuantificador existencial son duales:
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
y
Pero, usando las leyes de De Morgan,
y
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"):
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 .
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
- ^ Copi y Cohen [ cita completa necesaria ]
- ^ Hurley, Patrick J. (2015), Una breve introducción a la lógica (12a ed.), Cengage Learning, ISBN 978-1-285-19654-1
- ^ Moore y Parker [ se necesita cita completa ]
- ^ Hayes, Andy; Wu, Vincent. "Leyes de De Morgan" . https://brilliant.org/ . Enlace externo en
|website=
( ayuda ) - ^ Álgebra de Boole por RL Goodstein. ISBN 0-486-45894-6
- ^ 2000 problemas resueltos en electrónica digital por SP Bali
- ^ Teoremas de DeMorgan en mtsu.edu
- ^ Historia de la lógica formal de Bocheński
- ^ Guillermo de Ockham, Summa Logicae , parte II, secciones 32 y 33.
- ^ Jean Buridan, Summula de Dialectica . Trans. 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
- ^ Augustus De Morgan (1806–1871) Archivado el 15 de julio de 2010 en la Wayback Machine por Robert H. Orr
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 .