Baixe o app para aproveitar ainda mais
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
Compartilhar