Álgebra de Conjuntos

Prévia do material em texto

A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
A´lgebra de Conjuntos
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica e Estat´ıstica, UFF
Marc¸o de 2011
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Suma´rio
• A´lgebra de conjuntos.
• Provas alge´bricas.
• Diagramas gerais.
• Diagramas numerados.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Venn
• Matema´tico ingleˆs.
• Levou os diagramas a se´rio.
John Venn
(1834 – 1923)
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
A´lgebra de conjuntos
Dados:
• Letras maiu´sculas:
A,B,C , . . . ,A1,B1,C1, . . . ,An,Bn,Cn, . . .
S´ımbolos para operac¸o˜es:
∩,∪,−−
• Expresso˜es (bem formadas) envolvendo letras e s´ımbolos
para operac¸o˜es.
• Igualdade e incluso˜es entre estas operac¸o˜es.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
A´lgebra de conjuntos
Problema:
• Identificar igualdades e incluso˜es que sa˜o verdadeiras
para quaisquer conjuntos A,B,C , . . .
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas alge´bricas
Ideia:
(1) Escolher um reperto´rio de igualdades e incluso˜es que sa˜o
intuitivamente verdadeiras para quaisquer conjuntos
A,B,C , . . ..
(2) Provar as outras igualdades e incluso˜es a partir daquelas
listadas em (1), usando as propriedades ba´sicas da
igualdade e da inclusa˜o.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Problema 1
Apresente uma prova alge´brica das seguintes inclusa˜o e
igualdade:
(a) A ∪ B ⊆ A ∪ B
(b) A ∩ B ∪ C = (A ∩ B) ∩ (A ∩ C )
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas alge´bricas
Igualdades e incluso˜es intuitivamente verdadeiras para
quaisquer conjuntos A,B,C :
(1) Associatividade de ∩ e de ∪:
A ∩ (B ∩ C ) = (A ∩ B) ∩ C
A ∪ (B ∪ C ) = (A ∪ B) ∪ C
(2) Comutatividade de ∩ e de ∪:
A ∩ B = B ∩ A
A ∪ B = B ∪ A
(3) Idempoteˆncia de ∩ e de ∪:
A ∩ A = A
A ∪ A = A
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas alge´bricas
(4) Elemento neutro de ∩ e de ∪:
A ∩ U = A
A ∪ ∅ = A
(5) Elemento zero de ∩ e de ∪:
A ∩ ∅ = ∅
A ∪ U = U
(6) Distributividade de ∩ sobre ∪, e de ∪ sobre ∩:
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas alge´bricas
(7) Involutividade de −−:
A = A
(8) Leis de De Morgan:
A ∩ B = A ∪ B
A ∪ B = A ∩ B
(9) Leis de absorc¸a˜o:
A ∩ (A ∪ B) = A
A ∪ (A ∩ B) = A
(10) Definic¸o˜es de ∅ e U :
A ∩ A = ∅
A ∪ A = U
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas alge´bricas
(11) ∅ = U
(12) U = ∅
(13) A ∩ B ⊆ A
(14) A ⊆ A ∪ B
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas alge´bricas
Propriedades ba´sicas da igualdade
(para quaisquer conjuntos A,B,C ):
(1) Reflexividade:
A = A.
(2) Simetria:
Se A = B, enta˜o B = A.
(3) Transitividade:
Se A = B e B = C , enta˜o A = C .
(4) Substitutividade:
Se A = B, enta˜o se substituimos qualquer ocorreˆncia de A
por uma ocorreˆncia de B em uma expressa˜o C , obtendo
uma expressa˜o C [A← B], temos que C [A← B] ⊆ C .
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas alge´bricas
Propriedades ba´sicas da inclusa˜o
(para quaisquer conjuntos A,B,C ):
(1) Reflexividade:
A ⊆ A.
(2) Antissimetria:
Se A ⊆ B e B ⊆ A, enta˜o A = B.
(3) Transitividade:
Se A ⊆ B e B ⊆ C , enta˜o A ⊆ C .
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Problema 2
Apresente uma prova alge´brica das seguintes igualdades:
(a) (A ∪ B) ∩ B = A ∩ B
(b) A ∩ B ∪ (B ∩ C ) = A ∪ B
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas alge´bricas
Dados os conjuntos A e B, tais que A = B,
uma prova alge´brica da igualdade deve seguir
o seguinte modelo de redac¸a˜o:
1. Escreva “Prova:” ao iniciar a prova;
2. Escreva
A = C1 (justificativa 1)
= C2 (justificativa 2)
= C3 (justificativa 3)
...
...
...
= Cn (justificativa n)
= B (justificativa n + 1)
onde “(justificativa i)” e´ uma indicac¸a˜o de quais
propriedades ba´sicas ou hipo´teses do problema justificam a
igualdade na linha i .
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas alge´bricas
Dados os conjuntos A e B, tais que A ⊆ B,
uma prova alge´brica da inclusa˜o deve seguir
o seguinte modelo de redac¸a˜o:
1. Escreva “Prova:” ao iniciar a prova;
2. Escreva
A ⊆ C1 (justificativa 1)
⊆ C2 (justificativa 2)
⊆ C3 (justificativa 3)
...
...
...
⊆ Cn (justificativa n)
⊆ B (justificativa n + 1)
onde “(justificativa i)” e´ uma indicac¸a˜o de quais
propriedades ba´sicas ou hipo´teses do problema justificam a
inclusa˜o na linha i .
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas gerais
• Diagramas gerais sa˜o diagramas que representam todas as
possibilidades de relac¸o˜es de inclusa˜o entre um
determinado nu´mero de conjuntos.
• Em um diagrama geral os conjuntos sa˜o representados por
regio˜es conexas, simples e fechadas do plano. Estas regio˜es
sa˜o usualmente representadas por c´ırculos ou elipses.
@GAFBECD @GAFBECD
na˜o conexas
HOINJMKL '!&"%#$
na˜o simples
@GFECD
na˜o fechada
• Dados n conjuntos, sempre existe um diagrama geral para
eles. Estes diagramas podem ser dif´ıceis de desenhar,
quando n ≥ 5.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas gerais
Diagrama geral para 1 conjunto:
U
pwqvrust
A
As regio˜es representadas sa˜o A e A.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas gerais
Diagrama geral para 2 conjuntos:
U
pwqvrust
A
pwqvrust
B
As regio˜es representadas sa˜o A ∪ B, A ∩ B, B ∩ A e A ∩ B.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramasnumerados
Diagramas gerais
Diagrama geral para 3 conjuntos:
U
pwqvrust
A
pwqvrust
B
pwqvrust
C
As regio˜es representadas sa˜o A ∪ B ∪ C , A∩B ∪ C , B ∩A ∪ C ,
C ∩ A ∪ B, A ∩ B ∩ C , A ∩ C ∩ B, B ∩ C ∩ A, e A ∩ B ∩ C .
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas gerais
Quantas regio˜es tera´ um diagrama geral para 4 conjuntos?
Quais sa˜o elas?
E para 5 conjuntos?
Voceˆ seria capaz de generalizar este resultado para um n
gene´rico? Boa sorte!
http://www.combinatorics.org/Surveys/ds5/VennEJC.html
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
Um diagrama numerado para n conjuntos e´ um diagrama geral
para n conjuntos onde cada regia˜o esta´ rotulada com um dos
nu´meros 1, 2, 3, . . . , 2n.
Que nu´mero rotula cada regia˜o na˜o e´ muito importante. Mas
vamos seguir o padra˜o exemplificado nos exemplos que seguem.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
Diagrama numerado para 1 conjunto:
U
pwqvrust
A
1
2
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
Diagrama numerado para 2 conjuntos:
U
1
pwqvrust
A
2 pwqvrust
B
34
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
Diagrama numerado para 3 conjuntos:
U
1
pwqvrust
A
2 pwqvrust
B
3
pwqvrust
C
4
5
76
8
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
Diagramas numerados podem ser usados para:
1. provar que uma inclusa˜o ou igualdade e´ verdadeira, para
todos os conjuntos;
2. provar que uma inclusa˜o ou igualdade e´ falsa, exibindo
conjuntos (finitos!) que falsificam a inclusa˜o ou igualdade.
Primeiramente, vamos ver alguns exemplos.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
Exemplo 1
Para verificar se A ∩ B ⊆ A ∪ B, para todos os conjuntos A e
B, fazemos o seguinte:
1. Consideramos o diagrama numerado para 2 conjuntos.
U
1
pwqvrust
A
2 pwqvrust
B
34
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
2. Calculamos uma sequeˆncia de ro´tulos r(A ∩ B) que
corresponde a` regia˜o A ∩ B.
U
1
pwqvrust
A
2 pwqvrust
B
34
r(A ∩ B) = 4
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
3. Calculamos uma sequeˆncia de ro´tulos r(A ∪ B) que
corresponde a` regia˜o A ∪ B.
U
1
pwqvrust
A
2 pwqvrust
B
34
r(A ∪ B) = 234
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
4. Comparamos as sequeˆncias r(A ∩ B) = 4 e
r(A ∪ B) = 234.
Como todos os ro´tulos que esta˜o em r(A ∩ B) = 4 esta˜o
tambe´m em r(A ∪ B) = 234, temos que
a inclusa˜o e´ verdadeira para quaisquer conjuntos.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Provas por diagramas numerados
Dados os conjuntos A e B, tais que A ⊆ B,
uma prova por diagramas numerados da inclusa˜o deve seguir
o seguinte modelo de redac¸a˜o:
1. Escreva “Prova:” ao iniciar a prova;
2. Desenhe o diagrama numerado para n conjuntos, onde n e´
a quantidade de letras maiu´sculas que ocorrem na
apresentac¸a˜o dos conjuntos A e B.
3. Explique, ta˜o detalhadamente quanto achar necessa´rio,
por que todos os ro´tulos da sequeˆncia de ro´tulos associada
a A ocorrem na sequeˆncia de ro´tulos associada a B.
4. Escreva “ ” para terminar a prova.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
Exemplo 2
Para verificar se A ∩ B ⊆ A ∩ B, para todos os conjuntos A e
B, fazemos o seguinte:
1. Consideramos o diagrama numerado para 2 conjuntos.
U
1
pwqvrust
A
2 pwqvrust
B
34
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
2. Calculamos uma sequeˆncia de ro´tulos r(A ∩ B) que
corresponde a` regia˜o A ∩ B.
U
1
pwqvrust
A
2 pwqvrust
B
34
r(A ∩ B) = 4
r(A ∩ B) = 123
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
3. Calculamos uma sequeˆncia de ro´tulos r(A ∩ B) que
corresponde a` regia˜o A ∪ B.
U
1
pwqvrust
A
2 pwqvrust
B
34
r(A) = 24
r(A) = 13
r(B) = 34
r(B) = 12
r(A ∩ B) = 1
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
4. Comparamos as sequeˆncias r(A ∩ B) = 123 e
r(A ∩ B) = 1.
Como nem todos os ro´tulos em r(A ∩ B) = 123 aparecem
em r(A ∩ B) = 1, temos que
existem conjuntos para os quais a inclusa˜o e´ falsa.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
Usando o diagrama numerado, podemos obter um
contra-exemplo para a inclusa˜o A ∩ B ⊆ A ∩ B, isto e´,
podemos obter conjuntos A e B em um universo U tais que
A ∩ B 6⊆ A ∩ B.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Diagramas numerados
Contra-exemplo:
Considere o universo como o conjunto de todos os ro´tulos:
U = {1, 2, 3, 4}
Defina A e B como sendo os conjuntos cujos elementos sa˜o os
ro´tulos que ocorrem nas sequeˆncias r(A) e r(B):
A = {2, 4} e B = {3, 4}
Neste caso, temos que A ∩ B = {1, 2, 3} 6⊆ {1} = A ∩ B.
A´lgebra de
Conjuntos
Renata de
Freitas e
Petrucio
Viana
A´lgebra de
conjuntos
Provas
alge´bricas
Diagramas
gerais
Diagramas
numerados
Exerc´ıcios
Refac¸a os exerc´ıcios indicados nos slides das aulas 1, 2, 4 e 5,
utilizando provas alge´bricas e provas por diagramas numerados.
	Álgebra de conjuntos
	Provas algébricas
	Diagramas gerais
	Diagramas numerados