Leggi di De Morgan

teoremi relativi alla logica booleana

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 regole logiche.

I teoremi modifica

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

Dimostrazione modifica

  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

Dimostrazione tabellare modifica

             
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

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, 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 teorema modifica

Dimostrazione tabellare modifica

             
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

Voci correlate modifica

Collegamenti esterni modifica

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