Leggi di De Morgan

Le leggi di De Morgan sono due identità fondamentali che descrivono come l’operazione di complementazione interagisce con l’unione e l’intersezione di insiemi (o, in logica, come la negazione interagisce con la congiunzione e la disgiunzione).

Enunciato Insiemistico

Dati due insiemi $A$ e $B$ in un universo $\Omega$:

1. Prima legge: Il complementare dell’unione è l’intersezione dei complementari. $(A \cup B)^c = A^c \cap B^c$
2. Seconda legge: Il complementare dell’intersezione è l’unione dei complementari. $(A \cap B)^c = A^c \cup B^c$

Enunciato Logico

In termini di logica proposizionale, indicando con $\neg$ la negazione, con $\lor$ la disgiunzione (OR) e con $\land$ la congiunzione (AND):

1. $\neg(P \lor Q) \iff (\neg P \land \neg Q)$
2. $\neg(P \land Q) \iff (\neg P \lor \neg Q)$

Significato Ingegneristico

• Elettronica Digitale: Le leggi di De Morgan permettono di implementare qualsiasi funzione logica utilizzando esclusivamente porte NAND o NOR. Questo è cruciale nella produzione di microchip, dove l’uso di un unico tipo di porta logica semplifica il layout del silicio e riduce i costi.
• Semplificazione di Circuiti: Sono usate per ridurre il numero di componenti in un circuito digitale, trasformando espressioni complesse in forme più semplici e meno dispendiose in termini di area e consumo energetico.
• Programmazione: In informatica, permettono di scrivere clausole condizionali (if) più leggibili e di ottimizzare i compilatori nella gestione delle espressioni booleane.

Vedi anche: Operazioni tra Insiemi, Algebra di Boole.