Quali sono le leggi di De Morgan?

Le statistiche matematiche a volte richiedono l'uso della teoria degli insiemi. Le leggi di De Morgan sono due affermazioni che descrivono le interazioni tra varie operazioni di teoria degli insiemi. Le leggi sono quelle per ogni due set UN e B:

1. (UN ∩ B)^C = UN^C U B^C.
2. (UN U B)^C = UN^C ∩ B^C.

Dopo aver spiegato cosa significa ciascuna di queste affermazioni, vedremo un esempio di ciascuna di queste che viene utilizzata.

Imposta operazioni teoriche

Per capire cosa dicono le Leggi di De Morgan, dobbiamo ricordare alcune definizioni di operazioni di teoria degli insiemi. In particolare, dobbiamo conoscere l'unione e l'intersezione di due insiemi e il complemento di un insieme.

Le leggi di De Morgan riguardano l'interazione tra unione, intersezione e complemento. Richiama questo:

• L'intersezione degli insiemi UN e B è costituito da tutti gli elementi comuni a entrambi UN e B. L'intersezione è indicata da UN ∩ B.
• L'unione dei set UN e B è costituito da tutti gli elementi che in entrambi UN o B, compresi gli elementi in entrambi i set. L'intersezione è indicata da A U B.
• Il complemento del set UN è costituito da tutti gli elementi che non sono elementi di UN. Questo complemento è indicato con A^C.

Ora che abbiamo ricordato queste operazioni elementari, vedremo la dichiarazione delle Leggi di De Morgan. Per ogni coppia di set UN e B noi abbiamo:

1. (UN ∩ B)^C = UN^C U B^C
2. (UN U B)^C = UN^C ∩ B^C

Queste due affermazioni possono essere illustrate mediante l'uso dei diagrammi di Venn. Come visto di seguito, possiamo dimostrare usando un esempio. Per dimostrare che queste affermazioni sono vere, dobbiamo dimostrarle usando le definizioni delle operazioni di teoria degli insiemi.

Esempio delle leggi di De Morgan

Ad esempio, considera l'insieme di numeri reali da 0 a 5. Scriviamo questo in notazione di intervallo [0, 5]. All'interno di questo set abbiamo UN = [1, 3] e B = [2, 4]. Inoltre, dopo aver applicato le nostre operazioni elementari abbiamo:

• Il complemento UN^C = [0, 1) U (3, 5]
• Il complemento B^C = [0, 2) U (4, 5]
• L'Unione UN U B = [1, 4]
• L'intersezione UN ∩ B = [2, 3]

Iniziamo calcolando l'unione UN^C U B^C.  Vediamo che l'unione di [0, 1) U (3, 5] con [0, 2) U (4, 5] è [0, 2) U (3, 5]. L'intersezione UN ∩ B è [2, 3]. Vediamo che il complemento di questo set [2, 3] è anche [0, 2) U (3, 5]. In questo modo abbiamo dimostrato che UN^C U B^C = (UN ∩ B)^C.

Ora vediamo l'intersezione di [0, 1) U (3, 5] con [0, 2) U (4, 5] è [0, 1) U (4, 5]. Vediamo anche che il complemento di [ 1, 4] è anche [0, 1) U (4, 5]. In questo modo lo abbiamo dimostrato UN^C ∩ B^C = (UN U B)^C.

Denominazione delle leggi di De Morgan

Nel corso della storia della logica, persone come Aristotele e William of Ockham hanno rilasciato dichiarazioni equivalenti alle Leggi di De Morgan. 

Le leggi di De Morgan prendono il nome da Augustus De Morgan, che visse dal 1806 al 1871. Sebbene non abbia scoperto queste leggi, è stato il primo a introdurre formalmente queste affermazioni usando una formulazione matematica nella logica proposizionale.