Princípio da Inclusão-Exclusão
PiR2 :: Recursos extras :: Demonstrações
Página 1 de 1
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:
=\&hash;A+\&hash;B-\&hash;(A\cap&space;B)})
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:

\\\&hash;B=(y+z)\\\&hash;(A\cap&space;B)=y\\\&hash;A+\&hash;B=x+2.y+z\\\&hash;A+\&hash;B-\&hash;(A\cap&space;B)=x+2.y+z-y=x+y+z\\\\\text{Ora,&space;mas&space;x+y+z&space;e&space;a&space;propria&space;uniao&space;de&space;A&space;e&space;B}\\\\\&hash;(A\cup&space;B)=x+y+z\\\therefore&space;\\\boxed{&hash;(A\cup&space;B)=\&hash;A+\&hash;B-\&hash;(A\cap&space;B)})
Agora para três elementos:
![\boxed{\#(A\cup B\cup C)=\#A+\#B+\#C-[\#(A\cap B)+\#(A\cap C)+\#(B\cap C)]+\#(A\cap B\cap C)}](https://latex.codecogs.com/gif.latex?\boxed{\&hash;(A\cup&space;B\cup&space;C)=\&hash;A+\&hash;B+\&hash;C-[\&hash;(A\cap&space;B)+\&hash;(A\cap&space;C)+\&hash;(B\cap&space;C)]+\&hash;(A\cap&space;B\cap&space;C)})
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\cup B\cup C)=\#[(A\cup B)\cup C]=\\\#(A\cup B)+\#C-\#[(A\cup B)\cap C]=\\\#A+\#B-\#(A\cap B)+\#C-\#[(A\cap C)\cup (B\cap C)]=\\\#A+#B-#(A\cap B)+\#C-\#(A\cap C)-\#(B\cap C)\\\therefore \\\#(A\cup B\cup C)=\#A+\#B+\#C-[\#(A\cap B)+\#(A\cap C)+\#(B\cap C)]+\#(A\cap B\cap C)](https://latex.codecogs.com/gif.latex?\&hash;(A\cup&space;B\cup&space;C)=\&hash;[(A\cup&space;B)\cup&space;C]=\\\&hash;(A\cup&space;B)+\&hash;C-\&hash;[(A\cup&space;B)\cap&space;C]=\\\&hash;A+\&hash;B-\&hash;(A\cap&space;B)+\&hash;C-\&hash;[(A\cap&space;C)\cup&space;(B\cap&space;C)]=\\\&hash;A+&hash;B-&hash;(A\cap&space;B)+\&hash;C-\&hash;(A\cap&space;C)-\&hash;(B\cap&space;C)\\\therefore&space;\\\&hash;(A\cup&space;B\cup&space;C)=\&hash;A+\&hash;B+\&hash;C-[\&hash;(A\cap&space;B)+\&hash;(A\cap&space;C)+\&hash;(B\cap&space;C)]+\&hash;(A\cap&space;B\cap&space;C))
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):
![\#(A\cup B\cup C\cup D)=\#A+\#B+\#C+\#D-[\#(A\cap B)+\#(A\cap C)+\#(A\cap D)+\#(B\cap C)+\#(B\cap D)+\#(C\cap D)]+\[\#(A\cap B\cap C)+\#(A\cap B\cap D)+\#(A\cap C\cap D)+\#(B\cap C\cap D)]-\#(A\cap B\cap C\cap D)](https://latex.codecogs.com/gif.latex?\&hash;(A\cup&space;B\cup&space;C\cup&space;D)=\&hash;A+\&hash;B+\&hash;C+\&hash;D-[\&hash;(A\cap&space;B)+\&hash;(A\cap&space;C)+\&hash;(A\cap&space;D)+\&hash;(B\cap&space;C)+\&hash;(B\cap&space;D)+\&hash;(C\cap&space;D)]+\[\&hash;(A\cap&space;B\cap&space;C)+\&hash;(A\cap&space;B\cap&space;D)+\&hash;(A\cap&space;C\cap&space;D)+\&hash;(B\cap&space;C\cap&space;D)]-\&hash;(A\cap&space;B\cap&space;C\cap&space;D))
E assim para 5, para 6, 7... etc.

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.
Willian Honorio- Matador
- Mensagens : 1271
Data de inscrição : 27/04/2016
Idade : 26
Localização : São Paulo
PiR2 :: Recursos extras :: Demonstrações
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos
|
|