Teoremi di De Morgan

(Reindirizzamento da Leggi di De Morgan)

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 binari, cioè ON-OFF).

I teoremiModifica

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

DimostrazioneModifica

 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 teoremaModifica

Dimostrazione tabellareModifica

             
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 algebricaModifica

Secondo teoremaModifica

Dimostrazione tabellareModifica

             
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 algebricaModifica

Voci correlateModifica

Collegamenti esterniModifica

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