Lleis de De Morgan

Representació gràfica de les 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).

Història

Les lleis porten el nom d’Augustus De Morgan (1806–1871), que va introduir una versió formal de les lleis a la lògica proposicional clàssica. La formulació de De Morgan va estar influenciada per l’algebraització de la lògica empresa per George Boole, que posteriorment va consolidar la pretensió de De Morgan a la troballa. Tot i això, Aristòtil va fer una observació similar, que era coneguda pels lògics grecs i medievals. Per exemple, al Plantilla:Segle, Guillem d'Ockham va escriure les paraules que resultarien llegint les lleis. Jean Buridan, a la seva Summulae de Dialectica, també descriu les regles de conversió que segueixen les línies de les lleis de De Morgan. Tot i així, a De Morgan se li dona el mèrit d’enunciar les lleis en els termes de la lògica formal moderna i d’incorporar-les al llenguatge de la lògica. Les lleis de De Morgan es poden demostrar fàcilment i fins i tot poden semblar trivials. Tanmateix, aquestes lleis són útils per fer inferències vàlides en proves i arguments deductius.

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.

$\mathrm{\neg }(A\cup B)\leftrightarrow (\mathrm{\neg }A)\cap (\mathrm{\neg }B)$

$\mathrm{\neg }(A\cap B)\leftrightarrow (\mathrm{\neg }A)\cup (\mathrm{\neg }B)$

Prova

Cal utilitzar les taules de valors de veritat,

$\mathrm{\neg }(A\cup B)\leftrightarrow (\mathrm{\neg }A)\cap (\mathrm{\neg }B)$
$A$	$B$	$A\cup B$	$\mathrm{\neg }(A\cup B)$	$\mathrm{\neg }A$	$\mathrm{\neg }B$	$(\mathrm{\neg }A)\cap (\mathrm{\neg }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}=\bar{A}\cup \bar{B}$ si i només si $\overline{A\cap B}\subseteq \bar{A}\cup \bar{B}$ i $\overline{A\cap B}\supseteq \bar{A}\cup \bar{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 \bar{A}$ o $x\in \bar{B}$

$x\in \bar{A}\cup \bar{B}$

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

$\supseteq$ inclusió:

$x\in \bar{A}\cup \bar{B}$

$x\in \bar{A}$ o $x\in \bar{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 \bar{A}\cup \bar{B}$

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

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

Amb proposicions

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

• Veritat
• Si veritat per n

$\mathrm{\neg }(a_1\cap a_2\cap ...\cap A_n\cap A_{n+1})$

$\leftrightarrow \mathrm{\neg }((a_1\cap a_2\cap ...\cap A_n)\cap A_{n+1})$

$\leftrightarrow (\mathrm{\neg }(a_1\cap a_2\cap ...\cap A_n))\cup (\mathrm{\neg }{A}_{n+1})$

$\leftrightarrow (\mathrm{\neg }{a}_1)\cup (\mathrm{\neg }{a}_2)\cup ...⋓(\mathrm{\neg }{A}_n)\cup (\mathrm{\neg }{A}_{n+1})$

Vegeu també

• Lògica algebraica