Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Teoria dos Conjuntos
Prof. Dr. Leandro Balby Marinho
Matemática Discreta
Prof. Dr. Leandro Balby Marinho
1 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Roteiro
1. Teoria dos Conjuntos
2. Operações em Conjuntos
3. Identidades de Conjuntos
Prof. Dr. Leandro Balby Marinho
2 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Teoria dos Conjuntos
I
Um conjunto é uma coleção não ordenada de objetos.
I
O estudo moderno dos conjuntos deve-se a Georg Cantor
(1870).
I
São usados para representar muitas estruturas discretas
importantes, tais como, combinações, relações e grafos.
I
Há duas versões da teoria dos conjuntos:
I
I
Teoria ingênua de Cantor (adotada nesse curso)
Teoria axiomática
Prof. Dr. Leandro Balby Marinho
2 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Convenções
I
Os objetos de um conjunto são chamados de elementos ou
membros.
I
Letras maiúsculas denotam conjuntos e minúsculas membros
dos conjuntos.
I
Escrevemos a ∈ A para denotar que a é um membro do
conjunto A e a ∈
/ A o contrário.
I
Exemplo 1: O conjunto das vogais no alfabeto
V = {a, e, i, o, u}.
I
Exemplo 2: O conjunto P dos pares positivos menores que 10
P = {2, 4, 6, 8}
Prof. Dr. Leandro Balby Marinho
3 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Representação de Conjuntos
I
Listando total ou parcialmente os elementos, por exemplo,
B = {5, 7, 9}
C = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}
I
Usando recursividade, por exemplo
I
I
3 ∈ S (caso base)
Se x ∈ S então 3x ∈ S (passo recursivo)
Prof. Dr. Leandro Balby Marinho
4 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Representação de Conjuntos
É comum definir uma regra que caracterize os elementos de um
conjunto, por exemplo,
A = {x | x é um aluno nessa sala}
P = {x ∈ Z+ | x é par e x < 10}
Q + = {x ∈ R | x = p/q, p ∈ Z+ , q ∈ Z+ e q 6= 0}
Prof. Dr. Leandro Balby Marinho
5 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exercı́cio 1
Redefina os conjuntos abaixo através de uma regra (veja slide anterior).
a) {2, 4, 6, 8, 10, . . .}
1 1 1 1
b) {1, , , , , . . .}
2 3 4 5
c) {0, 1, 2, . . . , 50}
Prof. Dr. Leandro Balby Marinho
6 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Alguns Conjuntos Importantes
I
N = {0, 1, 2, 3, . . .}, conjuntos dos números naturais.
I
Z = {. . . , −2, −1, 0, 1, 2, . . .}, conjunto dos inteiros.
I
Z+ = {1, 2, 3, . . .}, conjunto dos inteiros positivos.
I
Q = {p/q | p ∈ Z, q ∈ Z, e q 6= 0}, conjunto dos números
racionais.
I
R, conjunto dos números reais.
Conjuntos podem ter outros conjuntos como membros!
Exemplo 3: D = {N, Z, Q, R} é um conjunto contendo quatro
elementos, no qual cada elemento corresponde a um conjunto.
Prof. Dr. Leandro Balby Marinho
7 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Igualdade de Conjuntos
Definição 1
Sejam A e B conjuntos, então A = B se e somente se
∀x(x ∈ A ↔ x ∈ B)
Exemplo 4: Os conjuntos {1, 2, 3}, {3, 2, 1} são iguais pois possuem os
mesmos elementos.
Prof. Dr. Leandro Balby Marinho
8 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Conjunto Vazio
O conjunto vazio é o conjunto que não contém nenhum elemento
e é denotado por ∅ ou { }.
Não confundir ∅ com {∅}!
Exemplo 5:
(i) A = {x | x ∈ N e x < 0} = ∅
(ii) B = {x | x ∈ R e x 2 = −1} = ∅
Prof. Dr. Leandro Balby Marinho
9 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Subconjuntos
Definição 2
O conjunto A é um subconjunto de B, denotado por A ⊆ B, se e
somente se
∀x(x ∈ A → x ∈ B)
Prof. Dr. Leandro Balby Marinho
10 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exercı́cio 2
Sejam
A = {x | x ∈ N e x ≥ 5}
B = {10, 12, 16, 20}
C = {x | ∃y (y ∈ N e x = 2y )}
Determine quais das proposições abaixo são verdadeiras.
a) B ⊆ C
b) A ⊆ C
c) 26 ∈ C
d) {11, 12, 13} ⊆ A
e) {12} ∈ B
f) {12} ⊆ B
Prof. Dr. Leandro Balby Marinho
11 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Subconjuntos
Teorema 1
Seja S um conjunto não vazio,
(i) ∅ ⊆ S e (ii) S ⊆ S.
Prova de (i): Precisamos provar que ∀x(x ∈ ∅ → x ∈ S) é verdadeiro. Como x ∈ ∅ é sempre falso, segue que x ∈ ∅ → x ∈ S é
sempre verdadeiro.
Prova de (ii): Precisamos provar que ∀x(x ∈ S → x ∈ S) é
verdadeiro. Como x ∈ S é sempre verdadeiro, segue que x ∈ S →
x ∈ S é sempre verdadeiro.
Prof. Dr. Leandro Balby Marinho
12 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Subconjuntos Próprios
Definição 3
O conjunto A é um subconjunto próprio de B, denotado por
A ⊂ B, se e somente se
∀x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x ∈
/ A)
Prof. Dr. Leandro Balby Marinho
13 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exemplo 6
Sejam
A = {x | x é um múltiplo de 4}
B = {x | x é um múltiplo de 8}
Mostre que B ⊂ A.
Prof. Dr. Leandro Balby Marinho
14 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exemplo 6
Sejam
A = {x | x é um múltiplo de 4}
B = {x | x é um múltiplo de 8}
Mostre que B ⊂ A.
Solução: Como x ∈ B é um múltiplo de 8 então x = 8m para algum
inteiro m. Isso pode ser escrito como 2 · 4 · m ou x = 4k, onde
k = 2m. Portanto, x também é um múltiplo de 4 e então x ∈ A.
Finalmente, como existem números que são múltiplos de 4 mas não
de 8 (e.g. 12) então B ⊂ A.
Prof. Dr. Leandro Balby Marinho
14 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Cardinalidade
Definição 4
Seja S um conjunto. Se há exatamente n elementos distintos em
S, no qual n é um inteiro não negativo, então S é um conjunto
finito e n é a cardinalidade de S denotada por |S|.
Exemplo 7: Seja A o conjunto dos inteiros positivos pares menores
que 10. Então |A| = 4.
Exemplo 8: Seja V o conjunto das vogais do alfabeto da lı́ngua
Portuguesa. Então |V | = 5.
Prof. Dr. Leandro Balby Marinho
15 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Conjunto das Partes
Definição 5
Seja S um conjunto. O conjunto das partes é o conjunto de todos
os subconjuntos de S e é denotado por P(S).
Prof. Dr. Leandro Balby Marinho
16 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exemplos
Exemplo 9: Determine o conjunto das partes do conjunto {1, 2, 3}.
Prof. Dr. Leandro Balby Marinho
17 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exemplos
Exemplo 9: Determine o conjunto das partes do conjunto {1, 2, 3}.
Solução:
P({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Exemplo 10: Determine o conjunto das partes do conjunto {∅}.
Solução: P({∅}) = {∅, {∅}}
Prof. Dr. Leandro Balby Marinho
17 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Cardinalidade do Conjunto das Partes
Teorema 2
Se S é um um conjunto finito tal que |S| = n, o conjunto das
partes de S contém |P(S)| = 2n elementos. Portanto |S| < |P(S)|.
Prof. Dr. Leandro Balby Marinho
18 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Prova Teorema 2
Prova por inducão:
∀n ∈ N : |S| = n → |P(S)| = 2n
Caso Base: Quando n = 0, sabemos que
|S| = 0 ↔ S = ∅
Portanto,
|P(∅)| = |{∅}| = 1 = 20
Prof. Dr. Leandro Balby Marinho
19 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Prova Teorema 2 cont.
I
Hip. indutiva: |S| = k → |P(S)| = 2k
I
Mostrar: |S| = k + 1 → |P(S)| = 2k+1
I
Seja x ∈ S
I
Considere um conjunto S 0 = S \ {x}
I
Note que |S 0 | = k
I
Inclua x a todos os subconjuntos de S 0
I
Observe que
|P(S)| = |P(S 0 )| + |P(S 0 )| com x incluso
{z
}
| {z } |
2k
k
2k
k+1
=2·2 =2
Prof. Dr. Leandro Balby Marinho
20 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Enuplas Ordenadas
Quando a ordem de elementos em uma coleção é importante, usamos
enuplas ordenadas.
Definição 5
Uma enupla ordenada (a1 , a2 , . . . , an ) é uma coleção ordenada que
tem a1 como primeiro elemento, a2 como segundo elemento,. . . , e
an como n-ésimo elemento.
Quando n = 2, temos duplas ou pares ordenados. Os pares ordenados (a, b) e (c, d) são iguais se e somente se a = c e b = d.
Prof. Dr. Leandro Balby Marinho
21 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Produtos Cartesianos
Definição 6
Sejam A e B conjuntos. O produto cartesiano de A e B é definido
por
A × B = {(a, b) | a ∈ A ∧ b ∈ B}
Exemplo 11: Qual o produto cartesiano de A = {1, 2} e B =
{a, e, i}?
A × B = {(1, a), (1, e), (1, i), (2, a), (2, e), (2, i)}
Os produtos cartesianos de A × B e B × A não são iguais a
não ser que A = ∅ ou B = ∅ ou A = B.
Prof. Dr. Leandro Balby Marinho
22 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Produtos Cartesianos Generalizados
Definição 7
O produto cartesiano dos conjuntos A1 , A2 , . . . , An é definido por
A1 × A2 × . . . × An = {(a1 , a2 , . . . , an ) | ai ∈ Ai para i = 1, 2, . . . , n}
Exercı́cio 3: Defina o produto cartesiano dos conjuntos
A = {a, b, c}, B = {x, y } e C = {0, 1}
Prof. Dr. Leandro Balby Marinho
23 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Roteiro
1. Teoria dos Conjuntos
2. Operações em Conjuntos
3. Identidades de Conjuntos
Prof. Dr. Leandro Balby Marinho
24 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
União
Definição 8
Sejam A e B conjuntos. A união de A e B é definida por
A ∪ B = {x | x ∈ A ∨ x ∈ B}
Prof. Dr. Leandro Balby Marinho
24 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exemplos
Exemplo 12: A união dos conjuntos A = {1, 2, 3} e B = {2, 3, 4}
é A ∪ B = {1, 2, 3, 4}.
Exercı́cio 4: Sejam A = {a, b, c, d, e} e B = {a, b, c, d, e, f , g , h}
ache A ∪ B.
Prof. Dr. Leandro Balby Marinho
25 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Interseção
Definição 9
Sejam A e B conjuntos. A interseção de A e B é definida por
A ∩ B = {x | x ∈ A ∧ x ∈ B}
Dois conjuntos são disjuntos se sua interseção for vazia.
Prof. Dr. Leandro Balby Marinho
26 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exemplos
Exemplo 13: A interseção dos conjuntos A = {1, 2, 3} e
B = {2, 3, 4} é A ∩ B = {2, 3}.
Exercı́cio 5: Sejam
A = {x | x = 3n, n ∈ N} e B = {x | x = 4n, n ∈ N}
ache A ∩ B.
Exercı́cio 6: Sejam A e B dois conjuntos tais que (A ∩ B) ⊆ B e
B 6⊂ A. Desenhe o diagrama de Venn correspondente.
Prof. Dr. Leandro Balby Marinho
27 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Diferença (ou Subtração)
Definição 11
Sejam A e B conjuntos. A diferença entre B e A é definida por
B \ A = {x | x ∈ B ∧ x ∈
/ A}
Prof. Dr. Leandro Balby Marinho
28 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exemplos
Exemplo 14: A diferença dos conjuntos A = {1, 2, 3} e
B = {2, 3, 4} é A \ B = {1}.
Exercı́cio 7: Sejam A = {a, b, c, d, e} e B = {a, b, c, d, e, f , g , h}
ache B \ A.
Prof. Dr. Leandro Balby Marinho
29 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Complemento
Definição 12
Seja U o conjunto universo. O complemento de A é definida por
Ā = {x | x ∈
/ A}
Prof. Dr. Leandro Balby Marinho
30 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exercı́cio
Exercı́cio 8: Seja o conjunto universo U o conjunto de todas as
pessoas e A = {x | x é um aluno dessa turma}. Determine Ā.
Prof. Dr. Leandro Balby Marinho
31 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Roteiro
1. Teoria dos Conjuntos
2. Operações em Conjuntos
3. Identidades de Conjuntos
Prof. Dr. Leandro Balby Marinho
32 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Algumas Identidades Importantes
Identidade
A∪∅=A
A∩U =A
A∪U =U
A∩∅=∅
A∪A=A
A∩A=A
A∪B =B ∪A
A∩B =B ∩A
(Ā) = A
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
A ∪ (B ∪ C ) = (A ∪ B) ∪ C
A ∩ (B ∩ C ) = (A ∩ B) ∩ C
A ∪ (A ∩ B) = A
A ∩ (A ∪ B) = A
A ∪ B = Ā ∩ B̄
A ∩ B = Ā ∪ B̄
A ∪ Ā = U
A ∩ Ā = ∅
Prof. Dr. Leandro Balby Marinho
Nome
Leis de Identidade
Leis de Dominação
Leis de Idempotência
Leis Comutativas
Lei da Complementação
Leis Distributivas
Leis Associativas
Leis de Absorção
Leis de De Morgan
Leis de Complemento
32 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Provando Identidades
I
Para provar que A = B precisamos provar que A ⊆ B e
B ⊆ A.
I
A ideia é tomar um elemento arbitrário de A e mostrar que
esse elemento também pertence a B.
Prof. Dr. Leandro Balby Marinho
33 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exemplo
Exemplo 15: Prove a segunda lei de De Morgan A ∩ B = Ā ∪ B̄.
x ∈ A ∩ B → {x | x ∈
/ A ∩ B}
pela definição de complemento
→ {x | ¬(x ∈ (A ∩ B))}
pela definição do sı́mbolo ∈
/
→ {x | ¬(x ∈ A ∧ x ∈ B)}
→ {x | ¬(x ∈ A) ∨ ¬(x ∈ B)}
pela definição de interseção
primeira lei de De Morgan da lógica
→ {x | x ∈
/ A∨x ∈
/ B}
pela definição do sı́mbolo ∈
/
→ {x | x ∈ Ā ∨ x ∈ B̄}
pela definição de complemento
→ {x | x ∈ Ā ∪ B̄}
pela definição de união
→ x ∈ Ā ∪ B̄
Prof. Dr. Leandro Balby Marinho
34 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Derivando Identidades
Podemos usar identidades já demonstradas para derivar outras identidades.
Exemplo 16: Sejam A, B e C conjuntos. Mostre que
A ∪ (B ∩ C ) = (C̄ ∪ B̄) ∩ Ā
A ∪ (B ∩ C ) = Ā ∩ (B ∩ C )
primeira lei de De Morgan
= Ā ∩ (B̄ ∪ C̄ )
segunda lei de De Morgan
= (B̄ ∪ C̄ ) ∩ Ā
comutatividade de interseções
= (C̄ ∪ B̄) ∩ Ā
comutatividade de uniões
Prof. Dr. Leandro Balby Marinho
35 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exercı́cios
Exercı́cio 9: Prove a primeira lei de De Morgan A ∪ B = Ā ∩ B̄.
Prof. Dr. Leandro Balby Marinho
36 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Uniões e Interseções Generalizadas
Definição 13
A união de uma coleção de conjuntos A1 , A2 , . . . , An é definida por
A1 ∪ A2 ∪ . . . ∪ An =
n
[
Ai
i=1
Definição 14
A interseção de uma coleção de conjuntos A1 , A2 , . . . , An é definida por
A1 ∩ A2 ∩ . . . ∩ An =
n
\
Ai
i=1
Prof. Dr. Leandro Balby Marinho
37 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Exemplos
Exemplo 17: Seja Ai = {i, i + 1, i + 2}. Então
n
[
Ai =
i=1
Prof. Dr. Leandro Balby Marinho
n
[
{i, i + 1, i + 2, . . .} = {1, 2, 3, . . .}
i=1
38 / 39
UFCG CEEI
Teoria dos Conjuntos
Operações em Conjuntos
Identidades de Conjuntos
Referências
Keneth H. Rosen. Discrete Mathematics and Its Applications.
Sexta Edição. McGRAW-HILL International Edition, 2007.
Judith L. Gersting. Fundamentos Matemáticos para a Ciência
da Computação. Quinta Edição. LTC, 2004.
Prof. Dr. Leandro Balby Marinho
39 / 39
UFCG CEEI