Álgebra de conjuntos e diagramasmd

Prévia do material em texto

Novo Módulo de MD 2013 Unidade 1
Matemática Discreta
Tópicos da Teoria dos Conjuntos
Texto da Semana 10, Parte 2
Álgebra de Conjuntos e Diagramas Gerais
Sumário
1 Álgebra de conjuntos 2
1.1 Observações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Diagramas gerais 3
2.1 Observações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Diagramas numerados 6
Neste texto, apresentamos um método baseado no uso de diagramas para re-
solver o Problema da Identidade Conjuntista, ou seja, o problema de, dada uma
igualdade conjuntista, determinar se ela é uma identidade ou não. Em particular,
abordamos os conceitos de diagrama geral, diagrama numerado, comparação de dia-
grama e contra-exemplo baseado em diagrama. Após estudarmos os conteúdos deste
texto, vamos ser capazes de:
– entender o que é um diagrama geral para n conjuntos;
– desenhar diagramas gerais para 1, 2, 3 e 4 conjuntos;
– entender o que é um diagrama geral numerado para n conjuntos;
– aplicar o Método dos Diagramas Gerais para resolver o problema de decidir se
uma dada igualdade é uma identidade.
1
Novo Módulo de MD 2013 Unidade 1
1 Álgebra de conjuntos
Recordamos que:
Uma expressão conjuntista é uma expressão formada a partir das constantes
∅ , U
e das variáveis para conjuntos
A , B , C , . . . , X , Y , Z
indexadas ou não, por aplicações sucessivas das operações
∩ , ∪ , c
Além disso:
Uma igualdade conjuntista é um enunciado da forma
E1 = E2
onde E1 e E2 são expressões conjuntistas quaisquer.
A novidade é que vamos, também considerar as inclusões conjuntistas :
Uma inclusão conjuntista é um enunciado da forma
E1 ⊆ E2
onde E1 e E2 são expressões conjuntistas quaisquer.
Exemplo 1 (a) Inclusões envolvendo conjunto vazio e conjunto universo:
∅ ∪ A ⊆ A , ∅ ∪ A ∪B ⊆ A ∪B , ∅ ∪ A ∪B ∪ C ⊆ A ∪B ∪ C
(b) Inclusões envolvendo interseção e união:
A ∩B ⊆ A ∪B , A ∪B ⊆ A ∩B , (A ∩B) ∪ C ⊆ (A ∪B) ∩ C
(c) Inclusões envolvendo complementação:
Ac ⊆ ∅ , (A ∩B)c ⊆ Ac , (A ∩B ∩ C)c = Ac ∩Bc
2
Novo Módulo de MD 2013 Unidade 1
A Álgebra de Conjuntos é o estudo das inclusões e igualdades conjuntistas.
O principal problema da Álgebra de Conjuntos é, identificar as igualdades e
inclusões conjuntistas que são verdadeiras para quaisquer conjuntos A,B,C, . . .
1.1 Observações
Observação 1 Já vimos um método para resolver a parte deste problema referente
às igualdades conjuntistas. O método se baseia essencialmente em:
1. traduzir as igualdades em enunciados moleculares formados a partir de enun-
ciados atômicos simples pela aplicação de conectivos (e quantificadores);
2. usar tabelas de avaliação para decidir certas equivalências.
Embora a aplicação deste método não apresente dificuldades, podemos dizer que ele
é um método lógico, pois se baseia diretamente na lógica dos conectivos e, por esta
razão, não está muito próximo da maneira usual como os matemáticos justificam
igualdades conjuntistas.
Matemáticos usam conectivos (e quantificadores), mas não de maneira direta
por meio de tabelas. Eles preferem textos explicativos como aqueles que usamos no
Texto da Semana 9, para justificar as igualdades e inclusões verdadeiras, para todos
os conjuntos.
2 Diagramas gerais
Vamos, agora, estudar outro método para resolver o problema de, dada uma
igualdade ou inclusão conjuntista, decidir se ela é V para todos os conjuntos. O
método que vamos empregar também não está muito próximo da maneira como os
matemáticos gostam de resolver este problema, por usar diagramas e não textos
explicativos. Mas, como veremos, ele tem uma vantagem sobre a simples tentativa
de escrever um texto explicando que uma igualdade ou inclusão acontece.
3
Novo Módulo de MD 2013 Unidade 1
Diagramas gerais são diagramas que representam todas as possibilidades de
um objeto do universo pertencer aos n conjuntos.
Em um diagrama geral o universo é representado por um retângulo.
Em um diagrama geral os conjuntos que estão sendo considerados são repre-
sentados por regiões conexas, delimitadas por curvas simples e fechadas do
plano, interiores ao retângulo que representa o universo.
não conexa não simples não fechada
Sempre que posśıvel, as regiões do diagrama que representam os conjuntos são
delimitadas por ćırculos ou elipses.
Exemplo 2 (a) Um diagrama geral para 1 conjunto, A, pode ser desenhado como
um retângulo que representa o universo U , possuindo em seu interor 1 ćırculo cujo
interior representa A:
U
A
As regiões representadas no diagrama são:
1. Ac : interior ao retângulo e exterior ao ćırculo;
2. A : interior ao retângulo e interior ao ćırculo.
(b) Um diagrama geral para 2 conjuntos, A e B, pode ser desenhado como um
retângulo que representa o universo U , possuindo em seu interior 2 ćırculos que se
sobrepõem: o interior de um representa A e o interior do outro representa B:
U
A B
As regiões representadas no diagrama são:
1. (A ∪B)c : interior ao retângulo e exterior aos dois ćırculos;
4
Novo Módulo de MD 2013 Unidade 1
2. A ∩ Bc : interior ao retângulo, interior ao ćırculo da esquerda e exterior ao
ćırculo da direita;
3. B ∩ Ac : interior ao retângulo, exterior ao ćırculo da esquerda e interior ao
ćırculo da direita;
4. A ∩B : interior ao retângulo e interior aos dois ćırculos.
(c) Um diagrama geral para 3 conjuntos, A, B e C, pode ser desenhado como um
retângulo que representa o universo U , possuindo em seu interior 3 ćırculos que se
sobrepõem dois-a-dois: o interior de um representa A, o interior do outro representa
B, e o interior do último representa C:
U
A B
C
As regiões representadas no diagrama são:
1. (A ∪B ∪ C)c : interior ao retângulo e exterior aos 3 ćırculos;
2. A ∩ (B ∪ C)c : interior ao retângulo, interior ao ćırculo superior da esquerda
e exterior aos outros dois ćırculos;
3. B ∩ (A ∪ C)c : interior ao retângulo, interior ao ćırculo superior da direita e
exterior aos outros dois ćırculos;
4. C ∩ (A ∪B)c : interior ao retângulo, interior ao ćırculo inferior e exterior aos
outros dois ćırculos;
5. A∩B∩Cc : interior ao retângulo, comum aos dois ćırculos superiores e exterior
ao ćırculo inferior;
6. A ∩ C ∩ Bc : interior ao retângulo, comum aos ćırculos superior da esquerda
e inferior, e exterior ao ćırculo superior da direita;
7. B ∩ C ∩ Ac : interior ao retângulo, comum aos ćırculos superior da direita e
inferior, e exterior ao ćırculo superior da esquerda;
8. A∩B∩C : interior ao retângulo e interior aos três ćırculos, simultaneamente.
5
Novo Módulo de MD 2013 Unidade 1
2.1 Observações
Observação 2 O próximo passo, no estudo dos diagramas gerais seria investigar a
construção de diagramas gerais para 4, 5, 6 e, até mesmo, uma quantidade finita
qualquer de conjuntos. Não vamos entrar em detalhes quanto a este problema
aqui mas, apenas, observar que o seguinte diagrama é um diagrama geral para 4
conjuntos.
A B
C
D
U
Observe que o diagrama acima é constrúıdo pela superposição de 4 elipses. Na ver-
dade, é imposśıvel construir um diagrama geral para 4 conjuntos pela superposição
de 4 ćırculos.
Observação 3 Em 1880, o Lógico inglês John Venn (1834 – 1923) apresentou
um procedimento cuja aplicação permite desenhar diagramas gerais para qualquer
número de conjuntos.
Teorema de Venn, 1880
Dados n conjuntos, sempre existe um diagrama geral para eles, isto é, para
todo número natural n, existe um diagrama formado por um retângulo que
possui em seu interior n curvas conexas, simples e fechadas, que representam
todas as possibilidades de um objeto do universo pertencer aos n conjuntos.
3 Diagramas numerados
Um diagrama numerado para n conjuntos é um diagrama geral para n conjun-
tos onde cada região está rotulada com um dos números 1, 2, 3, . . . , 2n.
Que número rotula cada região não é muito importante. Mas vamos sempre
seguir o padrão mostrado nos exemplosque seguem.
6
Novo Módulo de MD 2013 Unidade 1
Exemplo 3 (a) A seguinte figura é um diagrama numerado para 1 conjunto:
U
A
1
2
(b) A seguinte figura é um diagrama numerado para 2 conjuntos:
U
1
A
2
B
34
(c) A seguinte figura é um diagrama numerado para 3 conjuntos:
U
1
A
2
B
3
C
4
5
76 8
(d) A seguinte figura é um diagrama numerado para 4 conjuntos:
A B
C
D
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
U
1
Nosso principal interesse em diagramas numerados decorre do fato que eles po-
dem ser usados para decidir as inclusões e as igualdades conjuntistas de uma maneira
simples e prazeirosa!
7
Novo Módulo de MD 2013 Unidade 1
Podemos usar diagramas numerados para mostrar que uma inclusão ou igual-
dade é verdadeira, para todos os conjuntos.
Exemplo 4 (a) 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
A
2
B
34
2. Calculamos uma sequência de rótulos r[A∩B] que corresponde à região A∩B.
Neste caso, observando o diagrama, vemos que r[A ∩B] = 4.
3. Calculamos a sequência de rótulos r[A ∪B] que corresponde à região A ∪B.
Neste caso, observando o diagrama, vemos que r[A ∪B] = 234.
4. Comparamos as sequências r[A ∩B] = 4 e r[A ∪B] = 234.
Como todos os rótulos que estão em r[A∩B] = 4 estão também em r[A∪B] =
234, temos que a inclusão é verdadeira para quaisquer conjuntos.
Podemos usar diagramas numerados para provar que uma inclusão ou igual-
dade é falsa, exibindo conjuntos (finitos!) que falsificam a inclusão ou igual-
dade.
Exemplo 5 (a) Para verificar se (A∩B)c ⊆ Ac ∩Bc, para todos os conjuntos A e
B, fazemos o seguinte:
1. Consideramos o diagrama numerado para 2 conjuntos.
U
1
A
2
B
34
8
Novo Módulo de MD 2013 Unidade 1
2. Calculamos a sequência de rótulos r[(A ∩B)c] que corresponde à região (A ∩
B)c.
Neste caso, observando o diagrama, vemos que r[A ∩ B] = 4 e assim, r[(A ∩
B)c] = 123.
3. Calculamos a sequência de rótulos r[Ac∩Bc] que corresponde à região Ac∩Bc.
Neste caso, observando o diagrama, vemos que r[A] = 24, r[Ac] = 13, r[B] =
34, r[Bc] = 12 e, finalmente, r[Ac ∩ Ac] = 1.
4. Comparamos as sequências r[(A ∩B)c] = 123 e r[Ac ∩ Ac] = 1.
5. Como nem todos os rótulos em r[(A∩B)c] = 123 aparecem em r[Ac∩Ac] = 1,
temos que existem conjuntos para os quais a inclusão é falsa.
6. Agora, usando os rótulos obtidos a partir do diagrama numerado, podemos
obter um contra-exemplo para a inclusão (A∩B)c ⊆ Ac∩Bc, isto é, podemos
obter conjuntos A e B em um universo U tais que (A ∩B)c 6⊆ Ac ∩Bc.
De fato, consideremos o universo U como o conjunto de todos os rótulos, ou
seja:
U = {1, 2, 3, 4}
Definimos A e B como sendo os conjuntos cujos elementos são os rótulos que
ocorrem nas sequências r[A] e r[B], ou seja:
A = {2, 4} , B = {3, 4}
Neste caso, temos que (A ∩B)c = {1, 2, 3} 6⊆ {1} = Ac ∩Bc.
c© 2012 Márcia Cerioli e Petrucio Viana
Coordenação da Disciplina MD/CEDERJ-UAB
9