Matemática Discreta para Computação: Prova 1 – 06/09/2017

Aluno(a):______________________________________________________

1. Considere as premissas: “Se o universo é finito, então a vida é curta.”, “Se a vida vale a pena, então a vida é complexa.”, “Se a vida é curta ou complexa, então a vida tem sentido.”, “A vida não tem sentido.” Verifique, usando regras de inferência e equivalências lógicas, quais das conclusões podem ser inferidas:

a) Se o universo é finito e a vida vale a pena, então a vida tem sentido.

b) A vida não é curta.

c) A vida não é complexa ou o universo não é finito.

d) A vida vale a pena se e somente se a vida tem sentido.

2. Escreva cada uma das afirmações a seguir em notação simbólica usando as letras de proposição D, C, A. a. Se o cavalo estiver descansado, o cavaleiro vencerá.

b. O cavaleiro só vencerá se o cavalo estiver descansado e a armadura for forte.

c. Um cavalo descansado é uma condição necessária para o cavaleiro vencer.

d. O cavaleiro vencerá se e somente se a armadura for forte.

e. Uma condição suficiente para o cavaleiro vencer é que a armadura seja forte ou o cavalo esteja descansado.

3. Escreva cada afirmação a seguir usando quantificadores. A seguir verifique se é possível chegar a alguma conclusão a partir das hipóteses dadas. Escreva a conclusão encontrada e indique as regras usadas.

a. Todas as flores são plantas. Violetas são flores.

b. Todas as flores são vermelhas ou roxas. Lírios são flores. Lírios não são roxos.

4. Demonstre que “A soma de um inteiro com seu quadrado é par”. Diga qual prova usou.

5. Conjuntos a. Determine o conjunto A se o conjunto potência de A esta dado por {Ø, {a}, {Ø, {a}}}

b. Quais das proposições a seguir são verdadeiras para todos os conjuntos A, B e C? Justifique

Se A ⊆ B e B ⊆ A, então A = B.

{Ø} = Ø

{Ø} = {0}

Ø ∈ {Ø}

Ø ⊆ A

Matemática Discreta para Computação: Prova 2 - 18/10/2017

Aluno(a):_______________________________________________________________

1. (1,5p) Quais propriedades deve cumprir uma função para ser bem definida? Determine se as

funções a seguir são bem definidas, justifique:

a. 𝑓: ℤ+ × ℤ+ → ℤ, 𝑓(𝑥, 𝑦) =𝑥+𝑦

𝑥2 b. 𝑔: ℤ+ → ℝ, 𝑔(𝑥) =𝑥3−1

√𝑥2

2. (1,5p) Quais propriedades deve cumprir uma função para possuir inversa? Encontre as inversas

das funções ou justifique porque não tem inversa:

a. 𝑓: ℝ → ℝ, 𝑓(𝑥) = 𝑥 − |𝑥| b. 𝑔: ℝ𝑥ℝ → ℝ𝑥ℝ, 𝑔(𝑥, 𝑦) = (𝑦 + 1, 𝑥 + 1)

3. (2p) Prove usando indução matemática que 2𝑛 + 3 ≤ 2𝑛 para qualquer inteiro positivo 𝑛 ≥ 4

4. (0,25p) Quantas “palavras” de oito letras do alfabeto da língua portuguesa são possíveis, se devem iniciar com as letras BO (nesta ordem) e terminar com a letra X? (as outras letras podem ser repetidas)

5. (0,75p) Mostre que se há 30 estudantes em uma sala, então pelo menos dois têm sobrenomes que começam com a mesma letra.

6. (2p) Quantas soluções possíveis há para a equação: 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 20 se 𝑥1 ≤ 3?

7. (2p) Mostre que se n e k são inteiros positivos com nk 1 , então 12

k

kn

k

n

Matemática Discreta para Computação: Prova 3 – 04/12/2017

Aluno(a):______________________________________________________

1. (1p) Seja 𝑅 a relação que contem o par (𝑎, 𝑏) se 𝑎 e 𝑏 forem cidades, tal que

existe um Vôo direto sem escalas de 𝑎 para 𝑏. Quando é que um para (𝑎, 𝑏)

está na relação

a. 𝑅2? b. 𝑅3? c. 𝑅∗?

2. (1p) Quais propriedades deve ter uma relação para ser uma relação de

equivalência? Determine se 𝑅 no conjunto de todas as pessoas é uma relação

de equivalência 𝑅 = {(𝑎, 𝑏)| 𝑎 𝑒 𝑏 𝑓𝑎𝑙𝑎𝑚 𝑢𝑚𝑎 𝑚𝑒𝑠𝑚𝑎 𝑙í𝑛𝑔𝑢𝑎}

3. (1p) Defina uma relação de equivalência no conjunto “Estados do Brasil” e

determine as classes de equivalência para essa relação.

4. (1p) Defina relação de ordem parcial e verifique se a relação representada pela matriz zero-um (Figura 1) é de ordem parcial. Justifique.

[

1 1 1 01 1 1 00 0 1 11 1 0 1

]

Figura 1

Figura 2

5. (1p) Defina reticulado e determine se o

POSET com o Diagrama de Hasse mostrado na Figura 2 é um reticulado.

6. (0,5p) Desenhe os seguintes grafos: simples, multigrafo, pseudogrado, dirigido,

multigrafo dirigido.

7. (0,5p) É possível existir um grafo simples com 15 vértices, cada um de grau 5?

Justifique.

8. (1,5p) Para quais valores de n estes grafos são bipartidos?

a. Kn b. Cn c. Wn

9. (1p) Defina circuito e trajeto Euleriano e mostre o circuito e/ou trajeto Euleriano

no grafo da Figura 3 caso exista.

10. (1p) Defina circuito Hamiltoniano e mostre o circuito Hamiltoniano no grafo da

Figura 4 caso exista.

11. (0,5p) Escreva o Teorema de Kuratowski sobre planaridade de grafos. É

possível desenhar o grafo planar do grafo da Figura 5? Se sim, indique as

regiões planares desse grafo.

Figura 3

Figura 4

Figura 5

Matemática Discreta para Computação: Prova substitutiva – 12/12/2017

Aluno(a):______________________________________________________

1. (0,5p) Seja 𝐴 o conjunto de estudantes que mora a um quilómetro de distancia da faculdade e 𝐵, o

conjunto dos estudantes que vão a pé para as aulas. Descreva quais são os estudantes em cada

conjunto abaixo:

a) 𝐴 − 𝐵

b) 𝐴 ∪ 𝐵

2. (1,5p) De um exemplo de uma função dos Naturais para os Naturais que é:

a) Injetora, mas não Sobrejetora

b) Nem Injetora nem Sobrejetora.

3. (0,8p) O somatório de uma sequencia pode ser representado pela notação mostrada na Equação 1. a) Explique o que significa cada termo do somatório.

∑ 𝑎𝑗

𝑛

𝑗=𝑚

Equação1

b) Utilize a Equação 1 e represente a soma da sequência: 1 +1/4 + 1/9 + 1/16 + 1/25 + .......

4. (1,5p) Verifique todas as propriedades de uma Relação de equivalência para 𝑅 definida sobre o

conjunto de todos os números reais e de termine se é uma Relação de equivalência

𝑅 = {(𝑥, 𝑦)| 𝑥 = ±𝑦}

5. (1p) Explane como se determinam os fechos: reflexivo e simétrico de uma relação usando a

representação em matriz. Coloque um exemplo para cada fecho.

6. (1p) Explane como se determina o fecho transitivo de uma relação. Coloque um exemplo.

7. (1p) Defina: (a) Relação de ordem parcial (b) Relação de ordem total.

8. (1,2p) Para quais valores de n estes grafos possuem circuitos euleriano?

a. Kn b. Cn c. Wn

9. (1p) Justifique a existência de Circuito ou Trajeto Euleriano na Figura 1 e redesenhe mostrando o

circuito ou trajeto.

10. (0,5p) Determine se o par de grafos mostrados na Figura 2 é isomorfo. Mostre as funções aresta-

aresta.

Figura 1

Figura 2