Principio di inclusione ed esclusione
Da Wikipedia, l'enciclopedia libera.
Il termine principio di inclusione ed esclusione viene usato per denotare una formula che permette di esprimere la cardinalità di un insieme individuato come unione di insiemi finiti mediante le cardinalità di intersezioni di questi insiemi, cardinalità inferiori e quindi tendenzialmente più facili da determinare.
Denotiamo con |A| la cardinalità di un insieme A e consideriamo una famiglia finita di insiemi finiti :A1,A2,...,An Per la cardinalità dell'unione di tale famiglia si ha
Nel caso n=2 la formula si riduce a quella, molto intuitiva e ricavabile dalle definizioni, esprimibile come
Nel caso n=3 il principio si esprime con l'uguaglianza
Questa si dimostra servendosi più volte della precedente e della distributività della intersezione rispetto alla unione:
Anch'essa è interpretabile senza difficoltà mediante un diagramma di Eulero - Venn.
Nel caso generale si dimostra per induzione su n: si assume vera per una famiglia di n insiemi e si manipola l'espressione per la famiglia estesa con An + 1 servendosi delle formule relativa a famiglie con al più n insiemi.
Il principio è stato utilizzato da Nicolaus Bernoulli (II) (1695-1626); la formula viene attribuita ad Abraham de Moivre (1667-1754); per il suo utilizzo e per la comprensione della sua portata vengono ricordati Joseph Sylvester (1814-1897) ed Henri Poincaré (1854-1912).
Vedi anche
- Formula di inversione di Moebius-Rota
- Disuguaglianza di Bonferroni
- Teorema della probabilità totale
- Reticolo booleano