A Matemática Discreta Questões

Questão 1: Resolva os itens indicando todos os cálculos que fizer.

(a) Enconte a fatoração do número 111.

(b) Utilizando a fatoração obtida no Item (a), descubra quantos divisores positivos o número 111 tem. Em seguida, liste todos os divisores positivos de 111.

OBS.: Não será válido calcular os divisores para contá-los depois. É necessário

encontrar o total de divisores de forma independente da listagem dos divisores.

(c) Verifique se o número 713 é primo.

(d) Fatores os números 525 e 882. Utilize estas fatorações para calcular os valores

de mdc(525, 882) e mmc(525, 882).

(e) Encontre todos os divisores positivos comuns de 525 e 882.

(f) Encontre dois números x e y tais que mdc(x, y) = 14 e mmc(x, y) = 588.

Os números fornecidos devem ser diferentes de 14 e 588. Explique como os

encontrou.

Questão 2: Prove: “Para a, b inteiros positivos, se a | b, então mdc(a, b) = a e mmc(a, b) = b.”

Questão 3: Usando Prova por Indução, prove que:

“Para todo n inteiro positivo, 3 | n

3 + 2n”.

Questão 4: Usando Prova por Indução, prove que:

“Para todo n inteiro positivo, se n é ímpar, então n

2

é ímpar”.

Questão 5: Considere a definição recursiva abaixo para a função mist:

Definição 1 Seja Σ um alfabeto e Σ∗ o conjunto das strings definidas sobre Σ,

Caso BASE: mist(λ) = λ

Caso RECURSIVO: Para todo x ∈ Σ∗

e para todo a ∈ Σ, mist(x.a) = a.mist(x)

OBS.: Nesta definição, a notação “s.t” indica a concatenação (junção) das strings

s e t. Nos nossos exemplos anteriores, quando tínhamos uma string x e um caractere a, com frequência escrevíamos “xa” para nos referirmos à string obtida pela

adição de uma cópia do caractere “a” ao fim da string “x”. Com esta notação, nós

escreveríamos “x.a” para obter este resultado. Estamos utilizando este ponto por

uma questão de conveniência, pois escrever “amist(x)” não funcionaria bem.

Assumindo que o alfabeto Σ nos permitiria escrever a string “discreta”, utilize a

definição fornecida para calcular o resultado de mist(discreta).

Ao final, explique: o que a função mist faz?

Questão 6: Seja R ⊆ Z × Z tal que R = { (x, y) | x − y é divisível por 3 }:

(a) prove que R é reflexiva.