Se riscontri problemi nella visualizzazione dei caratteri, clicca qui

Teoremi di De Morgan

Da Wikipedia, l'enciclopedia libera.

I teoremi di De Morgan, o leggi di De Morgan sono relativi alla logica booleana e stabiliscono relazioni di equivalenza tra gli operatori di congiunzione logica "and" e "or". Sono utilizzati per l'analisi di circuiti logici (elettrici, elettronici, pneumatici, comunque digitali, cioè ON-OFF).

I teoremi[modifica | modifica wikitesto]

I due teoremi sono duali:

Con riferimento a termini insiemistici il primo si enuncia affermando che se un elemento non appartiene ad per allora o non appartiene ad , o non appartiene a o non appartiene ad entrambi. Il secondo teorema si enuncia affermando che se un elemento non appartiene ad , allora non appartiene ad e non appartiene a .

L'immediata generalizzazione a un numero n di variabili:

Nella logica proposizionale possono essere formulate in vario modo:

oppure

oppure

e nella teoria degli insiemi:

oppure

e

oppure

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 wikitesto]

Exquisite-kfind.png 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[modifica | modifica wikitesto]

Dimostrazione tabellare[modifica | modifica wikitesto]

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 wikitesto]

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

Secondo teorema[modifica | modifica wikitesto]

Dimostrazione tabellare[modifica | modifica wikitesto]

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 wikitesto]

Voci correlate[modifica | modifica wikitesto]

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