Leyes de De Morgan

Las leyes de Morgan son una parte de la Lógica proposicional y analítica ,y fue creada por Augustus De Morgan (Madura,1806-Londres,1871).

Las leyes de De Morgan

Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o invertidas) es igual al producto de las n variables negadas individualmente; y que inversamente, el producto de n variables 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)$

Prueba

Hay que utilizar las tablas de valores de verdad

$\lnot (A\cup B)\leftrightarrow (\lnot A)\cap (\lnot B)$
$A$	$B$	$A\cup B$	$\lnot (A\cup B)$	$\lnot A$	$\lnot B$	$(\lnot A)\cap (\lnot B)$
V	V	V	F	F	F	F
V	F	V	F	F	V	F
F	V	V	F	V
F	F	F	V	V	V	V

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 cualquier x:

$\subseteq$ inclusión:

$x\in {\overline {A\cap B}}$

$x\notin {A\cap B}$

$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}}$

$x\notin A$ ó $x\notin B$

$x\notin {A\cap B}$

$x\in {\overline {A\cap B}}$

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

${\overline {A\cap B}}\subseteq {\overline {A}}\cup {\overline {B}}$ y ${\overline {A\cap B}}\supseteq {\overline {A}}\cup {\overline {B}}$ por lo tanto ${\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}$ Q.E.D.

para ${\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}$ se puede utilizar un método similar.

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})$