# 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 su 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:
* ${\overline {0}}=1$ e, viceversa, ${\overline {1}}=0$
* $\mathbf {\overline {a}}$ è la negazione logica di $\mathbf {a}$
* $\mathbf {a} ={\overline {\overline {\mathbf {a} }}}$ (due negazioni logiche si elidono così che una variabile negata due volte equivale alla variabile stessa non negata)
* $\mathbf {a} +1=1$
* $\mathbf {a} \cdot 0=0$
* $\mathbf {a} +\mathbf {\overline {a}} =1$
* $\mathbf {a} \cdot \mathbf {\overline {a}} =0$
* $\left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =\mathbf {a} +\left(\mathbf {b} +\mathbf {c} \right)$
* $\left(\mathbf {a} \cdot \mathbf {b} \right)\cdot \mathbf {c} =\mathbf {a} \cdot \left(\mathbf {b} \cdot \mathbf {c} \right)$
* $\left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =\left(\mathbf {a} \cdot \mathbf {c} \right)+\left(\mathbf {b} \cdot \mathbf {c} \right)$
* $\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 |