Instituto Federal de Educação, Ciência e
Tecnologia de São Paulo - IFSP
Campus de Caraguatatuba
20 Semestre de 2013
Matemática Discreta 2 – MD 2
Prof. Lineu Mialaret
Aula 2: Conjuntos
Matemática Discreta 2
Aula 2 - 1
©Prof. Lineu Mialaret
Introdução (1)
 Pode-se dizer que a Teoria dos Conjuntos é em grande
parte trabalho de um único matemático:
 George Cantor (1845-1918).
 Essa teoria é uma das pedras fundamentais da Matemática.
E muitos conceitos em Ciência da Computação podem ser
expressos de maneira conveniente usando-se conjuntos.
 Operações podem ser realizadas em conjuntos para gerar
novos conjuntos.
 Tecnologia de Banco de Dados é o exemplo clássico do
uso de conjuntos em computação.
Matemática Discreta 2
Aula 2 - 2
©Prof. Lineu Mialaret
Introdução (2)
 A noção de conjunto não é suscetível de uma definição
precisa. Ela surge a partir de noções mais simples, ou
seja, é uma noção primitiva.
 Conjunto não se define formalmente. Usa-se uma idéia
intuitiva de que se trata de uma coleção de objetos (não
ordenada e sem repetição).
 Esses
objetos de um
propriedade em comum.
conjunto
possuem
alguma
 Qualquer objeto que tenha essa propriedade pertence ao
conjunto.
 Qualquer
objeto que não tenha essa propriedade não
pertence ao conjunto.
Matemática Discreta 2
Aula 2 - 3
©Prof. Lineu Mialaret
Introdução (3)
 Sintetizando, objetos de um conjunto não possuem
nenhuma ordem de apresentação e cada um é listado
apenas uma vez. É redundante listá-lo de novo.
 Exemplos de conjuntos:
 O conjunto formado por todas as mulheres da sala.
 O conjunto formado por todos(as) os(as) corinthianos(as)
da sala.
 O conjunto formado por todas as pessoas com mais de 15
anos na sala.
 O conjunto formado pelos alunos de computação do IF de
Caraguatatuba.
Matemática Discreta 2
Aula 2 - 4
©Prof. Lineu Mialaret
Notação (1)
 Usa-se letras maiúsculas A, B, ...,
para denotar os
conjuntos e minúsculas c, d, ..., para os elementos.
 Usa-se o símbolo  para denotar pertinência em um
conjunto. Dessa forma:
 c  A significa que c pertence ao conjunto A ou é elemento
do conjunto A.
 d  A significa que o elemento d não pertence ao conjunto
A ou não é elemento do conjunto A.
 Usa-se chaves para indicar um conjunto.
 Se A = {azul, verde, branco}, então verde  A e preto  A.
 Os elementos em um conjunto não tem nenhuma ordem,
de modo que
 {azul, verde, branco} é o mesmo que {branco, azul, verde}.
Matemática Discreta 2
Aula 2 - 5
©Prof. Lineu Mialaret
Notação (2)
 Diz-se que dois conjuntos são iguais se eles contém os
mesmos elementos. Em notação de lógica de predicados
tem-se:
 A = B significa x((x  A → x  B)  (x  B → x  A))
 Ex.: Os conjuntos {1,3,5} e {5,3,1} são iguais.
 Ao se descrever um conjunto, deve-se ter um modo de
identificar seus elementos.
 Para um conjunto finito (com n elementos, n  0), isso é
feito listando-se
elementos.
(todos
ou
parcialmente)
os
seus
 Ex.: V = {a, e, i, o, u}.
Matemática Discreta 2
Aula 2 - 6
©Prof. Lineu Mialaret
Notação (3)
 Para um conjunto infinito (que não é finito), pode-se indicar
a forma geral listando os primeiros elementos.
 Ex.: S é o conjunto de todos os inteiros positivos pares, então
S = {2, 4, 6,…}.
 Pode-se usar de recorrência, explicitando um dos
elementos do conjunto S e descrevendo-se os outros
elementos em termos dos já conhecidos.
 Ex.:
1) 2  S
2) Se n  S, então (n + 2)  S.
 Finalmente, pode-se descrever esse conjunto por meio de
uma propriedade que caracteriza seus elementos.
 Ex.: S = {x | x é um inteiro positivo par},
 que se lê: “o conjunto de todos os x tais que x é um inteiro
positivo par”.
Matemática Discreta 2
Aula 2 - 7
©Prof. Lineu Mialaret
Notação (4)
 A notação para um conjunto cujos elementos são
denotados por uma propriedade P é S = {x | P(x)}.
 A notação baseada na lógica formal torna mais claro a
propriedade que caracteriza os elementos de um
conjunto.
 S = {x | P(x)} significa
 x((x  S → P(x))  (P(x) → x  S))
 Traduzindo:
 Todos os elementos de S têm a propriedade P e tudo
que tem a propriedade P pertence a S.
Matemática Discreta 2
Aula 2 - 8
©Prof. Lineu Mialaret
Notação (5)
 Exercício 1 - Descreva cada um dos conjuntos a seguir,
listando seus elementos:
a) {x | x é um inteiro e 3 < x ≤ 7}.
b) {x | x é um mês com 30 dias}.
c) {x | x é a capital do Brasil}.
Matemática Discreta 2
Aula 2 - 9
©Prof. Lineu Mialaret
Notação (6)
 Exercício 1 - Descreva cada um dos conjuntos a seguir,
listando seus elementos:
a) {x | x é um inteiro e 3 < x ≤ 7}.
b) {x | x é um mês com 30 dias}.
c) {x | x é a capital do Brasil}.
 Respostas:
a) {4,5,6,7}.
b) {abril, junho, setembro, novembro}.
c) {Brasília}.
Matemática Discreta 2
Aula 2 - 10
©Prof. Lineu Mialaret
Notação (7)
 Exercício 2 - Descreva cada um dos conjuntos a seguir,
por meio da propriedade que caracteriza seus elementos:
a) {1,4,9,16}.
b) {o açougueiro, o padeiro, o produtor de maçãs}.
c) {2,3,5,7,11,13,17,...}.
Matemática Discreta 2
Aula 2 - 11
©Prof. Lineu Mialaret
Notação (8)
 Exercício 2 - Descreva cada um dos conjuntos a seguir,
por meio da propriedade que caracteriza seus elementos:
a) {1,4,9,16}.
b) {o açougueiro, o padeiro, o produtor de maçãs}.
c) {2,3,5,7,11,13,17,...}.
 Respostas:
a) {x | x é um dos quatro primeiros quadrados perfeitos}.
b) {x | x é um dos três comerciantes do bairro}.
c) {x | x é um número primo}.
Matemática Discreta 2
Aula 2 - 12
©Prof. Lineu Mialaret
Notação (9)
 É
conveniente usar-se uma notação padrão para
determinados conjuntos, de modo que a referência a eles
seja mais fácil.
 N = o conjunto de todos os inteiros não negativos (0  N)
 N = {0, 1, 2, 3, ...}
 Z = conjunto de todos os inteiros
 Z = {..., -3, -2, -1,0, 1, 2, 3, ...}
 Q = conjunto dos números racionais
 Definido por
 {p/q | p  Z, q  Z, e q ≠ 0}
 Q = { -7/6, 5/8 }
 Z  Q, pois se p  Z, p = (p/1)  Q
Matemática Discreta 2
Aula 2 - 13
©Prof. Lineu Mialaret
Notação (10)
 Todo número racional pode ser representado na forma
decimal, e pode-se ter dois casos:
 Representação decimal é finita
7/4 = 1,75.
 Representação decimal é infinita (periódica)
1/3=0,333...
 I = conjunto dos números irracionais
 Sejam os números
 2 = 1,4142135...
 3 = 1,7320...
 Existem decimais infinitas não periódicas, às quais se dá o
nome de números irracionais, os quais não podem ser
escritos na forma a/b.
Matemática Discreta 2
Aula 2 - 14
©Prof. Lineu Mialaret
Notação (11)
 R = o conjunto dos números reais
 R = Q  I = {x | x é racional ou x é irracional}
 Logo, são números reais,
 os números naturais;
 os números inteiros;
 os números racionais;
 os números irracionais.
 Sintetizando:
Matemática Discreta 2
Aula 2 - 15
©Prof. Lineu Mialaret
Notação (12)
 Chama-se de intervalo a determinados subconjuntos dos
números reais. Assim, dados dois números reais a e b,
com a < b, tem-se,
 intervalo aberto: (a, b) = {x ∈ R | a < x < b}
 intervalo fechado: [a, b] = {x ∈ R | a ≤ x ≤ b}
 intervalo semi-aberto à direita: (a, b] = {x ∈ R | a < x ≤ b}
 intervalo semi-aberto à esquerda: [a, b) = {x ∈ R | a ≤ x < b}
 intervalos infinitos:
 (a, + ∞) = {x ∈ R | x > a}
 [a, + ∞) = {x ∈ R | x ≥ a}
 (– ∞, a) = {x ∈ R | x < a}
 (– ∞, a] = {x ∈ R | x ≤ a}
 Obs.:
(– ∞, + ∞) = R.
Matemática Discreta 2
Aula 2 - 16
©Prof. Lineu Mialaret
Notação (13)
 Um conjunto que não tem elementos (o assim chamado
conjunto vazio) é denotado por  ou por { }.
 Ex.: S = { x | x  N e x < 0}, então S = .
 Obs.:
 ≠ {  }.
 A cardinalidade (ou tamanho) de um conjunto A é o
número de elementos desse conjunto:
 É denotada pelas barras de valor absoluto em torno do
símbolo do conjunto, |A|.
 Ex.:
 Se B = {1, 2, 3, 4, 5} então |B| = 5.
 Se E = {1, 2} então |E| = 2.
 Um conjunto finito possui cardinalidade finita (um inteiro)
enquanto um conjunto infinito possui cardinalidade infinita.
Matemática Discreta 2
Aula 2 - 17
©Prof. Lineu Mialaret
Relacionamento entre Conjuntos (1)
 Para os conjuntos A = {3,5,12} e B = {2,3,5,12}, observa-
se que todo elemento de A é também elemento de B.
 Diz-se que A é um subconjunto de B (essa definição
engloba o caso adicional do conjunto A ser igual a B).
 Se A é um subconjunto de B, simboliza-se
 por A  B, que se lê “A está contido em B” ou “B contém
A”, simbolizado por B  A.
 Caso contrário, indica-se que “A não está contido em B”,
simbolizado por A ⊈ B ou “B não contém A”, denotado por
B ⊉ A.
 Se A  B, mas A ≠ B (há pelo menos um elemento de B
que não pertence a A), então diz-se que A é um
subconjunto próprio de B, sendo simbolizado por A  B
(a notação  também representa subconjuntos próprios).
Matemática Discreta 2
Aula 2 - 18
©Prof. Lineu Mialaret
Relacionamento entre Conjuntos (4)
 Exercício 4 – Sejam os conjuntos
 A = {1,7,9,15}
 B = {7,9}
 C = {7,9,15,20}
 Verificar o valor lógico das seguintes proposições:
 BC
( )
 BA
( )
 BA
( )
 AC
( )
 15  C
( )
 {7}  A
( )
 { }C
( )
Matemática Discreta 2
Aula 2 - 19
©Prof. Lineu Mialaret
Relacionamento entre Conjuntos (5)
 Exercício 4 – Sejam os conjuntos
 A = {1,7,9,15}
 B = {7,9}
 C = {7,9,15,20}
 Verificar o valor lógico das seguintes proposições:
 BC
(V)
 BA
(V)
 BA
(V)
 AC
(V)
 15  C
(V)
 {7}  A
(V)
 { }C
(V)
Matemática Discreta 2
Aula 2 - 20
©Prof. Lineu Mialaret
Conjunto de Conjunto (1)
 Para um dado conjunto S qualquer, pode-se formar um
novo conjunto cujos elementos são subconjuntos de S.
 Esse novo conjunto é chamado de conjunto de partes de S
(ou conjunto potência) e simbolizado por P(S).
 Seja S = {0,1}. Então P(S) = {{ }, {0}, {1}, {1,0}}
 Os elementos de P(S) são conjuntos.
 Para qualquer conjunto S, o conjunto de partes P(S) no
mínimo tem como elementos { } e S.
 Isso ocorre pois sempre é verdade que { }  S e S  S.
 Heurística:
 Para encontrar P(S), começa-se com { }, depois coloca-se os
conjuntos formados por um elemento de S, depois aos
formados por dois elementos de S, por três e assim por
diante, até o próprio conjuntoS.
 Número de elementos de P(S) ?
Matemática Discreta 2
Aula 2 - 21
©Prof. Lineu Mialaret
Conjunto de Conjunto (2)
 Exercício 5 –
1) Qual é o conjunto das partes do conjunto {0,1,2}?
2) Qual é o conjunto das partes do conjunto vazio {}?
3) Qual é o conjunto das partes do conjunto { {} }?
Matemática Discreta 2
Aula 2 - 22
©Prof. Lineu Mialaret
Conjunto de Conjunto (3)
 Exercício 5 –
1) Qual é o conjunto das partes do conjunto {0,1,2}?
2) Qual é o conjunto das partes do conjunto vazio?
3) Qual é o conjunto das partes do conjunto { {} }?
 Respostas:
 P({0,1,2}) = { {}, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2} }.
 P({ } = { {} }.
 P({ {} }) = { {}, { {} } }.
Matemática Discreta 2
Aula 2 - 23
©Prof. Lineu Mialaret
Operações em Conjuntos (1)
 Grande parte de operações que envolvem números
podem ser realizadas em conjuntos.
 Dado um conjunto S, podemos definir operações no
conjunto P(S).
 O conjunto S, nesse caso, é chamado de conjunto universo
ou universo do discurso, o qual define o contexto dos
objetos em discussão.
 Ex.:
 Se S = Z, então os subconjuntos conterão apenas
inteiros.
 Operações:
 Unárias, quando ocorrem em apenas um elemento
(operando) do conjunto, por ex., a negação.
 Binárias, quando envolvem dois elementos (operandos) do
conjunto, por ex., a subtração.
Matemática Discreta 2
Aula 2 - 24
©Prof. Lineu Mialaret
Operações em Conjuntos (2)
 Exemplo 1:
 Seja S o conjunto de alunos de cursos superiores do IF de
Caraguatatuba. Sejam A o conjunto dos alunos que
estudam computação e B o conjunto dos alunos que
estudam administração. Ambos, A e B, pertencem a P(S).
 Um novo conjunto de alunos pode ser definido, consistindo
dos alunos que estudam computação ou administração. Esse
novo conjunto é a união de A e B.
 Outro novo conjunto pode ser formado consistindo de alunos
que estudam computação e administração ao mesmo tempo.
Esse conjunto é a interseção de A e B.
Matemática Discreta 2
Aula 2 - 25
©Prof. Lineu Mialaret
Operações em Conjuntos (3)
 Definição: Sejam A, B conjuntos pertencentes a P(S).
 A união de A e B, denotada por A  B, é definida por:
 {x | x  A ou x  B}.
 A interseção de A e B, denotada por A  B é definida por:
 {x | x  A e x  B}.
 Ex.:
 Seja A = {1,3,5,7,9} e B = {3,5,6,10,11} (Os conjuntos A e B
são elementos de P(S)).
 Então
 A  B = {1,3,5,6,7,9,10,11}
 A  B = {3,5}
 Obs.:
 Os conjuntos obtidos são elementos de P(S).
 Os elementos repetidos são listados uma só vez.
Matemática Discreta 2
Aula 2 - 26
©Prof. Lineu Mialaret
Operações em Conjuntos (4)
 Para facilitar a representação, pode-se usar Diagramas
de Venn (homenagem ao matemático John Venn) para
se visualizar as operações binárias de união e
interseção.
 Diagrama de Venn para A  B:
S
A
B
AB
Matemática Discreta 2
Aula 2 - 27
©Prof. Lineu Mialaret
Operações em Conjuntos (5)
 Diagrama de Venn para A  B:
S
A
B
AB
Matemática Discreta 2
Aula 2 - 28
©Prof. Lineu Mialaret
Operações em Conjuntos (6)
 Definição: Seja A um conjunto pertencente a P(S). O
complemento de A, simbolizado por A (ou Α ) é definido
por {x | x  S e x  A}.
 Diagrama de Venn para A:
S
A
A
 Obs.:
 A representa a parte amarela do diagrama.
Matemática Discreta 2
Aula 2 - 29
©Prof. Lineu Mialaret
Operações em Conjuntos (7)
 Definição: Sejam A, B subconjuntos pertencentes a P(S).
A diferença entre conjuntos, simbolizada por A - B é
definida por {x | x  A e x  B}.
 A – B pode ser reescrita como {x | x  A e x  B’}, ou
 A – B pode ser reescrita como A  B’.
 E a diferença B – A?
 Diagrama de Venn para A - B:
A
B
S
A-B
Matemática Discreta 2
Aula 2 - 30
©Prof. Lineu Mialaret
Operações em Conjuntos (8)
 Definição: Dois conjuntos A e B tais que A  B =  são
denominados de conjuntos disjuntos.
 Ex.: A – B e B – A são conjuntos disjuntos.
 Diagrama de Venn para conjuntos disjuntos:
Matemática Discreta 2
Aula 2 - 31
©Prof. Lineu Mialaret
Operações em Conjuntos (9)
 Exercício 6 – Sejam os conjuntos
 A = {1,2,3,5,10},
 B = {2,4,7,8,9}, e
 C = {5,8,10},
 Subconjuntos de S = {1,2,3,4,5,6,7,8,9,10}.
 Encontrar os seguintes conjuntos:
A  B
A – C
 B  (A  C)
Matemática Discreta 2
Aula 2 - 32
©Prof. Lineu Mialaret
Operações em Conjuntos (10)
 Exercício 6 – Sejam os conjuntos
 A = {1,2,3,5,10},
 B = {2,4,7,8,9}, e
 C = {5,8,10},
 Subconjuntos de S = {1,2,3,4,5,6,7,8,9,10}.
 Resposta:
 Encontrar os seguintes conjuntos:
 A  B = {1,2,3,4,5,7,8,9,10}
 A – C = {1,2,3}
 B  (A  C) = {1,3,5,10}
Matemática Discreta 2
Aula 2 - 33
©Prof. Lineu Mialaret
Operações em Conjuntos (11)
 Definição: Sejam os conjuntos A e B subconjuntos de S.
O produto cartesiano de A e B, denotado por A  B, é
definido por {(x,y) | x  A e y  B}.
 É o conjunto de todos os pares ordenados com o primeiro
componente do par sendo um elemento de A e o segundo
componente do par sendo um elemento de B.
 A  B não é subconjunto do conjunto S (A  B não é uma
operação binária fechada em S).
 Pode-se abreviar A  A por A2.
 Ex.:
 Sejam A = {1,2} e B = {3,4,5}.
 O prod. cartesiano A  B ={(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)}
1
3
4
2
5
Matemática Discreta 2
3
4
5
Aula 2 - 34
©Prof. Lineu Mialaret
Operações em Conjuntos (12)
 Outro Ex.:
 Sejam L = {A,B,C} e N = {1,2}.
 Prod. cartesiano L  N ={(A,1),(A,2),(B,1),(B,2),(C,1),(C,2)}.
LN
L
N
Matemática Discreta 2
Aula 2 - 35
©Prof. Lineu Mialaret
Operações em Conjuntos (13)
 Exercício 7 – Sejam os conjuntos
 A = {1,2},
 B = {3,4}.
 Encontrar os seguintes conjuntos:
A  B
B  A
 A2
 A3
Matemática Discreta 2
Aula 2 - 36
©Prof. Lineu Mialaret
Operações em Conjuntos (14)
 Exercício 7 – Sejam os conjuntos
 A = {1,2},
 B = {3,4}.
 Resposta:
 Encontrar os seguintes conjuntos:
 A  B = {(1,3),(1,4),(2,3),(2,4)}.
 B  A = ((3,1),(3,2),(4,1),(4,2)}.
 A2 = A  A = {(1,1),(1,2),(2,1),(2,2)}.
 A3 = A  A  A =
= (A  A)  A =
= A2  A =
= {(1,1),(1,2),(2,1),(2,2)}  {1,2} =
= {(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)}.
Matemática Discreta 2
Aula 2 - 37
©Prof. Lineu Mialaret
Operações em Conjuntos (15)
 Exercício para se pensar – Sejam os conjuntos
 Pagadores = {João, José},
 Caloteiros = {Joaquim, João}.
 Encontrar os seguintes conjuntos que contenham:
 Só as pessoas que são Pagadores ou Caloteiros.
 Só as pessoas que são Pagadores e Caloteiros.
 Só as pessoas que são somente Pagadores.
 Só as pessoas que são somente Caloteiros.
Matemática Discreta 2
Aula 2 - 38
©Prof. Lineu Mialaret
Identidades Em Conjuntos (1)
 Há uma série de igualdades entre conjuntos nas
operações
de
união,
interseção,
diferença
e
complementação.
 Essas igualdades são independentes dos subconjuntos
particulares utilizados e são chamadas de Identidades
Básica de Conjuntos.
 Essas identidades são semelhantes (em propósito) as
equivalências tautológicas da lógica matemática.
 São apresentadas na próxima transparência.
Matemática Discreta 2
Aula 2 - 39
©Prof. Lineu Mialaret
Identidades Em Conjuntos (2)
Identidades Básicas Envolvendo Conjuntos (1).
Matemática Discreta 2
Aula 2 - 40
©Prof. Lineu Mialaret
Identidades Em Conjuntos (3)
Identidades Básicas Envolvendo Conjuntos (2).
Matemática Discreta 2
Aula 2 - 41
©Prof. Lineu Mialaret
Identidades Em Conjuntos (4)
 Exemplo 2: Provar a identidade 3a (transp. 40).
 A  (B  C) = (A  B)  (A  C)
 Prova-se essa igualdade entre conjuntos mostrando-se a
inclusão em ambas as direções, ou seja, prova-se que:
 A  (B  C)  (A  B)  (A  C) e
 (A  B)  (A  C)  A  (B  C).
 Para mostrar-se que A  (B  C)  (A  B)  (A  C), seja
x um elemento qualquer de A  (B  C). Pode-se então
proceder-se da seguinte forma:
 x  A  (B  C)  x  A ou x  (B  C)
 x  A ou (x  B e x  C)
 (x  A ou x  B) e (x  A ou x  C)
 x  (A  B) e x  (A  C)
 x  (A  B)  (A  C).
Matemática Discreta 2
Aula 2 - 42
©Prof. Lineu Mialaret
Identidades Em Conjuntos (5)
 Para mostrar-se que (A  B)  (A  C)  A  (B  A),
basta refazer o argumento de trás para a frente.
 As identidades apresentadas podem ser usadas para
provar-se outras identidades envolvendo conjuntos.
 Exemplo 3:
 Provar que (A  (B  C)  ((A  (B  C))  (B  C)) = ,
para A, B, e C subconjuntos quaisquer de S.
Matemática Discreta 2
Aula 2 - 43
©Prof. Lineu Mialaret
Identidades Em Conjuntos (6)
 O dual de cada identidade também aparece na lista.
 A identidade dual é obtida permutando-se o símbolo  por
 e S com .
 Exemplo 4: o dual da identidade
 (A  (B  C)  ((A  (B  C))  (B  C)) =  é
 (A  (B  C)  ((A  (B  C))  (B  C)) = S.
Matemática Discreta 2
Aula 2 - 44
©Prof. Lineu Mialaret
Identidades Em Conjuntos (7)
 Sintetizando
os métodos usados
identidades envolvendo conjuntos:
Matemática Discreta 2
Aula 2 - 45
para
se
provar
©Prof. Lineu Mialaret
Identidades Em Conjuntos (8)
 Exercício 8 - Usando as identidades básicas, prove a
identidade abaixo:
 (C  (A  B))  ((A  B)  C) = A  B, onde A, B, e C são
subconjuntos arbitrários de S.
 Enunciar a identidade dual que se obtém.
Matemática Discreta 2
Aula 2 - 46
©Prof. Lineu Mialaret
Identidades Em Conjuntos (9)
 Exercício 8 - Usando as identidades básicas, prove a
identidade abaixo:
 (C  (A  B))  ((A  B)  C) = A  B, onde A, B, e C são
subconjuntos arbitrários de S.
 Enunciar a identidade dual que se obtém.






Resposta:
(C  (A  B))  ((A  B)  C) =
((A  B)  C)  ((A  B)  C) =
(A  B)  (C  C)
=
(A  B)  (S)
=
(A  B)
Matemática Discreta 2
Aula 2 - 47
(1b)
(3b)
(5a)
(4b)
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (1)
 Um conjunto finito (um conjunto com n elementos para
algum inteiro positivo n) possui um número conhecido de
elementos.
 Num conjunto finito S, sempre se pode designar um
elemento como sendo o primeiro, s1, um outro como o
segundo s2, e assim por diante.
 Se existem k elementos no conjunto, eles podem ser
listados na ordem selecionada: s1, s2, ..., sk.
 Essa lista representa o conjunto todo.
 O número de elementos em um conjunto finito é a
denominada cardinalidade do
conjunto tem a cardinalidade k.
Matemática Discreta 2
Aula 2 - 48
conjunto.
Logo,
esse
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (2)
 Num conjunto infinito T (um conjunto que não é finito)
pode-se ainda selecionar-se um primeiro elemento, t1,
um segundo elemento, t2, e assim por diante de modo
que a lista t1, t2, ..., tk representa todos os elementos do
conjunto.
 Todo elemento do conjunto aparece na lista em algum
momento. Tal conjunto infinito é denominado de
enumerável.
 Conjuntos
finitos e conjuntos enumeráveis são
denominados de conjuntos contáveis (pode-se contar ou
enumerar os elementos do conjunto).
 Ser contável não significa que se pode dizer qual o numero total
de elementos no conjunto. Significa que se pode dizer quem é o
primeiro, o segundo e assim por diante.
Matemática Discreta 2
Aula 2 - 49
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (3)
 Exemplo 4: O conjunto N é enumerável.
 Para provar a enumerabilidade, precisa-se apenas exibir
um modo de contar os elementos.
 Para o conjunto N de inteiros não negativos, é claro que
0,1,2,3, ... é uma enumeração que certamente incluirá
todos os elementos do conjunto.
Matemática Discreta 2
Aula 2 - 50
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (4)
 Exercício 9: Provar que o conjunto dos inteiros positivos
pares é enumerável.
Matemática Discreta 2
Aula 2 - 51
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (5)
 Exercício 9: Provar que o conjunto dos inteiros positivos
pares é enumerável.
 Resposta:
 Uma
enumeração
2,4,6,8,10,12,...
Matemática Discreta 2
dos
inteiros
Aula 2 - 52
positivos
pares
é
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (6)
 Exercício 10: Provar que Q+, conjunto dos números
racionais positivos é enumerável.
Matemática Discreta 2
Aula 2 - 53
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (7)
 Exercício 10: Provar que Q+, conjunto dos números
racionais positivos é enumerável.
 Resposta:
 Supondo que cada racional positivo pode ser escrito como
uma fração de inteiros positivos, pode-se escrever todas
essas frações com numerador 1 na primeira linha,
numerador 2 na segunda linha e assim por diante,
conforme apresentado abaixo.
Matemática Discreta 2
Aula 2 - 54
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (8)
 Nesse formato, como se pode enumerar o conjunto?
 Para mostrar que esse arranjo é enumerável, pode-se
passar um fio, com uma seta apontando o sentido,
percorrendo todo o arranjo, começando em 1/1, conforme
apresentado abaixo.
Matemática Discreta 2
Aula 2 - 55
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (9)
 Começando por um dos cantos, observa-se que o arranjo é
enumerável.
 Caso se comece seguindo apenas a primeira linha,
jamais se terminará para chegar nas outras linhas.
 Para melhorar a enumeração, pode-se ainda simplificar as
frações, como por exemplo (1/1 = 2/2, 1/2=2/4, …).
 Portanto, a enumeração de Q+ começa com 1/1, 2/1, 1/2,
3/1, 4/1, ...
Matemática Discreta 2
Aula 2 - 56
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (10)
 Existem conjuntos infinitos que não são contáveis (ou
seja, são os denominados não enumeráveis).
 Um conjunto não enumerável é tão grande que não existe
uma maneira de se contar os elementos e obter todo o
conjunto nesse processo.
 Ex.: números reais, irracionais, complexos, etc.
Matemática Discreta 2
Aula 2 - 57
©Prof. Lineu Mialaret
Conjuntos Contáveis e Não Contáveis (11)
 Pesquisa: Provar que o conjunto de todos os números
reais entre 0 e 1 é não enumerável.
 Dica: Usar o método de diagonalização de Cantor.
Matemática Discreta 2
Aula 2 - 58
©Prof. Lineu Mialaret