Il principio di inclusione-esclusione è una formula del calcolo combinatorio che permette di calcolare correttamente la cardinalità dell’unione di più insiemi (o la probabilità dell’unione di più eventi), evitando di contare più volte gli elementi che appartengono alle intersezioni.
Caso di due insiemi
Per due insiemi A e B, la cardinalità dell’unione è la somma delle cardinalità meno la cardinalità dell’intersezione (che altrimenti sarebbe contata due volte): |A \cup B| = |A| + |B| - |A \cap B|
Caso di tre insiemi
|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|
Caso generale (Formula di Poincaré)
Per n insiemi A_1, \dots, A_n, la formula alterna somme e sottrazioni delle intersezioni di ordine crescente: | \bigcup_{i=1}^n A_i | = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} | \bigcap_{i=1}^n A_i |
Significato Ingegneristico
- Analisi di Affidabilità di Rete: Se un sistema critico funziona se almeno uno di n componenti è attivo, il principio di inclusione-esclusione permette di calcolare la probabilità di successo totale conoscendo le probabilità di funzionamento dei singoli componenti e delle loro interdipendenze (guasti a causa comune).
- Sicurezza Informatica: Utilizzato per calcolare la copertura di diversi strumenti di rilevamento intrusioni (IDS) che possono identificare lo stesso attacco (overlapping coverage).
- Informatica Teorica: È alla base di algoritmi per il calcolo del numero di grafi con determinate proprietà o per la risoluzione di problemi di soddisfacibilità (SAT).
Vedi anche: Operazioni tra Insiemi, Calcolo Combinatorio.