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}
per
B
{\displaystyle B}
, allora o non appartiene ad
A
{\displaystyle A}
o non appartiene a
B
{\displaystyle B}
o non appartiene ad entrambi. Il secondo teorema si enuncia affermando che se un elemento non appartiene ad
A
+
B
{\displaystyle A+B}
, allora non appartiene ad
A
{\displaystyle A}
e non appartiene a
B
{\displaystyle B}
.
È immediata la generalizzazione a un numero
n
{\displaystyle n}
di variabili:
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 a}
,
b
{\displaystyle b}
e
c
{\displaystyle c}
tre variabili booleane:
0
¯
=
1
{\displaystyle {\overline {0}}=1}
e, viceversa,
1
¯
=
0
{\displaystyle {\overline {1}}=0}
a
¯
{\displaystyle {\overline {a}}}
è la negazione logica di
a
{\displaystyle a}
a
=
a
¯
¯
{\displaystyle a={\overline {\overline {a}}}}
(due negazioni logiche si elidono così che una variabile negata due volte equivale alla variabile stessa non negata)
a
+
1
=
1
{\displaystyle a+1=1}
a
⋅
0
=
0
{\displaystyle a\cdot 0=0}
a
+
a
¯
=
1
{\displaystyle a+{\overline {a}}=1}
a
⋅
a
¯
=
0
{\displaystyle a\cdot {\overline {a}}=0}
(
a
+
b
)
+
c
=
a
+
(
b
+
c
)
{\displaystyle \left(a+b\right)+c=a+\left(b+c\right)}
(
a
⋅
b
)
⋅
c
=
a
⋅
(
b
⋅
c
)
{\displaystyle \left(a\cdot b\right)\cdot c=a\cdot \left(b\cdot c\right)}
(
a
+
b
)
⋅
c
=
(
a
⋅
c
)
+
(
b
⋅
c
)
{\displaystyle \left(a+b\right)\cdot c=\left(a\cdot c\right)+\left(b\cdot c\right)}
a
+
(
b
⋅
c
)
=
(
a
+
b
)
⋅
(
a
+
c
)
{\displaystyle a+\left(b\cdot c\right)=\left(a+b\right)\cdot \left(a+c\right)}
(notare come questa proprietà sia valida solamente nell'algebra booleana, non nella comune algebra)
DIMOSTRAZIONE :
I)
(
a
+
b
)
+
a
¯
⋅
b
¯
=
{\displaystyle (a+b)+{\overline {a}}\cdot {\overline {b}}=}
(Si applica la proprietà 11 )
=
[
(
a
+
b
)
+
a
¯
]
⋅
[
(
a
+
b
)
+
b
¯
]
=
{\displaystyle =\left[(a+b)+{\overline {a}}\right]\cdot \left[\left(a+b\right)+{\overline {b}}\right]=}
(Si applica la proprietà 8 )
=
[
(
a
+
a
¯
)
+
b
]
⋅
[
(
b
+
b
¯
)
+
a
]
=
{\displaystyle =\left[\left(a+{\overline {a}}\right)+b\right]\cdot \left[\left(b+{\overline {b}}\right)+a\right]=}
(Si applica la proprietà 6 )
=
[
(
1
)
+
b
]
⋅
[
(
1
)
+
a
]
=
{\displaystyle =[(1)+b]\cdot [(1)+a]=}
(Si applica la proprietà 4 )
=
1
+
1
=
1.
{\displaystyle =1+1=1.}
II)
(
a
+
b
)
⋅
(
a
¯
⋅
b
¯
)
=
{\displaystyle (a+b)\cdot \left({\overline {a}}\cdot {\overline {b}}\right)=}
(Si applica la proprietà 10 )
=
a
⋅
(
a
¯
⋅
b
¯
)
+
b
⋅
(
a
¯
⋅
b
¯
)
=
{\displaystyle =a\cdot \left({\overline {a}}\cdot {\overline {b}}\right)+b\cdot \left({\overline {a}}\cdot {\overline {b}}\right)=}
(Si applica la proprietà 9 )
=
b
¯
⋅
(
a
⋅
a
¯
)
+
a
¯
⋅
(
b
⋅
b
¯
)
=
{\displaystyle ={\overline {b}}\cdot \left(a\cdot {\overline {a}}\right)+{\overline {a}}\cdot \left(b\cdot {\overline {b}}\right)=}
(Si applica la proprietà 7 )
=
b
¯
⋅
(
0
)
+
a
¯
⋅
(
0
)
=
{\displaystyle ={\overline {b}}\cdot \left(0\right)+{\overline {a}}\cdot \left(0\right)=}
(Si applica la proprietà 5 )
=
0
+
0
=
0
{\displaystyle =0+0=0}
Sia ora
c
=
a
¯
⋅
b
¯
{\displaystyle c={\overline {a}}\cdot {\overline {b}}}
; otteniamo da I) e II) rispettivamente le equazioni:
I-bis)
(
a
+
b
)
+
c
=
1
{\displaystyle (a+b)+c=1}
II-bis)
(
a
+
b
)
⋅
c
=
0.
{\displaystyle (a+b)\cdot 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}(a+b)+{\overline {(a+b)}}=1\\(a+b)+c=1\end{cases}}\implies c={\overline {(a+b)}}\implies {\overline {c}}=(a+b).}
s2)
{
(
a
+
b
)
⋅
(
a
+
b
)
¯
=
0
(
a
+
b
)
⋅
c
=
0
⟹
c
=
(
a
+
b
)
¯
⟹
c
¯
=
(
a
+
b
)
.
{\displaystyle {\begin{cases}(a+b)\cdot {\overline {(a+b)}}=0\\(a+b)\cdot c=0\end{cases}}\implies c={\overline {(a+b)}}\implies {\overline {c}}=(a+b).}
Adoperando nuovamente la sostituzione
c
=
a
¯
⋅
b
¯
{\displaystyle c={\overline {a}}\cdot {\overline {b}}}
e, successivamente, la proprietà 3), si ottiene infine:
c
¯
=
(
a
+
b
)
⟹
a
¯
⋅
b
¯
¯
=
(
a
+
b
)
⟹
a
¯
⋅
b
¯
=
(
a
+
b
)
¯
.
{\displaystyle {\overline {c}}=(a+b)\implies {\overline {{\overline {a}}\cdot {\overline {b}}}}=(a+b)\implies {\overline {a}}\cdot {\overline {b}}={\overline {(a+b)}}.}
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
Per le proprietà [10], [9] e [7] si verifica che
(
a
⋅
b
)
⋅
(
a
¯
+
b
¯
)
=
a
¯
⋅
(
a
⋅
b
)
+
b
¯
(
a
⋅
b
)
=
(
a
¯
⋅
a
)
⋅
b
+
(
b
¯
⋅
b
)
⋅
a
=
0
⋅
b
+
0
⋅
a
=
0
+
0
=
0
{\displaystyle (a\cdot b)\cdot ({\overline {a}}+{\overline {b}})={\overline {a}}\cdot (a\cdot b)+{\overline {b}}(a\cdot b)=({\overline {a}}\cdot a)\cdot b+({\overline {b}}\cdot b)\cdot a=0\cdot b+0\cdot a=0+0=0}
(
a
⋅
b
)
⋅
(
a
¯
+
b
¯
)
=
0.
{\displaystyle (a\cdot b)\cdot ({\overline {a}}+{\overline {b}})=0.}
Mentre per le proprietà [11], [6] e [4]:
(
a
⋅
b
)
+
(
a
¯
+
b
¯
)
=
(
a
¯
+
b
¯
+
a
)
⋅
(
a
¯
+
b
¯
+
b
)
=
(
b
¯
+
1
)
(
a
¯
+
1
)
=
1
⋅
1
=
1
{\displaystyle (a\cdot b)+({\overline {a}}+{\overline {b}})=({\overline {a}}+{\overline {b}}+a)\cdot ({\overline {a}}+{\overline {b}}+b)=({\overline {b}}+1)({\overline {a}}+1)=1\cdot 1=1}
(
a
⋅
b
)
+
(
a
¯
+
b
¯
)
=
1.
{\displaystyle (a\cdot b)+({\overline {a}}+{\overline {b}})=1.}
Per la [6] e la [7] sappiamo che
(
a
⋅
a
⋅
b
)
=
0
;
{\displaystyle (a\cdot a\cdot b)=0;}
(
a
⋅
b
)
+
(
a
⋅
b
)
¯
=
1.
{\displaystyle (a\cdot b)+{\overline {(a\cdot b)}}=1.}
A questo punto dimostrare il teorema equivale a dimostrare l'unicità del complemento.
Siano quindi
X
=
a
⋅
b
,
{\displaystyle X=a\cdot b,}
Y
=
a
¯
+
b
¯
,
{\displaystyle Y={\overline {a}}+{\overline {b}},}
Z
=
(
a
⋅
b
)
¯
.
{\displaystyle Z={\overline {(a\cdot b)}}.}
Le relazioni prima ottenute si possono riscrivere come:
X
⋅
Y
=
0
{\displaystyle X\cdot Y=0}
X
+
Y
=
1
{\displaystyle X+Y=1}
X
⋅
Z
=
0
{\displaystyle X\cdot Z=0}
X
+
Z
=
1
{\displaystyle X+Z=1}
da cui, sfruttando l'elemento neutro e sostituendo, ricaviamo
Y
=
Y
⋅
1
=
Y
⋅
(
X
+
Z
)
=
X
⋅
Y
+
Y
⋅
Z
=
0
+
Y
Z
=
Y
Z
{\displaystyle Y=Y\cdot 1=Y\cdot (X+Z)=X\cdot Y+Y\cdot Z=0+YZ=YZ}
Z
=
Z
⋅
1
=
Z
⋅
(
X
+
Y
)
=
X
⋅
Z
+
Y
⋅
Z
=
0
+
Y
Z
=
Y
Z
{\displaystyle Z=Z\cdot 1=Z\cdot (X+Y)=X\cdot Z+Y\cdot Z=0+YZ=YZ}
quindi
Y
=
Z
{\displaystyle Y=Z}
ossia
a
¯
+
b
¯
=
(
a
⋅
b
)
¯
.
{\displaystyle {\overline {a}}+{\overline {b}}={\overline {(a\cdot b)}}.}
De Morgan, leggi di , in Enciclopedia della Matematica , Istituto dell'Enciclopedia Italiana , 2013.
(EN ) De Morgan laws , su Enciclopedia Britannica , Encyclopædia Britannica, Inc.
(EN ) Eric W. Weisstein, de Morgan's Laws , su MathWorld , Wolfram Research.
(EN ) Leggi di De Morgan , su Encyclopaedia of Mathematics , Springer e European Mathematical Society.
(EN ) Denis Howe, DeMorgan's theorem , in Free On-line Dictionary of Computing . Disponibile con licenza GFDL