discreta - Aula 06 - Conjuntos

RESOLUÇÃO DISCRETA DE PROBLEMAS

CONJUNTOS

CONJUNTOS

• A teoria de conjuntos é fundamental, pois muitos dos conceitos desenvolvidos na computação são baseadas em conjuntos ou na construção de conjuntos.
• Teoria dos conjuntos é a base para o Modelo Relacional, implementado amplamente pelas engines de banco de dados relacionais.
• Teoria dos Grafos: Conjuntos são usados para representar vértices e arestas na teoria dos grafos. Algoritmos que percorrem grafos, como busca em largura (BFS, do inglês breadth-first search) e busca em profundidade (DFS, do inglês depth-first search), frequentemente utilizam conjuntos para acompanhar os nós visitados ou para implementar estruturas de dados como conjuntos de adjacência.

DEFINIÇÕES

• Um conjunto é uma coleção, sem repetição e sem qualquer ordenação, dos objetos denominados elementos.
• O termo elementos é usado de forma ampla e pode designar um objeto concreto ou abstrato.

DEFINIÇÕES

• Exemplos:
• As vogais a, e, i, o, u;
• O par de sapatos preferidos;
• Os dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;
• Os número pares 0, 2, 4, 6, ...;
• O vazio: {∅};
• O personagem Snoopy, a letra a, a baía da Guanabara e o Pelé.

Denotação

• Há duas formas de denotar um conjunto:
• Denotação por extensão:
• É dada pela listagem dos elementos do cojunto.
• Vogais = {a, e, i, o, u}

• Denotação por compreensão:
• A definição é feita a partir de uma propriedade do conjunto:
• Pares = {n | n é número par}
• Assim:
• {x | p(x)}
• Um determinado elemento x é elemento deste conjunto se a propriedade p é verdadeira para x.

pertinência

• Se um determinado elemento a pertence a um conjunto A, então:
• a ∈ A
• Caso contrário:
• a ∉ A

• Exemplo:
• Relativamente ao conjunto Vogais = {a, e, i, o, u}, tem-se que:
• a ∈ Vogais
• h ∉ Vogais

Finito e infinito

• Conjunto Finito:
• Pode ser denotado por extensão, ou seja, estando exaustivamente todos os seus elementos:
• A = {0, 1, 2, 3, 4, ..., 500}
• B = {x | x é brasileiro}

• Conjunto Infinito:
• Não pode ser listar todos os seus valores:
• Pares = {0, 2, 4, 6, 8, 10, ...}

• As barras de valor absoluto em torno de um conjunto representa a cardinalidade ou tamanho do conjunto:
• A = {0, 1, 2, 3, 4, ..., 500} |A| = 501

continência

• Se todos os elementos de um conjunto A também são elementos de um conjunto B, então se afirma que A esta contido em B.
• A ⊆ B
• Neste caso, afirma-se que A é um subconjunto de B.

• Adicionalmente, se A está contido em B mas exite um b ∈ B tal que b ∉ A, então afirma que A está contido propriamente em B.
• A ⊂ B

• Exemplo:
• {a, b} ⊆ {a, b}
• {a, b} ⊂ {a, b, c}

igualdade

• Os conjuntos A e B são ditos conjuntos iguais se, e somente se, possuem exatamente os mesmos elementos.
• A = B se e somente se A ⊆ B e B ⊆ A

• Exemplo:
• {1, 2, 3} = {x | x > 0 e x < 4}
• {1, 2, 3} = {3, 3, 3, 2, 2, 1}

Álgebra

• Álgebra de conjuntos corresponde às operações definidas sobre todos os conjuntos.
• As operações sobre conjuntos são classificadas em reversíveis e não-reversíveis.
• Não-reversíveis:
• União
• Interseção
• Reversíveis:
• Complemento
• Conjunto das partes
• Produto Cartesiano

União

• A operação de união é uma operação binária.
• Quando aplicada a dois conjuntos A e B resulta em um novo conjunto constituído pelos elementos que pertencem a pelo menos um dos dois conjuntos.
• Os elementos pertencem ao conjunto A ou ao conjunto B.

A ∪ B = {x | x ∈ A ∨ x ∈ B}

propriedades da união

• Elemento neutro:
• A ∪ ∅ = A
• Idempotência:
• A ∪ A = A
• Comutativa:
• A ∪ B = B ∪ A
• Associativa:
• A ∪ (B∪C) = (A∪B)∪C

Interseção

• A operação de união é uma operação binária.
• Quando aplicada a dois conjuntos A e B resulta em um novo conjunto constituído pelos elementos que pertencem simultaneamente aos dois conjuntos.
• Os elementos pertencem ao conjunto A e ao conjunto B.

A ∩ B = {x | x ∈ A ∧ x ∈ B}

propriedades da interseção

• Elemento neutro:
• A ∩ U = A
• Idempotência:
• A ∩ A = A
• Comutativa:
• A ∩ B = B ∩ A
• Associativa:
• A ∩ (B∩C) = (A∩B)∩C

União e interseção

• Distribuição da interseção sobre a união:
• A∩(B∪C) = (A∩B)∪(A∩C)
• Distribuição da união sobre a interseção:
• A∪(B∩C) = (A∪B)∩(A∪C)
• Absorção:
• A∩(A∪B) = A
• A∪(A∩B) = A

complemento

• Entede-se por operações reversíveis uma operação a partir de cujo resultado pode-se recuperar os operandos originais.

• Complemento:
• A operação de complemento é uma operação unária.
• A operação de complemento, aplicada a um conjunto A, resulta no conjunto complemento em relação ao conjunto univero U.

~A = {x∈U| x∉A}

diferença

• sejam A e B conjuntos, a diferença dos conjuntos é dada por:

A-B = A∩(~B) A-B = {x | x∈A e x∉B}

conjunto das partes

• Conjunto das partes é uma operação unária.
• Quando aplicada a um conjunto A, resulta no conjunto de todos os subconjuntos de A.

• Exemplo:
• C = {a, b, c}
• P = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b, c}, {a, b, c}}

P(A) ou 2A P(A) = {x | x⊆A}

produto cartesiano

• O produto cartesiano é uma operação binária.
• Quando aplicada aos dois conjuntos A e B, resulta em um conjunto constituído de sequencias de duas componentes, sendo que o primeiro componente de cada sequencia é um elemento de A e o segundo componente um elemento de B.

• Exemplo:
• A = {a, b}
• B = {0, 1, 2}
• AxB = {<a,0>, <a,1>, <a,2>,<b,0>, <b,1>, <b,2>}

Bibliografia

GERSTING, Judith L. Fundamentos matemáticos para a ciência da computação : um tratamento moderno de matemática discreta. 5. ed. Rio de Janeiro: LTC,2004. 597p.

OBRIGADO!