Lleis de De Morgan

Les lleis de De Morgan són una part de la Lògica proposicional i analítica, i va ser creada per Augustus De Morgan (Madurai, 1806 - Londres, 1871).

Les lleis de De Morgan

Les lleis de De Morgan declaren que la suma de n variables globalment negades (o invertides) és igual al producte de les n variables negades individualment, i que inversament, el producte de n variables globalment negades és igual a la suma de les n variables negades individualment.

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

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

Prova

Cal utilitzar les taules de valors de veritat

$\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	F	F	V	V	V	V

Demostració formal

$\overline{A \cap B}= \overline{A}\cup \overline{B}$ si i només si $\overline{A \cap B}\subseteq \overline{A}\cup \overline{B}$ i $\overline{A \cap B}\supseteq \overline{A}\cup \overline{B}$.

per a qualsevol x:

$\subseteq$ inclusió:

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

$x \notin{A \cap B}$

$x \notin A$ o $x \notin B$

$x \in \overline A$ o $x \in \overline B$

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

Per tant $\overline{A \cap B}\subseteq \overline{A}\cup \overline{B}$

$\supseteq$ inclusió:

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

$x \in \overline A$ o $x \in \overline B$

$x \notin A$ o $x \notin B$

$x \notin{A \cap B}$

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

Per tant $\overline{A \cap B}\supseteq \overline{A}\cup \overline{B}$

$\overline{A \cap B}\subseteq \overline{A}\cup \overline{B}$ i $\overline{A \cap B}\supseteq \overline{A}\cup \overline{B}$ per tant $\overline{A \cap B}= \overline{A}\cup \overline{B}$ Q.E.D.

per $\overline{A \cup B}= \overline{A}\cap \overline{B}$ es pot utilitzar un mètode similar.

Amb proposicions

La prova utilitza la associativitat i la distributivitat de les lleis $\cap$ i $\cup$.

• Veritat
• Si veritat per 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})$