Leyes de De Morgan


Representación gráfica de las leyes de De Morgan

En lógica proposicional y álgebra de Boole, las leyes de De Morgan[3] son un par de reglas de transformación que son ambas reglas de inferencia válidas. Las normas permiten la expresión de las conjunciones y disyunciones puramente en términos de vía negación.

Las reglas se pueden expresar en español como:

La negación de la conjunción es la disyunción de las negaciones.
La negación de la disyunción es la conjunción de las negaciones.

o informalmente como:

"no (A y B)" es lo mismo que "(no A) o (no B)"


y también,

"no (A o B)" es lo mismo que "(no A) y (no B)"

Las reglas pueden ser expresadas en un lenguaje formal con dos proposiciones P y Q, de esta forma:

donde:

  • ¬ es el operador de negación (NO)
  • es el operador de conjunción (Y)
  • es el operador de disyunción (O)
  • ⇔ es un símbolo metalógico que significa "puede ser reemplazado en una prueba lógica"

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

Notación formal

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

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

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

y negación de la disyunción

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

donde , y son proposiciones expresadas en algún sistema formal.

Forma de sustitución

Normalmente, las leyes de De Morgan se muestran en forma compacta como se muestran arriba, con la negación de la salida de la izquierda y la de las entradas a la derecha.

Conjunción

La conjunción de dos preposiciones es equivalente a la negación de la disyunción de los términos negados

Disyunción

La disyunción de dos preposiciones es equivalente a la negación de la conjunción de la negación de P y la negación de Q

Negaciones de operadores en las conjunciones y disyunciones

Conjunción con P negada

La conjunción de la proposición P negada y la preposición Q es equivalente a la negación de la disyunción de P y la negación de Q

Conjunción con Q negada

La conjunción de la proposición P y la preposición Q negada es equivalente a la negación de la disyunción de la negación de P y Q

Conjunción tanto de P como de Q negadas

La conjunción de la proposición P y Q negadas es equivalente a la negación de la disyunción de P y Q

Disyunción con P negada

La disyunción de la proposición P negada y la preposición Q es equivalente a la negación de la conjunción de P y la negación de Q

Esta forma también es equivalente al implica de la negación del término P y la negación del término Q

Disyunción con Q negada

La disyunción de la proposición P y la preposición Q negada es equivalente a la negación de la disyunción de la negación de P y Q

Disyunción tanto de P como de Q negadas

La disyunción de la proposición P y Q negadas es equivalente a la conjunción de la disyunción de P y Q

Esto pone de relieve la necesidad de invertir tanto en las entradas como en las salidas, así como también cambiar el operador, haciendo una sustitución.

Teoría de conjuntos y el álgebra de Boole

En la teoría de conjuntos y el álgebra de Boole, a menudo se indica como "Intercambio de Unión e intersección bajo la complementación",[4] que puede ser expresado formalmente como:

  • que puede ser expresado formalmente como:

donde:

  • A es la negación de A, la línea alta está escrita sobre las términos que se niegan
  • ∩ es el intersección operador (Y)
  • ∪ es el operador unión (O)

La forma generalizada es:

donde I es un conjunto indexado, posiblemente incontable.

Se puede recordar la ley de De Morgan, en notación de conjunto, mediante la regla nemotécnica "romper la línea, cambiar el signo".[5]

Ingeniería

En ingeniería electrónica e informática, la ley de De Morgan se escribe comúnmente como:

donde:

  • es el Y lógico
  • es el O lógico
  • la barra superior es el NO lógico de lo que está por debajo de la barra superior.
Other Languages