Leyes de De Morgan

Las leyes de De Morgan son una parte de la lógica proposicional y álgebra de Boole, y fueron creadas por Augustus De Morgan (1806-1871).

Las leyes de De Morgan

Las Leyes de De Morgan sirven para declarar que la suma de n variables proposicionales globalmente negadas (o invertidas) es igual al producto de las n variables negadas individualmente y que inversamente, el producto de n variables proposicionales globalmente negadas es igual a la suma de las n variables negadas individualmente.

$\lnot(A \cup B) \Leftrightarrow (\lnot A) \cap (\lnot B)$

$\lnot(A \cap B) \Leftrightarrow (\lnot A) \cup (\lnot B)$

Demostración formal

$\overline{A \cap B}=\overline{A} \cup \overline{B}$ si y solo si $\overline{A \cap B}\subseteq\overline{A} \cup \overline{B}$ y $\overline{A \cap B}\supseteq\overline{A} \cup \overline{B}$.

para cualquiera x: $x \notin A$ ó $x \notin B$

$x \in \overline A$ ó $x \in \overline B$

$x \in \overline A \cup \overline B$

Por lo tanto $\overline{A \cap B}\subseteq\overline{A} \cup \overline{B}$

$\supseteq$ inclusión:

$x \in \overline A \cup \overline B$

$x \in \overline A$ ó $x \in \overline B$

Con proposiciones

La prueba utiliza la asociatividad y la distributividad de las leyes $\cap$ y $\cup$.

• Verdad
• Si verdad por n

$\lnot(A_1 \cap A_2 \cap ... \cap A_n \cap A_{n+1})$

$\Leftrightarrow (\lnot ( (A_1 \cap A_2 \cap ... \cap A_n) \cap A_{n+1})$

$\Leftrightarrow (\lnot (A_1 \cap A_2 \cap ... \cap A_n)) \cup (\lnot A_{n+1})$

$\Leftrightarrow (\lnot A_1) \cup (\lnot A_2) \cup ... \cup (\lnot A_n) \cup (\lnot A_{n+1})$