Leggi di De Morgan

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Rappresentazione delle leggi di De Morgan attraverso due diagrammi di Venn. In ciascun caso l'insieme risultante è quello colorato di blu o qualche sua sfumatura

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

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

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. (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 | 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]

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica