Leggi di De Morgan

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

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 due teoremi sono duali:

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

È immediata la generalizzazione a un numero ${\displaystyle n}$ di variabili:

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

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

Nella logica proposizionale possono essere formulate in vario modo:

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

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

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

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

oppure

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

e

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

oppure

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

Lo stesso argomento in dettaglio: Tabella della verità.

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

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle {\overline {p}}}$	${\displaystyle {\overline {q}}}$	${\displaystyle p\vee q}$	${\displaystyle {\overline {p\vee 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 ${\displaystyle \mathbf {a} }$, ${\displaystyle \mathbf {b} }$ e ${\displaystyle \mathbf {c} }$ tre variabili booleane:

1. ${\displaystyle {\overline {0}}=1}$ e, viceversa, ${\displaystyle {\overline {1}}=0}$
2. ${\displaystyle \mathbf {\overline {a}} }$ è la negazione logica di ${\displaystyle \mathbf {a} }$
3. ${\displaystyle \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. ${\displaystyle \mathbf {a} +1=1}$
5. ${\displaystyle \mathbf {a} \cdot 0=0}$
6. ${\displaystyle \mathbf {a} +\mathbf {\overline {a}} =1}$
7. ${\displaystyle \mathbf {a} \cdot \mathbf {\overline {a}} =0}$
8. ${\displaystyle \left(\mathbf {a} +\mathbf {b} \right)+\mathbf {c} =\mathbf {a} +\left(\mathbf {b} +\mathbf {c} \right)}$
9. ${\displaystyle \left(\mathbf {a} \cdot \mathbf {b} \right)\cdot \mathbf {c} =\mathbf {a} \cdot \left(\mathbf {b} \cdot \mathbf {c} \right)}$
10. ${\displaystyle \left(\mathbf {a} +\mathbf {b} \right)\cdot \mathbf {c} =\left(\mathbf {a} \cdot \mathbf {c} \right)+\left(\mathbf {b} \cdot \mathbf {c} \right)}$
11. ${\displaystyle \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) ${\displaystyle \left(\mathbf {a} +\mathbf {b} \right)+{\overline {\mathbf {a} }}\cdot {\overline {\mathbf {b} }}=}$

(Si applica la proprietà 11)

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

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

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

(Si applica la proprietà 4)

${\displaystyle =1+1=1}$

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

(Si applica la proprietà 10)

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

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

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

(Si applica la proprietà 5)

${\displaystyle =0+0=0}$

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

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

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

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

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

Questa sezione sull'argomento matematica è ancora vuota. Aiutaci a scriverla!

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

• 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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica