Princípio da Inclusão-Exclusão

Olá,

Hoje provaremos a validade de uma relação útil para a teoria dos conjuntos assim como para contagem chamada de ''Princípio da Inclusão-Exclusão''. Faremos aqui a demonstração para o caso mais simples (2 conjuntos numéricos) utilizando o diagrama de Venn-Euler, e, para o caso com 3 conjuntos, utilizaremos álgebra munida das propriedades dos conjuntos numéricos. Veremos que a partir destas podemos generalizar para quantos conjuntos quisermos.
  
Na sua versão mais simples, o princípio nos diz que:




Demonstração:


 Seja y o número de elementos comuns entre dois conjuntos A e B, x os elementos que pertençam a A e não a B e z os elementos que pertençam a B e não a A, temos:






 Agora para três elementos:



A primeira vista essa expressão pode assustar, não obstante, é interessante interpretá-la da seguinte maneira: A união dos 3 conjuntos é a soma dos elementos de cada conjunto não pertencente aos outros 2, somada com a diferença da soma de todas as intersecções tomadas duas a duas e posteriormente acrescida da intersecção dos 3 conjuntos.

 Demonstração:



  A partir das relações para 2 e 3 conjuntos podemos deduzir para quantos conjuntos quisermos. Por exemplo, para 2 conjuntos a união é a soma dos elementos não pertencentes ao outro subtraída da intersecção entre eles; para 3, a união é a soma dos elementos de cada conjunto não pertencente aos outros, subtraída da soma das intersecção dos elementos tomados 2 a 2 e acrescida da soma dos elementos da intersecção dos 3 conjuntos. 
  Agora para 4, podemos dizer que a a união dos 4 conjuntos é a soma de todos os elementos de cada conjunto e não pertencente ao outros, subtraída da soma das intersecções tomadas 2 a 2, somada de todas as intersecções tomadas 3 a 3 e subtraída da intersecção dos 4 conjuntos. Traduzindo (e sejam A, B, C e D os conjuntos):




E assim para 5, para 6, 7... etc.