01 revisao de conjuntos

Prévia do material em texto

Revisão de Teoria dos Conjuntos
INF05008 - Fundamentos de algoritmos
Instituto de Informática
Universidade Federal do Rio Grande do Sul
Porto Alegre, Brasil
http://www.inf.ufrgs.br
2011/2
Conjuntos
▸ Coleções de elementos
▸ Sem ordem▸ Sem repetição▸ Descritos por extensão ou compreensão
▸ Extensão: Enumeração dos elementos entre chaves
{4, 5} {a,b,c} {}
▸ Compreensão: Propriedade que caracteriza os elementos
Ex.: Conjunto dos números inteiros maiores que 42
{x ∣ x ∈ Z ∧ x > 42}
INF05008 Revisão de Teoria dos Conjuntos 2/11
Conjuntos
▸ Conjunto vazio: ∅ ou {}{∅} ≠ ∅
▸ Cardinalidade: Número de elementos de um conjunto
∣∅∣ = 0
∣{∅}∣ = 1
∣{a,b,c}∣ = 3
∣N∣ = ℵ0 (infinito)
INF05008 Revisão de Teoria dos Conjuntos 3/11
Operações sobre Conjuntos
▸ x ∈ A (pertinência): Relaciona um elemento x a um conjunto A,
sendo válida se x pertencer a A.
4 ∈ N {4} /∈ N
▸ A ⊆ B (continência): Relaciona um conjunto A a um conjunto B,
sendo válida se todo elemento de A for também elemento de B.
4 /⊆ N {4} ⊆ N
N ⊆ Z ∅ ⊆ {1, 2, 3, 4}
INF05008 Revisão de Teoria dos Conjuntos 4/11
Operações sobre conjuntos (cont.)
▸ A ∪B (união): Conjunto contendo todos os elementos que ocorrem
em A ou em B.
{1, 2, 3} ∪ {5} = {1, 2, 3, 5} {a,b} ∪ {a} = {a,b}
▸ A ∩B (intersecção): Conjunto contendo todos os elementos que
ocorrem em A e em B.
{1, 2, 3} ∩ {5} = ∅ {a,b} ∩ {a} = {a}
INF05008 Revisão de Teoria dos Conjuntos 5/11
Operações sobre conjuntos (cont.)
▸ A ×B (conjunto dos pares): Conjunto de todos os pares
ordenados (a,b), onde a ∈ A e b ∈ B.
A = {a,b} B = {1, 2}
A ×B = {a,b} × {1, 2} = { (a, 1), (a, 2), (b, 1), (b, 2) }
▸ P(A) ou 2A (conjunto potência): Conjunto de todos os
subconjuntos de A.
P({a,b}) = { {}, {a}, {b}, {a,b} }
(a cardinalidade de P(A) é 2∣A∣)
▸ Escreva o conjunto potência P(A ×B), onde A e B são conforme
acima.
INF05008 Revisão de Teoria dos Conjuntos 6/11
Relações
▸ Uma relação binária R ∶ A→ B é uma associação entre
elementos de um conjunto A com elementos de um conjunto B.
A = {a,b} B = {1, 2}
R = { (a, 1), (a, 2), (b, 2) }
▸ Também se usa a notação R ⊆ A ×B para denotar relações.
▸ Uma relação é dita funcional (ou função) se, para todo a ∈ A não
há dois elementos distintos b,b′ ∈ B relacionados a a.
INF05008 Revisão de Teoria dos Conjuntos 7/11
Funções
▸ Uma função f ∶ A→ B é um mapeamento de elementos de A para
elementos de B
▸ A é o domínio (ou origem) de f .▸ B é o contradomínio (ou destino) de f .▸ O conjunto de todos os elementos de B aos quais algum a ∈ A está
associado é chamado de imagem de f .
▸ Ex.: A = {x1,x2}, B = {y1,y2,y3}, f ∶ A→ B = {(x1,y1), (x2,y3)}
Dom(f) = {x1,x2}
Codom(f) = {y1,y2,y3}
Img(f) = {y1,y3}
INF05008 Revisão de Teoria dos Conjuntos 8/11
Funções (cont.)
▸ f é dita total (ou totalmente definida) se todo elemento a ∈ A possui
um elemento associado em B
▸ Normalmente se usa f ∶ A⇀ B para representar que f é parcial, e
A→ B para denotar que f é totalmente definida.
INF05008 Revisão de Teoria dos Conjuntos 9/11
Funções (cont.)
▸ Nesta disciplina trabalharemos essencialmente com funções
parciais, mas usando a seta comum →.
▸ Funções totais são casos particulares de funções parciais, e serão
indicadas explicitamente.
▸ Definições de funções:
f ∶ N→ N Domínio e contradomínio
f(x) = x + 1 Definição da transformação
INF05008 Revisão de Teoria dos Conjuntos 10/11
Composição de funções
▸ Considere f ∶ A→ B e g ∶ B → C. A função g ○ f ∶ A→ C é
denominada a composição de f e g.
A
g○f
��
f
// B g
// C
g(f(x)) = g ○ f(x)
▸ Composição só é possível entre funções compatíveis. Duas
funções f e g são compatíveis sss (se somente se)
dom(g) = codom(f).
INF05008 Revisão de Teoria dos Conjuntos 11/11