Aula 2 conjuntose combinatória

Curso: Ciência da Computação Turma: 3º Semestre

Matemática Discreta

Aula 2

Conjuntos e Combinatória

Matemática Discreta 2

Notas de Aula✔ O conteúdo da aula de hoje está no capítulo 3 do livro

do Gersting.


Conjuntos

Conjunto é uma coleção não-ordenada de objetos.

Usamos letras maiúsculas para denotarem conjuntos e o símbolo є para denotar que um elemento pertence ao conjunto. Portanto, a є A significa que a é um elemento, ou membro, do conjunto A e b ∉A significa que o objeto b não é um elemento do conjunto A. Usamos chaves para indicar conjuntos.

EXEMPLO 1

Se A = {violeta, mostarda, vermelho}, então mostarda є A e púrpura ∉A.


Conjuntos

Como um conjunto é uma coleção não-ordenada de objetos, a ordem na qual os elementos são escritos não importa; portanto {violeta, mostarda, vermelho}, denota o mesmo conjunto que {mostarda, vermelho, violeta}.

Além disso, cada elemento de um conjunto é listado apenas uma vez; seria redundante listá-los mais do que uma única vez.


Conjuntos

Dois conjuntos são iguais se contêm os mesmos elementos. (Em uma definição, "se" significa, na verdade, "se, e somente se", portanto dois conjuntos são iguais se, e somente se, eles contêm os mesmos elementos.)


Conjuntos

Exemplos de conjuntos

A = {1,2,3,4,5,6,7,8,9,0}

B = {1,2,3,4,5,6,...}

C = { x | x é inteiro positivo par}


Relações entre Conjuntos

Para A = {2, 3, 5, 12} e B = {2, 3,4, 5, 9, 12}, todo elemento de A é também um elemento de B. Quando isto acontece, dizemos que A é um subconjunto de B.

Se A é um subconjunto de B, escrevemos, A ⊆ B. Se A ⊆ B mas A ≠ B (existe pelo menos um elemento de B que não é elemento de A), então A é dito um subconjunto próprio de B e denotado por A ⊂ B.


Operações em Conjuntos

Dado um conjunto arbitrário S, podemos definir algumas operações binárias e unárias no conjunto S, neste caso, é chamado o conjunto universo ou universo de discurso P(S).

Operação binária: Trabalha com dois operandos.

Operação unária: Trabalha somente com um operando.


Operações em Conjuntos

União

– A U B que gera C, é o conjunto de todos os elementos de A mais os elementos de B.

Intersecção

– A ∩ B que gera C, é o conjunto dos elementos quer pertecem a A e também a B.

Complemento de um conjunto

– Para um conjunto A є P(S) o seu complemento A' é { x | x є S e x ∉A}

Produto Cartesiano

– Sejam A e B subconjuntos de S. O produto cartesiano de A e B, denotado por A x B é definido por AxB = {(x,y) | x є A e y є B}.

– Portanto, o produto Cartesiano de dois conjuntos A e B é o conjunto de todos os pares ordenados cujas primeiras coordenadas pertençam a A e as segundas pertençam a B. O produto cruzado não é uma operação binária em S.

– Quando fazemos o produto cartesiano de um conjunto para ele mesmo denotamos A2


Propriedades de ConjuntosPropriedades de conjuntos

A U A = A ou A ∩ A = A → Idempotência.

A U B = B U A ou A ∩ B = B ∩ A → Comutatividade

(A U B) U C = A U (B U C) ou (A ∩ B) ∩ C = A ∩ (B ∩ C) → Associatividade

(A U B) ∩ C = (A ∩ C) U (B ∩ C) ou (A ∩ B) U C = (A U C) ∩ (B U C) → Distributividade

(A U B) ∩ A = A ou (A ∩ B) U A = A → Absorção

A – (B U C) = (A – B) ∩ (A – C) ou A – (B ∩ C) = (A – B) U (A – C) → Leis de Morgan


Linguagem de Programação e Conjuntos

Página 107 do livro texto.


Conjuntos Contáveis e Incontáveis

Em um conjunto finito 5, podemos sempre designar um elemento como o primeiro, s

1; outro elemento corno o

segundo, s2, e assim por diante. Se houver k elementos no

conjunto, esses elementos podem ser listados na ordem que selecionarmos:

s1, s

2, s

3, s

4,...,s

k

Esta lista representa todo o conjunto.

Se o conjunto for infinito, pode ser que ainda sejamos capazes de selecionar um primeiro elemento s

1, um segundo

elemento s2 e assim por diante, de forma que a lista

representa todos os elementos do conjunto.

s1, s

2, s

3, s

4,...

Esse último conjunto é incontável.


Contagem

A combinatória é o ramo da Matemática que trata da contagem. Tratar a contagem é importante, sempre que temos recursos finitos.

– Quanto espaço um banco de dados consome?

– Quantos usuários a configuração de um computador pode suportar?

– Quantos cálculos um determinado algoritmo envolve?)

Problemas de contagem normalmente se resumem em determinar quantos elementos existem em um conjunto finito. Esta questão que parece trivial pode ser difícil de ser respondida.


O Princípio da Multiplicação

Exemplo: Um analista pode fazer escolha de um entre dois banco de dados, e de uma entre três linguagens de programação. Quantos conjuntos diferentes dessa combinação o programador pode ter?

*Estudar o exemplo 28 da página 121 do livro.



Seja M o conjunto de banco de dados M = {B1, B2}

Seja A o conjunto das linguagens A = {L1, L2, L3}

Podemos construir um árvore de opções.



Se existem n1 possibilidades para um primeiro

evento e n2 possibilidades para um segundo

evento, então existem n1 . n

2 possibilidades para

a sequência dos dois eventos.


Exemplo 1

A última parte do número de seu telefone contém quatro dígitos. Quantos números de quatro dígitos existem?

5 minutos para pensar.


Exemplo 1A última parte do número de seu telefone contém quatro dígitos. Quantos

números de quatro dígitos existem?

Podemos imaginar um número de quatro dígitos como o total de possibilidades de uma sequência de etapas de escolha do primeiro dígito, depois do segundo, depois do terceiro e, finalmente, do quarto dígito. O primeiro dígito pode ser qualquer dos 10 dígitos entre 0 e 9, portanto há 10 possibilidades para a primeira etapa. Da mesma forma, há 10 possibilidades para as etapas de escolha dos segundo, terceiro e quarto dígitos. Usando o Princípio da Multiplicação, multiplicamos o número de possibilidades de cada etapa da sequência. Portanto, há 10.10.10.10 = 10.000 números diferentes.


Exemplo 2

Pensando no exemplo anterior quantos números de quatro dígitos sem repetições de dígitos existem?


Exemplo 2

Pensando no exemplo anterior quantos números de quatro dígitos sem repetições de dígitos existem?

Novamente, temos a sequência de etapas de seleção dos quatro dígitos, mas não são permitidas repetições. Existem 10 possibilidades para a escolha do primeiro dígito, mas apenas nove para a escolha do segundo, pois não podemos usar o que já foi usado para o primeiro dígito, e assim por diante. Existem, portanto, 10.9.8.7 = 5040 números diferentes sem repetições de dígitos.


Conjuntos e o Princípio da Adição

Para qualquer conjunto finito S, seja |S| o número de elementos em S. Se A e B são conjuntos finitos, então

|A X B| = |A|.|B|

A x B consiste em todos os pares ordenados com a primeira componente em A e a segunda componente em B. A escolha desses pares ordenados é equivalente a escolher, em sequência, a primeira componente dentre as possibilidades, e então escolher a segunda, para a qual existem possibilidades. O resultado segue, então, o Princípio da Multiplicação.


O Princípio da Adição

Suponha que desejamos escolher uma sobremesa dentre três tortas e quatro bolos. De quantas formas isto pode ser feito? Existem dois eventos, um com três resultados possíveis (escolher uma torta) e outro com quatro resultados possíveis (escolher um bolo). No entanto, não estamos compondo uma sequência de dois eventos, uma vez que desejamos apenas uma sobremesa, que precisa ser escolhida dentre as possibilidades de dois conjuntos disjuntos. O número de possibilidades é o número total de opções que temos, 3 + 4 = 7. Isto ilustra o Princípio da Adição.


O Princípio da Adição

Se A e B são eventos disjuntos com n1 e n

2

possibilidades, respectivamente, então o número total de possibilidades para o evento A ou B é n

1 + n

2.


Exemplo do Princípio da Adição

Um comprador deseja comprar um veículo de uma concessionária. A concessionária tem 23 carros e 14 caminhões em estoque. Quantas possíveis escolhas o comprador pode ter?

O comprador deseja escolher um carro ou caminhão. São eventos disjuntos; escolher um carro tem 23 possibilidades e escolher um caminhão tem 14. Pelo Princípio da Adição, a escolha de um veículo tem 23 + 14 = 37 possibilidades. Perceba que os requisitos para os eventos A e B são conjuntos disjuntos. Portanto, se um comprador desejar comprar um veículo de uma concessionária que tenha 23 carros, 14 caminhões e 17 veículos vermelhos, não podemos dizer que o comprador tem 23 + 14 + 17 possibilidades de escolha.


Exemplo 2 do Princípio da Adição

Quantos números de quatro dígitos começam com 4 ou 5?

Podemos considerar dois casos disjuntos — números que começam por 4 e números que começam por 5. Para a contagem dos números que começam por 4, existe uma forma de escolher o primeiro dígito, e 10 possibilidades para as etapas de escolha de cada um dos outros dígitos. Portanto, pelo Princípio da Multiplicação, existem 1 • 10 • 10 • 10 = 1000 formas de escolher um número de quatro dígitos começando com 4. O mesmo raciocínio mostra que existem 1000 formas de escolher um número de quatro dígitos começando por 5. Pelo Princípio da Adição, existem 1000 + 1000 = 2000 resultados possíveis ao todo.


Árvores de Decisão

Antônio está jogando "cara-ou-coroa". Cada lançamento resulta em cara (C) ou coroa (K). De quantas formas ele pode lançar a moeda cinco vezes sem obter duas caras consecutivas?

5 minutos para fazer a árvore de decisão.


Árvores de Decisão

Antônio está jogando "cara-ou-coroa". Cada lançamento resulta em cara (C) ou coroa (K). De quantas formas ele pode lançar a moeda cinco vezes sem obter duas caras consecutivas?

Se desenharmos a árvore de decisão. Cada lançamento de moeda tem duas possibilidades: o ramo à esquerda está marcado com um C para cara, e o ramo da direita com um K para coroa. Sempre que um C aparecer em um ramo, o próximo nível pode conter apenas um ramo para a direita (K). Existem 13 possibilidades.


Próxima Aula

Ler o capítulo 3 do livro do Gersting.


Exercícios

1. Exercício 1 da página 125 do livro texto.

2. Exercício 5 da página 125.

3. Exercício 12 da página 126.

4. Da página 126 fazer 16, 19, 23, 24, 41 até 50.

Education

Aula 2 conjuntose combinatória