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.

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

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:

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

¬(W+Y) = (¬W) * (¬Y)

¬(W*Y) = (¬W) + (¬Y)

1 + W = 1

0 * W = 0

0 + W = W

1 * W = W

Dimostrazione

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:

Primo teorema

Dimostrazione tabellare

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

Dimostrazione algebrica

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

1. ${\displaystyle {\overline {0}}=1}$ e, viceversa, ${\displaystyle {\overline {1}}=0}$
2. ${\displaystyle {\overline {a}}}$ è la negazione logica di ${\displaystyle a}$
3. ${\displaystyle a={\overline {\overline {a}}}}$ (due negazioni logiche si elidono così che una variabile negata due volte equivale alla variabile stessa non negata)
4. ${\displaystyle a+1=1}$
5. ${\displaystyle a\cdot 0=0}$
6. ${\displaystyle a+{\overline {a}}=1}$
7. ${\displaystyle a\cdot {\overline {a}}=0}$
8. ${\displaystyle \left(a+b\right)+c=a+\left(b+c\right)}$
9. ${\displaystyle \left(a\cdot b\right)\cdot c=a\cdot \left(b\cdot c\right)}$
10. ${\displaystyle \left(a+b\right)\cdot c=\left(a\cdot c\right)+\left(b\cdot c\right)}$
11. ${\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) ${\displaystyle (a+b)+{\overline {a}}\cdot {\overline {b}}=}$

(Si applica la proprietà 11)

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

(Si applica la proprietà 8)

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

(Si applica la proprietà 6)

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

(Si applica la proprietà 4)

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

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

(Si applica la proprietà 10)

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

(Si applica la proprietà 9)

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

(Si applica la proprietà 7)

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

(Si applica la proprietà 5)

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

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

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

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

${\displaystyle {\overline {c}}=(a+b)\implies {\overline {{\overline {a}}\cdot {\overline {b}}}}=(a+b)\implies {\overline {a}}\cdot {\overline {b}}={\overline {(a+b)}}.}$

Secondo teorema

Dimostrazione tabellare

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

Dimostrazione algebrica

Per le proprietà [10], [9] e [7] si verifica che

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

${\displaystyle (a\cdot b)\cdot ({\overline {a}}+{\overline {b}})=0.}$

Mentre per le proprietà [11], [6] e [4]:

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

${\displaystyle (a\cdot b)+({\overline {a}}+{\overline {b}})=1.}$

Per la [6] e la [7] sappiamo che

${\displaystyle (a\cdot a\cdot b)=0;}$

${\displaystyle (a\cdot b)+{\overline {(a\cdot b)}}=1.}$

A questo punto dimostrare il teorema equivale a dimostrare l'unicità del complemento.

Siano quindi ${\displaystyle X=a\cdot b,}$ ${\displaystyle Y={\overline {a}}+{\overline {b}},}$ ${\displaystyle Z={\overline {(a\cdot b)}}.}$

Le relazioni prima ottenute si possono riscrivere come:

${\displaystyle X\cdot Y=0}$

${\displaystyle X+Y=1}$

${\displaystyle X\cdot Z=0}$

${\displaystyle X+Z=1}$

da cui, sfruttando l'elemento neutro e sostituendo, ricaviamo

${\displaystyle Y=Y\cdot 1=Y\cdot (X+Z)=X\cdot Y+Y\cdot Z=0+YZ=YZ}$

${\displaystyle Z=Z\cdot 1=Z\cdot (X+Y)=X\cdot Z+Y\cdot Z=0+YZ=YZ}$

quindi ${\displaystyle Y=Z}$ ossia

${\displaystyle {\overline {a}}+{\overline {b}}={\overline {(a\cdot b)}}.}$

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, 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

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