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)}}$