Matemática Discreta I
BCC101
Teoria de Conjuntos
Teoria de Conjuntos
A Teoria de Conjuntos é adequada para
descrever e explicar todas as
estruturas matemáticas.
A Teoria de Conjuntos constitui também
a base matemática para a definição de
Tipos de Dados em Computação
2
O que é um conjunto?
Um conjunto é uma coleção de objetos
Cada objeto da coleção é dito um
elemento do conjunto.
Exemplos:
𝐍 = {0,1,2,3,…}
𝐙 = {…,-3,-2,-1,0,1,2,3,…}
𝐐 = {n/m | n,m ∈ 𝐙, m≠0 }
𝐑
números naturais
números inteiros
números racionais
números reais
3
Mais exemplos de conjuntos
𝐁 = {T,F}
conjunto Booleano
C = {a,e,I,o,u}
conjunto das vogais
D = {(0,0),(1,5),(3,2)}
conjunto de pares de números
E = {{1,2},{10},{3,3,3}} conjunto de conjuntos
F = {3,{2,5},{5,8,2}}
-
elementos não precisam ser do mesmo tipo
3∈F
{2,5} ∈ F
2∉F
4
Cardinalidade
Se A é um conjunto finito, a cardinalidade
de A é o número de elementos de A
Notação: |A|
Exemplos:
- A = {a,b,c,d}
- B = {{1,2}, {1,2,3}}
|A| = 4
|B| = 2
5
Conjunto Vazio
{ } conjunto vazio: não possui elementos
–3{}
– x  { } — não importa o que seja x
–  = { } — a letra Grega phi denota o
conjunto vazio
Observação:  ≠ {}
-
|| = 0
|{}| = 1
6
Exercício
F = {,{},{{}}}
1.Qual é a cardinalidade de F?
2. ∈ F ?
3. ∈ {{}} ?
7
Notação para conjuntos
 { x | x  {2, 3, 5, 7, 11} , x  4}
– {5, 7, 11}
 { x + x | x  {2, 3, 5, 7, 11} , x  3 , x  11}
– {6, 10, 14}
 {f(x) | x  A, p(x)}
– Denota o conjunto cujos elementos têm a
forma f(x), onde x  A e é tal que p(x) é true
 Para evitar contradições:
– Deve ser especificado o universo de discurso
– Exemplos inválidos:
{X | X é um conjunto}
{X | X  X}
Nestes, o universo de discurso não é especificado
8
Exercícios
Listar os elementos dos seguintes conjuntos:
1.{n ∈ 𝐍 | n é primo}
2.{n2 | n ∈ 𝐙 }
3.{x ∈ 𝐑 | x2 – 2 = 0}
4.{x ∈ 𝐙 | x2 – 2 = 0}
5.{x ∈ 𝐙 | |x| < 4}
6.{2x ∈ 𝐙 | |x| < 4}
7.{x ∈ 𝐙 | |2x| < 4}
8.{X | X ∈ {{1,2},{3,4,5,6},{7}}, |X|<3 }
9
Subconjuntos e Igualdade
A é um subconjunto de B
– Definição: A  B  x. (x  A  x  B)
– Exemplos
• {2, 3, 5, 7}  {2, 3, 5, 7, 11}
•   A — independentemente do que seja A
Igualdade entre conjuntos
– Definição: A = B  (A  B) e (B  A)
A é um subconjunto próprio de B
– Definição: A  B  (A  B) e (A  B)
10
Exercícios
Quais afirmações são verdadeiras?
1. 1 ∈ {1,{1}}
11. 𝐍 ∈ {𝐍}
2. 1  {1,{1}}
12. 𝐍  {𝐍}
3. {1} ∈ {1,{1}}
13.  ∈ {𝐍}
4. {1}  {1,{1}}
14.   {𝐍}
5. {{1}} ∈ {1,{1}}
15.  ∈ {,𝐍}
6. {{1}}  {1,{1}}
16.   {,𝐍}
7. 𝐍 ∈ 𝐍
17. {𝐍}  {,𝐍}
8. 𝐍  𝐍
18. {𝐍}  {,{𝐍}}
9.  ∈ 𝐍
19. {𝐍} ∈ {,{𝐍}}
10.   𝐍
20.  ∈ 
11
Operações:
Conjunto Potência
Cojunto Potência de A: P (A)
– Definição: P (A) = {S | S  A}
– Exemplos
• P({2, 3, 5}) = {, {2}, {3}, {5}, {2,3}, {2,5}, {3,5},
{2,3,5}}
• P() = {}
– |P (A)| = 2|A|
(será
provado mais tarde, usando indução )
• Quantos elementos tem P(P())?
– P(P()) = { , {} }
• Quantos elementos tem P(P(P()))?
– P(P(P())) = { , {}, {{}}, {, {}} }
• Quantos elementos tem P(P(P(P())))?
– 24 = 16
• Quantos elementos tem P(P(P(P(P()))))?
– 216 — um bocado! em torno de 65.000
12
Exercícios
Liste todos elementos de cada conjunto:
1.P({0,1,3})
2.P({1})
3.P()
4.P({1,{1,2}})
5.P({𝐙,𝐍})
13
Operações: Produto Cartesiano
Produto Cartesiano de A e B: AxB
– Definição: A  B = {(a, b) | a  A e b  B}
– Exemplos
• {2, 3}  {3, 5, 7} = {(2,3), (2,5), (2,7), (3,3), (3,5), (3,7)}
• {0, 1, 2, …}  {1, 2, 3, …} = conjunto de todos os pares de
números naturais em que o segundo componente ≠ 0
– Notação: A2 = A x A
• A0 = {()}
A1 = A
A2 = AxA
A3 = AxAxA …
– |A x B| = |A| x |B|
Exercícios:
 A x B = B x A para todo A e B?
 Quantos elementos tem A  P(A)?
14
Operações: União e Interseção
União de A e B
– Definição: A  B = {x | x  A ∨ x  B}
– Exemplos
• {2, 3, 5}  {5, 7, 11} = {2, 3, 5, 7, 11}
•   A = A — independentemente do que seja A
• {, {}}  { {{}}, {, {}} } = {, {}, {{}}, {, {}} }
Interseção de A e B
– Definição: A  B = {x | x  A ∧ x  B}
– Exemplos
• {2, 3, 5, 7}  {2, 7, 11} = {2, 7}
•   A =  — independentemente do que seja A
Conjuntos disjuntos
– Definição: A e B são disjuntos  A  B =  15
Operações: União Disjunta
União disjunta de A e B
– Definição: A + B = {(0,x) | xA}∪{(1,x) | xB}
– Exemplos
• {2,3,5} + {3,5,7} = {(0,2), (0,3), (0,5), (1,3), (1,5),(1,7)}
•  + {2,3} = {(1,2),(1,3)}
• {2,3} +  = {(0,2),(0,3)}
16
Operações: Diferença e Complemento
Diferença A menos B
– Definição: A – B = {x | x  A ∧ x  B}
– Exemplos
• {2, 3, 5, 7} – {2, 7, 11} = {3, 5}
• A –  = A — independentemente do que seja A
•  – A =  — independentemente do que seja A
• Complemento de A
– Definição: A’= U–A onde U é o universo de discurso
– Exemplos - universo de discurso = N
• {2, 3, 4, 5}’ = {0, 1}  {6, 7, 8, …}
• {2x | x  {0, 1, 2, …}}’ = {2x+1 | x  {0, 1, 2, …}}
17
Exercícios
Sejam A = {a,b,c,d,e} B={d,e,f} C={1,2,3}
1.
2.
3.
4.
5.
AB
AB
A–B
B–A
(A-B)  (B-A)
6.
7.
8.
9.
AC
AC
A–C
(A  C)  (A – C)
10. (A  B) x B
11. (AxC)  (BxC)
Álgebra de Conjuntos
Identidade
Zero
Idempotência
A  A
A U  A
A U  U
A  
A A  A
Complemento
De Morgan
Duplo complemento
A A
A A  A
A A U
A B  A B
A A  
A B  A B
19
Commutatividade
Associatividade
A B  B  A
A  ( B  C )  ( A  B)  C
A  ( B  C )  ( A  B)  C
Absorção
Distributividade
A B  B  A
A  ( A  B)  A
A  ( A  B)  A
A  ( B  C )  ( A  B)  ( A  C )
A  ( B  C )  ( A  B)  ( A  C )
20
Prova direta – mais um exemplo
• Teorema: Sejam A,B e C conjuntos. Se
A∩C ⊆ B e a ∈ C, então a ∉ A-B.
– Hipóteses:
– Conclusão:
A∩C ⊆ B e a ∈ C
a ∉ A-B
a ∉ A\B = ¬(a ∈A-B)
= ¬(a ∈A ∧ a ∉ B)
= ¬a ∈A ∨ ¬ a ∉ B
= ¬a ∈A ∨ a ∈ B
= a ∈A ➝ a ∈ B
21
Prova direta – mais um exemplo
(continuação)
Trocamos a demonstração de a ∉ A-B por
uma demonstração de a ∈A ➝ a ∈ B, que
é mais simples.
• Agora é só usar uma das estratégias que
envolvem o conectivo ➝
• Como você concluiria a prova?
22
Paradoxo de Russel
Bertrand Russell (1872-1970)
Uma teoria ingênua de conjuntos pode levar a
paradoxos. Considere:
A = {X | X é um conjunto e X ∉ X}
- {1,2} ∈ A
- 𝐍∈A
- Seja X = {X}.
X∉A
Paradoxo: A∈A ?
23
Teoria Axiomática de Conjuntos
Para evitar os paradoxos que podem ocorrer em
uma teoria ingênua de conjuntos, foi proposta,
por Zermelo e Frankel, uma teoria axiomática,
que inclui como axiomas:
 Princípio da Boa Ordem
 Nenhum conjunto não vazio C pode ter a
propriedade de que C ∩ x ≠ , para todos os seus
elementos x que sejam conjuntos.
Isso exclui conjuntos tais como X = {X}.
24
Princípio da Boa Ordem
Todo subconjunto não vazio de números naturais
tem um menor elemento:
A ⊆ 𝐍 e A≠ → existe x0∈A tal que
x0 ≤ x, para todo x∈A
É uma propriedade fundamental de 𝐍
Não vale para números reais:
A = {1/n | n∈𝐍} não tem um menor elemento
25
Princípio da Boa Ordem- consequência
Algoritmo de Divisão: Dados dois números naturais
a e b, com b>0, existem números naturais q e r tais
que a = qb + r e 0 ≤ r < b
Prova: Dados a e b, com b>0, construa o conjunto
A = {a – xb | x∈𝐙, 0 ≤ a – xb}
(A é não vazio)
Por exemplo, se a=17 e b=3, A ={2,5,8,11,14,17,…}
Seja r o menor elemento de A.
Então r=a–qb, p/ algum q∈𝐙 e, portanto, a=qb+r.
Além disso, r<b: se r≥b, então um número não
negativo r-b=(a-qb)-b=a-(q+1)b, da forma a–xb
seria o menor elemento de A, ao invés de ser r.
26
Funções
Função — algumas definições e terminologia
Uma função f de tipo A  B é uma relação
binária com domínio A e contra domínio B, que
satisfaz a propriedade
aA.b1B.b2B. ((a, b1)f  (a, b2)f)  (b1=b2)
Em computação:
Tipo do argumento : A (ou dominio de f)
Tipo do resultado: B
(ou contra dominio de f)
A propriedade acima garante que a função
retorna um e exatamente um resultado, para
cada possível valor do argumento
27
Funções
Oficialmente, uma função é um conjunto de
pares ordenados
Este conjunto de pares oerdenados é o grafo
da função
Também conhecido como representação
extensional da função
Menos formalmente
Uma função é uma regra que associa um
resultado a cada argumento
Essa regra é conhecida como representação
intensional da função
28
Extensional versus Intensional
 Representação extensional
– Conjunto de pares ordenados
• f: A  B (f tem dominio A e contra-dominio B)
• f = {(x, f(x)) | x  A}  A  B
[representação extensional de f: A  B]
– Representação unívoca
• Existe uma única representação extensional de uma
função
– Igualdade funcional
• Duas funções são iguais se têm a mesma
representação extensional
29
Extensional versus Intensional
 Representação intensional
– Equações associaindo resultados a argumentos
– Não é única
• Uma função pode ter mais de uma representação
intensional
• Exemplos
f(x) = (x – 1)(x+1), g(x) = x2 – 1
tipo: Integer  Integer
qsort = … , msort = …
tipo: [] []
30
Composição de Funções
Composição: aplicação encadeada de funções
– Os tipos devem ser compatíveis
• se f tem tipo a -> b e g tem tipo b -> c
então g o f tem tipo a -> c
• (g o f) x = g(f x)
– Exemplos
inc1 x = x + 1
inc2 x = x + 2
inc2 = inc1 . inc1
sqr x = xx
poly x = xx + 1
poly = inc1 . sqr
31
Imagem e Imagem Inversa
Imagem
f :: A  B
XA
f(X) = {f(x) | x  X}
Imagem inversa
B
A
X
f(X)
B
A
f :: A  B
YB
f-1(Y) = {x  A | f(x)  Y}
f
-1
f (Y)
f
Y
32
Sobrejetora
f :: AB é sobrejetora sse f(A) = B
 f é sobrejetora se sua imagem é todo o
contra domíno
Algumas funções sobrejetoras
even :: Integer -> Bool
even = (== 0) . (`mod` 2)
clock :: {0, 1, 2, …}  {1, 2, …, 12}
clock x = 1 + (x `mod` 12)
Algumas funções não sobrejetoras
dbl :: Integer -> Integer
dbl x = x + x
sqr :: Integer -> Integer
sqr x = xx
clock :: {0, 1, 2, …}  {0, 1, 2, …}
clock = 1 + (x `mod` 12)
33
Injetora
 f :: AB injetora sse bB. |f-1({b})|  1
 sse a imagem inversa de um conjunto unitário
é um conjunto unitário ou vazio
 Função que não ‘tromba’ no contra domínio
 Algumas funções injetoras
integerize :: Bool -> Integer
integerize False = 0
integerize True = 1
sqr :: {0, 1, 2, …}  {0, 1, 2, …}
sqr x = xx
inc1 :: Integer -> Integer
inc1 x = x + 1
 Não injetora
even :: Integer -> Bool
even = (== 0) . (`mod` 2)
34
Bijetora
f: A→B é bijetora sse
(f é injetora)  (f é sobrejetora)
– Correspondência um a um entre A e B
Algumas funções bijetoras
not :: Bool -> Bool
inc1 :: Integer -> Integer
not False = True
inc1 x = x + 1
not True = False
counterClock :: {1, 2, …, 12}  {1, 2, …, 12}
counterClock x = 13 – x
Não bijetoras
dbl :: Integer -> Integer
injetora mas não sobrejetora
dbl x = x + x
clock :: {0, 1, 2, …}  {1, 2, …, 12
sobrejetora mas não injetora
clock x = 1 + (x `mod` 12)
35
Bijetora
f: A→B é bijetora sse
(f é injetora)  (f é sobrejetora)
– Correspondência um a um entre A e B
Algumas funções bijetoras
not :: Bool -> Bool
inc1 :: Integer -> Integer
not False = True
inc1 x = x + 1
not True = False
counterClock :: {1, 2, …, 12}  {1, 2, …, 12}
counterClock x = 13 – x
Não bijetoras
dbl :: Integer -> Integer
dbl x = x + x
injetora mas não sobrejetora
clock :: {0, 1, 2, …}  {1, 2, …, 12
clock x = 1 + (x `mod` 12)
sobrejetora mas não injetora
36