Leggi di De Morgan

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 teoremi

I due teoremi sono duali:

${\overline {A\cdot B}}={\overline {A}}+{\overline {B}}$

${\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$ per $B$, allora o non appartiene ad $A$ o non appartiene a $B$ o non appartiene ad entrambi. Il secondo teorema si enuncia affermando che se un elemento non appartiene ad $A+B$, allora non appartiene ad $A$ e non appartiene a $B$.

È immediata la generalizzazione a un numero $n$ di variabili:

${\overline {A\cdot B\cdot C\cdots }}={\overline {A}}+{\overline {B}}+{\overline {C}}+\dots$

${\overline {A+B+C+\dots }}={\overline {A}}\cdot {\overline {B}}\cdot {\overline {C}}\dots$

Nella logica proposizionale possono essere formulate in vario modo:

${\begin{matrix}\neg {(a\wedge b)}=\neg {a}\vee \neg {b}\\\neg {(a\vee b)}=\neg {a}\wedge \neg {b}\end{matrix}}\quad$

oppure

$\quad {\begin{matrix}{\overline {(a\wedge b)}}={\overline {a}}\vee {\overline {b}}\\{\overline {(a\vee b)}}={\overline {a}}\wedge {\overline {b}}\end{matrix}}$

oppure

${\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\cap B)^{C}=A^{C}\cup B^{C}$

oppure

${\overline {(A\cap B)}}={\overline {A}}\cup {\overline {B}}$

e

$(A\cup B)^{C}=A^{C}\cap B^{C}$

oppure

${\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

Dimostrazione

I teoremi si possono dimostrare sia algebricamente che con l'ausilio della tabella della verità, essendo i casi da provare in numero finito:

Primo teorema

Dimostrazione tabellare

$p$	$q$	${\overline {p}}$	${\overline {q}}$	$p\vee q$	${\overline {p\vee q}}$	${\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

Dimostrazione algebrica

Prima di passare alla dimostrazione è utile annotare alcune proprietà e definizioni dell'algebra booleana; si considerino $\mathbf {a}$, $\mathbf {b}$ e $\mathbf {c}$ tre variabili booleane:

1. ${\overline {0}}=1$ e, viceversa, ${\overline {1}}=0$
2. $\mathbf {\overline {a}}$ è la negazione logica di $\mathbf {a}$
3. $\mathbf {a} ={\overline {\overline {\mathbf {a} }}}$ (due negazioni logiche si elidono così che una variabile negata due volte equivale alla variabile stessa non negata)
4. $\mathbf {a} +1=1$
5. $\mathbf {a} \cdot 0=0$
6. $\mathbf {a} +\mathbf {\overline {a}} =1$
7. $\mathbf {a} \cdot \mathbf {\overline {a}} =0$
8. $\left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =\mathbf {a} +\left(\mathbf {b} +\mathbf {c} \right)$
9. $\left(\mathbf {a} \cdot \mathbf {b} \right)\cdot \mathbf {c} =\mathbf {a} \cdot \left(\mathbf {b} \cdot \mathbf {c} \right)$
10. $\left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =\left(\mathbf {a} \cdot \mathbf {c} \right)+\left(\mathbf {b} \cdot \mathbf {c} \right)$
11. $\mathbf {a} +\left(\mathbf {b} \cdot \mathbf {c} \right)=\left(\mathbf {a} +\mathbf {b} \right)\cdot \left(\mathbf {a} +\mathbf {c} \right)$ (notare come questa proprietà sia valida solamente nell'algebra booleana, non nella comune algebra)

DIMOSTRAZIONE:

I) $\left(\mathbf {a} +\mathbf {b} \right)+{\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}=$

(Si applica la proprietà 11)

$=\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)

$=\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)

$=\left[\left(1\right)+\mathbf {b} \right]\cdot \left[\left(1\right)+\mathbf {a} \right]=$

(Si applica la proprietà 4)

$=1+1=1$

II) $\left(\mathbf {a} +\mathbf {b} \right)\cdot \left({\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}\right)=$

(Si applica la proprietà 10)

$=\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)

$={\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)

$={\overline {\mathbf {b} }}\cdot \left(0\right)+{\overline {\mathbf {a} }}\cdot \left(0\right)=$

(Si applica la proprietà 5)

$=0+0=0$

Sia ora $\mathbf {c} ={\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}$ ; otteniamo da I) e II) rispettivamente le equazioni:

I-bis) $\left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =1$

II-bis) $\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) ${\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) ${\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 $\mathbf {c} ={\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}$ e, successivamente, la proprietà 3), si ottiene infine:

${\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.

Secondo teorema

Dimostrazione tabellare

$p$	$q$	${\overline {p}}$	${\overline {q}}$	$p\wedge q$	${\overline {p\wedge q}}$	${\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

Voci correlate

• Algebra di Boole
• Funzione booleana
• Teorema di Shannon (elettronica)
• Teorema dell'assorbimento

Collegamenti esterni

• 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, Leggi di De Morgan, su MathWorld, Wolfram Research.
• (EN) Leggi di De Morgan, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) DeMorgan's theorem, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL