Rappresentazione delle leggi di De Morgan attraverso due diagrammi di Venn . In ciascun caso l'insieme risultante è quello colorato di blu o qualche sua sfumatura 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 su regole logiche.
I due teoremi sono duali :
A
⋅
B
¯
=
A
¯
+
B
¯
{\displaystyle {\overline {A\cdot B}}={\overline {A}}+{\overline {B}}}
A
+
B
¯
=
A
¯
⋅
B
¯
{\displaystyle {\overline {A+B}}={\overline {A}}\cdot {\overline {B}}}
Con riferimento a termini insiemistici, il primo si enuncia affermando che se un elemento non appartiene ad
A
{\displaystyle A}
B
{\displaystyle B}
A
{\displaystyle A}
B
{\displaystyle B}
A
+
B
{\displaystyle A+B}
A
{\displaystyle A}
B
{\displaystyle B}
È immediata la generalizzazione a un numero
n
{\displaystyle n}
A
⋅
B
⋅
C
⋯
¯
=
A
¯
+
B
¯
+
C
¯
+
…
{\displaystyle {\overline {A\cdot B\cdot C\cdots }}={\overline {A}}+{\overline {B}}+{\overline {C}}+\dots }
A
+
B
+
C
+
…
¯
=
A
¯
⋅
B
¯
⋅
C
¯
…
{\displaystyle {\overline {A+B+C+\dots }}={\overline {A}}\cdot {\overline {B}}\cdot {\overline {C}}\dots }
Nella logica proposizionale possono essere formulate in vario modo:
¬
(
a
∧
b
)
=
¬
a
∨
¬
b
¬
(
a
∨
b
)
=
¬
a
∧
¬
b
{\displaystyle {\begin{matrix}\neg {(a\wedge b)}=\neg {a}\vee \neg {b}\\\neg {(a\vee b)}=\neg {a}\wedge \neg {b}\end{matrix}}\quad }
oppure
(
a
∧
b
)
¯
=
a
¯
∨
b
¯
(
a
∨
b
)
¯
=
a
¯
∧
b
¯
{\displaystyle \quad {\begin{matrix}{\overline {(a\wedge b)}}={\overline {a}}\vee {\overline {b}}\\{\overline {(a\vee b)}}={\overline {a}}\wedge {\overline {b}}\end{matrix}}}
oppure
¬
(
P
∧
Q
)
=
(
¬
P
)
∨
(
¬
Q
)
¬
(
P
∨
Q
)
=
(
¬
P
)
∧
(
¬
Q
)
{\displaystyle {\begin{matrix}\neg (P\wedge Q)=(\neg P)\vee (\neg Q)\\\neg (P\vee Q)=(\neg P)\wedge (\neg Q)\end{matrix}}}
e nella teoria degli insiemi :
(
A
∩
B
)
C
=
A
C
∪
B
C
{\displaystyle (A\cap B)^{C}=A^{C}\cup B^{C}}
oppure
(
A
∩
B
)
¯
=
A
¯
∪
B
¯
{\displaystyle {\overline {(A\cap B)}}={\overline {A}}\cup {\overline {B}}}
e
(
A
∪
B
)
C
=
A
C
∩
B
C
{\displaystyle (A\cup B)^{C}=A^{C}\cap B^{C}}
oppure
(
A
∪
B
)
¯
=
A
¯
∩
B
¯
{\displaystyle {\overline {(A\cup B)}}={\overline {A}}\cap {\overline {B}}}
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:
p
{\displaystyle p}
q
{\displaystyle q}
p
¯
{\displaystyle {\overline {p}}}
q
¯
{\displaystyle {\overline {q}}}
p
∨
q
{\displaystyle p\vee q}
p
∨
q
¯
{\displaystyle {\overline {p\vee q}}}
p
¯
∧
q
¯
{\displaystyle {\overline {p}}\wedge {\overline {q}}}
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
a
{\displaystyle \mathbf {a} }
b
{\displaystyle \mathbf {b} }
c
{\displaystyle \mathbf {c} }
0
¯
=
1
{\displaystyle {\overline {0}}=1}
1
¯
=
0
{\displaystyle {\overline {1}}=0}
a
¯
{\displaystyle \mathbf {\overline {a}} }
negazione logica di
a
{\displaystyle \mathbf {a} }
a
=
a
¯
¯
{\displaystyle \mathbf {a} ={\overline {\overline {\mathbf {a} }}}}
a
+
1
=
1
{\displaystyle \mathbf {a} +1=1}
a
⋅
0
=
0
{\displaystyle \mathbf {a} \cdot 0=0}
a
+
a
¯
=
1
{\displaystyle \mathbf {a} +\mathbf {\overline {a}} =1}
a
⋅
a
¯
=
0
{\displaystyle \mathbf {a} \cdot \mathbf {\overline {a}} =0}
(
a
+
b
)
+
c
=
a
+
(
b
+
c
)
{\displaystyle \left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =\mathbf {a} +\left(\mathbf {b} +\mathbf {c} \right)}
(
a
⋅
b
)
⋅
c
=
a
⋅
(
b
⋅
c
)
{\displaystyle \left(\mathbf {a} \cdot \mathbf {b} \right)\cdot \mathbf {c} =\mathbf {a} \cdot \left(\mathbf {b} \cdot \mathbf {c} \right)}
(
a
+
b
)
⋅
c
=
(
a
⋅
c
)
+
(
b
⋅
c
)
{\displaystyle \left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =\left(\mathbf {a} \cdot \mathbf {c} \right)+\left(\mathbf {b} \cdot \mathbf {c} \right)}
a
+
(
b
⋅
c
)
=
(
a
+
b
)
⋅
(
a
+
c
)
{\displaystyle \mathbf {a} +\left(\mathbf {b} \cdot \mathbf {c} \right)=\left(\mathbf {a} +\mathbf {b} \right)\cdot \left(\mathbf {a} +\mathbf {c} \right)}
DIMOSTRAZIONE :
I)
(
a
+
b
)
+
a
¯
⋅
b
¯
=
{\displaystyle \left(\mathbf {a} +\mathbf {b} \right)+{\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}=}
(Si applica la proprietà 11 )
=
[
(
a
+
b
)
+
a
¯
]
⋅
[
(
a
+
b
)
+
b
¯
]
=
{\displaystyle =\left[\left(\mathbf {a} +\mathbf {b} \right)+{\overline {\mathbf {a} }}\right]\cdot \left[\left(\mathbf {a} +\mathbf {b} \right)+\mathbf {\overline {b}} \right]=}
(Si applica la proprietà 8 )
=
[
(
a
+
a
¯
)
+
b
]
⋅
[
(
b
+
b
¯
)
+
a
]
=
{\displaystyle =\left[\left(\mathbf {a} +{\overline {\mathbf {a} }}\right)+\mathbf {b} \right]\cdot \left[\left(\mathbf {b} +{\overline {\mathbf {b} }}\right)+\mathbf {a} \right]=}
(Si applica la proprietà 6 )
=
[
(
1
)
+
b
]
⋅
[
(
1
)
+
a
]
=
{\displaystyle =\left[\left(1\right)+\mathbf {b} \right]\cdot \left[\left(1\right)+\mathbf {a} \right]=}
(Si applica la proprietà 4 )
=
1
+
1
=
1
{\displaystyle =1+1=1}
II)
(
a
+
b
)
⋅
(
a
¯
⋅
b
¯
)
=
{\displaystyle \left(\mathbf {a} +\mathbf {b} \right)\cdot \left({\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}\right)=}
(Si applica la proprietà 10 )
=
a
⋅
(
a
¯
⋅
b
¯
)
+
b
⋅
(
a
¯
⋅
b
¯
)
=
{\displaystyle =\mathbf {a} \cdot \left({\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}\right)+\mathbf {b} \cdot \left({\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}\right)=}
(Si applica la proprietà 9 )
=
b
¯
⋅
(
a
⋅
a
¯
)
+
a
¯
⋅
(
b
⋅
b
¯
)
=
{\displaystyle ={\overline {\mathbf {b} }}\cdot \left(\mathbf {a} \cdot {\overline {\mathbf {a} }}\right)+{\overline {\mathbf {a} }}\cdot \left(\mathbf {b} \cdot {\overline {\mathbf {b} }}\right)=}
(Si applica la proprietà 7 )
=
b
¯
⋅
(
0
)
+
a
¯
⋅
(
0
)
=
{\displaystyle ={\overline {\mathbf {b} }}\cdot \left(0\right)+{\overline {\mathbf {a} }}\cdot \left(0\right)=}
(Si applica la proprietà 5 )
=
0
+
0
=
0
{\displaystyle =0+0=0}
Sia ora
c
=
a
¯
⋅
b
¯
{\displaystyle \mathbf {c} ={\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}}
I) e II) rispettivamente le equazioni:
I-bis)
(
a
+
b
)
+
c
=
1
{\displaystyle \left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =1}
II-bis)
(
a
+
b
)
⋅
c
=
0
{\displaystyle \left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =0}
Unendo le proprietà 6) e 7) rispettivamente alle equazioni I-bis) e II-bis) si possono impostare i due sistemi equivalenti:
s1)
{
(
a
+
b
)
+
(
a
+
b
)
¯
=
1
(
a
+
b
)
+
c
=
1
⟹
c
=
(
a
+
b
)
¯
⟹
c
¯
=
(
a
+
b
)
{\displaystyle {\begin{cases}\left(\mathbf {a} +\mathbf {b} \right)+{\overline {\left(\mathbf {a} +\mathbf {b} \right)}}=1\\\left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =1\end{cases}}\implies \mathbf {c} ={\overline {\left(\mathbf {a} +\mathbf {b} \right)}}\implies {\overline {\mathbf {c} }}=\left(\mathbf {a} +\mathbf {b} \right)}
s2)
{
(
a
+
b
)
⋅
(
a
+
b
)
¯
=
0
(
a
+
b
)
⋅
c
=
0
⟹
c
=
(
a
+
b
)
¯
⟹
c
¯
=
(
a
+
b
)
{\displaystyle {\begin{cases}\left(\mathbf {a} +\mathbf {b} \right)\cdot {\overline {\left(\mathbf {a} +\mathbf {b} \right)}}=0\\\left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =0\end{cases}}\implies \mathbf {c} ={\overline {\left(\mathbf {a} +\mathbf {b} \right)}}\implies {\overline {\mathbf {c} }}=\left(\mathbf {a} +\mathbf {b} \right)}
Adoperando nuovamente la sostituzione
c
=
a
¯
⋅
b
¯
{\displaystyle \mathbf {c} ={\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}}
3), si ottiene infine:
c
¯
=
(
a
+
b
)
⟹
a
¯
⋅
b
¯
¯
=
(
a
+
b
)
⟹
a
¯
⋅
b
¯
=
(
a
+
b
)
¯
{\displaystyle {\overline {\mathbf {c} }}=\left(\mathbf {a} +\mathbf {b} \right)\implies {\overline {{\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}}}=\left(\mathbf {a} +\mathbf {b} \right)\implies {\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}={\overline {\left(\mathbf {a} +\mathbf {b} \right)}}}
c.v.d.
p
{\displaystyle p}
q
{\displaystyle q}
p
¯
{\displaystyle {\overline {p}}}
q
¯
{\displaystyle {\overline {q}}}
p
∧
q
{\displaystyle p\wedge q}
p
∧
q
¯
{\displaystyle {\overline {p\wedge q}}}
p
¯
∨
q
¯
{\displaystyle {\overline {p}}\vee {\overline {q}}}
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 Enciclopedia della Matematica , Istituto dell'Enciclopedia Italiana , 2013. (EN De Morgan laws Enciclopedia Britannica (EN Leggi di De Morgan MathWorld (EN Leggi di De Morgan Encyclopaedia of Mathematics (EN DeMorgan's theorem Free On-line Dictionary of Computing Disponibile con licenza GFDL 
![{\displaystyle =\left[\left(\mathbf {a} +\mathbf {b} \right)+{\overline {\mathbf {a} }}\right]\cdot \left[\left(\mathbf {a} +\mathbf {b} \right)+\mathbf {\overline {b}} \right]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ec844dfda9cd0b79ed3b15a45b77f2fb869bf45)
![{\displaystyle =\left[\left(\mathbf {a} +{\overline {\mathbf {a} }}\right)+\mathbf {b} \right]\cdot \left[\left(\mathbf {b} +{\overline {\mathbf {b} }}\right)+\mathbf {a} \right]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14c79f92e12642bdd52e0cf7a8679c182110e4ef)
![{\displaystyle =\left[\left(1\right)+\mathbf {b} \right]\cdot \left[\left(1\right)+\mathbf {a} \right]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e1249c741990e737935e4ddcc152b3e5f5bc3f7)
