Fundamentos de algoritmos para computação - ap1 - cederj

Curso de Tecnologia em Sistemas de Computação
Disciplina Fundamentos de Algoritmos para Computação
Gabarito da AP1 - Primeiro Semestre de 2010
Questões:
1. (2.0) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.
Se for verdadeira, prove, se for falsa justifique.
(a) ∅ = {∅}
Resposta: FALSO. Dois conjuntos são iguais se todo elemento de um conjunto é elemento do outro conjunto e vice-versa.
O conjunto ∅ não tem elementos enquanto {∅} tem um elemento,
∅ ∈ {∅}. Logo, ∅ = {∅}.
(b) (A ∩ B ) ∪ C = (A ∪ C ) ∩ B
Resposta: FALSO. Contra-exemplo: Sejam os conjuntos A =
{1, 2, 3}, B = {3, 4, 5} e C = {1, 3, 5}.
Temos que (A ∩ B ) = {3}, (A ∩ B ) ∪ C = {1, 3, 5}, (A ∪ C ) =
{1, 2, 3, 5} e (A ∪ C ) ∩ B = {3, 5}.
Podemos concluir que (A ∩ B ) ∪ C = (A ∪ C ) ∩ B .
(c) n((A ∪ B ) ∩ C ) ≤ n(A ∩ C ) + n(B ∩ C )
Resposta: VERDADEIRO. Pela propriedade distributiva, temos que (A ∪ B ) ∩ C = (A ∩ C ) ∪ (B ∩ C ), e isto implica em dizer que n((A ∪ B ) ∩ C ) = n((A ∩ C ) ∪ (B ∩ C )).
Portanto,

n((A ∪ B ) ∩ C )
= n((A ∩ C ) ∪ (B ∩ C ))
= n(A ∩ C ) + n(B ∩ C )−n((A ∩ C ) ∩ (B ∩ C ))
= n(A ∩ C ) + n(B ∩ C ) −n(A ∩ B ∩ C )

=
=
=
=

´
E negativo

≤ n(A ∩ C ) + n(B ∩ C )
2. (2.0) Mostre por indução matemática que:
23n − 1 é divisível por 7 para todo natural n ≥ 1.
Resposta: Seja P (n) : 23n − 1 divisível por 7 , para todo n ∈ N.
Base da indução:
Para n = 1, temos que 23.1 − 1 = 7, que é divisível por 7, portanto P(1) é verdadeira.
Hipótese de indução: Suponhamos que a proposição se verifica para k , isto é, P(k) é verdadeira:
P (k ) : 23k − 1 é divisível por 7 ,ou seja, para algum q ∈ N temos que
23k − 1 = 7q .
Devemos provar que P(k + 1) é verdadeira, isto é:
P (k + 1) : 23(k+1) − 1 é divisível por 7
De fato, da hipótese indutiva indutiva temos que 23k = 1 + 7q .
Portanto, desenvolvendo 23(k+1) − 1 e usando a igualdade acima, resulta:

23(k+1) − 1 =
=
=
=
=

23k .23 − 1
(1 + 7q )23 − 1
8 + 7 × 8.q − 1
7 + 7 × 8.q
7