Lleis de De Morgan

Les lleis porten el nom d’Augustus De Morgan (1806–1871),^[2] 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 segle XIV, Guillem d'Ockham va escriure les paraules que resultarien llegint les lleis.^[3] 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.^[4] 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.^[5] Tanmateix, aquestes lleis són útils per fer inferències vàlides en proves i arguments deductius.

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.^[6]

${\displaystyle \lnot (A\cup B)\leftrightarrow (\lnot A)\cap (\lnot B)}$

${\displaystyle \lnot (A\cap B)\leftrightarrow (\lnot A)\cup (\lnot B)}$

Cal utilitzar les taules de valors de veritat,^[7]

${\displaystyle \lnot (A\cup B)\leftrightarrow (\lnot A)\cap (\lnot B)}$
${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\cup B}$	${\displaystyle \lnot (A\cup B)}$	${\displaystyle \lnot A}$	${\displaystyle \lnot B}$	${\displaystyle (\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

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

per a qualsevol x:^[7]

${\displaystyle \subseteq }$ inclusió:

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

${\displaystyle x\notin {A\cap B}}$

${\displaystyle x\notin A}$ o ${\displaystyle x\notin B}$

${\displaystyle x\in {\overline {A}}}$ o ${\displaystyle x\in {\overline {B}}}$

${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

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

${\displaystyle \supseteq }$ inclusió:

${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

${\displaystyle x\in {\overline {A}}}$ o ${\displaystyle x\in {\overline {B}}}$

${\displaystyle x\notin A}$ o ${\displaystyle x\notin B}$

${\displaystyle x\notin {A\cap B}}$

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

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

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

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

La prova utilitza l'associativitat i la distributivitat de les lleis ${\displaystyle \cap }$ i ${\displaystyle \cup }$ .^[8]

• Veritat
• Si veritat per n

${\displaystyle \lnot (a_{1}\cap a_{2}\cap ...\cap A_{n}\cap A_{n+1})}$

${\displaystyle \leftrightarrow \lnot ((a_{1}\cap a_{2}\cap ...\cap A_{n})\cap A_{n+1})}$

${\displaystyle \leftrightarrow (\lnot (a_{1}\cap a_{2}\cap ...\cap A_{n}))\cup (\lnot A_{n+1})}$

${\displaystyle \leftrightarrow (\lnot a_{1})\cup (\lnot a_{2})\cup ...\Cup (\lnot A_{n})\cup (\lnot A_{n+1})}$