Le leggi di De Morgan, o teoremi di De Morgan, sono relative alla logica booleana e stabiliscono relazioni di equivalenza tra gli operatori di congiunzione e disgiunzione logica.
Sono utilizzate per l'analisi di circuiti logici (elettrici, elettronici, pneumatici, comunque binari, cioè ON-OFF) e per la dimostrazione di teoremi basati regole logiche.
I due teoremi sono duali:
![{\displaystyle {\overline {A\cdot B}}={\overline {A}}+{\overline {B}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d761e79b286cd35b3cfafbb14f9bd56aadcaf588)
![{\displaystyle {\overline {A+B}}={\overline {A}}\cdot {\overline {B}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6337e58ec6cd300cde7cc8ccad80c802965f809)
Con riferimento a termini insiemistici, il primo si enuncia affermando che se un elemento non appartiene ad
per
, allora o non appartiene ad
o non appartiene a
o non appartiene ad entrambi. Il secondo teorema si enuncia affermando che se un elemento non appartiene ad
, allora non appartiene ad
e non appartiene a
.
È immediata la generalizzazione a un numero
di variabili:
![{\displaystyle {\overline {A\cdot B\cdot C\cdots }}={\overline {A}}+{\overline {B}}+{\overline {C}}+\dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/aea62174563a9ed878e3fee3d867cd70b7ee9579)
![{\displaystyle {\overline {A+B+C+\dots }}={\overline {A}}\cdot {\overline {B}}\cdot {\overline {C}}\dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/422e33453e74c310a436c4eef80e60fef52fa4ac)
Nella logica proposizionale possono essere formulate in vario modo:
![{\displaystyle {\begin{matrix}\neg {(a\wedge b)}=\neg {a}\vee \neg {b}\\\neg {(a\vee b)}=\neg {a}\wedge \neg {b}\end{matrix}}\quad }](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dc41721d846238504f0ec00492de6079cf883b4)
oppure
![{\displaystyle \quad {\begin{matrix}{\overline {(a\wedge b)}}={\overline {a}}\vee {\overline {b}}\\{\overline {(a\vee b)}}={\overline {a}}\wedge {\overline {b}}\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/817f1c0325e546bbccde5d5af599f070ff7e7830)
oppure
![{\displaystyle {\begin{matrix}\neg (P\wedge Q)=(\neg P)\vee (\neg Q)\\\neg (P\vee Q)=(\neg P)\wedge (\neg Q)\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9714c21c19ce997a5c1e792bd3fd07e078a33aa)
e nella teoria degli insiemi:
![{\displaystyle (A\cap B)^{C}=A^{C}\cup B^{C}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/745cfa0d4a5ec83a0d6eca1748c1b6fb92706c22)
oppure
![{\displaystyle {\overline {(A\cap B)}}={\overline {A}}\cup {\overline {B}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f88fa55216b54b6a93edad78a9402b78cb2bd6b)
e
![{\displaystyle (A\cup B)^{C}=A^{C}\cap B^{C}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db228f912f93a427173138c915d3aa48ddd5a021)
oppure
![{\displaystyle {\overline {(A\cup B)}}={\overline {A}}\cap {\overline {B}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f09f507298d4c4c98fe293b39a4792f18458293)
In pratica esse descrivono il comportamento dei connettivi logici (AND e OR) quando una negazione viene tolta da o inserita in una formula in parentesi. Se si raccoglie la negazione fuori parentesi o la si distribuisce tra i termini in parentesi, il connettivo si trasforma nel suo opposto.
Espresse in forma tabellare:
¬(W+Y) = (¬W) * (¬Y)
|
¬(W*Y) = (¬W) + (¬Y)
|
1 + W = 1
|
0 * W = 0
|
0 + W = W
|
1 * W = W
|
I teoremi si possono dimostrare sia algebricamente che con l'ausilio della tabella della verità, essendo i casi da provare in numero finito:
|
|
|
|
|
|
|
V |
V |
F |
F |
V |
F |
F
|
V |
F |
F |
V |
V |
F |
F
|
F |
V |
V |
F |
V |
F |
F
|
F |
F |
V |
V |
F |
V |
V
|
Prima di passare alla dimostrazione è utile annotare alcune proprietà e definizioni dell'algebra booleana; si considerino
,
e
tre variabili booleane:
e, viceversa, ![{\displaystyle {\overline {1}}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99421fe9e31befbc05b7b03d98d25465fa935e39)
è la negazione logica di ![{\displaystyle \mathbf {a} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a957216653a9ee0d0133dcefd13fb75e36b8b9d)
(due negazioni logiche si elidono così che una variabile negata due volte equivale alla variabile stessa non negata)
![{\displaystyle \mathbf {a} +1=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6b8e11bb45e500095038aff935a120d924a7882)
![{\displaystyle \mathbf {a} \cdot 0=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4373bddccb1b0fe7ed89dded376d10e76b9c0f28)
![{\displaystyle \mathbf {a} +\mathbf {\overline {a}} =1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e3b13454cf479e01ded6e84cdb683a62bdc7617)
![{\displaystyle \mathbf {a} \cdot \mathbf {\overline {a}} =0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18a89f453770c78aa4dce261742af886f945913b)
![{\displaystyle \left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =\mathbf {a} +\left(\mathbf {b} +\mathbf {c} \right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11a971c3ff7cf540544113757e81168bd1e9255c)
![{\displaystyle \left(\mathbf {a} \cdot \mathbf {b} \right)\cdot \mathbf {c} =\mathbf {a} \cdot \left(\mathbf {b} \cdot \mathbf {c} \right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9282ae63a745ba6a76ee0ddeb1a7ad304b990f9)
![{\displaystyle \left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =\left(\mathbf {a} \cdot \mathbf {c} \right)+\left(\mathbf {b} \cdot \mathbf {c} \right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a604e7ef2350adeb25944b06a873611cd51cd7f9)
(notare come questa proprietà sia valida solamente nell'algebra booleana, non nella comune algebra)
DIMOSTRAZIONE:
I)
(Si applica la proprietà 11)
(Si applica la proprietà 8)
(Si applica la proprietà 6)
(Si applica la proprietà 4)
II)
(Si applica la proprietà 10)
(Si applica la proprietà 9)
(Si applica la proprietà 7)
(Si applica la proprietà 5)
Sia ora
; otteniamo da I) e II) rispettivamente le equazioni:
I-bis)
II-bis)
Unendo le proprietà 6) e 7) rispettivamente alle equazioni I-bis) e II-bis) si possono impostare i due sistemi equivalenti:
s1)
s2)
Adoperando nuovamente la sostituzione
e, successivamente, la proprietà 3), si ottiene infine:
c.v.d.
|
|
|
|
|
|
|
V |
V |
F |
F |
V |
F |
F
|
V |
F |
F |
V |
F |
V |
V
|
F |
V |
V |
F |
F |
V |
V
|
F |
F |
V |
V |
F |
V |
V
|
- De Morgan, leggi di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
![Modifica su Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png)
- (EN) De Morgan laws, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
![Modifica su Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png)
- (EN) Eric W. Weisstein, Leggi di De Morgan, su MathWorld, Wolfram Research.
![Modifica su Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png)
- (EN) Leggi di De Morgan, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
![Modifica su Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png)
- (EN) DeMorgan's theorem, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL