Leyes de De Morgan: enunciado, demostración y ejemplos

Leyes de De Morgan: enunciado, demostración y ejemplos
Índice
  1. Enunciado de las leyes de De Morgan
  2. Explicación con palabras
  3. Demostración con tabla de verdad
    1. Demostración para conjuntos
  4. Ejemplos de las leyes de De Morgan
    1. Ejemplo 1: con conjuntos de números
    2. Ejemplo 2: negar una frase en lógica
    3. Ejemplo 3: simplificar una expresión booleana
    4. Ejemplo 4: una condición en un programa
  5. Errores habituales
  6. Generalizaciones
  7. Historia
  8. Preguntas frecuentes
    1. ¿Qué dicen las leyes de De Morgan?
    2. ¿Es lo mismo el teorema de Morgan que las leyes de De Morgan?
    3. ¿Cómo se aplican en el álgebra de Boole?
    4. ¿Cómo se demuestran?
  9. Fuentes

Actualizado el

Las leyes de De Morgan explican cómo se niega una conjunción o una disyunción: negar «p y q» equivale a decir «no p o no q», y negar «p o q» equivale a «no p y no q». Al negar, la «y» se convierte en «o» y al revés. Sirven para simplificar expresiones lógicas, circuitos digitales y condiciones de programas, y valen igual para conjuntos.

Enunciado de las leyes de De Morgan

Son dos leyes, una dual de la otra. Por eso a veces se habla de «teorema de Morgan» en singular y otras de «teoremas» o «leyes de Morgan»: el nombre correcto es leyes de De Morgan, por el apellido del matemático, Augustus De Morgan.

ContextoPrimera leySegunda ley
Lógica proposicional¬(p ∧ q) ≡ ¬p ∨ ¬q¬(p ∨ q) ≡ ¬p ∧ ¬q
Conjuntos(A ∩ B)c = Ac ∪ Bc(A ∪ B)c = Ac ∩ Bc
Álgebra de Boole(A·B)' = A' + B'(A + B)' = A'·B'
Programación (C, Java, JavaScript)!(x && y) == (!x || !y)!(x || y) == (!x && !y)

El símbolo ¬ es la negación, ∧ la conjunción («y»), ∨ la disyunción («o» inclusivo) y ≡ significa que las dos fórmulas son lógicamente equivalentes: tienen el mismo valor de verdad en todos los casos. En el álgebra de Boole se suele escribir la negación con una barra encima o con una comilla, el producto para «y» y la suma para «o».

Explicación con palabras

Piensa en la frase «hoy hace frío y llueve». Para que sea falsa basta con que falle una de las dos partes: o no hace frío, o no llueve (o ninguna de las dos cosas). Eso es la primera ley.

Ahora la frase «estudio física o química». Su negación no es «no estudio física o no estudio química», sino «no estudio física y no estudio química»: para que la disyunción sea falsa tienen que fallar las dos. Esa es la segunda ley.

Demostración con tabla de verdad

En lógica proposicional, dos fórmulas son equivalentes si coinciden fila a fila en su tabla de verdad. Con dos variables hay cuatro combinaciones (V = verdadero, F = falso):

pq¬(p ∧ q)¬p ∨ ¬q¬(p ∨ q)¬p ∧ ¬q
VVFFFF
VFVVFF
FVVVFF
FFVVVV

La tercera y la cuarta columna son idénticas, y también la quinta y la sexta: las dos leyes quedan demostradas. Es una demostración completa, porque no hay más casos posibles.

Demostración para conjuntos

Para probar (A ∪ B)c = Ac ∩ Bc se comprueba que cada conjunto está contenido en el otro siguiendo un elemento x:

  1. x ∈ (A ∪ B)c significa que x no está en A ∪ B.
  2. Eso ocurre exactamente cuando x no está en A y x no está en B (si estuviera en uno de los dos, estaría en la unión).
  3. Es decir, x ∈ Ac y x ∈ Bc, o sea, x ∈ Ac ∩ Bc.

Como cada paso es un «si y solo si», la igualdad es completa. La otra ley se prueba igual. Si te ayuda verlo, dibuja los dos conjuntos en un diagrama de Venn y sombrea cada lado de la igualdad: sale la misma región.

Ejemplos de las leyes de De Morgan

Ejemplo 1: con conjuntos de números

Sea U = {1, 2, …, 12}, A los números pares y B los múltiplos de 3. Entonces A ∪ B = {2, 3, 4, 6, 8, 9, 10, 12} y su complementario es {1, 5, 7, 11}. Por otro lado, Ac = {1, 3, 5, 7, 9, 11} y Bc = {1, 2, 4, 5, 7, 8, 10, 11}; su intersección también es {1, 5, 7, 11}. La segunda ley se cumple: son los números que no son ni pares ni múltiplos de 3.

Ejemplo 2: negar una frase en lógica

Negación de «el número es positivo y par»: «el número no es positivo o no es par». El −4 y el 3 hacen verdadera la negación, cada uno por un motivo distinto.

Ejemplo 3: simplificar una expresión booleana

Simplifica F = ((A·B) + C)'.

  1. Segunda ley sobre la suma exterior: F = (A·B)'·C'.
  2. Primera ley sobre el producto: F = (A' + B')·C'.

La negación ha «bajado» hasta las variables. En electrónica digital esto permite construir cualquier circuito solo con puertas NAND o solo con NOR: una NAND, (A·B)', es lo mismo que una OR con las entradas negadas, A' + B'. Esta y otras reglas de simplificación están en la guía de postulados y teoremas del álgebra de Boole.

Ejemplo 4: una condición en un programa

Un bucle debe seguir mientras no se cumpla «x > 0 y y > 0». La condición !(x > 0 && y > 0) se puede reescribir como (x <= 0 || y <= 0), que se lee mejor. Atención: la negación de «>» es «<=», no «<».

Para practicar con negaciones de frases, conjuntos y circuitos, tienes una colección de ejercicios de De Morgan con la solución explicada.

Errores habituales

  • Negar las partes sin cambiar el conector. ¬(p ∧ q) no es ¬p ∧ ¬q. La frase «no es verdad que hoy haga frío y llueva» no implica que no haga frío.
  • Confundir el «o» lógico con el exclusivo. Las leyes usan el «o» inclusivo: ¬p ∨ ¬q es verdadero también cuando fallan las dos.
  • Negar mal las comparaciones. La negación de «a < b» es «a ≥ b».

Generalizaciones

Por inducción, las leyes valen para cualquier número de términos:

¬(p1 ∧ p2 ∧ … ∧ pn) ≡ ¬p1 ∨ ¬p2 ∨ … ∨ ¬pn

y lo mismo intercambiando ∧ y ∨. Con conjuntos se cumplen incluso para familias infinitas: el complementario de una unión es la intersección de los complementarios.

También tienen su versión con cuantificadores, que es la que más se usa al negar enunciados matemáticos: ¬(∀x P(x)) ≡ ∃x ¬P(x) y ¬(∃x P(x)) ≡ ∀x ¬P(x). Negar «todos los alumnos aprobaron» es «algún alumno no aprobó», no «ningún alumno aprobó». El «para todo» funciona como una gran conjunción y el «existe» como una gran disyunción.

Historia

Augustus De Morgan (1806-1871), matemático británico, dejó escritas estas leyes en el lenguaje de la lógica formal en su libro Formal Logic, de 1847. La idea era conocida antes: los lógicos medievales, como Guillermo de Ockham en el siglo XIV, ya enunciaban con palabras estas reglas. A De Morgan se le atribuyen por haberlas formulado en términos de la lógica moderna, en la misma época en que George Boole convertía la lógica en un álgebra.

Si te interesa qué distingue una ley como esta de un axioma, lo tienes en la guía sobre qué es un teorema. Las leyes de De Morgan son teoremas de la lógica proposicional clásica: se deducen de las definiciones de los conectores, como acabas de ver con la tabla de verdad.

Preguntas frecuentes

¿Qué dicen las leyes de De Morgan?

Que la negación de una conjunción es la disyunción de las negaciones, ¬(p ∧ q) ≡ ¬p ∨ ¬q, y que la negación de una disyunción es la conjunción de las negaciones, ¬(p ∨ q) ≡ ¬p ∧ ¬q.

¿Es lo mismo el teorema de Morgan que las leyes de De Morgan?

Sí. Son dos leyes duales y se las llama indistintamente teorema, teoremas o leyes de (De) Morgan. El apellido del autor es De Morgan.

¿Cómo se aplican en el álgebra de Boole?

(A·B)' = A' + B' y (A + B)' = A'·B'. Se usan para llevar las negaciones hasta las variables y para pasar de puertas AND/OR a NAND/NOR.

¿Cómo se demuestran?

Con una tabla de verdad de cuatro filas: las columnas de ¬(p ∧ q) y ¬p ∨ ¬q coinciden en todas, y lo mismo las de ¬(p ∨ q) y ¬p ∧ ¬q. Para conjuntos, siguiendo un elemento por doble inclusión.

Fuentes

Teoremas

RELACIONADOS

Subir