# 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 segle xiv, 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.
$\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 l'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})$

## Referències

* ↑ Hurley, Patrick J. A Concise Introduction to Logic. 12th. Cengage Learning, 2015. ISBN 978-1-285-19654-1.
* ↑ DeMorgan’s Theorems Arxivat 2008-03-23 a Wayback Machine. at mtsu.edu
* ↑ William of Ockham, Summa Logicae, part II, sections 32 and 33.
* ↑ Jean Buridan, Summula de Dialectica. Trans. Gyula Klima. New Haven: Yale University Press, 2001. See especially Treatise 1, Chapter 7, Section 5. ISBN 0-300-08425-0
* ↑ Augustus De Morgan (1806–1871) Arxivat 2010-07-15 a Wayback Machine. by Robert H. Orr
* ↑ 2000 Solved Problems in Digital Electronics by S. P. Bali
* 1 2 ; Wu, Vincent«De Morgan's Laws».
* ↑ Boolean Algebra by R. L. Goodstein. ISBN 0-486-45894-6

## Vegeu també

* Lògica algebraica