Ahora toca revisar otra de las propiedades de uso frecuente en la lógica proposicional, hablamos de las demostraciones de las leyes de DeMorgan de Distribución de la conjunción y la disyunción. El uso de estas leyes es habitual en lo que se refiere a teoría de conjuntos y, por extensión, permean toda la matemática: desde la teoría de las probabilidades, la topología e incluso tienen presencia en la electrónica y la programación. Como es de costumbre, desgranaremos las demostraciones de estas leyes a partir de las técnicas de deducción que ya hemos obtenido hasta ahora.

Leyes de DeMorgan

Las leyes de DeMorgan son un conjunto de equivalencias que formalizan la distribución de las negaciones con la conjunción y la disyunción. Formalmente se expresan a través de las equivalencias:

\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)

\neg(\alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg \beta)

Estas equivalencias probadas se pueden obtener sin la necesidad de hacer una demostración como la que hemos hecho hasta ahora, ya que nos podemos valer de las definiciones que relacionan las conjunciones con las disyunciones y un poco de juego con la equivalencia de doble negación y sustituciones. De la definición de la conjunción se sigue que:

(A \wedge B):= \neg(\neg A \vee \neg B)

Aplicando una negación a ambos lados de ésta expresión tenemos que

\neg(A \wedge B):= \neg\neg(\neg A \vee \neg B)

Luego, por la equivalencia de doble negación obtenemos

\neg(A \wedge B)\dashv \vdash (\neg A \vee \neg B)

Finalmente, remplazando A=\alpha y B=\beta, obtenemos la primera equivalencia de DeMorgan

\boxed{\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)}

Para obtener la segunda podemos continuar jugando con la expresión que teníamos antes de hacer el remplazo agregando nuevamente una negación a ambos lados, obteniendo

\neg\neg(A \wedge B)\dashv \vdash \neg(\neg A \vee \neg B)

Y luego, por doble negación obtenemos que

\neg(\neg A \vee \neg B) \dashv \vdash (A \wedge B)

Si sobre esta última expresión remplazamos A=\neg\alpha y B=\neg\beta, llegaremos a que

\neg(\neg \neg\alpha \vee \neg \neg\beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)

Que debido a la equivalencia de doble negación conducirá a la segunda equivalencia de DeMorgan

\boxed{\neg( \alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)}

Además, de forma completamente análoga podemos obtener algunas formas adicionales, que no son más que variaciones de las que acabamos de revisar

\neg(\neg\alpha \wedge \beta) \dashv \vdash (\alpha \vee \neg \beta)

\neg(\neg\alpha \vee \beta) \dashv \vdash (\alpha \wedge \neg \beta)

\neg(\alpha \wedge \neg\beta) \dashv \vdash (\neg\alpha \vee \beta)

\neg(\alpha \vee \neg\beta) \dashv \vdash (\neg\alpha \wedge \beta)

Reglas de Distributividad entre la Conjunción y la Disyunción

Como su nombre indica, estas reglas nos permiten distribuir los conjuntos y disyuntos dentro de una expresión. Estas leyes se resumen en las siguientes dos equivalencias:

Como ya es costumbre en lo que hemos visto hasta ahora, aunque esto se trata de un resultado conocido su demostración no tiene nada de trivial. Si bien, para completar esta demostración se debe razonar en ambas direcciones, en esta ocasión sólo daré la demostración en un sólo sentido, la demostración en el sentido reverso quedará como ejercicio para el lector.

∧ – Distributividad

Para demostrar que ocurre \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)) se tiene el siguiente razonamiento.

Con esto queda demostrado que \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)). Ahora es tu turno de poner a prueba lo aprendido y te aventures a demostrar por tu cuenta que \{((\alpha \wedge \beta)\vee(\alpha \wedge \gamma))\}\vdash (\alpha \wedge(\beta \vee\gamma)).

∨ – Distributividad

La demostración de \{(\alpha \vee(\beta \wedge\gamma))\}\vdash((\alpha \vee \beta)\wedge(\alpha \vee \gamma)) se obtiene a partir del siguiente razonamiento:

Esto es la mitad de la demostración, ahora sólo falta hacerla de regreso, pero eso queda como ejercicio para el lector :3

Consideraciones Finales

Con esta revisión que hemos hecho de las demostraciones de las leyes de De Morgan de distribución de la conjunción y la disyunción, podemos dar por concluido nuestro estudio sobre las técnicas de deducción de la lógica proposicional y cómo éstas convergen en la demostración de las leyes de la lógica clásica, o al menos las más importantes.

Es importante completar todas las demostraciones propuestas para reforzar los conocimientos sobre estas técnicas. Para hacerlo un poco menos complicado, es muy conveniente comparar las demostraciones en busca de similitudes, ya que es posible que la estrategia que funcionó en una demostración funcione con algunas variaciones para lograr otra.

Una última cosa que vale la pena señalar es el orden que elegí para desarrollar estas demostraciones. Debes notar que cada demostración utilizó los resultados de algunas de las demostraciones previas. Elegí este orden porque personalmente me resultó más sencillo de esta manera. Un buen ejercicio para mejorar tus habilidades en estas cosas es formularte la pregunta «¿Podré armar estas demostraciones en un orden diferente siguiendo esta misma metodología?». Te recomiendo encarecidamente que intentes obtener estas demostraciones en un orden distinto y que uses cada demostración para obtener las siguientes porque, aunque no logres hacerlo, la práctica que surge del intento te otorgará una mejor comprensión de las demostraciones y de los métodos utilizados en la lógica.