Resumêra

Questão 1 (Média): Qual é a forma equivalente de A → B?

1.50 pontos Média

A) ¬A ∨ B B) A ∨ B C) ¬A ∧ ¬B D) A ∧ B E) ¬A ∨ ¬B

Resposta correta: A) ¬A ∨ B

Explicação: a implicação A → B é logicamente equivalente a ¬A ∨ B. Sendo assim, essa é a forma correta.

Questão 2 (Difícil): Dada S(n) = 3 S(n-1) + 2 com S(1)=4, qual é a solução fechada?

2.50 pontos Difícil

A) S(n) = 5·3^{n-1} - 1 B) S(n) = 3^{n} + 1 C) S(n) = 2·3^{n-1} - 1 D) S(n) = 4·3^{n-1} - 2 E) S(n) = 3^{n} - 2

Resposta correta: A) S(n) = 5·3^{n-1} - 1

Explicação: solução típica para S(n) = a S(n-1) + b com S(1)=4 resulta em S(n) = C·3^{n} - 1; usando S(1) = 4 determina C = 5/3, resultando S(n) = (5/3)·3^{n} - 1 = 5·3^{n-1} - 1.

Questão 3 (Difícil): Aplicando o Teorema de Mestre, qual é o resultado de B(n) = 4 B(n/2) + n^2?

2.50 pontos Difícil

A) Θ(n^2) B) Θ(n^2 log n) C) Θ(n^3) D) Θ(n) E) Θ(log n)

Resposta correta: B) Θ(n^2 log n)

Explicação: para a recorrência S(n) = a S(n/b) + n^c com a = 4, b = 2 e c = 2, temos a = b^c, logo S(n) = Θ(n^c log n) = Θ(n^2 log n).

Questão 4 (Extremamente Difícil): Sobre contraposição, escolha a afirmação correta.

3.50 pontos Extrema

A) A contraposição usa a negação da conclusão para provar a afirmação original. B) A contraposição declara que ¬Q → ¬P é logicamente equivalente a P → Q. C) A contraposição não pode ser usada quando P é verdadeiro. D) Contraposição é útil apenas para demonstrações diretas, nunca para indiretas. E) Contraposição é equivalente a indução matemática.

Resposta correta: B) A contraposição declara que ¬Q → ¬P é logicamente equivalente a P → Q.

Explicação: pela equivalência lógica (P → Q) ≡ (¬Q → ¬P). Utiliza-se para demonstrar propriedades quando é mais fácil trabalhar com a negação da tese.

Fundamentos Matemáticos para Computação - Lógica

Questões sobre o conteúdo