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

Leyes de De Morgan: ejercicios resueltos de lógica, conjuntos y Boole
Índice
  1. Recordatorio de las dos leyes
  2. Ejercicios básicos: comprobar y negar
    1. Ejercicio 1. Comprobar la primera ley con una tabla de verdad
    2. Ejercicio 2. Negar una frase
    3. Ejercicio 3. Complemento de una suma con una variable negada
    4. Ejercicio 4. Tres variables
  3. Ejercicios con conjuntos
    1. Ejercicio 5. Complementos en un universo finito
    2. Ejercicio 6. Negar un enunciado con cuantificador
  4. Ejercicios de simplificación booleana
    1. Ejercicio 7. Un error frecuente: ¬(A ∧ B ∨ C)
    2. Ejercicio 8. Simplificar F = (A'·B + C)'
    3. Ejercicio 9. Simplificar F = ((A·B)'·(A' + B))'
    4. Ejercicio 10. Una condición en programación
  5. Ejercicios de circuitos: NAND y NOR
    1. Ejercicio 11. Una puerta OR solo con NAND
    2. Ejercicio 12. Una puerta AND solo con NOR
  6. Errores que restan puntos
  7. Cómo se usan en una demostración
  8. Preguntas frecuentes
    1. ¿Cuáles son las leyes de De Morgan?
    2. ¿Cómo se niega «A y B» en una frase?
    3. ¿Cuál es la regla práctica para aplicarlas?
    4. ¿Valen para más de dos variables?
    5. ¿Para qué sirven en electrónica?
  9. Fuentes

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.

ÁmbitoPrimera leySegunda 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.

pqp ∧ q¬(p ∧ q)¬p¬q¬p ∨ ¬q
VVVFFFF
VFFVFVV
FVFVVFV
FFFVVVV

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)).

Fuentes

Teoremas

RELACIONADOS

Subir