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 \dots} = \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 \land b) = \neg a \lor \neg b \\ \neg (a \lor b) = \neg a \land \neg b \end{matrix}

oppure

\begin{matrix} \overline{(a \land b)} = \overline{a} \lor \overline{b} \\ \overline{(a \lor b)} = \overline{a} \land \overline{b} \end{matrix}

oppure

\begin{matrix} \neg (P \land Q) = (\neg P) \lor (\neg Q) \\ \neg (P \lor Q) = (\neg P) \land (\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

Template:Vedi anche 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 \lor q$	$\overline{p \lor q}$	$\overline{p} \land \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 $a$ , $b$ e $c$ tre variabili booleane:

$\overline{0} = 1$ e, viceversa, $\overline{1} = 0$
$\overline{a}$ è la negazione logica di $a$
$a = \overline{\overline{a}}$ (due negazioni logiche si elidono così che una variabile negata due volte equivale alla variabile stessa non negata)
$a + 1 = 1$
$a \cdot 0 = 0$
$a + \overline{a} = 1$
$a \cdot \overline{a} = 0$
$(a + b) + c = a + (b + c)$
$(a \cdot b) \cdot c = a \cdot (b \cdot c)$
$(a + b) \cdot c = (a \cdot c) + (b \cdot c)$
$a + (b \cdot c) = (a + b) \cdot (a + c)$ (notare come questa proprietà sia valida solamente nell'algebra booleana, non nella comune algebra)

DIMOSTRAZIONE:

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

(Si applica la proprietà 11)

= [(a + b) + \overline{a}] \cdot [(a + b) + \overline{b}] =

(Si applica la proprietà 8)

= [(a + \overline{a}) + b] \cdot [(b + \overline{b}) + a] =

(Si applica la proprietà 6)

= [(1) + b] \cdot [(1) + a] =

(Si applica la proprietà 4)

= 1 + 1 = 1 .

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

(Si applica la proprietà 10)

= a \cdot (\overline{a} \cdot \overline{b}) + b \cdot (\overline{a} \cdot \overline{b}) =

(Si applica la proprietà 9)

= \overline{b} \cdot (a \cdot \overline{a}) + \overline{a} \cdot (b \cdot \overline{b}) =

(Si applica la proprietà 7)

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

(Si applica la proprietà 5)

= 0 + 0 = 0

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

I-bis) $(a + b) + c = 1$

II-bis) $(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) ${\begin{matrix} (a + b) + \overline{(a + b)} = 1 \\ (a + b) + c = 1 \end{matrix} ⟹ c = \overline{(a + b)} ⟹ \overline{c} = (a + b) .$

s2) ${\begin{matrix} (a + b) \cdot \overline{(a + b)} = 0 \\ (a + b) \cdot c = 0 \end{matrix} ⟹ c = \overline{(a + b)} ⟹ \overline{c} = (a + b) .$

Adoperando nuovamente la sostituzione $c = \overline{a} \cdot \overline{b}$ e, successivamente, la proprietà 3), si ottiene infine:

\overline{c} = (a + b) ⟹ \overline{\overline{a} \cdot \overline{b}} = (a + b) ⟹ \overline{a} \cdot \overline{b} = \overline{(a + b)} .

Secondo teorema

Dimostrazione tabellare

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

(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

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

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

(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

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

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

(a \cdot a \cdot b) = 0;

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

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

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

Le relazioni prima ottenute si possono riscrivere come:

X \cdot Y = 0

X + Y = 1

X \cdot Z = 0

X + Z = 1

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

Y = Y \cdot 1 = Y \cdot (X + Z) = X \cdot Y + Y \cdot Z = 0 + Y Z = Y Z

Z = Z \cdot 1 = Z \cdot (X + Y) = X \cdot Z + Y \cdot Z = 0 + Y Z = Y Z

quindi $Y = Z$ ossia

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

Voci correlate

Collegamenti esterni

Template:Portale

Leggi di De Morgan

Indice

I teoremi

Dimostrazione

Primo teorema

Dimostrazione tabellare

Dimostrazione algebrica

Secondo teorema

Dimostrazione tabellare

Dimostrazione algebrica

Voci correlate

Collegamenti esterni

Menu di navigazione

Leggi di De Morgan

I teoremi

Dimostrazione

Primo teorema

Dimostrazione tabellare

Dimostrazione algebrica

Secondo teorema

Dimostrazione tabellare

Dimostrazione algebrica

Voci correlate

Collegamenti esterni

Menu di navigazione

Ricerca