Teoremi 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  .

È immediata la generalizzazione a un numero   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

Prima di passare alla dimostrazione è utile annotare alcune proprietà e definizioni dell'algebra booleana; si considerino  ,   e   tre variabili booleane:

1)   e, viceversa,  

2)   è la negazione logica di  

3)   (due negazioni logiche si elidono così che una variabile negata due volte equivale alla variabile stessa non negata)

4)  

5)  

6)  

7)  

8)  

9)  

10)  

11)   (notare come questa proprietà sia valida solamente nell'algebra booleana e non nella comune algebra)


DIMOSTRAZIONE:

I)  

(Si applica la proprietà 11)

 

(Si applica la proprietà 8)

 

(Si applica la proprietà 6)

 

(Si applica la proprietà 4)

 


II)  

(Si applica la proprietà 10)

 

(Si applica la proprietà 9)

 

(Si applica la proprietà 7)

 

(Si applica la proprietà 5)

 


Sia ora   ; otteniamo da I) e II) rispettivamente le equazioni:

I-bis)  

II-bis)  


Unendo le proprietà 6) e 7) rispettivamente alle equazioni I-bis) e II-bis) si possono impostare i due sistemi equivalenti:

s1)  

s2)  


Adoperando nuovamente la sostituzione   e, successivamente, la proprietà 3), si ottiene infine:

 

c.v.d.

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