Teoremi di De Morgan

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

I teoremi di De Morgan, o leggi di De Morgan sono relativi alla logica booleana. Sono utilizzati per l'analisi di circuiti logici (elettrici, elettronici, pneumatici, comunque digitali, cioè ON-OFF).

I teoremi[modifica | modifica sorgente]

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.

L'immediata 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[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi 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[modifica | modifica sorgente]

dimostrazione tabellare[modifica | modifica sorgente]

 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[modifica | modifica sorgente]

Questa relazione vale per dualità all'altra dimostrazione, quindi rimandiamo alla dimostrazione algebrica del secondo teorema.

Secondo teorema[modifica | modifica sorgente]

dimostrazione tabellare[modifica | modifica sorgente]

 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

dimostrazione algebrica[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

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