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:
- Prima legge: Il complementare dell’unione è l’intersezione dei complementari. (A \cup B)^c = A^c \cap B^c
- 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):
- \neg(P \lor Q) \iff (\neg P \land \neg Q)
- \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.