1 - ED-Conjuntos1-2013

Prévia do material em texto

Estruturas Discretas
Teoria dos Conjuntos
2º. Sem.2013
HAC ED2013 1
• Um conjunto é uma coleção de objetos, sem repetição e 
não ordenada.
• Um objeto não pode aparecer em um conjunto mais de 
uma vez.
• Não há ordem para os elementos do conjunto.
• Exemplo:
{2, 3, ½} , {3, ½, 2} , {2, 2, 3, ½} 
representam o mesmo conjunto.
HAC ED2013 2
• Um objeto que pertence a um conjunto é chamado 
elemento do conjunto ou membro do conjunto.
• A pertinência de um elemento a um conjunto é denotada 
pelo símbolo ∈.pelo símbolo ∈.
• A expressão x ∈∈∈∈ A significa que o objeto x é elemento do 
conjunto A.
• A expressão x ∉∉∉∉ A significa que o objeto x não é 
elemento do conjunto A.
HAC ED2013 3
• Exemplos: 
– 2 ∈ {2, 3, ½} 
– 5 ∉ {2, 3, ½}
– 1 ∉ {2, 3, ½}– 1 ∉ {2, 3, ½}
• Outras formas de ler a expressão “é elemento de”: é 
membro de, pertence a, está em.
HAC ED2013 4
Cardinalidade, conjunto finito e infinito
• A cardinalidade ou tamanho de um conjunto A é o número 
de objetos no conjunto e é denotada pelas barras de valor 
absoluto em torno do símbolo do conjunto: 
| A | | A | 
• Um conjunto é finito se sua cardinalidade é um inteiro (é 
finita). 
• Caso contrário, dizemos que o conjunto é infinito.
HAC ED2013 5
• Exemplo: 
– Conjunto finito:
– A = {2, 3, ½}, |A| = 3– A = {2, 3, ½}, |A| = 3
– Conjunto infinito:
– O conjunto de todos os números pares.
• Não podemos encontrar um número k que 
represente o número de elementos desse 
conjunto. 
HAC ED2013 6
Conjuntos enumeráveis e não 
enumeráveis
• Conjuntos enumeráveis:
• É possível construir uma lista ordenada com os elementos desse 
conjunto. Todo elemento do conjunto aparecerá na lista em algum 
momento, apesar de não podermos efetivamente construir a lista 
completa.completa.
• Exemplo: 
– N (números naturais)
“0” é o primeiro elemento, “1” é o segundo, “2” é o terceiro e assim por diante.
A lista 0, 1, 2, 3, 4, ....contém todos os números naturais
HAC ED2013 7
Conjuntos enumeráveis e não 
enumeráveis
• Conjuntos não enumeráveis:
• Para esses conjuntos, é impossível construir uma lista de tal forma 
que todos os elementos do conjunto apareçam em algum momento. 
• Entre dois números quaisquer, sempre existe mais um.
• Exemplos: 
– R (números reais)
– [0, 1] números reais entre 0 e 1.
• Conjuntos finitos e infinitos enumeráveis são chamados contáveis.
HAC ED2013 8
Conjunto vazio
• O conjunto vazio é o conjunto desprovido de 
elementos. 
• Pode ser denotado por { } ou ∅. • Pode ser denotado por { } ou ∅. 
• A cardinalidade do conjunto vazio é zero.
HAC ED2013 9
Alguns conjuntos especiais:
• N = {0, 1, 2, 3, ....} – conjunto dos números naturais ou 
inteiros não negativos
• Z = {... -2, -1, 0, 1, 2, ....} – conjunto dos números inteiros• Z = {... -2, -1, 0, 1, 2, ....} – conjunto dos números inteiros
• Q - conjunto dos números racionais, formados pela 
divisão de 2 inteiros a/b com b≠0.
• R – conjunto dos números reais.
HAC ED2013 10
Descrição de conjuntos
• São duas as formas de descrever um conjunto:
• Listar os elementos entre chaves, separados por vírgula.
A = {a, e, i, o, u}
• Enunciar as propriedades que caracterizam os elementos 
do conjunto.
B = {x | x é um inteiro par, x > 0 }
HAC ED2013 11
Exemplos:
• A = {a, e, i, o, u} ou 
• A = {x | x é uma letra do alfabeto, x é vogal}
B = {2, 4, 6, 8, ...} (não é possível listar todos os • B = {2, 4, 6, 8, ...} (não é possível listar todos os 
elementos) ou 
• B = {x | x é um inteiro par, x > 0 }
HAC ED2013 12
Observação: 
A descrição de um conjunto pelas suas propriedades deve definir todos 
e somente os elementos do conjunto. Por exemplo, se o conjunto 
A = {a, e, i, o, u}
fosse descrito como A = {x | x é uma letra do alfabeto}, essa descrição 
estaria incorreta. 
A condição é necessária, mas não é suficiente para descrever os 
elementos do conjunto, já que é válida para outros elementos que 
não estão no conjunto.
HAC ED2013 13
Igualdade de conjuntos
• Dois conjuntos são iguais se tiverem exatamente os 
mesmos elementos.
• Exemplo:
• E = {x | x2 – 3x + 2 = 0} • E = {x | x – 3x + 2 = 0} 
• F = {2, 1} 
• G = {1, 2, 2, 1, 6/3} 
Logo, E = F = G 
• Observação: 
– Um conjunto não se altera se seus elementos forem 
repetidos ou reordenados.
HAC ED2013 14
• Qual a cardinalidade dos conjuntos a seguir:
– A = {a, b, c, d, e, f, g}
– B = {a, b, c, 1, x, 200, 201, 202}
– Conjunto dos números inteiros pares
– C = {x | x ∈ N, 20 < x < 30}
• Quais dos conjuntos a seguir são enumeráveis ou não enumeráveis:
– R
– N
– Z
– Conjunto dos números pares
– C = {x | x ∈ R, x < 0}
HAC ED2013 15
Conjunto Universo
• Em aplicações da teoria dos conjuntos, os 
elementos dos conjuntos considerados 
pertencem a algum conjunto maior conhecido 
como conjunto Universo, denotado por U.
• O conjunto A = {2, 4, 6, 8, ...} pode ser entendido 
como um conjunto definido sobre o conjunto 
universo U dos números naturais, ou dos 
inteiros. 
HAC ED2013 16
Exemplo
• O conjunto
A = {x | 10 ≤ x ≤ 20}
• Terá sua formatação exata conhecida apenas se 
soubermos qual o seu conjunto universo.
• Se U = N,
A = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
• Se U = R,
A = [10, 20]
HAC ED2013 17
Subconjuntos
• A é subconjunto de B se todo elemento de A 
também é elemento de B. 
• Diz-se que A está contido em B ou B contém A, 
usando os símbolos:usando os símbolos:
– A ⊆ B A está contido em B
– B ⊇ A B contém A
• A não é subconjunto de B se pelo menos um 
elemento de A não pertence a B, o que 
escrevemos A ⊄ B.
HAC ED2013 18
Exemplos
a) N ⊆ Z ⊆Q ⊆R
b) A = {2, 4, 6, 8, 10} B = { 2, 3, 4} 
C = {2, 3}
C ⊄ A B ⊄ A C ⊄ A B ⊄ A 
c) E = { 1, 3, 5} F = {5, 1, 3} 
E ⊆ F e F ⊆ E . Logo, E = F
Obs: Todo conjunto é subconjunto dele mesmo.
HAC ED2013 19
Teorema 1.1
• Para todo conjunto A, temos ∅⊆ A ⊆ U ( Todo 
conjunto A é subconjunto do conjunto universo e o 
conjunto vazio é subconjunto de A)
• Para todo conjunto A, A ⊆ A (Todo conjunto A é • Para todo conjunto A, A ⊆ A (Todo conjunto A é 
subconjunto dele mesmo)
• Se A ⊆ B e B ⊆ C então A ⊆ C 
• A = B se e somente se A ⊆ B e B ⊆ A 
HAC ED2013 20
• Dizemos que A é subconjunto próprio de B se B 
tiver pelo menos um elemento que não pertence a 
A, isto é, se A ⊆ B mas A ≠ B. Nesse caso 
escrevemos A ⊂ B.
• Exemplo:
– A = {2, 5, 7} e B = {2, 6, 7, 5}. 
– A é subconjunto próprio de B, ou seja, A ⊂ B.
HAC ED2013 21
Conjunto como elemento de outro conjunto
• A noção de conjunto é uma noção abstrata e bastante flexível. 
• Podemos ter, por exemplo, conjuntos como elementos de outro conjunto. 
• No conjunto 
A = {1, 2, {3, 4}, 5}
o conjunto {3, 4}, formado pelos elementos 3 e 4, é um elemento do conjunto 
A. 
• No conjunto
B = {a, {b}, c, d}
o conjunto de um único elemento {b} é um elemento do conjunto B. 
HAC ED2013 22
Conjunto vazio como elemento de outro 
conjunto
• O conjunto vazio também pode aparecer como elemento de outro 
conjunto.
• Exemplo:
C = {2, 4, ∅, {6, 8, 10}, {12, 14}}
• É correto afirmar:
• ∅∈ C
• ∅⊆ C
HAC ED2013 23
Observação:
• Os símbolos ⊆ e ∈ tem significados relacionados, 
porém, diferentes.
– A notação x ∈ A significa que x é elemento de A e 
– A notação A ⊆ B significa que todo elemento de A 
também é elemento de B. Assim,também é elemento de B. Assim,
• ∅⊆ {1, 2, 3} é verdadeiro
• ∅∈ {1, 2, 3} é falso
HAC ED2013 24
Diagrama de Venn
• Um diagrama de Venn é uma representação pictórica na qual 
os conjuntos são representados por áreas representadas porcurvas no plano.
• Um retângulo representa o conjunto universo e os demais 
conjuntos são representados por discos.
• É útil para representar operações entre conjuntos. 
HAC ED2013 25
Diagrama de Venn
UB
A
U
B
A
HAC ED2013 26
A A
a) A ⊆ B b) A e B são disjuntos
Figura 1.1 Diagrama de Venn
Operações entre conjuntos
• A união de dois conjuntos A e B, denotada por 
A ∪ B, é o conjunto de todos os elementos que pertencem a 
A ou a B:
A ∪ B = {x | x ∈ A ou x ∈ B}
• A interseção de dois conjuntos A e B, denotada por A ∩
B, é o conjunto dos elementos que pertencem a A e a B:
A ∩ B = {x | x ∈ A e x ∈ B}
• Se A ∩ B = ∅, A e B são ditos disjuntos.
HAC ED2013 27
U
BA
U
BA
HAC ED2013 28
a) A ∪ B b) A ∩ B 
Figura 1.2 Operações de união e interseção
• O complementar absoluto ou simplesmente o 
complementar de um conjunto A, denotado por AC ou 
por A´, é o conjunto dos elementos que pertencem a U
mas não pertencem a A:
AC = { x | x ∈ U, x ∉ A}
• O complementar relativo de um conjunto B em relação a 
A, ou a diferença entre A e B, denotada por A\B ou A – B, 
é o conjunto dos elementos que pertencem a A mas não 
pertencem a B:
A\B = {x | x ∈ A, x ∉ B}
HAC ED2013 29
U
U
A
A
B
HAC ED2013 30
a) A´ b) A - B 
Figura 1.3 Operações de complementar e diferença
• A Diferença Simétrica dos conjuntos A e B, 
denotada por A ⊕ B, consiste em todos os 
elementos que pertencem a A ou B mas não elementos que pertencem a A ou B mas não 
a ambos: 
A ⊕ B = (A ∪ B) \ (A ∩ B)
HAC ED2013 31
U
A B
HAC ED2013 32
A
Figura 1.5.A ⊕ B 
Exemplos
• A = {2, 3, 4, 5, 6} B = {4, 5, 6, 7, 8} C = {1, 8, 9}
• A ∪ B = {2, 3, 4, 5, 6, 7, 8}
• A ⊕ B = {2, 3, 7, 8}• A ⊕ B = {2, 3, 7, 8}
• A ∪ B ∪ C = {1, 2, 3, 4, 5, 6, 7, 8, 9}
• A ⊕ B ⊕ C = {1, 2, 3, 7, 9}
HAC ED2013 33