Leyes de De Morgan: ejercicios resueltos de lógica, conjuntos y Boole

Actualizado el
Las leyes de De Morgan dicen cómo se niega una conjunción o una disyunción: la negación de «A y B» es «no A o no B», y la negación de «A o B» es «no A y no B». En los ejercicios de examen aparecen de cuatro maneras: negar una frase, trabajar con complementos de conjuntos, simplificar una función booleana y convertir un circuito a puertas NAND o NOR. Aquí tienes doce ejercicios, de los más directos a los que combinan varias leyes.
Recordatorio de las dos leyes
En lógica proposicional, con ¬ para la negación, ∧ para «y» y ∨ para «o»:
¬(p ∧ q) ≡ ¬p ∨ ¬q y ¬(p ∨ q) ≡ ¬p ∧ ¬q
En álgebra de Boole se escriben con la barra o el apóstrofo: (A·B)' = A' + B' y (A + B)' = A'·B'. En conjuntos: (A ∪ B)c = Ac ∩ Bc y (A ∩ B)c = Ac ∪ Bc. La regla práctica es siempre la misma: se niega cada término y se cambia el operador. Si quieres repasar de dónde salen y cómo se demuestran, está todo en la guía de las leyes de De Morgan en lógica y álgebra de Boole.
| Ámbito | Primera ley | Segunda ley |
|---|---|---|
| Lógica | ¬(p ∧ q) ≡ ¬p ∨ ¬q | ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Boole | (A·B)' = A' + B' | (A + B)' = A'·B' |
| Conjuntos | (A ∩ B)c = Ac ∪ Bc | (A ∪ B)c = Ac ∩ Bc |
| Cuantificadores | ¬∀x P(x) ≡ ∃x ¬P(x) | ¬∃x P(x) ≡ ∀x ¬P(x) |
Ejercicios básicos: comprobar y negar
Ejercicio 1. Comprobar la primera ley con una tabla de verdad
Enunciado. Demuestra que ¬(p ∧ q) y ¬p ∨ ¬q son equivalentes.
Planteamiento. Dos fórmulas son equivalentes si tienen el mismo valor en todas las filas de la tabla. Con dos variables hay 22 = 4 filas.
| p | q | p ∧ q | ¬(p ∧ q) | ¬p | ¬q | ¬p ∨ ¬q |
|---|---|---|---|---|---|---|
| V | V | V | F | F | F | F |
| V | F | F | V | F | V | V |
| F | V | F | V | V | F | V |
| F | F | F | V | V | V | V |
Resultado. Las columnas cuarta y séptima coinciden fila a fila, así que las fórmulas son equivalentes.
Ejercicio 2. Negar una frase
Enunciado. Niega «Llueve y hace frío» y «Estudio matemáticas o estudio física».
Planteamiento. La primera es una conjunción; la segunda, una disyunción.
Resultado. «No llueve o no hace frío» (basta con que falle una de las dos cosas) y «No estudio matemáticas y no estudio física» (tienen que fallar las dos). Un error muy común es negar la primera como «No llueve y no hace frío», que es una afirmación más fuerte que la negación.
Ejercicio 3. Complemento de una suma con una variable negada
Enunciado. Simplifica (A + B')'.
Cálculo. Por la segunda ley, (A + B')' = A'·(B')'. Por la doble negación, (B')' = B.
Resultado. (A + B')' = A'·B.
Ejercicio 4. Tres variables
Enunciado. Escribe sin paréntesis negados ¬(p ∨ q ∨ r).
Planteamiento. Las leyes se generalizan a cualquier número de términos: se agrupa (p ∨ q) ∨ r y se aplica la ley dos veces.
Resultado. ¬(p ∨ q ∨ r) ≡ ¬p ∧ ¬q ∧ ¬r.
Ejercicios con conjuntos
Ejercicio 5. Complementos en un universo finito
Enunciado. En U = {1, 2, …, 10}, sean A = {1, 2, 3, 4, 5} y B = {4, 5, 6, 7}. Calcula (A ∪ B)c y (A ∩ B)c de dos formas.
Cálculo directo. A ∪ B = {1, …, 7}, luego (A ∪ B)c = {8, 9, 10}. A ∩ B = {4, 5}, luego (A ∩ B)c = {1, 2, 3, 6, 7, 8, 9, 10}.
Con De Morgan. Ac = {6, 7, 8, 9, 10} y Bc = {1, 2, 3, 8, 9, 10}. Su intersección es {8, 9, 10} y su unión es {1, 2, 3, 6, 7, 8, 9, 10}.
Resultado. Las dos vías dan lo mismo. Si lo dibujas, en un diagrama de Venn la zona sombreada de (A ∪ B)c es la que queda fuera de los dos círculos.
Ejercicio 6. Negar un enunciado con cuantificador
Enunciado. Niega «Todos los alumnos aprobaron» y «Existe un número primo par mayor que 2».
Resultado. «Algún alumno no aprobó» y «Ningún número primo par es mayor que 2» (es decir, todo primo par es menor o igual que 2).
Ejercicios de simplificación booleana
Ejercicio 7. Un error frecuente: ¬(A ∧ B ∨ C)
Enunciado. Elimina la negación exterior de ¬((A ∧ B) ∨ C).
Planteamiento. El operador principal es la disyunción ∨, porque ∧ se evalúa antes. Se aplica la segunda ley a «(A ∧ B) o C» y después la primera a ¬(A ∧ B).
Cálculo. ¬((A ∧ B) ∨ C) ≡ ¬(A ∧ B) ∧ ¬C ≡ (¬A ∨ ¬B) ∧ ¬C.
Resultado. (¬A ∨ ¬B) ∧ ¬C. La respuesta ¬A ∨ (¬B ∧ ¬C), que aparece en algunos apuntes, es incorrecta: con A falsa, B verdadera y C verdadera la expresión original vale F y esa otra vale V.
Ejercicio 8. Simplificar F = (A'·B + C)'
Cálculo. Por la segunda ley, F = (A'·B)'·C'. Por la primera, (A'·B)' = A + B'.
Resultado. F = (A + B')·C', que también puede escribirse A·C' + B'·C'.
Ejercicio 9. Simplificar F = ((A·B)'·(A' + B))'
Planteamiento. Fuera hay un producto negado: primera ley.
Cálculo. F = ((A·B)')' + (A' + B)' = A·B + A·B'. Sacando factor común, F = A·(B + B') = A·1.
Resultado. F = A. Las cuatro filas de la tabla lo confirman. Para este tipo de pasos (factor común, complemento, elemento neutro) conviene tener a mano los postulados y teoremas del álgebra de Boole.
Ejercicio 10. Una condición en programación
Enunciado. Un bucle se repite mientras not (x > 0 and y > 0). Reescribe la condición sin el not exterior.
Cálculo. Por la primera ley, not(P and Q) = (not P) or (not Q), y not(x > 0) es x ≤ 0.
Resultado. El bucle se repite mientras x ≤ 0 or y ≤ 0, es decir, hasta que los dos números sean positivos.
Ejercicios de circuitos: NAND y NOR
Ejercicio 11. Una puerta OR solo con NAND
Enunciado. Construye A + B usando únicamente puertas NAND.
Planteamiento. Una NAND calcula (X·Y)'. Si sus dos entradas son iguales, (X·X)' = X', así que hace de inversor.
Cálculo. Por la doble negación y la segunda ley, A + B = ((A + B)')' = (A'·B')'. Eso es una NAND cuyas entradas son A' y B', y cada una se obtiene con otra NAND: A' = NAND(A, A), B' = NAND(B, B).
Resultado. A + B = NAND(NAND(A, A), NAND(B, B)): tres puertas.
Ejercicio 12. Una puerta AND solo con NOR
Enunciado. Construye A·B usando únicamente puertas NOR.
Cálculo. Con la primera ley, A·B = ((A·B)')' = (A' + B')'. Esa es una NOR de A' y B', y cada inversor es una NOR con las entradas unidas: A' = NOR(A, A).
Resultado. A·B = NOR(NOR(A, A), NOR(B, B)). Es el mismo razonamiento que el ejercicio 11 cambiando los papeles de la suma y el producto: el principio de dualidad del álgebra de Boole.
Errores que restan puntos
- Negar los términos sin cambiar el operador. ¬(p ∧ q) no es ¬p ∧ ¬q.
- Cambiar el operador sin negar los términos. (A + B)' no es A·B.
- No respetar la prioridad. En A·B + C el operador principal es la suma; hay que localizarlo antes de aplicar la ley (ejercicio 7).
- Olvidar la doble negación. (B')' = B, y suele ser el paso que deja la expresión simplificada.
Cómo se usan en una demostración
Las leyes de De Morgan aparecen también en las demostraciones por contraposición y por reducción al absurdo, porque obligan a negar hipótesis compuestas. Si el enunciado es «si n es par y mayor que 2, entonces n no es primo», la contrarrecíproca es «si n es primo, entonces n es impar o n ≤ 2»: la negación de la conjunción se convierte en una disyunción. Para ver qué papel tienen las reglas lógicas dentro de una teoría, merece la pena leer qué es un teorema y en qué se diferencia de un axioma.
Preguntas frecuentes
¿Cuáles son las leyes de De Morgan?
Son dos equivalencias: la negación de una conjunción es la disyunción de las negaciones, ¬(p ∧ q) ≡ ¬p ∨ ¬q, y la negación de una disyunción es la conjunción de las negaciones, ¬(p ∨ q) ≡ ¬p ∧ ¬q.
¿Cómo se niega «A y B» en una frase?
Se dice «no A o no B». Por ejemplo, la negación de «llueve y hace frío» es «no llueve o no hace frío», no «no llueve y no hace frío».
¿Cuál es la regla práctica para aplicarlas?
Negar cada término y cambiar el operador: el «y» pasa a «o» y el «o» pasa a «y». En álgebra de Boole, el producto pasa a suma y la suma a producto.
¿Valen para más de dos variables?
Sí. Por ejemplo, ¬(p ∨ q ∨ r) ≡ ¬p ∧ ¬q ∧ ¬r y (A·B·C)' = A' + B' + C'. Se demuestra aplicando la ley de dos en dos.
¿Para qué sirven en electrónica?
Para convertir un circuito a un solo tipo de puerta. Por ejemplo, A + B = NAND(NAND(A, A), NAND(B, B)) y A·B = NOR(NOR(A, A), NOR(B, B)).
RELACIONADOS